Дизъюнктивные и конъюнктивные нормальные формы АВ

Если х — логическая переменная, δ {0,1}, то выражение

называется литерой. Литеры х и х называются контрарными.

Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.

Пример 6. Формулы x∨y∨z и x∨y∨x∨x — дизъюнкты.

формулы x∧y∧z и x∧y∧x — конъюнкты, а x является одновременно и дизъюнктом, и конъюнктом.

Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).

Пример7. Формула (x∧y)∨(y∧z) — ДНФ, формула (х∨z∨y)∧(x∨z)∧y — КНФ, а формула x∧y является одновременно КНФ и ДНФ.

Теорема 1.

1) Любая формула эквивалентна некоторой ДНФ.

2) Любая формула эквивалентна некоторой КНФ.

Опишем алгоритм приведения формулы к ДНФ.

1. Выражаем импликацию, участвующую в построении формулы, через дизъюнкцию и отрицание, используя эквивалентность φ→ψ≡φ∨ψ.

2. Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания по правилу x≡x.

3. Используя закон дистрибутивности φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

В результате применения пп. 1-3 получается ДНФ, эквивалентная исходной формуле.

Пример 8. Привести к ДНФ формулу φ ((x→y)∨(y→z)).

Решение. Выразим логическую операцию → через ∨ и: φ≡((x∨y)∨(y∨z)). Воспользуемся законами де Моргана и двойного отрицания: φ≡(x∨y)∧(y∨z)≡(x∧y)∧(y∨z)≡(x∧y)∧(y∨z). Используя закон дистрибутивности, приводим формулу к ДНФ: φ≡(x∧y∧y)∨(x∧y∧z).

Приведение формулы к КНФ производится аналогично при­ведению ее к ДНФ, только вместо п. 3 применяется п. 3':

3'. Используя закон дистрибутивности φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ), преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.

Пример 9. Привести к КНФ формулу φ (x→y)∧((y→z)→x).

Решение. Преобразуем формулу φ к формуле, не содержащей →: φ≡(x∨y)∧((y∨z)∨x). В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания: φ≡(x∨y)∧((y∧z)∨x)≡(x∨y)∧((y∧z)∨x). Используя закон дистрибутивности, приводим формулу к КНФ φ ≡ (x∨y)∧(x∨y)∧(x∨z). Упростим полученную формулу: (x∨y)∧(x∨y)∧(x∨z)≡(1)(x∨(y∧y))∧(x∨z)≡(2)x∧(x∨z)≡≡(3)x (для преобразования (1) использовался закон дистрибутивности, для (2) – эквивалентность 1 утверждения 1, для (3) — закон поглоще­ния). Таким образом, формула φ эквивалентными преобразованиями приводится к формуле x, являющейся одновременно ДНФ и КНФ.

 

2.1.4. Совершенные дизъюнктивные и конъюнктивные нормальные формы

 

Пусть (х₁,..., х_n) — набор логических переменных, Δ=(δ₁,…,δ_n) — набор нулей и единиц. Конституентой единицы набора Δ называется конъюнкт К¹(δ₁,…,δ_n)=x₁^δ1∧x₂^δ2∧…∧x_n^δn. Конституентой нуля набора Δ называется дизъюнкт К⁰(δ₁,…,δ_n)=x₁^1-δ1∨x₂^1-δ2∨…∨x_n^1-δn.

Отметим, что K¹(δ₁,δ₂,…,δ_n)=1 (K⁰(δ₁,δ₂,…,δ_n)=0) тогда и только тогда, когда x₁=δ₁, x₂=δ₂,…, x_n=δ_n.

Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых, а совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная х_i из набора {х₁,..., х_п} входит ровно один раз, причем входит либо сама х_i, либо ее отрицание x_i.

Пример 10. Формула x₁∧x₂∧x₃ есть конституента единицы K¹(1,0,1), формула x∨y∨z есть конституента нуля K⁰(0,0,1), формула (x₁∧x₂)∨(x₁∧x₂) – СДНФ, формула (x∨y∨z)∧(x∨y∨z)∧(x∨y∨z) – СКНФ, а формула (x₁∧x₂∧x₃)∨(x₁∧x₂∧x₃)∨(x₁∧x₂∧x₃) не является СДНФ.

Опишем алгоритм приведения формулы к СДНФ.

1. Приводим данную формулу к ДНФ.

2. Преобразовываем ее конъюнкты в конституенты единицыс помощью следующих действий:

а)если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ;

б)если в конъюнкт одна и та же литера x^δ входит несколько раз, то удаляем все литеры х^δ, кроме одной;

в)если в некоторый конъюнкт x₁^δ1∧…∧x_k^δk не входит переменная у, то этот конъюнкт заменяем на эквивалентную формулу x₁^δ1∧…∧x_k^δk∧(y∨y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида у∨y;

г)если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.

Пример 11. Найти СДНФ для ДНФ φ (x∧x)∨x∨(y∧z∧y).

Решение. Имеем φ≡x∨(y∧z)≡(x∧(y∨y))∨(y∧z∧(x∨x))≡ ≡(x∧y)∨(x∧y)∨(x∧y∧z)∨(x∧y∧z)≡

≡(x∧y∧(z∨z))∨(x∧y∧(z∨z))∨(x∧y∧z)∨(x∧y∧z)≡

≡(x∧y∧z)∨(x∧y∧z)∨(x∧y∧z)∨(x∧y∧z)∨(x∧y∧z)∨(x∧y∧z)≡

≡(x∧y∧z)∨(x∧y∧z)∨(x∧y∧z)∨(x∧y∧z)∨(x∧y∧z).

Описание алгоритма приведения формулы к СКНФ аналогично вышеизложенному описанию алгоритма приведения формулы к СДНФ и оставляется читателю в качестве упражнения.

 

Логическое следствие в АВ

Говорят, что формула ψ(х₁,...,х_п) АВ является логическим следствием формул φ₁(х₁,...,х_п),…,φ_m(х₁,...,х_п) АВ (обозначается ), если для любых из соотношений следует . Формулы называются гипотезами.

Пример 1. Доказать, что φ, φ→ψ, ψ→χ Построим таблицы истинности для каждой формулы:

 

φ	ψ	χ	φ→ψ	ψ→χ

 

Из таблицы истинности видно, что когда все гипотезы принимают значение равное 1, формула χ тоже принимает значение 1, значит, χ является логическим следствием, что и требовалось доказать.

Теорема 1.

1. Количество гипотез можно увеличивать.

2. Гипотезы можно переставлять в любом порядке.

3. тогда и только тогда, когда

4. тогда и только тогда, когда формула тождественно истина.

5. тогда и только тогда, когдаформула φ₁∧..∧φ_m∧ψ тождественно ложна.

Исчисление высказываний