Дискретная математика (стр. 1 из 10)

Министерство образования и науки

Российской Федерации

Российский химико-технологический университет

им. Д.И. Менделеева

Новомосковский институт

Издательский центр

T.П. Тюрина, В.И. Емельянов

Дискретная математика

(часть 3)

Учебное пособие

Новомосковск 2004

Содержание

Часть 3. Элементы алгебры логики............................................................ 3

3.1 Введение в алгебру логики....................................................................... 3

3.2 Основные функции алгебры логики......................................................... 5

3.3 Формулы алгебры логики........................................................................ 9

Контрольные вопросы.................................................................................. 12

3.4 Законы алгебры логики и следствия из них........................................... 12

Контрольные вопросы.................................................................................. 16

3.5 Логические функции многих переменных.............................................. 16

3.6 Построение формул алгебры логики по заданной таблице истинности 18

Контрольные вопросы и упражнения.......................................................... 26

3.7 Некоторые замкнутые классы (классы Поста). Понятие базиса............ 26

Контрольные вопросы и упражнения.......................................................... 34

3.8 Методы минимизации логических функций........................................... 34

Контрольные вопросы.................................................................................. 39

3.9 Неполностью определенные логические функции................................. 40

3.10 Формы представления булевых функций............................................ 41

3.10.1 Семантические деревья...................................................................... 42

3.10.2 Бинарные диаграммы решений (БДР)............................................... 45

3.11 Построение логических схем................................................................ 45

Контрольные вопросы.................................................................................. 45

3.12 Логические конечные автоматы............................................................ 46

3.12.1 Процессы............................................................................................ 50

3.12.2 Конечные автоматы............................................................................ 52

Контрольные вопросы.................................................................................. 55

БИБЛИОГРАФИЧЕСКИЙ СПИСОК........................................................... 60

Часть 3. Элементы алгебры логики

3.1 Введение в алгебру логики

Алгебру логики иначе еще называют алгеброй высказываний, логикой высказываний. Алгебра логики начала формироваться в 19 веке в трудах английского математика Дж. Буля.

Прежде всего, благодаря труду английского логика Джорджа Буля «Математический анализ логики», был достигнут подлинный прогресс науки, называемый математической логикой. Он перенёс на логику законы и правила математических действий, ввёл логические операции, предложил способ записи высказываний в символической форме.

В трудах Джорджа Буля и О. де Моргана математическая логика представлена как своеобразная алгебра – алгебра логики (алгебра высказываний).

Алгебра логики (алгебра высказываний) – раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.

Джордж Буль (1815–1864) родился в Линкольне (Англия). Сын сапожного мастера. Окончил только начальную школу и дальнейшие знания приобретал самоучкой. С 1849 г. Буль – профессор математики в Куинс – колледже в Корке (Ирландия), где преподавал до конца жизни. Буля почти в равной степени интересовали логика, математический анализ, теория вероятностей, этика Б. Спинозы, философские работы Аристотеля и Цицерона. Он считается несомненным создателем современной символической (математической) логики.

Огастес де Морган (1806–1871) родился в Индии в семье полковника английских войск. Получил образование в Кембриджском университете. Был профессором математики Лондонского университета. Математику и логику де Морган назвал азами точного знания и выражал сожаление, что математики не более заботятся о логике, чем логики о математике. Сам он стремился сблизить обе науки, и его главной заслугой явилось построение логики по образу и подобию математических наук. Независимо от Дж. Буля он открыл основные идеи алгебры логики.

«Логика Буля» основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истин», сколько и левая.

Высказывание – это имеющее смысл языковое выражение (повествовательное предложение), относительно которого в данной ситуации можно утверждать, что оно либо истинно, либо ложно, т. е. каждому высказыванию можно приписать истинное значение И (истина) или Л (ложь), но не то и другое одновременно.

Примеры:

1. НГТУ – крупнейший «вуз Новосибирска».

2. «Снег зелёный».

3. Р= «Чтобы подключиться к Интернету с домашнего компьютера, необходим модем и соответствующее ПО».

4. Крокодилы летают очень низко.

