Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
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-кубов, которые не содержатся в кубах более высокого порядка. 200 Глава 6. АЛГЕБРА ЛОГИКИ 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 . ¤ 6.8. ПРИНЦИП ДВОЙСТВЕННОСТИ ДЛЯ БУЛЕВЫХ ФУНКЦИЙ 201 § 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. (xy ∨ x z ∨ xyz) + = (x ∨ y) ∧ (x ∨ z) ∧ (x ∨ y ∨ z). ¤ Отметим, что если формула ϕ эквивалентна формуле ψ: ϕ ∼ ψ, то ϕ + ∼ ψ + Функция f (x 1 , . . . , x n ) называется самодвойственной, если f + (x 1 , . . . , x n ) = f (x 1 , . . . , x n ). 202 Глава 6. АЛГЕБРА ЛОГИКИ Пример 6.8.3. Покажем, что формула ϕ = xy ∨ xz ∨ yz задает самодвой- ственную функцию. С этой целью убедимся, что на всех противоположных наборах значений переменных (δ 1 , δ 2 , δ 3 ) и (1 − δ 1 , 1 − δ 2 , 1 − δ 3 ) формула принимает противо- положные значения. Действительно, составив таблицу истинности 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 ϕ 0 0 0 1 0 1 1 1 , получаем ϕ(0, 0, 0) = ϕ(1, 1, 1), ϕ(0, 0, 1) = ϕ(1, 1, 0), ϕ(0, 1, 0) = ϕ(1, 0, 1), ϕ(0, 1, 1) = ϕ(1, 0, 0). ¤ § 6.9. Полные системы булевых функций Как мы уже знаем из теоремы о функциональной полноте, любая булева функция представима в виде формулы, содержащей лишь операции ∧, ∨, ¬, т. е. в виде терма сигнатуры {∧, ∨, ¬}. В этом параграфе будет дано описание сигнатур, позволяющих получать любые булевы функции. Система булевых функций F = {f 1 , f 2 , . . . , f n } называется полной, если любая булева функция представима в виде терма сигнатуры {f 1 , f 2 , . . . , f n }, т. е. в виде суперпозиций функций из F. Из сказанного выше ясно, что система {∧, ∨, ¬} является полной. Ответ на вопрос о полноте произвольной системы F дает теорема Поста, форму- лируемая ниже. Введем определение классов Поста. 1. Класс P 0 — это класс булевых функций, сохраняющих нуль, т. е. функ- ций f (x 1 , . . . , x n ), для которых f (0, 0, . . . , 0) = 0: P 0 = {f | f (0, 0, . . . , 0) = 0}. 2. Класс P 1 — это класс булевых функций, сохраняющих единицу, т. е. функций f (x 1 , . . . , x n ), для которых f (1, 1, . . ., 1) = 1: P 1 = {f | f (1, 1, . . . , 1) = 1}. 3. Класс S — это класс самодвойственных функций: S = {f | f — самодвойственная функция}. 6.9. ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ 203 4. Класс M — это класс монотонных функций. Булева функ- ция f (x 1 , . . . , x n ) называется монотонной, если для любых наборов нулей и единиц (α 1 , . . . , α n ) и (β 1 , . . . , β n ) из условий α 1 6 β 1 , . . ., α n 6 β n следует f (α 1 , . . . , α n ) 6 f (β 1 , . . . , β n ). Таким образом, M = {f | f — монотонная функция}. 5. Класс L — это класс линейных функций. Булева функция f (x 1 , . . . , x n ) называется линейной, если в булевом кольце h{0, 1}; ⊕, ¯i функция f пред- ставима в виде f (x 1 , . . . , x n ) = c 0 ⊕ c 1 x 1 ⊕ c 2 x 2 ⊕ . . . ⊕ c n x n , где c 0 , c 1 , c 2 , . . ., c n ∈ {0, 1}. Коэффициенты c 0 , c 1 , . . ., c n линейной функции определяются из следу- ющих соотношений: c 0 = f (0, 0, . . . , 0), c 0 ⊕ c 1 = f (1, 0, . . . , 0), c 0 ⊕ c 2 = f (0, 1, . . . , 0), . . . , c 0 ⊕ c n = f (0, 0, . . . , 0, 1), т. е. c 0 = f (0, 0, . . . , 0), c 1 = c 0 ⊕ f (1, 0, . . . , 0) , . . . , c n = c 0 ⊕ f (0, 0, . . . , 1). (6.1) Таким образом, проверка линейности сводится к нахождению коэффи- циентов c i по формулам (6.1) и сопоставлению таблиц истинности данной формулы f (x 1 , . . . , x n ) и полученной формулы c 0 ⊕ c 1 x 1 ⊕ . . . ⊕ c n x n Пример 6.9.1. Проверим, является ли линейной функция x ∨ y. Имеем c 0 = 0 ∨ 0 = 0, c 1 = 0 ⊕ (1 ∨ 0) = 1, c 2 = 0 ⊕ (0 ∨ 1) = 1. Таким образом, c 0 ⊕ c 1 x ⊕ c 2 y = x ⊕ y. Сопоставляя таблицы истинности формул x ∨ y и x ⊕ y, убеждаемся, что они не совпадают. Вывод: функция x ∨ y нелинейна. ¤ Линейность функции можно также определить с помощью следующей теоремы. Теорема 6.9.1 (теорема Жегалкина). Всякая булева функция f (x 1 , . . . , x n ) представима полиномом Жегалкина, т. е. в виде f (x 1 , . . . , x n ) = L (i 1 ,...,i k ) x i 1 x i 2 . . . x i k ⊕ c, где в каждом наборе (i 1 , . . . , i k ) все i j различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых. 204 Глава 6. АЛГЕБРА ЛОГИКИ Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения различных переменных. Таким образом, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина. Для получения полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы булевой алгебры, аксиомы булева кольца h{0, 1}; ⊕, ¯i и равенства, выражающие операции ∧, ∨ и ¬ через операции этого булева кольца: x∨y = x⊕y ⊕xy, x(y ⊕z) = xy ⊕xz, x = x⊕1, x⊕0 = x, x ⊕ x = 1, xx = 0 и т. д. Пример 6.9.2. Определим, будет ли линейной функция f (x, y, z) = x yz∨ ∨ xyz ∨ xy z. Имеем f (x, y, z) = (xyz ⊕xyz ⊕xyzxyz)∨xy z = (xyz⊕ xyz)∨xy z = xyz⊕ ⊕xyz ⊕ xy z ⊕ (x yz ⊕ xyz)xy z = x yz ⊕ xyz⊕ xy z⊕ 0 = xz(y ⊕ y) ⊕ xy z = = xz · 1 ⊕ xy z = (x ⊕ 1)z ⊕ x(y ⊕ 1)(z ⊕ 1) = xz⊕ 1· z⊕ xyz ⊕ xz ⊕ xy ⊕ x = = x ⊕ z ⊕ xy ⊕ xyz. Полученный полином Жегалкина является нелинейным, и, следовательно, функция f также нелинейна. ¤ Заметим, что если в эквивалентности ϕ ∨ ψ ∼ ϕ ⊕ ψ ⊕ ϕ · ψ формулы ϕ и ψ являются различными конституентами единицы, то их произведение ϕ·ψ равно 0, и тогда ϕ ∨ ψ ∼ ϕ ⊕ ψ. Следовательно, для получения полинома Жегалкина из СДНФ можно сразу заменить ∨ на ⊕. Отметим, что каждый класс Поста замкнут относительно операций заме- ны переменных и суперпозиции, т. е. с помощью этих операций из функций, принадлежащих данному классу, можно получить только функции из этого же класса. Пример 6.9.3. Определим, к каким классам Поста относится булева функция f (x, y) = x | y. Так как f (0, 0) = 1, а f (1, 1) = 0, то f (x, y) / ∈ P 0 и f (x, y) / ∈ P 1 . Поскольку f (1, 0) 6= f (0, 1), то f (x, y) / ∈ S. Так как f (0, 0) > f (1, 1), то f (x, y) / ∈ M. Полином Жегалкина для функции f (x, y) = xy имеет вид 1 ⊕ xy в силу равенства x = 1 ⊕ x. Поэтому данная функция нелинейна. Таким образом, можно составить следующую таблицу Функция Классы P 0 P 1 S M L x | y нет нет нет нет нет 6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ 205 Теорема 6.9.2 (теорема Поста). Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P 0 , P 1 , S, M, L в системе F найдется функция, не принадлежащая этому классу. ¤ В силу теоремы Поста функция x | y образует полную систему, т. е. с помощью штриха Шеффера можно получить любую булеву функцию. В частности, x ∼ x | x, x ∧ y ∼ ¬¬(x ∧ y) ∼ ¬(x | y) ∼ (x | y) | (x | y). Система булевых функций F называется базисом, если она полна, а для любой функции f ∈ F система F \ {f } неполна. Теорема 6.9.3. Каждый базис содержит не более четырех булевых функций. Доказательство. Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f — функция из F, не принадлежащая клас- су P 0 . Тогда, с одной стороны, f (0, 0, . . . , 0) = 1, а с другой — из f ∈ P 1 следует, что f (1, 1, . . . , 1) = 1. Это означает, что f не является самодвой- ственной функцией, что противоречит предположению. ¤ Пример 6.9.4. Следующие системы булевых функций являются бази- сами: {∧, ¬}, {∨, ¬}, {→, ¬}, {↓}, {|}, {↔, ∨, 0}, {⊕, ∧, ↔}. ¤ Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из ба- зисных схем с помощью суперпозиций можно составить схему, соответству- ющую любой булевой функции. § 6.10. Функциональная декомпозиция 1. Определение и примеры Булева функция f (x 1 , . . ., x n ) называется разложимой, если она может быть представлена в виде суперпозиции функций g 1 , g 2 , . . . , g k (k < n) и F , каждая из которых имеет менее n переменных: f (x 1 , x 2 , . . ., x n ) = = F (g 1 , . . . , g k ). При этом функция f может быть реализована с помощью устройств, соответствующих функциям g 1 , g 2 , . . ., g k и F , как показано на рис. 6.10. Разложение функции f в виде суперпозиции g 1 , g 2 , . . ., g k и F 206 Глава 6. АЛГЕБРА ЛОГИКИ - • - • x 1 x n • - - • - - g 1 g 2 g k - - - F - f Рис. 6.10 называется декомпозицией функции f , а соответствующая схема, показан- ная на рис. 6.10, — декомпозиционной реализацией функции f . В дальнейшем будем использовать следующие обозначения логических устройств. Устройство, соответствующее функции x, будем называть ин- вертором и обозначать, как показано на рис. 6.11а, устройство, соответ- ствующее функции f (x 1 , . . . , x i−1 , x i , x i+1 , . . . , x n ), обозначим, как показано на рис. 6.11б, а устройство, соответствующее функции f (x 1 , x 2 , . . . , x n ), — на рис. 6.11в. Пример 6.10.1. На рис. 6.12 показана декомпозиционная реализация функции f (x 1 , x 2 , x 3 , x 4 ) = x 1 x 3 ∨ (x 2 ⊕ x 3 )x 4 ∨ x 1 x 4 , где g 1 = x 1 x 3 , g 2 = = (x 2 ⊕ x 3 )x 4 , g 3 = x 1 x 4 , F (y 1 , y 2 , y 3 ) = y 1 ∨ y 2 ∨ y 3 . ¤ x ©© © HH H e x e f x n x i+1 x i x i−1 x 1 f e x 1 x 2 x n а б в Рис. 6.11 6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ 207 d & ⊕ • • • x 1 x 3 x 2 x 4 d d & & W - f g 1 g 2 g 3 F Рис. 6.12 Пусть X = {x 1 , x 2 , . . . , x n } — множество входных переменных для функ- ции f (X) = F (g 1 (A 1 ), g 2 (A 2 ), . . . , g k (A k )), где A i — множества входных пере- менных, образующие разбиение множества X, т. е. A i 6= ∅, A i ∩ A j = ∅ для i 6= j и A 1 ∪ A 2 ∪ . . . ∪ A k = X. Тогда декомпозиция функции f называется дизъюнктивной. Недизъюнктивные декомпозиции называются нондизъюнк- тивными. Пример 6.10.2. На рис. 6.13 изображена реализация нондизъюнктив- ной декомпозиции f (x 1 , x 2 , x 3 , x 4 , x 5 ) = F (g 1 (x 1 , x 2 , x 3 ), g 2 (x 3 , x 4 , x 5 )). Здесь множества A 1 = {x 1 , x 2 , x 3 } и A 2 = {x 3 , x 4 , x 5 } не образуют разбиение мно- жества X = {x 1 , x 2 , x 3 , x 4 , x 5 }, поскольку A 1 ∩ A 2 6= ∅. ¤ • x 5 x 4 x 3 x 2 x 1 g 2 g 1 - F f Рис. 6.13 208 Глава 6. АЛГЕБРА ЛОГИКИ - x 5 x 4 x 3 x 2 x 1 F f g Рис. 6.14 2. Простая дизъюнктивная декомпозиция Дизъюнктивная декомпозиция функции f (x 1 , x 2 , . . . , x n ) вида f (x 1 , x 2 , . . . , x n ) = F (g(A 1 ), A 2 ) называется простой. Пример 6.10.3. На рис. 6.14 изображена реализация простой дизъюнк- тивной декомпозиции f (x 1 , x 2 , x 3 , x 4 , x 5 ) = F (g(x 1 , x 2 , x 3 ), x 4 , x 5 ). ¤ Чтобы определить свойства булевых функций, ко- · · · · · · A 1 A 2 Рис. 6.15 торые позволяют получать простые дизъюнктивные де- композиции в виде F (g(A 1 ), A 2 ), рассмотрим карту Кар- но функции f (рис. 6.15), где строки соответствуют пере- менным множества A 2 , а столбцы — переменным множе- ства A 1 (например, на рис. 6.6а изображена карта Карно с A 1 = {x 1 , x 2 } и A 2 = {x 3 }). Построенная таким образом карта Карно называется картой декомпозиции для пары (A 1 , A 2 ). Теорема 6.10.1. Булева функция f (x 1 , x 2 , . . . , x n ) тогда и только тогда имеет простую дизъюнктивную декомпозицию в форме f (X) = = F (g(A 1 ), A 2 ), когда карта декомпозиции функции f для пары (A 1 , A 2 ) содержит не более двух различных столбцов. ¤ Пример 6.10.4. Рассмотрим карту декомпозиции функции f (x 1 , x 2 , x 3 , x 4 , x 5 ), показанную на рис. 6.16. Так как имеются только два различных столбца, то существует простая дизъюнктивная декомпозиция функции f в форме f = F (g(x 1 , x 2 , x 3 ), x 4 , x 5 ). Для нахождения функции g(x 1 , x 2 , x 3 ) 6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ 209 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 x 4 x 2 x 5 x 3 x 3 x 1 Рис. 6.16 выберем строку карты, в ячейках которой содержатся как нули, так и едини- цы, например 4-ю строку (рис. 6.17). По выбранной строке составим функ- цию g с соответствующей таблицей истинности, показанной на рис. 6.18: g = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 Приведя полученную формулу к минимальной ДНФ, получаем g = = x 1 x 2 x 3 ∨ x 1 x 2 . Теперь для нахождения функции F заметим, что по выбору строки карты декомпозиции имеем g = 0 для столбца (1 1 1 0) T и g = 1 для столбца (1 0 0 1) T . Таким образом, мы получаем карту Карно функции F от переменных g, x 4 , x 5 в виде, изображенном на рис. 6.19. По карте Карно находим минимальную ДНФ функции F (g, x 4 , x 5 ) = gx 5 ∨ x 4 x 5 ∨ gx 5 . ¤ Если все столбцы карты декомпозиции идентичны, то функция не за- висит от переменных множества A 1 и декомпозиция является тривиальной. Если карта содержит два различных столбца, но комбинации цифр в них содержат либо все нули, либо все единицы, то функция не зависит от пере- менных множества A 2 1 0 0 0 1 1 0 0 x 2 x 3 x 3 x 1 Рис. 6.17 210 Глава 6. АЛГЕБРА ЛОГИКИ x 1 0 0 0 0 1 1 1 1 x 2 0 0 1 1 0 0 1 1 x 3 0 1 0 1 0 1 0 1 g 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 0 x 4 x 5 g Рис. 6.18 Рис. 6.19 3. Сложные дизъюнктивные декомпозиции Дизъюнктивная декомпозиция, не являющаяся простой, называется сложной. Рассмотрим два вида сложных декомпозиций: итеративную и мно- жественную. Итеративная функциональная декомпозиция представлена в следующей общей форме: f (X) = F (g m (. . . g 3 (g 2 (g 1 (A 1 ), A 2 ), A 3 ), . . . , A m ) (6.2) и основана на повторении простой дизъюнктивной декомпозиции по пере- менным A 1 , A 2 , . . ., A m Множественная функциональная декомпозиция имеет вид f (X) = F (g 1 (A 1 ), g 2 (A 2 ), . . . , g m (A m )). (6.3) Связь между сложными и простыми дизъюнктивными декомпозициями дается следующими теоремами. Теорема 6.10.2. Для данной булевой функции f (X) тогда и только то- гда существует итеративная дизъюнктивная декомпозиция вида (6.2), ко- гда существует простая дизъюнктивная декомпозиция вида f (X) = F m (g 0 m (A 1 , A 2 , . . . , A m−1 ), A m ), простая дизъюнктивная декомпозиция функции g 0 m g 0 m = F m−1 (g 0 m−1 (A 1 , A 2 , . . . , A m−2 ), A m−1 ), простая дизъюнктивная декомпозиция функции g 0 m−1 и т. д. до m = 1. При этом F = F m , g m = F m−1 , g m−1 = F m−2 , . . . , g 2 = F 1 , g 1 = g 0 1 . ¤ 6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ 211 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 x 4 x 2 x 3 x 3 x 1 1 1 1 1 1 1 0 0 x 3 x 2 x 1 а б Рис. 6.20 Теорема 6.10.3. Для данной булевой функции f (X) тогда и только то- гда существует множественная дизъюнктивная декомпозиция вида (6.3), когда существуют простые дизъюнктивные декомпозиции вида f (X) = F 1 (g 1 (A 1 ), A 2 , A 3 , . . . , A m ), f (X) = F 2 (g 2 (A 2 ), A 1 , A 3 , . . . , A m ), f (X) = F m (g m (A m ), A 1 , A 2 , . . . , A m−1 ). ¤ Пример 6.10.5. Пусть f = x 1 x 2 x 3 x 4 ∨x 1 x 2 x 3 x 4 ∨x 3 x 4 ∨ ∨ x 1 x 2 x 4 ∨x 1 x 2 x 4 Из карты декомпозиции, показанной на рис. 6.20а, получим простую дизъюнктивную декомпозицию f = F (g 1 (x 1 , x 2 , x 3 ), x 4 ), где g 1 = x 3 ∨ x 1 x 2 ∨ ∨x 1 x 2 и F = g 1 x 4 ∨ g 1 x 4 1 1 1 1 1 1 x 1 x 2 x 3 x 4 Рис. 6.21 Теперь рассмотрим функцию g 1 . Из карты, приведенной на рис. 6.20б, получим простую дизъ- юнктивную декомпозицию g 1 = F 1 (g 2 (x 1 , x 2 ), x 3 ), где g 2 = x 1 x 2 ∨ x 1 x 2 и F 1 = g 2 ∨ x 3 Эти две простые дизъюнктивные декомпозиции дают вместе итеративную дизъюнктивную декомпо- зицию f = F (F 1 (g 2 (x 1 , x 2 ), x 3 ), x 4 ). ¤ Пример 6.10.6. Пусть f = x 1 x 2 x 3 ∨ x 1 x 2 x 4 ∨ ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 4 . Карта декомпозиции, показанная на рис. 6.21, имеет две различные строки и два различных столбца и, следовательно, дает следую- щие две декомпозиции функции f : f = F 1 (g 1 (x 1 , x 2 ), x 3 , x 4 ), где g 1 (x 1 , x 2 ) = x 1 x 2 ∨ x 1 x 2 , F 1 (g 1 , x 3 , x 4 ) = g 1 x 3 ∨ g 1 x 4 , f = F 2 (g 2 (x 3 , x 4 ), x 1 , x 2 ), 212 Глава 6. АЛГЕБРА ЛОГИКИ где g 2 = x 3 ∨x 4 , F 2 = g 2 x 1 x 2 ∨g 2 x 1 x 2 . В соответствии с теоремой 6.10.3 су- ществует множественная дизъюнктивная декомпозиция f = F (g 1 (x 1 , x 2 ), g 2 (x 3 , x 4 )). Для нахождения функции F составим ее таблицу истинности, определя- емую всевозможными комбинациями значений g 1 и g 2 и соответствующими значениями функции f : g 1 (x 1 , x 2 ) g 2 (x 3 , x 4 ) F 0 0 0 0 1 0 1 0 0 1 1 1 Из таблицы истинности находим, что F = g 1 · g 2 . ¤ § 6.11. Логические сети 1. Определение и реализация булевых функций Мультиграф G = hM, U, Ri, в котором выделено k вершин (полюсов), на- зывается k-полюсной сетью. Сеть G, задаваемая неориентированным муль- тиграфом с k полюсами, в которой каждое ребро помечено буквой из алфа- вита X = {x 1 , x 2 , . . . , x n , x 1 , x 2 , . . . , x n }, называется k-полюсной контактной схемой. На рис. 6.22 приведен пример контактной схемы с двумя полюса- ми a 1 и a 6 • • • • • • HH HH HH ©© ©© ©© ````` ````` ````` Q Q Q Q Q Q Q µ´ ¶³ µ´ ¶³ a 1 a 2 a 3 a 4 a 5 a 6 x 1 x 2 x 3 x 1 x 2 x 1 x 2 x 3 x 3 Рис. 6.22 6.11. ЛОГИЧЕСКИЕ СЕТИ 213 Если в (k + 1)-полюсной схеме S один полюс выделен (он называется входным), а остальные полюса (выходные) равноправны, то S называется (1, k)-полюсником. Таким образом, если в приведенной на рис. 6.22 двухпо- люсной схеме рассматривать, например, полюс a 1 как входной, а полюс a 6 как выходной, то получаем (1, 1)-полюсник . Ребра контактной схемы называются контактами. Контакт, соответ- ствующий логической переменной x i , называется замыкающим и обозна- чается через ∅ −c b− ∅ . Замыкающий контакт пропускает ток при x i = 1. Кон- такт, соответствующий литере x i , называется размыкающим и обозначается как ∅ −c b − ∅ . Через него ток проходит при x i = 0. Таким образом, значение 1 интерпретируется как состояние переключателя “ток проходит”, а 0 — “ток не проходит”. Функции x i ∧ x j соответствует последовательное соединение контактов ∅ −c b−c b− ∅ , а функции x i ∨ x j — параллельное соединение кон- тактов a− c b − − c b −` Нетрудно заметить, что схеме, показанной на рис. 6.22, соответствуют электрическая схема, приведенная на рис. 6.23, а также схема контактов, изображенная на рис. 6.24. На последнем рисунке показаны контакты, зави- сящие от значений переменных x 1 , x 2 , x 3 , а также схема соединений контак- тов. Пусть a, b — полюса контактной схемы Σ, [a; b] — некоторая цепь из a в b, K [a;b] — конъюнкция литер, приписанных ребрам цепи [a; b]. Функция f a,b (X), определяемая формулой f a,b (X) = W [a;b] K [a;b] , в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса a и b, назы- вается функцией проводимости между полюсами a и b схемы Σ. Говорят, • • x 1 x 2 x 1 • • x 1 x 2 x 2 • x 3 - x 3 x 3 • Рис. 6.23 214 Глава 6. АЛГЕБРА ЛОГИКИ • • • ³³ ³³ • • • ³³ ³³ • a 1 a 6 x 1 x 2 x 3 Рис. 6.24 что функция g(X) реализуется (1, k)-полюсником, если существует такой выходной полюс b i , что f a,b i (X) = g(X), где a — входной полюс. (1, 1)- Полюсники называются эквивалентными, если они реализуют одну и ту же булеву функцию. Сложностью (1, 1)-полюсника называется число контак- тов. (1, 1)-полюсник, имеющий наименьшую сложность среди эквивалент- ных ему схем, называется минимальным. Сложность минимального (1, 1)- полюсника, реализующего функцию f , называется сложностью функции f в классе (1, 1)-полюсников и обозначается через L π (f ). Заметим, что задача нахождения минимального (1, 1)-полюсника среди эквивалентных данному (1, 1)-полюснику Σ равносильна нахождению сре- ди функций, реализуемых схемой Σ, функции, имеющей наименьшее чис- ло вхождений переменных. Действительно, функцию, реализуемую (1, 1)- полюсником, нетрудно представить в виде формулы, которая строится из ли- тер в соответствии с контактной схемой и имеет ровно столько вхожде- ний переменных, сколько контактов имеет схема. Например, изображенной на рис. 6.23 схеме соответствует булева функция f (x 1 , x 2 , x 3 ) = (x 1 ∨ x 2 ) · ((x 1 ∨ x 2 ) · x 3 ∨ x 3 ) ∨ x 1 x 2 x 3 . (6.4) Таким образом, задача нахождения минимального (1, 1)-полюсника сводится к минимизации соответствующей булевой функции. Эффективное уменьшение числа контактов достигается с помощью на- хождения минимальной ДНФ булевой функции. 6.11. ЛОГИЧЕСКИЕ СЕТИ 215 • x 1 x 2 x 1 x 2 x 3 x 3 x 3 - • • x 1 x 2 x 1 x 2 • x 3 x 3 - • а б Рис. 6.25 Найдем минимальную ДНФ функции (6.4), реализуемой схемой рис. 6.23. Придавая логическим переменным x 1 , x 2 , x 3 всевозможные значения, по схе- ме или формуле (6.4) получаем таблицу истинности: x 1 0 0 0 0 1 1 1 1 x 2 0 0 1 1 0 0 1 1 x 3 0 1 0 1 0 1 0 1 f 1 0 1 0 1 0 0 1 , по которой определим совершенную ДНФ: x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 Используя один из методов нахождения минимальной ДНФ, получаем фор- мулу x 1 x 3 ∨ x 2 x 3 ∨ x 1 x 2 x 3 , эквивалентную формуле (6.4) и соответствующую схеме, состоящей из семи контактов (рис. 6.25а). Отметим, что схема, изображенная на рис. 6.25а, допускает упрощение, соответствующее формуле (x 1 ∨ x 2 )x 3 ∨ x 1 x 2 x 3 , которое приведено на рис. 6.25б и является минимальной схемой. Сложность минимальной схемы рав- на 6: L π (f ) = 6. 2. Схемы из функциональных элементов Ориентированная бесконтурная сеть, в которой полюса делятся на вход- ные (входы) и выходные (выходы), называется схемой из функциональных элементов. Входные полюса помечаются символами переменных, а каждая вершина, отличная от входного полюса, — некоторым функциональным символом. При этом должны выполняться следующие условия: • если a — входной полюс, то полустепень захода вершины a равна нулю: deg − (a) = 0; • если вершина a не является полюсом и помечена n-местным функцио- нальным символом f , то deg − (a) = n и дуги, входящие в a, перенумерованы от 1 до n. Функциональным элементом называется всякий подмультиграф схемы, состоящий из невходного полюса a, помеченного соответствующим симво- лом f , и вершины, из которых исходят дуги в вершину a. 216 Глава 6. АЛГЕБРА ЛОГИКИ Пример 6.11.1. На рис. 6.26а представлена схема из функциональ- ных элементов. Здесь входные символы помечены символами перемен- ных x 1 , x 2 , x 3 ; ¬ — одноместный функциональный символ, соответствующий операции отрицания; & — двухместный символ, соответствующий операции конъюнкции; f 3 — некоторый двухместный символ; f 1 , f 2 , f 4 — некоторые трехместные символы. Вершины, помеченные символами f 1 , f 3 и f 4 , являются выходными полюсами. Им соответствуют термы: f 1 (x 1 , x 2 , x 3 ), f 3 (x 1 x 2 , f 1 (x 1 , x 2 , x 3 )), f 4 (f 3 (x 1 x 2 , f 1 (x 1 , x 2 , x 3 ), x 3 ), x 3 , f 2 (f 1 (x 1 , x 2 , x 3 ), f 1 (x 1 , x 2 , x 3 ), x 3 )). На рис. 6.26б изображен функциональный элемент, определяемый верши- ной, помеченной символом f 4 . Ему соответствует устройство, показанное на рис. 6.26в. ¤ В примере 6.11.1 продемонстрировано, что каждый вывод схемы порож- дает некоторый терм. Говорят, что функция f реализуется схемой Σ, если существует такой выход a схемы Σ, что функция f a , соответствующая терму выхода a, экви- валентна функции f . Схемы из функциональных элементов с одним выходом, у которых вход- ные полюса помечены символами x 1 , x 2 , . . ., x n , а вершины, отличные от вход- ных полюсов, — символами ∨, &, ¬, называются X n -функциональными схе- мами. Сложностью схемы из функциональных элементов называется чис- ло ее вершин, отличных от входных полюсов. X n -Функциональная схема Σ, •³ ³³ ³³ ³³ ³ ³ 1• ½ ½ ½ ½ ½½ > • ¢ ¢ ¢ ¢ ¢¢¸ • •H HH j HH H j Á • ©© ©© ©© *• ? • - H HH j•H HH j A A A A AAU U - x 3 x 2 x 1 f 4 f 3 & ¬ f 1 f 2 1 1 1 1 2 3 3 3 2 2 1 2 1 2 • ¡ ¡ ¡ µ - @ @ @ R f 4 f 4 а б в Рис. 6.26 6.11. ЛОГИЧЕСКИЕ СЕТИ 217 • • • • • • ¬ ¬ ¬ • HH H j HH H j ©© © * • • ©© ©© ©© * HH HH HH HH HH H H j XXXX XXXX XXXX z -• -• ¡ ¡ ¡ µ m ∨ & & & ∨ x 3 x 2 x 1 Рис. 6.27 g = z J(y 1 ,y 2 ,y 3 )+1 z 1 z 2 · · · z 8 y 3 y 2 y 1 Рис. 6.28 реализующая функцию f , называется минимальной, если всякая другая X n - функциональная схема, реализующая f , имеет сложность, не меньшую, чем сложность схемы Σ. Сложность минимальной схемы, реализующей функ- цию f , называется сложностью функции f в классе схем из функциональ- ных элементов и обозначается через L(f ). Пример 6.11.2. Сложность функции f = (x 1 ∨ x 2 )x 3 ∨ x 1 x 2 x 3 совпадает со сложностью X 3 -функциональной схемы, изображенной на рис. 6.27, и рав- на 8: L(f ) = 8. ¤ 3. Мультиплексоры Мультиплексором 2 m каналов (MUX 2 m ) называется схема с m + 2 m вхо- дами y 1 , y 2 , . . ., y m , z 1 , z 2 , . . ., z 2 m и одним выходом g, в которой при y 1 = b 1 , . . . , y m = b m выход g принимает значение g = z J(b 1 ,...,b m )+1 , где J(b 1 , . . . , b m ) = 2 0 b 1 + 2 1 b 2 + . . . + 2 m−1 b m На рис. 6.28 показан мультиплексор MUX 8 218 Глава 6. АЛГЕБРА ЛОГИКИ z 1 z 2 z p g 1 g 2 g q Решетка элементов & (c ih ) d C CC ¤ ¤¤ d C CC ¤ ¤¤ · · · d C CC ¤ ¤¤ b ³ ³ P P b ³ ³ P P b ³ ³ P P f 1 f 2 f m b (( hh b (( hh b (( hh Решетка элементов & (a ih ) Решетка элементов & (b hj ) Рис. 6.29 Рис. 6.30 Пример 6.11.3. Если m = 3, y 1 = 1, y 2 = 0, y 3 = 1, то g = = z J(1,0,1)+1 = z 6 . ¤ С помощью мультиплексора MUX 2 m , придавая переменным z 1 , z 2 , . . ., z 2 m постоянные значения, можно реализовать любую булеву функцию f (y 1 , y 2 , . . . , y m ). 4. Программируемые логические матрицы Рассмотрим схему, состоящую из p входов z 1 , . . ., z p и q выходов g 1 , . . ., g q (рис. 6.29), в которой значения выходов определяются матрицей соедине- ний (c ih ), 1 6 i 6 p, 1 6 h 6 q, c ih ∈ {0, 1} по следующим правилам: g h = (z 1 ∨ c 1h ) · (z 2 ∨ c 2h ) · . . . · (z p ∨ c ph ). Таким образом, g h = z i 1 z i 2 . . . z i r , где c i 1 h = c i 2 h = . . . = c i r h = 1, а остальные c ih равны 0. Полученная схема называется решеткой c p входами и q выходами элементов &, которая определяется матрицей соединений (c ih ). Программируемой логической матрицей (ПЛМ) называется изображен- ная на рис. 6.30 схема, получающаяся соединением решетки A с 2n входа- ми и k выходами, определяемой матрицей соединений (a ih ), и решетки B с k входами и m выходами, определяемой матрицей соединений (b hj ). Опишем преобразования, которые происходят при прохождении через ПЛМ значений переменных x 1 , x 2 , . . ., x n . Поскольку к каждому входу x i 6.12. ПРОВЕРКА ТЕОРЕТИКО-МНОЖЕСТВЕННЫХ СООТНОШЕНИЙ 219 присоединен инвертор x i , на 2n входов решетки A подаются значения пере- менных x 1 , x 1 , x 2 , x 2 , . . . , x n , x n . После прохождения решетки A h-й выход принимает значение функции (x 1 ∨ a 1h )(x 1 ∨ a 2h ) . . . (x n ∨ a 2n−1,h )(x n ∨ a 2n,h ), а последующей операции инвертирования соответствует функция (x 1 ∨ a 1h )(x 1 ∨ a 2h ) . . . (x n ∨ a 2n−1,h )(x n ∨ a 2n,h ). Полученные k значений (1 6 h 6 k) подаются на входы решетки B, после прохождения которой на выходе j образуется значение функции k ^ h=1 ((x 1 ∨ a 1h )(x 1 ∨ a 2h ) . . . (x n ∨ a 2n−1,h )(x ∨ a 2n,h ) ∨ b hj ). В заключение после инвертирования по законам де Моргана на выходе j получаем значение функции f j = k _ h=1 b hj (x 1 ∨ a 1h )(x 1 ∨ a 2h ) . . . (x n ∨ a 2n−1,h )(x n ∨ a 2n,h ), j = 1, . . . , m. Функции f j соответствует дизъюнкция конъюнктов (определяемых форму- лами (x 1 ∨ a 1h )(x 1 ∨ a 2h ) . . . (x n ∨ a 2n−1,h )(x n ∨ a 2n,h )) таких, что b hj = 1. Таким образом, при соответствующем выборе матриц (a ih ) и (b hj ) можно одновременно реализовать m произвольных ДНФ, содержащих не более k различных конъюнктов от переменных x 1 , x 2 , . . ., x n § 6.12. Проверка теоретико-множественных соотношений с помощью алгебры логики Мы уже отмечали, что теоретико-множественным операциям ∪, ∩, , ⊕ соответствует операции ∨, ∧, , ⊕ на множестве формул. Заменяя теоретико- множественные выражения на формулы и анализируя эти формулы, можно свести исследование взаимоотношения теоретико-множественных выраже- ний к изучению взаимосвязи формул. Следующий пример демонстрирует, как происходит проверка теоретико- множественных соотношений с помощью алгебры логики. 220 Глава 6. АЛГЕБРА ЛОГИКИ Пример 6.12.1. С помощью алгебры логики проверим истинность соот- ношения (A ⊕ B) \ C = A ⊕ (B \ C) (6.5) для любых множеств A, B, C. Поставим в соответствие множествам A, B и C логические переменные x, y и z. В силу тождества A \ B = A ∩ B (см. пример 1.1.6) выражение (A⊕B)\C преобразуется в формулу ϕ (x⊕y)∧z, а выражение A⊕(B\C) — в формулу ψ 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 ϕ 0 0 1 0 1 0 0 0 ψ 0 0 1 0 1 1 0 1, убеждаемся, что ϕ 6∼ ψ: f ϕ (1, 0, 1) = 0, а f ψ (1, 0, 1) = 1. Тем самым соотно- шение (6.5) неверно. Для построения контрпримера, опровергающего равенство (6.5), восполь- зуемся различием значений функций f ϕ и f ψ на наборе (1, 0, 1). Считая, что 1 соответствует множествам, содержащим некоторый элемент a, а 0 — множеству, не содержащему этот элемент, положим A {a}, B ∅, C {a}. Имеем (A ⊕ B) \ C = A \ A = ∅, тогда как A ⊕ (B \ C) = A ⊕ ∅ = A 6= ∅. ¤ § 6.13. Логические задачи Аппарат алгебры логики позволяет решать так называемые “логические” задачи. При этом самым трудным моментом является построение “модели” задачи, т. е. выделение элементарных высказываний и сведение задачи к про- верке некоторых свойств высказываний, возникающих из условий задачи. Пример 6.13.1. На следствии по делу о похищении автомобиля были допрошены четыре гангстера — Андре, Боб, Стив, Том. Андре сказал, что машину похитил Боб, Боб утверждал, что виноват Том. Том заверил следо- вателя, что Боб лжет. Стив настаивал, что автомобиль угнал не он. Следо- вателю удалось установить, что только один из гангстеров сказал правду. |