Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний




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

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

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

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

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

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

Теорема 2. Для любой формулы φ АВ существует ДНФ (КНФ) ψ АВ такая, что φ≡ψ.

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

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

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

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

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

Пример 10. Привести к ДНФ формулу φ ((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). Упростим полученную формулу: (x∧y∧y)∨(x∧y∧z)≡(1) (x∧y)∨(x∧y∧z)≡(2) x∧y (для преобразования (1) использовался закон идемпотентности, для (2) – закон поглощения). Таким образом, формула φ эквивалентными преобразованиями приводится к формуле x∧y, являющейся одновременно ДНФ и КНФ.

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

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

Пример 11. Привести к КНФ формулу φ (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.5. Совершенные дизъюнктивные и конъюнктивные

нормальные формы

 

Пусть 1,..., хn) — набор логических переменных, Δ=(δ1,…,δn) — набор нулей и единиц. Конституентой единицы набора Δ называется конъюнкт К11,…,δn)=x1δ1∧x2δ2∧…∧xnδn. Конституентой нуля набора Δ называется дизъюнкт К01,…,δn)=x11-δ1∨x21-δ2∨…∨xn1-δn.

Отметим, что K112,…,δn)=1 (K012,…,δn)=0) тогда и только тогда, когда x11, x22,…, xnn.

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

Пример 12. Формула x1∧x2∧x3 есть конституента единицы K1(1,0,1), формула x∨y∨z есть конституента нуля K0(0,0,1), формула (x1∧x2)∨(x1∧x2) – СДНФ, формула (x∨y∨z)∧(x∨y∨z)∧(x∨y∨z) – СКНФ, а формула (x1∧x2∧x3)∨(x1∧x2∧x3)∨(x1∧x2∧x3) не является СДНФ.

Теорема 3. Для любой не тождественно ложной (не тождественно истинной) формулы φ АВ существует единственая СДНФ (СКНФ) ψ АВ такая, что φ≡ψ.

Заметим, что единственность формулы в формулировке теоремы понимается с точностью до порядка следования конъюнктивных сомножителей и дизъюнктивных слагаемых в этой формуле.

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

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

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

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

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

в) если в конъюнкт x1δ1∧…∧xkδk не входит переменная у, то этот конъюнкт заменяем на эквивалентную формулу (x1δ1∧…∧xkδk∧y)∨(x1δ1∧…∧xkδk∧y);

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

В результате получается СДНФ.

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

Решение. Имеем φ≡x∨(y∧z)≡(x∧y)∨(x∧y)∨(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).

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







Дата добавления: 2014-11-10; просмотров: 3916. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2020 год . (0.004 сек.) русская версия | украинская версия