Лекция 3_2гр

1. Нормальные формы формул алгебры высказываний

2.

Теорема
2.
Любая выполнимая формула
( X 1 ,..., X n ) равносильна формуле вида
где
дизъюнкция
берется
по
всем
1,..., n {0,1}n,
упорядоченным наборам
удовлетворяющим условию F 1,..., n 1 .
Такая формула определяется однозначно (с
точностью до порядка членов конъюнкций и
дизъюнкций) и называется совершенной
дизъюнктивной
нормальной
формой
(сокращенно СДНФ) формулы .

3.

Теорема 3. Любая опровержимая формула
( X 1 ,..., X n ) равносильна формуле вида
где конъюнкция берется по всем упорядоченным
1,..., n {0,1}n, удовлетворяющим
наборам
условию F 1 ,..., n 0 .
Такая формула определяется однозначно (с
точностью до порядка членов конъюнкций и
дизъюнкций)
и
называется
совершенной
конъюнктивной нормальной формой (сокращенно
СКНФ) формулы .

4.

Алгоритм нахождения СДНФ и СКНФ
формулы ( X 1,..., X n ) :
1. Составить истинностную таблицу
формулы и добавить два столбца
«Совершенные конъюнкты» и «Совершенные
дизъюнкты».
2. Если при значениях ( X 1 ) k1,..., ( X n ) kn
значение ( ( X 1 ,..., X n )) формулы равно 1, то
в соответствующей строке таблицы в столбце
«Совершенные
конъюнкты»
записываем
X1k1 X nk n
конъюнкт
и
в
столбце
«Совершенные дизъюнкты» делаем прочерк.
При этом X i1 X i и X i0 X i .

5.

3. Если при значениях ( X 1 ) m1,..., ( X n ) mn
истинностное значение ( ( X 1 ,..., X n )) формулы
равно 0, то в соответствующей строке таблицы в
столбце «Совершенные дизъюнкты» записываем
X11 m1 X n1 mn
дизъюнкт
и
в
столбце
«Совершенные конъюнкты» делаем прочерк.
X1
…
Xn
...
( X 1 ,..., X n )
… … … ...
k1 … k n ...
… … … ...
m1 … mn ...
…
1
…
0
…
…
…
…
...
Совершенные Совершенные
конъюнкты
дизъюнкты
…
…
–
X1k1 X nk n
…
…
–
X11 m1 X n1 mn
…
…

6.

4. СДНФ формулы равна дизъюнкции
полученных
совершенных
конъюнктов:
( X1k1 X nk n ) … .
5. СКНФ формулы равна конъюнкции
полученных
совершенных
дизъюнктов:
( X11 m1 X n1 mn ) … .

7.

Пример. Найдем СДНФ и СКНФ для формулы
X
Y
Z
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
(X,Y,Z)
1
0
1
0
0
0
1
1
Совершенные
конъюнкты
X 0 Y0 Z0
Совершенные
дизъюнкты
–
–
X 1 Y1 Z 0
X 0 Y1 Z 0
–
–
–
–
X1 Y0 Z0
X 0 Y1 Z1
X 1 Y1 Z 0
–
–
X 1 Y1 Z1
X 0 Y1 Z 0
( X Y Z ) ( X Y Z ) ( X Y Z ) ( X Y Z ) .
( X Y Z ) ( X Y Z ) ( X Y Z ) ( X Y Z ) .

8. Логическое следование формул

9.

Определение. Формула называется
логическим следствием формул 1,..., m , если
при любой подстановке в эти формулы вместо
X 1 ,..., X n
их
переменных
конкретных
A1 ,..., An
высказываний
из
истинности
высказываний 1 ( A1,..., An ),..., m ( A1,..., An ) следует
истинность высказывания ( A1,..., An ) .
Символическое обозначение 1,..., m | называется логическим следованием.
Формулы 1,..., m называются посылками и
формула – следствием логического
следования 1,..., m | .

10.

Условие F1 ,..., F m |= F означает, что при
любых истинностных значениях переменных
X 1 ,..., X n из равенств
F1=1,…, Fm=1 следует равенство F=1.
Условие ¬( F1 ,..., F m |= F ) означает, что при
некоторых
истинностных
значениях
переменных X 1,..., X n выполняются равенства
F1=1,…, Fm=1 и F=0.

11.

12.

Основные правила логического следования:
1) правило отделения (или правило модус
поненс – от латинского modus ponens)
, | ;
2) правило контрапозиции
| ;
3) правило цепного заключения
1 2 , 2 3 | 1 3 ;
4) правило перестановки посылок
1 ( 2 3 ) | 2 ( 1 3 ) .

13.

Определение.
Множество
формул
1 ,..., m называется противоречивым,
если из него логически следует любая (в
том числе и тождественно ложная)
.
формула
Символически
это
записывается
.
В противном случае множество
1 ,..., m
формул
называется
выполнимым.

14.

Лемма (Критерии логического следования).
Условие 1,..., m | равносильно каждому из
следующих условий:
a) 1 ... m | ,
b) | 1 ... m ,
c) 1 , , m , | .
В частности, | равносильно | .
Отсюда также следует, что равносильно
тому, что | и | .

15.

Вывод: Следующие задачи равносильны:
а) проверка тождественной истинности
формул;
б) проверка логического следования
формул;
в) проверка тождественной ложности
формул;
г) проверка противоречивости множества
формул.