6. Таблица истинности для функции двух переменных

F1 – const 0 – постоянная 0

F2 – логическое умножение – конъюнкция (А И В).

F3 – отрицание логического следствия - НЕ (ЕСЛИ А ТО В).

F4 – аргумент А.

F5 – отрицание обратного логического следствия - НЕ (ЕСЛИ В ТО А).

F6 – аргумент В.

F7 – отрицание логической равнозначности - НЕ (А тогда и только тогда, когда В).

F8 – логическое сложение - дизъюнкция (А ИЛИ В).

F9 – отрицание логического умножения – НЕ (А И В).

F10 – логическая равнозначность - эквиваленция (А тогда и только тогда, когда В).

F11 – логическое отрицание аргумента B – инверсия (НЕ В).

F12 – обратное логическое следствие - импликация (ЕСЛИ В ТО А)

F13 – логическое отрицание аргумента А – инверсия (НЕ А).

F14 – логическое следствие - импликация (ЕСЛИ А ТО В).

F15 – отрицание логического сложения - НЕ (А ИЛИ В).

F16 – const 1 – постоянная 1

7. КНФ и ДНФ

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Алгоритм построения ДНФ

1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ.[1] Для этого можно использовать: Закон двойного отрицания, Закон де Моргана, Дистрибутивность.

Алгоритм построение см. ДНФ

8. Скнф и сднф

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных конъюнкций

в каждой конъюнкции нет одинаковых пропозициональных букв

каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причем единственная.

СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных дизъюнкций

в каждой дизъюнкции нет одинаковых пропозициональных букв

каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.