Читайте также:
|
Элементарной конъюнкцией называется конъюнкция элементарных высказываний и (или) отрицаний элементарных высказываний.
Например: 
Элементарной дизъюнкцией называется дизъюнкция элементарных высказываний и (или) отрицаний элементарных высказываний.
Например: 
Дизъюнктивной нормальной формой (ДНФ) данной формулы называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.
Иными словами, ДНФ представляет собой формулу у которой между скобок стоят только знаки дизъюнкции, а внутри скобок – конъюнкции переменных и отрицаний переменных.
Например, выражение 
является ДНФ.
При записи ДНФ часто опускают знаки конъюнкции 
Конъюнктивной нормальной формой (КНФ) данной формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.
Например, выражение 
– КНФ.
Алгоритм построения ДНФ/КНФ:
1. Перейти в сигнатуру алгебры логики (выразить все операции через дизъюнкцию, конъюнкцию и отрицание) – для этого используются законы (…)
2. Воспользоваться законом де Моргана (и правило отрицания) для того, чтобы отрицания стояли лишь над элементарными переменными высказываниями,
3. Применяя дистрибутивный закон необходимое число раз, привести формулу к необходимой форме.
Последний шаг обычно является наиболее трудным.
Дата добавления: 2015-04-20; просмотров: 163 | Поможем написать вашу работу | Нарушение авторских прав |