Логические функции и их преобразования.

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

Цель выполнения преобразований: привести исходное логическое выражение либо к КНФ, либо к ДНФ. 

Номер	Выражение	Название
1		Двойное отрицание
2	ab = ba	Переместительный закон
3	a+b = b+a	Переместительный закон
4	a(bc) = (ab)c	Сочетательный закон
5	a+(b+c) = (a+b)+c	Сочетательный закон
6	a&a&a&…&a = a
7	a+a+a+…+a = a
8	a&  = 0     (a =0)	Закон противоречия: невозможно, чтобы противоречащие высказывания были одновременно истинными.
9	a+  = 1	Закон исключённого третьего: либо высказывание, либо его отрицание должно быть истинным.
10	a&1 = a
11	a+1 = 1
12	a&0 = 0
13	a+0 = a
14	(a+b)(c+d) = ac+ad+bc+bd	Раскрытие скобок
15	a → b = +b	Импликация (логическое следование)
16	a ↔ b = (a → b) (b → a) = = ( +b)( +a) = +ab	Эквивалентность (равнозначность)
17		Отрицание от дизъюнкции (закон де Моргана)
18		Отрицание от конъюнкции (закон де Моргана)
19	a(b+c) = ab+ac	Закон дистрибутивности
20	a+bc = (a+b)(a+c)	Закон дистрибутивности
21	a+ b = a+b	Правило свёртки
22	+ab = +b	Правило свёртки
23	ab + c + bc = ab + c	Правило сокращения (расширения)
24	abc + a c = ac	Правило склеивания

Пример 1. Упростить выражения:

F₁(a,b)= = + +  = +

F₂(a,b,c)=  = = (b+ )  = b + = (b+1) =

F₃(a,b,c)= = (a+ )+b  = a+ (1+b) = a+

F₄(a,b,c) = (a+b)c+abc( +ab)+ ab+ b  = ac+bc+abc +abcab+b (a+ ) =

= ac+bc+abc+b  = ac(1+b)+b(c+ ) = ac+b

Пример 2. Найти отрицание следующей импликации (логического следования): «Если урок будет интересным, то никто из учеников (Маша, Виктор, Светлана) не будет смотреть в окно».

Решение.

Обозначим высказывания:

i (interesting) – «Урок интересный»;

 M – «Маша смотрит в окно»; 

B – «Виктор смотрит в окно"»;

C – «Светлана смотрит в окно"».

Алгебраическое выражение для импликации:

=  = i&  = i(M+B+C)

Словесное выражение отрицания импликации: «Урок интересный и либо Маша, либо Виктор, либо Светлана смотрит в окно».

Пример 3. Определить участника преступления, исходя из двух импликаций (логических следований):

1) «Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал»;
2) «Если Иванов не участвовал, то Сидоров не участвовал».
Решение.

Обозначим высказывания:

И – «Иванов участвовал в преступлении»;

П - "Петров участвовал в преступлении";

С- "Сидоров участвовал в преступлении".
Запишем сложное, состоящее из двух импликаций выражение в виде формулы: 

F(И,П,С) = (( +П)→С)&( → ) = ( )&( + ) = (И +С)(И+ ) =

= И И+ И +ИС+С  = И + И +ИС = И (1+ )+ИС = И +ИС = И( +С)

Для определения участника преступления это выражение должно иметь значение «истина»: И( +С)=1. В полученной конъюнкции оба элемента должны иметь значение «истина». Определим, при каких значениях аргументов это выражение равно 1. И=1 (Иванов является участником преступления).

( +С)=1

Составим таблицу истинности для этой функции и добавим к ней значение И=1:

И	П		С	+С	F (И,П,С)
1	0	1	0	1	1
1	0	1	1	1	1
1	1	0	0	0	0
1	1	0	1	1	1

По условию задачи количество участников преступления – 1. В таблице истинности этому условию удовлетворяет строка №1. Т.е. преступление совершил Иванов.

                                                              Вопросы

1. Основные логические операции: конъюнкция, дизъюнкция (оба вида), отрицание, импликация, эквивалентность. Примеры логических выражений.

1. Таблица истинности. Примеры. A and not A; A or not A

2. Основные законы математической логики: перестановочный, сочетательный и распределительный.

3. Законы де Моргана (закон отрицания).

4. (Совершенная) дизъюнктивная нормальная форма. Примеры.

5. Какое количество логических функций существует для двух аргументов?

6. Какое количество логических функций существует для трёх аргументов?

Пример 4.Имеются 2 коробки и 2 предмета: карандаш и ластик. В каждой коробке находится только 1 предмет. На коробке №1 написано: «По крайней мере, в одной из этих коробок находится карандаш». На коробке №2 написано: «Ластик находится в другой коробке». Известно, что надписи на коробках либо обе истинны, либо обе ложны. Определить положение карандаша и ластика  (номер коробки, в которой находится карандаш).

Решение. Сформулируем 2 высказывания относительно положения карандаша и ластика:

a – «В коробке №1 находится карандаш»;

b – «В коробке №2 находится карандаш».

и их отрицания:

 - «В коробке №1 находится ластик»;

 - «В коробке №2 находится ластик».

Надпись на коробке №1 можно сформулировать иначе: «Карандаш находится либо в коробке №1, либо в коробке №2». Выражение для надписи на коробке №1: Х = a+b.

Надпись на коробке №2 можно сформулировать иным образом: «Ластик находится в коробке №1». Выражение для надписи на коробке №2: Y = .

Утверждение в условии задачи о надписях на коробках можно выразить алгебраически: (X&Y)+( & ) = 1. Преобразуем выражение:

(X&Y) + ( & ) = XY + = (a+b) +( )a =a + b+ a = b

Итак, b = 1. Это равенство возможно только при условии, что «Ластик находится в коробке №1, и карандаш находится в коробке №2.