Совершенные нормальные формы
Совершенная нормальная форма данной формулы – это формула, равносильная данной, содержащая только отрицания, конъюнкции и дизъюнкции.
Конъюнктивный одночлен или конъюнт от переменных , ,…, – это конъюнкция этих переменных или их отрицаний.
Конъюнктивный (дизъюнктивный) одночлен от переменных ,…, называется совершенным, если от каждой пары – ¬ входит ровно 1 представитель. Например, (¬ ) ۸ ۸ ).
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конъюнктивных одночленов, т.е. выражение вида , где
i=1…p, - конъюнктивный одночлен.
Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктивных одночленов, то есть выражение вида i=1…e
Нормальная форма от переменных называется совершенной(СДНФ,СКНФ), если в нее входят только совершенные одночлены от этих переменных.
Алгоритм приведения формулы к СДНФ (СКНФ):
Выбрать все наборы переменных, при которых формула истинна (ложна).
Для каждого набора выписать совершенный конъюнктивный (дизъюнктивный) одночлен, логическое значение которого равно 1 (0) на нем и только на нем.
Полученные одночлены соединить знаками дизъюнкции (конъюнкции)
- Базовые понятия математической логики
- Алгебра высказываний
- Формулы алгебры высказываний
- Совершенные нормальные формы
- Булевы функции Основные свойства и теоремы
- Математическая модель представления релейно-контактных схем с помощью булевых функций
- Сумматоры.
- Четвертьсумматор
- Двоичный полусумматор
- Одноразрядный двоичный сумматор.
- Заключение