Нормальные и основные формы
Опубликовано: 19 Декабря, 2021
- Дизъюнктивные нормальные формы (DNF):
Формула, эквивалентная данной формуле и состоящая из суммы элементарных произведений, называется дизъюнктивной нормальной формой данной формулы.Пример :
(P ∧ ~ Q) ∨ (Q ∧ R) ∨ (~ P ∧ Q ∧ ~ R)- ДНФ формулы не уникальна.
- Конъюнктивная нормальная форма (CNF):
Формула, эквивалентная данной формуле и состоящая из произведения элементарных произведений, называется конъюнктивной нормальной формой данной формулы.Пример :
(P ~ ∨ Q) ∧ (Q ∨ R) ∧ (~ P ∨ Q ∨ ~ R)- CNF формулы не уникальна.
- Если каждая элементарная сумма в КНФ является тавтологией, то данная формула также является тавтологией.
- Принцип дизъюнктивной нормальной формы (PDNF):
Эквивалентная формула, состоящая только из дизъюнкций минтермов, называется главной дизъюнктивной нормальной формой формулы.Он также известен как каноническая форма суммы произведений .
Пример :
(P ∧ ~ Q ∧ ~ R) ∨ (P ∧ ~ Q ∧ R) ∨ (~ P ∧ ~ Q ∧ ~ R)- Минтерм состоит из союзов, в которых каждая переменная оператора или ее отрицание, но не то и другое, появляется только один раз.
- Минтермы записываются путем включения переменной, если ее значение истинности равно T, и ее отрицания, если ее значение истинности равно F.
- Принцип конъюнктивной нормальной формы (PCNF):
Эквивалентная формула, состоящая только из конъюнктивов maxterms, называется основной конъюнктивной нормальной формой формулы.Он также известен как каноническая форма произведения сумм .
Пример :
(P ∨ ~ Q ∨ ~ R) ∧ (P ∨ ~ Q ∨ R) ∧ (~ P ∨ ~ Q ∨ ~ R)- Maxterm состоит из дизъюнкций, в которых каждая переменная или ее отрицание, но не оба, появляются только один раз.
- Двойственный термин minterm называется maxterm.
- Каждый из maxterm имеет значение истинности F ровно для одной комбинации значений истинности переменных.
- Максимальные термины записываются путем включения переменной, если ее значение истинности равно F, и отрицания, если ее значение истинности равно T.