Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
, то существует представляющая ее формула ϕ, находящаяся в СДНФ: ϕ = _ f (δ 1 ,...,δ n )=1 K 1 (δ 1 , . . . , δ n ), и такое представление единственно с точностью до порядка следования конституент единицы. Если f 6≡ 1, то существует представляющая ее формула ϕ, находящаяся в СКНФ: ϕ = V f (δ 1 ,...,δ n )=0 K 0 (δ 1 , . . . , δ n ), и такое представление единственно с точностью до порядка следования консти- туент нуля. 6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 193 Пример 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). ¤ Описание алгоритма приведения КНФ к СКНФ аналогично вышеизло- женному описанию алгоритма приведения ДНФ к СДНФ и оставляется чи- тателю в качестве упражнения. 194 Глава 6. АЛГЕБРА ЛОГИКИ § 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. Фактор-алгебра F n /∼ изоморфна алгебре булевых функ- ций B n . Доказательство. Искомый изоморфизм ξ: F n /∼ ∼ → B n определяет- ся по следующему правилу: классу эквивалентности ∼ (ϕ) сопоставляется функция f ϕ , имеющая таблицу истинности произвольной формулы из мно- жества ∼ (ϕ). Поскольку разным классам эквивалентности соответствуют различные таблицы истинности, отображение ξ инъективно, а так как для любой булевой функции f из B n найдется формула ϕ ∈ Φ n , представляющая функцию f , то отображение ξ сюръективно. Сохранение операций ∧, ∨, , 0, 1 при отображении ξ проверяется непосредственно. ¤ По теореме о функциональной полноте каждой функции f ∈ B n , не яв- ляющейся константой 0, соответствует некоторая СДНФ ψ, принадлежащая классу ∼ (ϕ) = ξ −1 (f ) формул, представляющих функцию f . Возникает за- дача нахождения в классе ∼ (ϕ) дизъюнктивной нормальной формы, имею- щей наиболее простое строение. 6.6. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ДНФ 195 § 6.6. Минимизация булевых функций в классе ДНФ Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза. Пример 6.6.1. Формула x 2 x 3 x 4 — элементарное произведение, а форму- ла x 1 x 2 x 1 x 3 элементарным произведением не является. ¤ Формула ϕ(x 1 , x 2 , . . . , x n ) называется импликантой формулы ψ(x 1 , x 2 , . . . , x n ), если ϕ — элементарное произведение и ϕ ∧ ψ ∼ ϕ, т. е. для соответствующих формулам ϕ и ψ функций f ϕ и f ψ справедливо неравен- ство f ϕ 6 f ψ . Формула ϕ(x 1 , . . . , x n ) называется импликантой функции f , если ϕ — импликанта совершенной ДНФ, представляющей функцию f . Им- пликанта ϕ(x 1 , . . . , x n ) = x δ 1 i 1 x δ 2 i 2 . . . x δ k i k формулы ψ называется простой, если после отбрасывания любой литеры из ϕ не получается формула, являюща- яся импликантой формулы ψ. Пример 6.6.2. Найдем все импликанты и простые импликанты для фор- мулы ϕ(x, y) = x → y. Всего имеется 8 элементарных произведений с пере- менными x и y. Ниже приведены их таблицы истинности: x y ϕ = x → y x y xy xy xy x y x y 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 Из таблиц истинности заключаем, что формулы x y, xy, xy, x, y — все им- пликанты формулы ϕ, а из этих импликант простыми являются формулы x и y (формула x y, например, не является простой импликантой, поскольку отбрасывая литеру y, получаем импликанту x). ¤ Дизъюнкция всех простых импликант данной формулы (функции) назы- вается сокращенной ДНФ. Теорема 6.6.1. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ. ¤ 196 Глава 6. АЛГЕБРА ЛОГИКИ В примере 6.6.2 функция, соответствующая формуле x → y, представима формулой x ∨ y, которая является ее сокращенной ДНФ. Сокращенная ДНФ может содержать лишние импликанты, удаление ко- торых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой. Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно. Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МДНФ). Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции, сохраняю- щие таблицы истинности формул: • операция полного склеивания: ϕ · x ∨ ϕ · x 7→ ϕ, • операция неполного склеивания: ϕ · x ∨ ϕ · x 7→ ϕ ∨ ϕ · x ∨ ϕ · x, • операция элементарного поглощения: ϕ · x δ ∨ ϕ 7→ ϕ, δ ∈ {0, 1}. Теорема 6.6.2 (теорема Квайна). Если исходя из совершенной ДНФ функции произвести все возможные операции неполного склеивания, а за- тем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант. Пример 6.6.3. Пусть функция f (x, y, z) задана совершенной ДНФ ϕ = xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz. Тогда, производя в два этапа все возможные операции неполного склеивания, а затем элементарного поглощения, имеем ϕ ∼ xy(z ∨ z) ∨ yz(x ∨ x) ∨ yz(x ∨ x) ∨ xz(y ∨ y)∨ ∨xy(z ∨ z) ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼ ∼ xy ∨ yz ∨ yz ∨ xz ∨ xy ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼ ∼ y(x ∨ x) ∨ y(z ∨ z) ∨ xy ∨ yz ∨ yz ∨ xz ∨ xy∨ ∨xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼ ∼ y ∨ xy ∨ yz ∨ yz ∨ xz ∨ xy∨ ∨xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼ y ∨ xz. Таким образом, сокращенной ДНФ функции f является формула y ∨ xz. ¤ 6.6. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ДНФ 197 На практике при выполнении операций неполного склеивания на каж- дом этапе можно не писать члены, участвующие в этих операциях, а пи- сать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие ни в каком склеивании. Пример 6.6.4. Пусть функция f (x, y, z) задана совершенной ДНФ ϕ = = x y z ∨ x yz ∨ xyz ∨ xyz. Тогда, производя операции склеивания, а затем элементарного поглощения, имеем ϕ ∼ x y(z ∨ z) ∨ yz(x ∨ x) ∨ xz(y ∨ y) ∼ ∼ x y ∨ yz ∨ xz. ¤ Для получения минимальной ДНФ из сокращенной ДНФ использует- ся матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. Для примера 6.6.4 матрица Квайна имеет вид Импликанты Конституенты единицы x y z x yz xyz xyz x y ∗ ∗ yz ∗ ∗ xz ∗ ∗ В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т. е. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве ми- нимальной ДНФ выбирается тупиковая, имеющая наименьшее число вхож- дений переменных. В примере 6.6.4 по матрице Квайна находим, что минимальная ДНФ заданной функции есть x y ∨ xz. В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для на- хождения минимальных конъюнктивных нормальных форм (МКНФ). 198 Глава 6. АЛГЕБРА ЛОГИКИ § 6.7. Карты Карно Для формул с малым числом переменных имеется другой способ получе- ния простых импликант (и, значит, нахождения с помощью матрицы Квайна минимальной ДНФ). Этот способ основан на использовании так называемых карт Карно. Карта Карно для n переменных служит эффективным средством иллю- стративного представления n-куба. Она содержит 2 n ячеек, каждая из ко- торых соответствует одной из 2 n возможных комбинаций значений n ло- гических переменных x 1 , x 2 , . . ., x n . Карта строится в виде матрицы разме- ра 2 n−k на 2 k так, что ее столбцы соответствуют значениям переменных x 1 , . . . , x k , строки — значениям переменных x k+1 , . . . , x n , а соседние ячейки (как по вертикали, так и по горизонтали) отличаются только значением од- ной переменной (рис. 6.5). На рис. 6.6 приведены карты Карно для функций трех и четырех пере- менных соответственно. В этих картах все ячейки, отмеченные скобкой x i (по строке и столбцу), представляют входные комбинации с x i = 1, а в неот- меченных строках и столбцах ячейки соответствуют комбинациям с x i = 0 (см. рис. 6.6а, на котором разными способами изображена одна и та же кар- та). Например, на рис. 6.6а ячейка a соответствует набору 001 значений пе- ременных x 1 , x 2 , x 3 . Отметим, что для каждой функции может быть постро- ено несколько различных карт. На рис. 6.6б изображены две карты Карно для функции четырех переменных. Первая карта соответствует разбиению переменных {{x 1 , x 2 }, {x 3 , x 4 }}, а вторая — {{x 1 }, {x 2 , x 3 , x 4 }}. У каждой вершины n-куба есть ровно n смежных с ней вершин, т. е. вершин, отличающихся от нее только одной координатой. Поскольку в кар- те Карно каждая ячейка может иметь не более четырех ячеек, соседних по строке или столбцу, для представления точек, отличающихся только 00 . . . 0 00 . . . 1 . . . x 1 . . . x k . . . 10 . . . 0 00 . . . 0 · · · 00 . . . 1 · · · . . . x k+1 . . . x k · · · · · · · · · · · · . . . 10 . . . 0 · · · Рис. 6.5 6.7. КАРТЫ КАРНО 199 a 00 01 11 10 1 0 x 3 x 1 x 2 x 3 x 2 x 1 c b x 1 x 2 x 3 x 4 g f e d x 1 x 2 x 3 x 4 x 4 а б Рис. 6.6 на одну координату, необходимо использовать и более удаленные ячейки. Например, точки b и c на рис. 6.6б отличаются только значением перемен- ной x 3 , т. е. являются смежными. Булева функция может быть представлена на карте Карно выделени- ем 1-ячеек (т. е. ячеек, в которых функция принимает значение, равное 1). Подразумевается, что необозначенные ячейки соответствуют 0-точкам. На рис. 6.7 изображена карта, представляющая булеву функцию f (x, y, z), для которой f (0, 0, 0) = f (1, 1, 0) = f (1, 1, 1) = f (1, 0, 1) = 0, f (0, 1, 0) = f (1, 0, 0) = f (0, 0, 1) = f (0, 1, 1) = 1. x 1 x 2 x 3 1 1 1 1 Рис. 6.7 Для построения импликант берутся всевозмож- ные наборы 1-ячеек, образующих вершины некото- рого k-куба (т. е. 2 k точек таких, что соседние отли- чаются ровно одной координатой и при этом неко- торые n − k координат неподвижны: остаются неиз- менными для всех этих точек). Неподвижные коор- динаты образуют набор (δ 1 , . . . , δ n−k ), и требуемая импликанта имеет вид x δ 1 |