| МОУ Лицей №4. г. Люберцы 2010 г |
| Байрамов Ренат. 9 «Б» |
| Экзамен по «Информатике и ИКТ». |
Особую роль в алгебре логики играют классы дизъюнктивных и конъюнктивных совершенных нормальных форм.
Формулу называют конъюнкцией, если она является конъюнкцией одной из нескольких переменных, взятых с отрицанием или без отрицания. Одну переменную или ее отрицание считают одночленной элементарной конъюнкцией. Конъюнктивная нормальная форма (КНФ) - это нормальная форма, в которой булева формула имеет вид конъюнкции.
Формула A от k переменных называется совершенной конъюнктивной нормальной формулой (СНКФ), если:
1) А является КНФ, в которой каждая элементарная дизъюнкция ,причем на i-м месте этой дизъюнкции стоит либо переменная xi, либо ее отрицание; Все элементарные дизъюнкции в такой КНФ попарно различны.
Формула называется дизъюнктивной нормальной формой ДНФ, если она является дизъюнкцией неповторяющихся элементарных конъюнкций.
Формула А от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных x1, x2, …, xk, причем на i-м месте этой конъюнкции стоит либо переменная xi, либо ее отрицание;
2) Все элементарные конъюнкции в такой ДНФ попарно различны.