Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
n = hB n ; ∧, ∨, , 0, 1i образует булеву алгебру функций алгебры логики от n переменных (алгебру булевых функций). § 6.3. Эквивалентность формул Как показано в примере 6.1.1, различные формулы могут иметь одинако- вые таблицы истинности. Так возникает понятие эквивалентности формул. Формулы ϕ(x 1 , . . . , x n ) и ψ(x 1 , . . . , x n ) называются эквивалентными (ϕ ∼ ψ), если совпадают их таблицы истинности, т. е. совпадают представ- ляемые этими формулами функции f ϕ (x 1 , . . . , x n ) и f ψ (x 1 , . . . , x n ). Пример 6.3.1. Построив таблицы истинности формул x → y и y → x, убеждаемся в том, что (x → y) ∼ (y → x). ¤ Легко видеть, что отношение ∼ является отношением эквивалентности, т. е. оно рефлексивно (ϕ ∼ ϕ), симметрично (ϕ ∼ ψ ⇒ ψ ∼ ϕ) и транзитивно (ϕ ∼ ψ, ψ ∼ χ ⇒ ϕ ∼ χ). Отметим основные эквивалентности между формулами: 1) ((ϕ∧ψ)∧χ) ∼ (ϕ∧(ψ∧χ)), ((ϕ∨ψ)∨χ) ∼ (ϕ∨(ψ∨χ)) (ассоциативность ∧ и ∨); 2) (ϕ ∧ ψ) ∼ (ψ ∧ ϕ), (ϕ ∨ ψ) ∼ (ψ ∨ ϕ) (коммутативность ∧ и ∨); 3) (ϕ ∧ ϕ) ∼ ϕ, (ϕ ∨ ϕ) ∼ ϕ (идемпотентность ∧ и ∨); 4) (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ)), (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ)∧ ∧(ϕ ∨ χ)) (законы дистрибутивности); 5) (ϕ ∧ (ϕ ∨ ψ)) ∼ ϕ, (ϕ ∨ (ϕ ∧ ψ)) ∼ ϕ (законы поглощения); 6) ¬(ϕ ∧ ψ) ∼ ¬ϕ ∨ ¬ψ, ¬(ϕ ∨ ψ) ∼ ¬ϕ ∧ ¬ψ (законы де Моргана); 7) ¬¬ϕ ∼ ϕ (закон двойного отрицания); 6.3. ЭКВИВАЛЕНТНОСТЬ ФОРМУЛ 187 8) ϕ → ψ ∼ ¬ϕ ∨ ψ; 9) ϕ ↔ ψ ∼ ((ϕ → ψ) ∧ (ψ → ϕ)) ∼ ((¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ)); 10) (ϕ ∨ ¬ϕψ) ∼ (ϕ ∨ ψ), (¬ϕ ∨ ϕψ) ∼ (¬ϕ ∨ ψ); 11) ϕ(¬ϕ ∨ ψ) ∼ ϕψ, ¬ϕ(ϕ ∨ ψ) ∼ ¬ϕψ. Формула ϕ(x 1 , x 2 , . . . , x n ) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула при- нимает значение 1 (соответственно 0). Пример 6.3.2. Формула x∧y является одновременно выполнимой и опро- вержимой, поскольку 0 ∧ 0 = 0, а 1 ∧ 1 = 1. ¤ Формула ϕ(x 1 , . . . , x n ) называется тождественно истинной, общезначи- мой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) при всех наборах зна- чений переменных, т. е. функция f является константой 1 (константой 0). Пример 6.3.3. Формула x ∨ x является тождественно истинной, а фор- мула x ∧ x — тождественно ложной: x x ∨ x x ∧ x 0 1 0 1 1 0 Если ϕ — тождественно истинная формула, то будем писать |= ϕ. В про- тивном случае пишем 6|= ϕ. Таким образом, |= x ∨ x, 6|= x ∧ y, и 6|= x ∧ x. Очевидным является следующее Замечание 6.3.1. 1. Формула ϕ тождественно ложна тогда и только тогда, когда ¬ϕ тождественно истинна (|= ¬ϕ); 2. Формула ϕ опровержима тогда и только тогда, когда она не является тождественно истинной (6|= ϕ); 3. Формула ϕ выполнима тогда и только тогда, когда она не является тождественно ложной. Отметим, что тождественно истинные (соответственно тождественно лож- ные) формулы образуют класс эквивалентности по отношению ∼. Предложение 6.3.2. Если формула ϕ 1 тождественно истинна, ϕ 0 — тождественно ложна, то для любых формул ϕ и ψ справедливы следующие эквивалентности: ϕ ∧ ϕ 1 ∼ ϕ; ϕ ∧ ϕ 0 ∼ ϕ 0 ; ϕ ∨ ϕ 1 ∼ ϕ 1 ; ϕ ∨ ϕ 0 ∼ ϕ; (ϕψ → ϕ) ∼ ϕ 1 ; (ϕ → ϕ ∨ ψ) ∼ ϕ 1 ; ϕ ⊕ ϕ ∼ ϕ 0 ; ϕ ⊕ ϕ 1 ∼ ϕ; ϕ ⊕ ϕ 0 ∼ ϕ. 188 Глава 6. АЛГЕБРА ЛОГИКИ В заключение настоящего параграфа приведем список всевозможных бу- левых функций от двух переменных, а также основных формул, представ- ляющих эти функции: 0 0 1 1 x 0 1 0 1 y 0 0 0 0 x ∧ ¬x — константа 0 0 0 0 1 x ∧ y — конъюнкция 0 0 1 0 ¬(x → y) — запрет по y 0 0 1 1 x — повтор x 0 1 0 0 ¬(y → x) — запрет по x 0 1 0 1 y — повтор y 0 1 1 0 x ⊕ y — логическое сложение 0 1 1 1 x ∨ y — дизъюнкция 1 0 0 0 x ↓ y — стрелка Пирса 1 0 0 1 x ↔ y — эквивалентность 1 0 1 0 ¬y — отрицание y 1 0 1 1 y → x — обратная импликация 1 1 0 0 ¬x — отрицание x 1 1 0 1 x → y — прямая импликация 1 1 1 0 x | y — штрих Шеффера 1 1 1 1 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 является одновременно и дизъюнктом, и конъюнктом. ¤ 6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 189 Дизъюнкция конъюнктов называется дизъюнктивной нормальной фор- мой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормаль- ной формой (КНФ). Пример 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 . Используя закон дистрибутивности (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ)), преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции. 190 Глава 6. АЛГЕБРА ЛОГИКИ Пример 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 6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 191 Пример 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 . ¤ В силу принципа двойственности для булевых алгебр справедлива 192 Глава 6. АЛГЕБРА ЛОГИКИ Теорема 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 |