«А ты любишь информатику?» – это предложение не является высказыванием.

Уравнение 2+х=4 не является высказыванием. Однако, всякий раз, придавая переменной х определенное числовое значение, будем получать высказывание. Используя частицу «не», а также союзы «и», «или», связки «если …., то…», «тогда и только тогда, когда…» и т. п., можно из одних высказываний строить другие высказывания.

Изучением высказываний занимается Булева алгебра, в которой предполагается, что уже имеется некоторый запас высказываний, для каждого из которых известно истинно оно или ложно. Такие высказывания называют элементарными высказываниями. Из элементарных высказываний могут быть построены сложные с помощью операций алгебры логики.

Знаки логических операций называют логическими связками (или просто связками). Логические связки могут быть одноместные (унарные), двухместные (бинарные), трехместные (тернарные) и т. д.

В алгебре логики логические операции чаще всего описываются при помощи таблиц истинности, содержащих все наборы значений переменных и значения функции этих наборов. Алгебра логики не занимается обоснованием того, почему тому или иному элементарному высказыванию приписано значение истины или лжи. Этот вопрос решается за пределами алгебры логики.

Например: сумма углов в треугольнике – 180 градусов. Алгебра логики отвлекается и от смысловой содержательности высказывания. Она интересуется только одним свойством сложных высказываний: быть истинным (True– 1) или ложным (False– 0).

3.2 Основные функции алгебры логики

Основной задачей теории булевых функций является разработка систематического метода построения сложных функций из более простых. Этот метод основан на изучении свойств булевых функций.

Основными символами алгебры высказываний являются:

а) пропозиционные переменные Р1, Р2, Р3, …;

б) одноместная связка – (ù) и двуместные связки Ù (и), Ú (или), ®, Þ, Û;

в) скобки ().

Переменная, значениями которой являются высказывания, называется пропозиционной переменной.

Пусть А, В-некоторые элементарные высказывания.

Определим новое высказывание Ā (т. е. не А), будем называть его отрицанием (инверсия:

, Ā), представим таблицы значений функции отрицания:

А	Ā
10	01

Рассмотрим наборы истинных значений элементарных функций на наборах аргументов:

A	B
0011	0101

Таблица 1

№	Обозначение операции	Другие обозначения	Набор истинных значений	Название логической опции и связки	Как читается	Арифметическая модель
12	АÚВ	А+ВMax (А, В)	0111	Дизъюнкция, логическое сложение, «или»	А или В	A+B-A×B
23	АÙВ	А&ВА×ВMin (А, В)	0001	Конъюнкция, логическое умножение «и»	А и В	A×B
34	А®В	АÊВАÞВ	1101	Импликация, логическое следование	Если А, то ВА влечет В	1‑A+ A×B
45	А~В	АºВА«ВАÛВ	1001	Эквиваленция, эквивалентность	А тогда и только тогда, когда В; А эквивалентно В	1 – (A-B)2
56	АÅВ	А+ВАÚВАDВ	0110	Сумма по модулю 2, сумма Жегалкина	А плюс В; Либо А, либо В
67	А½В	1110	Штрих Шеффера, антиконъюнкция	Неверно, что А и В; А штрих Шеффера В
78	А¯В	А°ВАÚВ	1000	Стрелка Пирса, антидизъюнкция, функция Вебба, функция Даггера	Ни А, ни В; А стрелка Пирса В

Несмотря на то, что булевых функций от любого заданного числа m двоичных переменных конечное число, их слишком много, чтобы иметь запас преобразователей для любых встретившихся отображений. Рассмотрим сначала все возможные функции от одной двоичной переменной. Их четыре, две из них – константы (0 и 1), одна – тождественная функция и только одна – функция отрицания (функция НЕ) – является нетривиальной.

p	p
0	1
1	0

Очевидно, что число различных булевых функций от mпеременных равно 2 в степени

. При m = 2 это число 16, то есть всего функций от двух переменных 16, однако наиболее практически применимых из них меньше.

Суперпозиция двоичных функций может быть записана как формула, которую называют логической формулой.