Совершенные нормальные формы истинностных функций
Имеется два способа задания истинностных функций — формулой и истинностной таблицей. По формуле легко составляется истинностная таблица. На практике при конструировании различных электронных устройств возникает обратная задача – от истинностной таблицы перейти к формуле.
Для ее решения имеются два алгоритма. Пусть имеется истинностная функция
F(P1, ..., Рп), заданная истинностной таблицей.
|
P1 |
P2 |
Рз |
f{P1, P2, Р3) |
|
И |
И |
И |
И |
|
И |
И |
Л |
И |
|
И |
Л |
И |
И |
|
И |
Л |
Л |
Л |
|
Л |
И |
И |
И |
|
Л |
И |
Л |
Л |
|
Л |
Л |
И |
Л |
|
Л |
Л |
Л |
Л |
Алгоритм СДНФ (совершенная дизъюнктивная нормальная форма).
1.
Рассмотрим все те наборы значений
атомовP1,
..., Рп,
для которых
f(P1, ..., Рп)=И.
В примере такими наборами будут (И, И, И), (И, И, Л), (И, Л, И), (Л, И, И).
2. Для каждого из отобранных наборов составляем конъюнкцию из атомов P1, ..., Рп или их отрицаний, принимающую при данном наборе значение И.
Конъюнкции, содержащие все п атомов P1, ..., Рп (с отрицаниями или без них), называются элементарными конъюнкциями (длины п).
В нашем примере элементарными конъюнкциями будут такие формулы:
P1P2Pз
P1P2¬Pз
P1¬P2Pз
¬P1P2Pз.
в) Составляем дизъюнкцию выписанных элементарных конъюнкций. Для нашего примера получим такую дизъюнкцию:
P1P2Pз P1P2¬Pз P1¬P2Pз ¬P1P2Pз.
Определение. Дизъюнкция, составленная из элементарных конъюнкций, называется совершенной дизъюнктивной нормальной формой (СДНФ).
Составленная СДНФ выражает ту же истинностную функцию, что и истинностная таблица.
□ Пусть при данном наборе (P1, ..., Рп) истинностная функция, согласно истинностной таблице, имеет значение И: f(P1, ..., Рп)= И. Тогда этот набор будет среди выбранных, значит, среди составленных элементарных конъюнкций будет такая, которая при данном наборе примет значение И. Поэтому в СДНФ будет один (и только один) член, имеющий значение И. По определению дизъюнкции значение И будет иметь и СДНФ.
Пусть теперь при данном наборе (P1, ..., Рп) истинностная функция, согласно истинностной таблице, имеет значение JI. Тогда этого набора не будет среди выбранных, и, значит, все составленные элементарные конъюнкции будут иметь значение Л (элементарная конъюнкция обладает свойством принимать значение И только при том наборе, для которого она составлена). Итак, все члены СДНФ, а поэтому и она сама имеют значение JI. ■
Алгоритм СКНФ (совершенная конзъюнктивная нормальная форма).Этот алгоритм аналогичен алгоритму СДНФ.
1. Выбираем все те наборы значений атомов P1, ..., Рп, при которых истинностная функция имеет значение Л.
|
И |
Л |
Л |
|
Л |
И |
Л |
|
Л |
Л |
И |
|
Л |
Л |
Л |
2. Для каждого из этих наборов составляем дизъюнкцию из атомов P1, ..., Рп или их отрицаний, такую, что при данном наборе она принимает значение Л.
¬P1P2Pз.
P1¬P2Pз.
P1P2¬Pз.
P1P2Pз.
Дизъюнкции, содержащие все п атомов P1, ..., Рп (с отрицаниями или без них), называются элементарными дизъюнкциями (длины п).
3. Составляем конъюнкцию выписанных элементарных дизъюнкций.
(¬P1P2Pз)(P1¬P2Pз)(P1P2¬Pз)(P1P2Pз).
Определение. Конъюнкция, составленная из элементарных дизъюнкций, называется совершенной конъюнктивной нормальной формой (СКНФ).
Составленная СКНФ выражает ту же истинностную функцию, что и истинностная таблица.
Теорема. Всякая истинностная функция, не равная тождественно Л, может быть представлена в СДНФ. Всякая истинностная функция, не равная тождественно И, может быть представлена в СКНФ.