Полные системы истинностных функций
Теорема. Всякая истинностная функция, не равная тождественно Л, может быть представлена в СДНФ. Всякая истинностная функция, не равная тождественно И, может быть представлена в СКНФ.
Определение. Конъюнкция, составленная из элементарных дизъюнкций, называется совершенной конъюнктивной нормальной формой (СКНФ).
Определение. Дизъюнкция, составленная из элементарных конъюнкций, называется совершенной дизъюнктивной нормальной формой (СДНФ).
Составленная СДНФ выражает ту же истинностную функцию, что и истинностная таблица.
□ Пусть при данном наборе (P1,..., Рп) истинностная функция, согласно истинностной таблице, имеет значение И: f(P1,..., Рп)= И. Тогда этот набор будет среди выбранных, значит, среди составленных элементарных конъюнкций будет такая, которая при данном наборе примет значение И. Поэтому в СДНФ будет один (и только один) член, имеющий значение И. По определению дизъюнкции значение И будет иметь и СДНФ.
Пусть теперь при данном наборе (P1,..., Рп) истинностная функция, согласно истинностной таблице, имеет значение JI. Тогда этого набора не будет среди выбранных, и, значит, все составленные элементарные конъюнкции будут иметь значение Л (элементарная конъюнкция обладает свойством принимать значение И только при том наборе, для которого она составлена). Итак, все члены СДНФ, а поэтому и она сама имеют значение JI. ■
Алгоритм СКНФ (совершенная конзъюнктивная нормальная форма). Этот алгоритм аналогичен алгоритму СДНФ.
1. Выбираем все те наборы значений атомов P1,..., Рп, при которых истинностная функция имеет значение Л.
И | Л | Л |
Л | И | Л |
Л | Л | И |
Л | Л | Л |
2. Для каждого из этих наборов составляем дизъюнкцию из атомов P1,..., Рп или их отрицаний, такую, что при данном наборе она принимает значение Л.
¬ P1 Ú P2 Ú Pз.
P1 Ú¬ P2 Ú Pз.
P1 Ú P2 Ú¬ Pз.
P1 Ú P2 Ú Pз.
Дизъюнкции, содержащие все п атомов P1,..., Рп (с отрицаниями или без них), называются элементарными дизъюнкциями (длины п).
3. Составляем конъюнкцию выписанных элементарных дизъюнкций.
(¬ P1 Ú P2 Ú Pз)Ù(P1 Ú¬ P2 Ú Pз)Ù(P1 Ú P2 Ú¬ Pз)Ù(P1 Ú P2 Ú Pз).
Составленная СКНФ выражает ту же истинностную функцию, что и истинностная таблица.
Из теоремы следует, что для выражения любой истинностной функции достаточно трех логических операций: отрицания, конъюнкции и дизъюнкции.
Система { Ø, Ù. Ú} — полная, что следует из предыдущей теоремы.
Существуют и более “бедные” функциями системы, являющиеся полными. Теорема. Системы истинностных функций
{Ø, Ù }, {Ø, Ú }, {Ø, Þ}– полные .
□ Для доказательства полноты системы { Ø, Ù} достаточно, исходя из полноты системы { Ø, Ù. Ú} выразить дизъюнкцию через отрицание и конъюнкцию. Но это имеет место в силу равносильности
А Ú В ≡ Ø (Ø А Ù Ø В). (1)
Полнота системы { Ø, Ú} следует из равносильности
А Ù В ≡Ø (Ø А Ú Ø В). (2)
Полнота системы { Ø, Þ } следует из равносильности
А Þ В ≡ Ø А Ú В. (3)
Равносильности (1), (2), (3) можно доказать, например, составлением истинностных таблиц. ■
Среди указанных в таблице двухместных истинностных функций имеются и такие, которые в единственном числе образуют полную систему истинностных функций.
Например, функции штрих Шеффера (отрицание конъюнкции или дизъюнкция отрицаний ) и стрелка Пирса (отрицание дизъюнкции или конъюнкция отрицаний ):
А | В | А| В | А | В | А¯В | |
И | И | Л | И | И | Л | |
И | Л | И | И | Л | Л | |
Л | И | И | Л | И | Л | |
Л | Л | И | Л | Л | И |
Теорема. Системы истинностных функций {|} и {¯} – полные .
□ Полноту системы {|} доказывают равносильности:
ØА º А | А,
АÚВ= (А | А) | (В | В)
АÙВ= (А | В) | (А | В)
Покажем, что Ø и Ù выражаются через |.
А | А|A | |
и | л | л |
л | и | и |
А | В | А|В | (А|B)|(A|B) | AÙB |
и | и | л | и | и |
и | л | и | л | л |
л | и | и | л | л |
л | л | и | л | л |
Т.к. - полная система функций, а {|} выражается через , то{|} - полная система.
Полноту системы {¯} доказывают равносильности:
ØА º А¯А,
АÙВ= (А¯А)¯(В¯В)
АÚВ= (А¯В)¯(А¯В)
Выразим через ¯
A | A¯A | |
и | л | л |
л | и | и |
Покажем, что
А | В | ||||
и | и | л | л | и | и |
и | л | л | и | л | л |
л | и | и | л | л | л |
л | л | и | и | л | л |
Т.к. {}- полная система функций, то - полная система функций. ■