Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
x ∨ ¬x — константа 1. § 6.4. Дизъюнктивные и конъюнктивные нормальные формы Если x — логическая переменная, δ ∈ {0, 1}, то выражение x δ = ( x, если δ = 1, x, если δ = 0 называется литерой. Литеры x и x называются контрарными. Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнк- ция литер. Пример 6.4.1. Формулы x ∨ y ∨ z и x ∨ y ∨ x ∨ x — дизъюнкты, формулы x 1 x 2 x 3 и x 1 x 2 x 1 — конъюнкты, а x является одновременно и дизъюнктом, и конъюнктом. ¤ 192 Глава 6. АЛГЕБРА ЛОГИКИ Дизъюнкция конъюнктов называется дизъюнктивной нормальной фор- мой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормаль- ной формой (КНФ). Пример 6.4.2. Формула xy ∨ yz — ДНФ, формула (x ∨ z ∨ y)(x ∨ z)y — КНФ, а формула xy является одновременно КНФ и ДНФ. ¤ Теорема 6.4.1. 1. Любая формула эквивалентна некоторой ДНФ. 2. Любая формула эквивалентна некоторой КНФ. Опишем алгоритм приведения формулы к ДНФ. 1. Выражаем все логические операции, участвующие в построении фор- мулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалент- ности (ϕ → ψ) ∼ (¬ϕ ∨ ψ), (ϕ ↔ ψ) ∼ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ) и определения операций |, ↓ и ⊕. 2. Используя законы де Моргана, переносим все отрицания к пере- менным и сокращаем двойные отрицания по правилу ¬¬x ∼ x. 3. Используя закон дистрибутивности (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ∧ χ)), преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъ- юнкций. В результате применения пп. 1–3 получается ДНФ данной формулы. ¤ Пример 6.4.3. Приведем к ДНФ формулу ϕ = ((x → y) ↓ ¬(y → z)). Выразим логические операции → и ↓ через ∧, ∨ и ¬: ϕ ∼ (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 0 . Используя закон дистрибутивности (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ)), преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции. 6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 193 Пример 6.4.4. Приведем к КНФ формулу ϕ = (x → y) ∧ ((y → z) → x). Преобразуем формулу ϕ к формуле, не содержащей →: ϕ ∼ (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) — эквивалентность 4 предложения 6.3.2., для (3) — закон поглощения). Таким образом, формула ϕ из примера 6.1.1 эквивалентными преобразованиями приводится к формуле x (являющейся одновременно ДНФ и КНФ формулы ϕ). ¤ Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают со- вершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ). Пусть (x 1 , . . . , x n ) — набор логических переменных, ∆ = (δ 1 , . . . , δ n ) — набор нулей и единиц. Конституентой единицы набора ∆ называется конъ- юнкт K 1 (δ 1 , . . . , δ n ) x δ 1 1 x δ 2 2 . . . x δ n n . Конституентой нуля набора ∆ на- зывается дизъюнкт K 0 (δ 1 , . . . , δ n ) x 1−δ 1 1 ∨ x 1−δ 2 2 ∨ . . . ∨ x 1−δ n n Отметим, что K 1 (δ 1 , δ 2 , . . . , δ n ) = 1 (K 0 (δ 1 , δ 2 , . . . , δ n ) = 0) тогда и только тогда, когда x 1 = δ 1 , x 2 = δ 2 , . . ., x n = δ n Совершенной ДНФ называется дизъюнкция некоторых конституент еди- ницы, среди которых нет одинаковых, а совершенной КНФ называется конъ- юнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная x i из набора {x 1 , . . . , x n } входит ровно один раз, причем входит либо сама x i , либо ее отрицание x i 194 Глава 6. АЛГЕБРА ЛОГИКИ Пример 6.4.5. Формула x 1 x 2 x 3 есть конституента единицы K 1 (1, 0, 1), формула x ∨ y ∨ z есть конституента нуля K 0 (0, 0, 1), формула x 1 x 2 x 3 ∨ ∨x 1 x 2 x 3 — СДНФ, формула (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) — СКНФ, а формула x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 не является СДНФ. ¤ Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исход- ной формуле ϕ, предварительно рассмотрим разложения булевой функции f (x 1 , x 2 , . . . , x n ) по k переменным (для определенности по x 1 , x 2 , . . ., x k ) — разложения Шеннона. Теорема 6.4.2 (первая теорема Шеннона). Любая булева функция f (x 1 , x 2 , . . . , x n ) представима в виде разложения Шеннона: f (x 1 , x 2 , . . . , x k , x k+1 , . . . , x n ) = = _ по всем наборам (δ 1 ,...,δ k ) ( k ∧ i=1 x δ i i )f (δ 1 , δ 2 , . . . , δ k , x k+1 , . . . , x n ). Доказательство. Прежде всего заметим, что x δ i i = 1 ⇔ x i = δ i . Под- ставим произвольно вместо первых k переменных их значения: x 1 = δ ∗ 1 , x 2 = δ ∗ 2 , . . ., x k = δ ∗ k . Тогда левая часть доказываемой формулы равна f (δ ∗ 1 , δ ∗ 2 , . . . , δ ∗ k , x k+1 , . . . , x n ). Правая часть представляет собой дизъюнкцию 2 k конъюнкций вида x δ 1 1 x δ 2 2 . . . x δ k k f (δ 1 , δ 2 , . . . , δ k , x k+1 , . . . , x n ), которые этой подстановкой разбиваются на два класса. К первому классу относится конъ- юнкция, у которой набор (δ 1 , δ 2 , . . . , δ k ) совпадает с набором (δ ∗ 1 , δ ∗ 2 , . . . , δ ∗ k ): (δ ∗ 1 ) δ ∗ 1 (δ ∗ 2 ) δ ∗ 2 . . . (δ ∗ k ) δ ∗ k f (δ ∗ 1 , δ ∗ 2 , . . . , δ ∗ k , x k+1 , . . . , x n ) = = 1 · 1 · . . . · 1 · f (δ ∗ 1 , δ ∗ 2 , . . . , δ ∗ k , x k+1 , . . . , x n ) = = f (δ ∗ 1 , δ ∗ 2 , . . . , δ ∗ k , x k+1 , . . . , x n ). Эта конъюнкция равна левой части формулы. Ко второму классу относится 2 k − 1 конъюнкций, у каждой из которых хотя бы в одной переменной x i , i ∈ {1, 2, . . . , k} выполнено условие δ ∗ i 6= δ i . Следовательно, каждая из них равна нулю. Используя закон a ∨ 0 = a, получаем, что левая и правая части формул равны при любой подстановке переменных x 1 , x 2 , . . . , x n . ¤ В силу принципа двойственности для булевых алгебр справедлива 6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 195 Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f (x 1 , x 2 , . . . , x n ) представима в виде разложения Шеннона: f (x 1 , x 2 , . . . , x k , x k+1 , . . . , x n ) = = ^ по всем наборам (δ 1 ,...,δ k ) ( k ∨ i=1 x 1−δ i i ∨ f (δ 1 , δ 2 , . . . , δ k , x k+1 , . . . , x n )). В предельном случае, когда k = n, для булевой функции f (x 1 , x 2 , . . . , x n ), не равной нулю, получаем ее представление в виде совершенной ДНФ: f (x 1 , x 2 , . . . , x n ) = _ по всем наборам (δ 1 ,δ 2 ,...,δ n ), на которых f (δ 1 ,...,δ n )=1 ( n ∧ i=1 x δ i i ). Аналогично для булевой функции f (x 1 , x 2 , . . . , x n ), не равной единице, получаем ее представление в виде совершенной КНФ: f (x 1 , x 2 , . . . , x n ) = ^ по всем наборам (δ 1 ,δ 2 ,...,δ n ), на которых f (δ 1 ,...,δ n )=0 ( n ∨ i=1 x 1−δ i i ). Приведенные формулы позволяют сформулировать следующую теорему. Теорема 6.4.4 (о функциональной полноте). Для любой булевой функ- ции f найдется формула ϕ, представляющая функцию f . Если f 6≡ 0, то существует представляющая ее формула ϕ, находящаяся в СДНФ: ϕ = _ f (δ 1 ,...,δ n )=1 K 1 (δ 1 , . . . , δ n ), и такое представление единственно с точностью до порядка следования конституент единицы. Если f 6≡ 1, то существует представляющая ее формула ϕ, находящаяся в СКНФ: ϕ = V f (δ 1 ,...,δ n )=0 K 0 (δ 1 , . . . , δ n ), и такое представление единственно с точностью до порядка следования консти- туент нуля. 196 Глава 6. АЛГЕБРА ЛОГИКИ Пример 6.4.6. Найти СДНФ и СКНФ функции f (x, y, z), заданной сле- дующей таблицей истинности: x 0 0 0 0 1 1 1 1 y 0 0 1 1 0 0 1 1 z 0 1 0 1 0 1 0 1 f (x, y, z) 1 0 0 1 0 1 0 1 По теореме о функциональной полноте СДНФ имеет вид ϕ 1 = x y z∨ ∨xyz ∨ xyz ∨ xyz, а СКНФ — ϕ 2 = (x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z). ¤ Итак, для нахождения СДНФ и СКНФ исходной формулы ϕ составляет- ся ее таблица истинности, а затем по ней строится требуемая совершенная нормальная форма. В примере 6.4.6, имея, скажем, СДНФ ϕ 1 для функции f , можно соста- вить ее таблицу истинности и по ней найти СКНФ ϕ 2 Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким, чем следующий алгоритм. Для нахождения СДНФ данную формулу приводим сначала к ДНФ, а за- тем преобразовываем ее конъюнкты в конституенты единицы с помощью следующих действий: а) если в конъюнкт входит некоторая переменная вместе со своим отри- цанием, то мы удаляем этот конъюнкт из ДНФ; б) если в конъюнкт одна и та же литера x δ входит несколько раз, то уда- ляем все литеры x δ , кроме одной; в) если в некоторый конъюнкт x δ 1 1 . . . x δ k k не входит переменная y, то этот конъюнкт заменяем на эквивалентную формулу x δ 1 1 . . . x δ k k ∧ (y ∨ y) и, приме- няя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида (y ∨ y); г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ. Пример 6.4.7. Найдем СДНФ для ДНФ ϕ = xx ∨ x ∨ yzy. Имеем ϕ ∼ ∼ x∨yz ∼ (x(y∨y)∨(x∨x)yz) ∼ (xy∨xy∨xyz∨xyz) ∼ ∼ (xy(z∨z)∨xy(z∨z)∨ ∨xyz∨xyz) ∼ (xyz∨xyz∨xyz∨xy z∨xyz∨xyz) ∼ (xyz∨xyz∨xyz∨xy z∨xyz). ¤ Описание алгоритма приведения КНФ к СКНФ аналогично вышеизло- женному описанию алгоритма приведения ДНФ к СДНФ и оставляется чи- тателю в качестве упражнения. 6.5. ДВУХЭЛЕМЕНТНАЯ БУЛЕВА АЛГЕБРА 197 § 6.5. Двухэлементная булева алгебра. Фактор-алгебра алгебры формул Рассмотрим множество B 0 = {0, 1} и определим на нем операции ∧, ∨, согласно таблицам истинности формул x ∧ y, x ∨ y, x. Тогда система B 0 = hB 0 ; ∧, ∨, , 0, 1i является двухэлементной булевой алгеброй (см. при- мер 2.6.3, п. 1). Формулы алгебры логики, содержащие лишь логические операции ∧, ∨, , являются термами в B 0 . По теореме о функциональной полноте в булевой алгебре B 0 с помощью терма можно задать любую буле- ву функцию. Обозначим через Φ n множество всех формул алгебры логики с пере- менными из множества {x 1 , x 2 , . . . , x n }. На множестве Φ n определены двух- местные операции конъюнкции и дизъюнкции — ∧: (ϕ, ψ) 7→ ϕ ∧ ψ, ∨: (ϕ, ψ) 7→ ϕ ∨ ψ — и одноместная операция отрицания : ϕ 7→ ϕ. Выде- лим на множестве Φ n две константы x 1 ∧ x 1 и x 1 ∨ x 1 . Тем самым получается алгебра формул F n hΦ n ; ∧, ∨, , x 1 ∧x 1 , x 1 ∨x 1 i. Нетрудно заметить, что от- ношение ∼ эквивалентности формул является конгруэнцией на алгебре F n , и поэтому можно задать фактор-алгебру F n /∼. На фактор-множестве Φ n /∼ операции ∧, ∨ и определяются следующим образом: ∼(ϕ)∧ ∼ (ψ) = ∼(ϕ∧ψ), ∼(ϕ)∨ ∼(ψ) = ∼(ϕ ∨ ψ), ∼(ϕ) = ∼(¬ϕ). На множестве Φ n /∼ выделяют- ся две константы: 0 = ∼(x 1 ∧ x 1 ) и 1 = ∼(x 1 ∨ x 1 ). Полученная система hΦ n /∼; ∧, ∨, , 0, 1i является фактор-алгеброй F n /∼. Теорема 6.5.1. |