Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
Фактор-алгебра F n /∼ изоморфна алгебре булевых функ- ций B n . Доказательство. Искомый изоморфизм ξ: F n /∼ ∼ → B n определяет- ся по следующему правилу: классу эквивалентности ∼ (ϕ) сопоставляется функция f ϕ , имеющая таблицу истинности произвольной формулы из мно- жества ∼ (ϕ). Поскольку разным классам эквивалентности соответствуют различные таблицы истинности, отображение ξ инъективно, а так как для любой булевой функции f из B n найдется формула ϕ ∈ Φ n , представляющая функцию f , то отображение ξ сюръективно. Сохранение операций ∧, ∨, , 0, 1 при отображении ξ проверяется непосредственно. ¤ По теореме о функциональной полноте каждой функции f ∈ B n , не яв- ляющейся константой 0, соответствует некоторая СДНФ ψ, принадлежащая классу ∼ (ϕ) = ξ −1 (f ) формул, представляющих функцию f . Возникает за- дача нахождения в классе ∼ (ϕ) дизъюнктивной нормальной формы, имею- щей наиболее простое строение. 198 Глава 6. АЛГЕБРА ЛОГИКИ § 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, представима в виде сокращенной ДНФ. ¤ 6.6. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ДНФ 199 В примере 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. ¤ 200 Глава 6. АЛГЕБРА ЛОГИКИ На практике при выполнении операций неполного склеивания на каж- дом этапе можно не писать члены, участвующие в этих операциях, а пи- сать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие ни в каком склеивании. Пример 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. В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для на- хождения минимальных конъюнктивных нормальных форм (МКНФ). 6.7. КАРТЫ КАРНО 201 § 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 202 Глава 6. АЛГЕБРА ЛОГИКИ 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 i 1 . . . x δ n−k i n−k , где x j — переменная, соответствующая значению δ j Пример 6.7.1. Точки b и c на рис. 6.6б лежат в 1-кубе, который опре- деляет конъюнкт x 1 x 2 x 4 . Точки {d, e, f, g} образуют 2-куб, представляющий импликанту x 1 x 4 . ¤ Определение простых импликант функции сводится к нахождению всех k-кубов, которые не содержатся в кубах более высокого порядка. 6.7. КАРТЫ КАРНО 203 x 1 x 2 x 3 x 4 1 1 1 1 1 1 1 1 1 ' & $ % ³ ´ ¶ ³ µ ´ ¶ µ ³ ´ ¶ µ ³ ´ ¶ µ ³ ´ ¶ µ ³ ´ ¶ µ Рис. 6.8 Пример 6.7.2. Простые импликанты для карты Карно, приведенной на рис. 6.7, равны x 1 x 2 , x 1 x 2 x 3 , x 1 x 3 Пример 6.7.3. На рис. 6.8 показана карта Карно, простые импликанты которой имеют вид x 2 x 3 x 4 , x 1 x 2 x 3 , x 1 x 3 x 4 , x 1 x 2 x 4 , x 2 x 3 x 4 , x 1 x 2 x 4 , x 1 x 3 . Заме- тим, что импликанты x 1 x 2 x 3 , x 1 x 2 x 3 , x 1 x 3 x 4 и x 1 x 3 x 4 не являются простыми, так как образуемые ими 1-кубы содержатся в 2-кубе x 1 x 3 . ¤ После нахождения простых импликант задача по- x 1 x 2 x 3 – 1 – – 1 Рис. 6.9 строения минимальной ДНФ сводится к изучению матрицы Квайна, как показано в § 6.6. При нагляд- ном размещении простых импликант в карте Кар- но удается непосредственно находить минимальную ДНФ, выбирая те простые импликанты, которые по- крывают все единицы и имеют наименьшее возмож- ное число вхождений переменных. Так, минималь- ной ДНФ для функции, изображенной на рис. 6.8, является формула x 2 x 3 x 4 ∨ x 1 x 3 x 4 ∨ x 1 x 2 x 4 ∨ x 1 x 3 Карты Карно применимы и для не всюду определенных функций. В этом случае выделяются максимальные k-кубы, покрывающие ненулевые ячейки и содержащие хотя бы одну единицу. Пример 6.7.4. На рис. 6.9 представлена карта Карно для частичной функции f , зависящей от трех переменных x 1 , x 2 , x 3 . Сокращенная ДНФ имеет вид x 2 x 3 ∨ x 1 x 3 ∨ x 1 x 2 ∨ x 2 x 3 , а МДНФ — x 2 x 3 ∨ x 1 x 3 ∨ x 2 x 3 или x 2 x 3 ∨ x 1 x 2 ∨ x 2 x 3 . ¤ 204 Глава 6. АЛГЕБРА ЛОГИКИ § 6.8. Принцип двойственности для булевых функций В § 2.6 мы говорили о двойственности в классе булевых алгебр, кото- рая проявляется в том, что на множестве B со структурой булевой алгеб- ры B можно ввести структуру двойственной алгебры B + , в которой роль операции ∧ играет ∨, роль операции ∨ — ∧, а в качестве нуля (единицы) используется 1 (соответственно 0). При этом между алгебрами B и B + име- ется изоморфизм ϕ: x 7→ x. В этом параграфе мы рассмотрим соответствие булевых функций при изоморфизме ϕ. Функция f + (x 1 , . . . , x n ) называется двойственной по отношению к функ- ции f (x 1 , . . . , x n ), если f + (x 1 , . . . , x n ) = f (x 1 , . . . , x n ). Двойственная функция получается из исходной при замене значений всех переменных, а также значений функции на противоположные, т. е. в таблице истинности нужно заменить 0 на 1, а 1 на 0. Пример 6.8.1. Двойственной к функции x ∧ y является функция, соот- ветствующая формуле ¬(x ∧ y), т. е. ¬¬(x ∨ y) или x ∨ y: (x ∧ y) + = x ∨ y. Аналогично (x ∨ y) + = x ∧ y, (x) + = x. ¤ Принцип двойственности. Если f (x 1 , . . . , x n ) = g(h 1 (x 1 , . . . , x n ), . . . , h m (x 1 , . . . , x n )), то f + (x 1 , . . . , x n ) = g + (h + 1 (x 1 , . . . , x n ), . . . , h + m (x 1 , . . . , x n )). Таким образом, функция, двойственная суперпозиции функций, есть со- ответствующая суперпозиция двойственных функций. Принцип двойственности удобен при нахождении двойственных функ- ций, представленных формулами, содержащими лишь конъюнкции, дизъ- юнкции и отрицания. В этом случае в исходной формуле конъюнкции заме- няются на дизъюнкции, а дизъюнкции — на конъюнкции. Таким образом, ДНФ соответствует КНФ, КНФ — ДНФ, СДНФ — СКНФ, СКНФ — СДНФ. Пример 6.8.2. ( |