Доказательство
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Необходимо обратить внимание на следующие два тождества. В дальнейшем они будут играть большую роль.
9)
–
первый закон Моргана.
Доказательство
|
|
|
|
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
10)
–
второй закон Моргана.
Доказательство
|
|
|
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
11)
–
закон двойного отрицания.
12)
–
закон противоречия.
13)
–
закон исключенного третьего.
14) .
15)
.
16)
.
Доказательство
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Тождества, содержащие константы:
17)
.
18)
.
19)
.
20)
.
21) .
22)
.
23)
.
24)
.
25)
.
26)
.
Тождества, содержащие константы:
17) .
18) .
19) .
20) .
21) .
22) .
23) .
24) .
25) .
26) .
§4. Дизъюнктивные нормальные формы (ДНФ)
В этом параграфе мы докажем, что все высказывания с помощью логических тождеств можно привести к некоторому единообразному стандартному виду, в котором они наиболее эффективно поддаются исследованию.
Определение 1
Пусть F –
высказывание и
.
Утверждение 2
в том и только в том случае, когда
.
Доказательство
Достаточно построить таблицу истинности
для
:
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Непосредственно видно, что
на тех и только тех наборах, где
.
Утверждение доказано.
Определение 3
Конъюнкция логических переменных или их отрицаний называется элементарной конъюнкцией.
Общий вид элементарной конъюнкции:
.
Примеры
.
Пятая формула не является элементарной конъюнкцией, так как отрицание расположенно не над переменной, а над более сложным выражением. Шестая формула не является элементарной конъюнкцией, так как в ней присутствует дизъюнкция, тогда как элементарные конъюнкции могут содержать лишь конъюнкции и отрицания над логическими переменными. Все остальные примеры являются элементарными конъюнкциями.
Определение 4
Высказывание называется дизъюнктивной
нормальной формой, если оно представляет
собою дизъюнкцию элементарных конъюнкций.
Общий вид ДНФ:
,
где каждая
,
в свою очередь, является элементарной
конъюнкцией.
Примеры
1)
;
2)
;
3)
;
4)
;
5)
;
6)
;
7)
.
Второе высказывание не является ДНФ, так как в ДНФ перемножаются лишь переменные или их отрицания. Пятое высказывание не является ДНФ, так как в ДНФ отрицание может располагаться лишь над переменными. Остальные высказывания являются дизъюнктивными нормальными формами.
Теорема 5
Любое высказывание равносильно дизъюнктивной нормальной форме (говорят еще так: “любое высказывание приводимо к ДНФ”).
Доказательство
Будем доказывать методом математической индукции по числу логических операций, входящих в высказывание .
В силу тождеств
можно в высказывании
избавиться от всех импликаций и
эквивалентностей, входящих в
.
Например, пусть
,
тогда
.
Получили высказывание, равносильное
и не содержащее "®"
и "«".
В дальнейшем будем считать, что
высказывание
построено из логических переменных и
операций
.
Через n
обозначим количество операций, входящих
в
.
Пусть n=0,
тогда высказывание
,
следуя определению, может быть лишь
простейшим высказыванием или логической
переменной
.
Очевидно, что это высказывание есть
ДНФ.
Допустим, утверждение о приведении к
ДНФ доказано для всех высказываний с
числом логических операций
.
И докажем теперь его для высказывания
,
которое содержит
логических операций. Опять же, следуя
определению высказывания и тому
обстоятельству, что в
нет импликаций и эквивалентностей,
представимо в одном из трех видов:
,
или
,
или
.
В первых двух случаях на высказывания
и
в сумме приходится
логических операций, значит, каждое из
них содержит
операций. В третьем случае
содержит ровно
логических операций. Во всех случаях
и
по индуктивному предположению приводятся
к ДНФ, поэтому можно считать, что
,
где
и
–
элементарные конъюнкции.
В первом случае
,
то есть F является дизъюнкцией элементарных конъюнкций, то есть ДНФ.
Во втором случае
.
Так как произведение элементарных конъюнкций есть элементарная конъюнкция, значит, и во втором случае приводимо к ДНФ.
Осталось доказать приводимость к ДНФ
в третьем случае, то есть когда
.
Для упрощения выкладок будем считать,
что l=2 и
каждая элементарная конъюнкция есть
произведение двух логических переменных
или их отрицаний, то есть
.
При доказательстве того, что F приводимо к ДНФ, нам придется воспользоваться следующим простым равенством, которое мы рекомендуем доказать самостоятельно:
.
Итак, начинаем приводить F к ДНФ:
,
то есть и в последнем, третьем случае F приводимо к ДНФ.
Таким образом, теорема доказана.
Пример
Привести к ДНФ высказывание
.