БУЛЕВА АЛГЕБРА

БУЛЕВА АЛГЕБРА

В этом параграфе будут рассмотрены представления ло­гических функций в виде суперпозиций функций И, ИЛИ, НЕ.

Разложение функций по переменным. Совершенная дизъ­юнктивная нормальная форма. Введем обозначение х⁰ = , х¹ = х. Пусть— параметр, равный 0 или 1. Тогда = 1, если х = и = 0, если х а.

¹ До сих пор все, что говорилось о формулах и суперпозициях, было справедливо не только для логических, но и для любых функций вообще (см. § 1-2). Данный же метод проверки эквивалентности годится только для функций о конечными областями определения.

 

 

Теорема 3-1. Всякая логическая функция f (х₁, ..., х_n) может быть представлена в следующем виде:

f(x_{1 ,} ..., x_{m ,} x_m+1, ..., x_n )= f(, ..., , x_m+1, ..., x_n ), (3–4)

, ...,

где m n, а дизъюнкция берется по всем 2^m наборам зна­чений переменных x₁, ..., х_m.

Это равенство называется разложением по переменным х₁, ..., х_m. Например, при n = 4, m = 2 разложение (3-4) имеет вид:

f(x₁, x₂, x₃, x₄) = f(0, 0, x₃, x₄) f&(0, 1, x₃, x₄)

f(1, 0, x₃, x₄ ) f(1, 1, x₃, x₄).

Теорема доказывается подстановкой в обе части равен­ства (3-4) произвольного набора (, ..., , , ..., ) всех n переменных. Так как= 1 только когда х = а, то среди 2^m конъюнкций , ..., правой части (3-4) в 1 обратится только одна — та, в которой = , ..., = . Все остальные конъюнкции равны 0.

Поэтому полу­чим: f(, ..., ) = ... f(, ..., , , ..., )=f(, ..., ),

т. е. тождество. D

При m =1 из (3-4) получаем разложение функции по одной переменной:

f(x₁, x₂, ..., x_n) = f(0, x₂, ..., x_n) x₁f(1, x₂, ..., x_n) (3-5)

Ясно, что аналогичное разложение справедливо для любой из n переменных.

Другой важный случай — разложение по всем n пере­менным (m = n). При этом все переменные в правой части (3-4) получают фиксированные значения и функции в конъ­юнкциях правой части становятся равными 0 или 1, что дает:

f(x₁, ..., x_n) = ... , (3-6)

f(, ..., )=1

где дизъюнкция берется по всем наборам (, ..., ), на которых f = 1. Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f.

СДНФ функции f содержит ровно столько дконъюнкций, сколько единиц в таблице f; каждому единичному набору (, ..., ) соответствует конъюнкция всех переменных, в которой x_i взято с отрицанием, если = 0, и без отрица­ния, если = 1. Таким образом, существует взаимно­однозначное соответствие между таблицей функции f (x₁, ..., x_n) и ее СДНФ и, следовательно, СДНФ для вся­кой логической функции единственна (как говорят в мате­матике, “единственна с точностью до порядка конъюнкций”: это означает, что ввиду коммутативности дизъюнкции и конъюнкции — см. далее (3-8) — формулы, получаемые из (3-6) перестановкой конъюнкций и букв в конъюнкции, не различаются и считаются одной и той же СДНФ). Напри­мер, функция, заданная табл. 3-1, имеет СДНФ

.

Единственная функция, не имеющая СДНФ, — это кон­станта 0.

Формулы, содержащие кроме - переменных (и, разу­меется, скобок) только знаки функций дизъюнкции, конъюн­кции и отрицания, будем называть булевыми формулами (напомним, что знак конъюнкции, как правило, опускается).

Соотношение (3-6) приводит к важной теореме.

Теорема 3-2. Всякая логическая функция может быть представлена булевой формулой, т. е. как суперпозиция конъюнкции, дизъюнкции и отрицания.

Действительно, для всякой функции, кроме константы 0, таким представлением может служить ее СДНФ. Кон­станту 0 можно представить булевой формулой [см. далее равенство (3-15)]. D

Булева алгебра функций и эквивалентные преобразо­вания в ней. Пусть функция f₁ задана формулой F₁ а функ­ция f₂ — формулой F₂. Подстановка F₁ и F₂ в дизъюнкцию дает формулу . Если взять формулу , эквивалентную F₁ (т. е. тоже представляющую f₁), и , эквивалентную f₂, то получим формулу , эквива­лентную . (Доказательство эквивалентности можно провести стандартным методом (см. § 3-1); рекомендуем читателю его проделать). Таким образом, дизъюнкцию можно рассматривать как бинарную операцию на множестве логических функций, которая каждой паре функций f₁, f₂ независимо от вида формул, которыми они представлены, однозначно ставит в соответствие функцию . Анало­гично этому можно рассматривать конъюнкцию как бинарную операцию, а отрицание — как унарную операцию над функциями.

Алгебра (Р₂; , &, ) основным множеством которой является все множество логических функций, а операция­ми — дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций. Операции булевой алгебры также часто называют булевыми операциями.

Фактически мы имеем дело, как правило, не с самими функциями в чистом виде, а с представляющими их формулами, т. е. с алгеброй формул, которых гораздо больше, чем функций, — ведь каждую функ­цию представляет бесконечное множество формул. Для того чтобы ал­гебра формул соответствовала алгебре функций, ей придается следую­щий вид. Элементами основного множества алгебры формул объявляются не формулы, а классы эквивалентности формул, т. е. классы формул, представляющих одну и ту же функцию. Результатом, например, дизъюнкции классов K₁ и K₂ считается класс всех формул, эквивалент­ных , где . Так определенная алгебра клас­сов формул называется алгеброй Линденбаума—Тарского. Она изоморф­на булевой алгебре функций. Этот изоморфизм настолько очевиден, что часто — особенно в прикладных работах — возникает смешение поня­тий формулы и функции. Следует ясно представлять себе, что, например, логическая схема на своем выходе реализует функцию от входов; когда же речь идет об эквивалентных преобразованиях, об упрощении и т. д., то имеются в виду преобразования формул, реализующих одну и ту же функцию.

Рассмотрим теперь основные свойства булевых опера­ций.

Ассоциативность:

a) x₁(x₂x₃) = (x₁x₂)x₃, б) (x₁ x₂) x₃ = x₁ (x₂ x₃). (3-7)

Коммутативность:

a) x₁x₂ = x₂x₁; б) x₁ x₂ = x₂ x_1. (3-8)

Дистрибутивность конъюнкции относительно дизъюнк­ции:

x₁(x₂x₃) = x₁x₂ x₁x₃ (3-9)

Дистрибутивность дизъюнкции относительно конъюнк­ции:

x₁ (x₂x₃) = (x₁ x₂)(x₁ x₃) (3-10)

Идемпотентность:

а) хх = х; б) x x = x. (3-11)
Двойное отрицание:

= x . (3-12)

Свойства констант:

а) x & 1 = x; б) x & 0 = 0; в) x 1 = 1; (3-13)
г) x 0 = x; д) = 1; е) = 0.

Правила де Моргана:

a) = ; б) = . (3-14)

Закон противоречия:

= 0. (3-15)

Закон “исключенного третьего”:

= 1. (3-16)

Соотношения (3-7) — (3-16) можно проверить указанным ранее стандартным методом — вычислением обеих частей равенств на всех наборах значений переменных. Ясно, что результат вычисления не зависит от того, как получены значения переменных, входящих в эти равенства, т. е. от того, являются ли эти переменные независимыми или, в свою очередь, получены в результате каких-то вычисле­ний. Поэтому равенства (3-7) — (3-16) остаются справед­ливыми при подстановке вместо переменных любых логи­ческих функций и, следовательно, любых формул, предста­вляющих эти функции. Важно лишь соблюдать следующее правило подстановки формулы вместо переменной: при под­становке формулы F вместо переменной х все вхождения переменной х в исходное соотношение должны быть одно­временно заменены формулой F. Например, соотношение = 1 полученное из (3-16), верно для любых F, а соотношение = 1 получено из (3-16) с нарушением правила подстановки и для некоторых F может оказаться неверным. Правило подстановки позволяет получать из соотношений (3-7) — (3-16) новые эквивалентные соотно­шения.

Зачем нужны эквивалентные соотношения? Во всякой алгебре (в том числе и в булевой алгебре функций) равен­ство F₁ = F₂ означает, что формулы F₁ и F₂ описывают один и тот же элемент алгебры, в данном случае одну и ту же логическую функцию f₁. Следовательно, если какая-либо формула F содержит F₁ в качестве подформулы, то замена F₁ на F₂ не изменяет элемента булевой алгебры f над которым производятся операции в формуле F; поэтому F', получен­ная из F такой заменой, эквивалентна F. Это утверждение представляет собой правило замены подформул, которое позволяет, используя эквивалентные соотношения, полу­чать формулы, эквивалентные данной.

Подчеркнем разницу между правилами подстановки и замены. При подстановке переменная заменяется на фор­мулу; формула может быть любой, но требуется одновре­менная ее подстановка вместо всех вхождений переменной. При замене подформул может быть заменена любая подфор­мула, однако не на любую другую, а только на эквивалент­ную ей. При этом замена всех вхождений исходной подфор­мулы не обязательна. Пусть имеется эквивалентность F₁ = F₂, где F₁ и F₂ содержат переменную х. Если вместо всех вхождений х в F₁ и F₂ подставить произвольную фор­мулу F, то получаются новые формулы и , причем не обязательно F₁ = ,F₂ = ; однако между собой новые формулы будут эквивалентны: = . Если же в F₁ какую-либо подформулу заменить на эквивалентную ей, то получится новая формула , эквивалентная F₁.

Пример 3-1. Возьмем первое из соотношений (3-14) и подставим вместо x₁. Получим , т. е. две формулы, неэквивалентные исходным, но эквива­лентные между собой. Если же в правой части нового соот­ношения заменить формулой , эквивалентной ей в силу (3-14), а в полученной подформуле х₁ заменить на эквивалентную ей в силу (3-12) формулу x_1, то все формулы в построенной цепи преобразований эквивалентны.

Такие преобразования, использующие эквивалентные соотношения (запас которых можно расширять с помощью правила подстановки) и правило замены, называются экви­валентными преобразованиями. Эквивалентные преобразо­вания являются мощным средством доказательства экви­валентности формул, как правило, более эффективным, чем их вычисление на наборах значений переменных.

Рассмотрим некоторые основные эквивалентные преоб­разования в булевой алгебре и новые соотношения, полу­чаемые с их помощью из (3-7) — (3-16). При этом будем иметь в виду, что в булевой алгебре принято опускать скобки в следующих двух случаях: а) при последователь­ном выполнении нескольких конъюнкций или дизъюнкций (например, вместо (х₁х₂)x₃ пишут х₁х₂x₃ — это не вызывает неоднозначности ввиду ассоциативности этих операций (3-7); б) если они являются внешними скобками у конъюнкции: например, вместо (x₁ (x₂ x₃)) (x₄x₅) пишут x₁ (x₂ x₃) x₄x₅. Оба соглашения совершенно аналогичны общепри­нятому опусканию скобок для умножения в арифметиче­ских формулах ¹.

1. Упрощение формул (т. е. получение эквивалентных формул, содержащих меньшее число символов).

а) Поглощение:

x xy = x; (3-17а)

x (x y) = x. (3-176)

Докажем подробно первое равенство [для его доказатель­ства используются последовательно соотношения (3-13а), (3-9), (3-1 Зв) и (3-1 За)]:

x xy = x & 1 xy = x(1 y) = x & 1 = x.

Второе равенство доказывается с помощью (3-9), (3-11) и первого равенства:

x(x y) = xx xy = x xy = x .

б) Склеивание:

xy = x. (3-18)

Доказательство: xy = x (y ) = x & 1 = x.

в) Обобщенное склеивание:

xz xy = xz (3-19)

Доказывается с помощью расщепления, т. е. применения (3-18) в обратную сторону и поглощения (3-17): xz xy = xz xyz = xz .

г) x = x y. (3-20)

Доказательство: x = xy xy xy = x y.

д) Обобщением равенств (3-17а) и (3-20) является ра­венство

x₁ f(x_1, x₂, ..., x_n) = x₁ f(0, x₂, ..., x_n) (3-21)

При доказательстве используется разложение по x₁ , (3-17а) и (3-20):

x₁ f(x₁, x₂, ..., x_n) = x₁ f(0, x₂, ..., x_n) x₁f(1, x₂, ..., x_n) = x₁ f(0, x₂, ..., x_n).

__________________

¹ Внимательный читатель должен был обратить внимание на то, что эти два соглашения; а также соотношения (3-13) использованы уже в формуле (3-4).

 

2. Приведение к дизъюнктивной нормальной форме (в том числе к СДНФ).

Элементарными конъюнкциями называются конъюнкции переменных или их отрицаний, в которых каждая пере­менная встречается не более одного раза. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций. Соотношение (3-19) показывает, что ДНФ функции может быть не един­ственной.

Приведение к ДНФ делается так. Сначала с помощью (3-12) и правил деМоргана (3-14) все отрицания “спускают­ся" до переменных. Затем раскрываются скобки, с помощью (3-11), (3-15) и (3-16) удаляются лишние конъюнкции и повторения переменных в конъюкциях, а с помощью (3-13)
удаляются константы.

Пример 3-2.

xy (y xz)= xy = xy = xy

= xy = = xy .

Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, напри­мер:

xy = xyz .

Если из формулы F₁ с помощью некоторых эквивалент­ных соотношений можно получить формулу F₂, то F₂ можно получить из F₁, используя те же эквивалентные соотноше­ния; иначе говоря, всякое эквивалентное преобразование обратимо. Это позволяет доказать следующую теорему.

Теорема 3-3. Для любых двух эквивалентных формул F₁ и F₂ существует эквивалентное преобразование F₁ в F₂ с помощью соотношений (3-7) — (3-16).

Действительно, преобразуем F₁ и F₂ в СДНФ. Поскольку F₁ и F₂ эквивалентны, то их СДНФ совпадают. Обратив второе преобразование, получим преобразование F₁ СДНФ F₂. D

Важность этой теоремы в том, что соотношений (3-7) — (3-16) оказывается достаточно для любого эквивалентного преобразования в булевой алгебре.

3. Приведение к конъюнктивной нормальной форме.

Аналогично ДНФ определяется конъюнктивная нор­мальная форма (КНФ) как конъюнкция элементарных дизъюнкций.

 

От ДНФ к КНФ перейдем следующим образом. Пусть ДНФ F имеет вид , где k₁, ..., k_m — элементарные конъюнкции. Формулу приведем к ДНФ . Тогда . По правилу де Моргана от­рицания элементарных конъюнкций преобразуются в эле­ментарные дизъюнкции, что и даст КНФ.

Пример 3-3.

.

Аналогом СДНФ является СКНФ — совершенная конъ­юнктивная нормальная форма, каждая элементарная дизъ­юнкция которой содержит все переменные. Единственная функция, не имеющая СКНФ, — константа 1.

Двойственность. Функция f₁ (x₁, ..., х_n) называется двойственной к функции f₂ (х₁, ..., х_n), если f₁ (x₁, ..., x_n) = f₂(, ..., ). Беря отрицание над обеими частями равен­ства и подставляя , ..., вместо x₁, ..., х_n получаем (, ..., ) = (, ..., ) = f₂ (x₁, ..., x_n), т. е. f₂ двой­ственна к f₁. Таким образом, отношение двойственности между функциями симметрично. Из определения двойствен­ности ясно, что для любой функции двойственная функция определяется однозначно. В частности, может оказаться, что функция двойственна самой себе. В этом случае она называется самодвойственной.

Пример 3-4. Дизъюнкция двойственна конъюнкции (в силу правил де Моргана); константа 1 двойственна 0; отрицание самодвойственно. Еще один традиционный при­мер самодвойственной функции — ху хz yz.

Пользуясь определением двойственности, нетрудно (пря­мой выкладкой) доказать следующее утверждение, называе­мое принципом двойственности: если в формуле F, представляющей функцию f, все знаки функций заменить соответственно на знаки двойственных функций, то полу-ченнаяформула F* будетпредставлять функцию f*, двойственную f. В булевой алгебре принцип двойственности имеет более конкретный вид, вытекающий из ранее приведенных примеров: если в формуле F, представляющей функцию f все конъюнкции заменить на дизъюнкции, дизъюнкции — на конъюнкции, 1 на 0, 0 на 1, то получим формулу F*, представляющую функцию f*, двойственную f.

Если функции равны, то и двойственные им функции также равны. Это позволяет с помощью принципа двойст­венности получать новые эквивалентные соотношения, пе­реходя от равенства F₁ = F₂ с помощью указанных замен к равенству F₁* = F₂*. Примером пары соотношений, полу­чаемых друг из друга по принципу двойственности, яв­ляются два равенства (3-17).

Булева алгебра и теория множеств. В примере 2-1, п. 3 были опи­саны булевы алгебры множеств. Общий термин “булева алгебра” для алгебр множеств и логических функций не случаен.

Всякая алгебра типа (2, 2, 1) называется булевой алгеброй, если ее операции удовлетворяют соотношениям (3-7) — (3-16). В алгебре множеств элементами являются подмножества фиксированного (“уни­версального”) множества U (напомним, что система всех подмножеств U обозначается через B(U)), операции & соответствует пересечение, операции — объединение, операции соответствует дополнение; еди­ницей является само множество U, нулем — пустое множество. Спра­ведливость соотношений (3-7) — (3-16) для алгебры множеств можно показать непосредственной их проверкой. Для этого нужно рассмотреть переменные в них как множества, знаки &, заменить на , и пока­зать, что если какой-либо элемент принадлежит множеству из левой части равенства, то он принадлежит правой части, и наоборот. Эту проверку мы предоставляем читателю.

В предыдущих главах уже отмечалось и использовалось (см. тео­рему 1-2) взаимно-однозначное соответствие Г между множеством B(U), где U = {a₁, ..., а_n}, и множеством В_n двоичных векторов длины n: каждому подмножеству М U соответствует двоичный вектор F (М) = = (, ..., ), где = 1, если a_i M, и = 0, если a_i M. Булева алгебра (В_n; , &, ) на множестве В_n определяется следующим образом: для любых векторов = (, ..., ) и = (, ..., )

= (,, ..., );

& = (& ,& , ..., & ); (3-22)
= (, , ..., ).

Поскольку компоненты (разряды) и векторов и принимают значения 0 и 1, то указанные операции над компонентами — это просто логические операции над двоичными переменными; операции над век­торами естественно назвать покомпонентными (поразрядными) логи­
ческими операциями над двоичными векторами. Такие операции (наряду с логическими операциями над переменными) входят, в частности, в систему команд любой современной ЭВМ. Выполнение их очень просто: вектор содержит единицы во всех разрядах, в которых есть 1 либо в , либо в , вектор & — в тех разрядах, в которых 1 есть и в , и в ; вектор содержит единицы в тех разрядах, в которых содержит нули. Например, если = 01011, = 11010, то = 11011, & = 01010, = 10100.

Теорема 3-4. Если |U| = n, то булева алгебра (B(U); , , ) изоморфна булевой алгебре (B_n; , &, ).

Взаимно-однозначное соответствие Г между подмножествами U и векторами из В_n было описано ранее. Остается показать, что Г — изоморфизм, т. е. что для него выполнено условие (2-1), которое в данном случае сводится к трем равенствам: если Г (M₁) = , а Г (М₂) = , то

Г(M₁M₂) = ;

Г(M₁M₂) = & ; (3-23)
Г(M₁) = .

Справедливость их вытекает непосредственно из (3-22): если a_i M₁ М_2, то i-й разряд вектора Г (М₁ М₂) = 1; с другой сто­роны, это означает, что a_i M₁ или a_i M₂, т. е. = 1 или = 1 и, следовательно, i-й разряд вектора равен 1. Если же a_i M₁ М₂, то i-й разряд Г (M₁ M₂) равен 0. Но тогда a_i M₁ и a_i М₂, следовательно, i-й разряд также равен 0. Аналогично доказы­ваются остальные два равенства. D

Эта теорема позволяет заменять теоретико-множественные операции (объединение, пересечение, дополнение) над системой подмножеств поразрядными логическими операциями над двоичными векторами. Такая замена очень часто используется при программировании, по­скольку представление двоичных векторов и поразрядные операции над ними в ЭВМ реализуются очень просто.

Рассмотрим теперь множество Р₂(m) всех логических функций m переменных х₁, ..., х_m. Оно замкнуто относительно операций &,, (результат их применения к функциям из P₂(m) снова дает функцию из Р₂ (m)) и, следовательно, образует конечную булеву алгебру (Р₂(m); , &, ), являющуюся подалгеброй булевой алгебры логических функций.

Теорема 3-5. Если |U| = 2^m, то булева алгебра множеств (B(U); , , ) изоморфна булевой алгебре функций (Р₂(m); , &, ).

Прежде всего отметим, что эти две алгебры равномощны и содер­жат элементов. Кроме того, поскольку все множества U одинаковой мощности порождают изоморфные булевы алгебры множеств (см. при­мер 2-2, п. 5), то теорему достаточно доказать для какого-либо конкрет­ного U, удовлетворяющего условию |U| = 2^m. В качестве такого U возьмем множество В_m и, следовательно, будем доказывать изоморфизм между

(B (В_m); , , ) и (Р₂(m); , &, ).

Обозначим через M_f множество единичных наборов функции f; тогда набор из В_m принадлежит M_f, если и только если f() = 1. Соответствие Г (f) = M_f между функциями и их единичными множест­вами является взаимно-однозначным соответствием между Р₂(m) и B(В_m), поскольку различным функциям соответствуют различные множества, и наоборот. (Функцию f, единичным множеством которой служит М, называют характеристической функцией множества М.) Покажем, что Г является изоморфизмом. Для этого достаточно прове­рить услойие (2-1), которое в данном случае сводится к трем равенствам

Г(fg) = M_fM_g;

Г(f&g) = M_fM_g;

Г() =

для любых функций f и g m переменных. Докажем первое из них. Пусть Г (f g). Тогда f ()g () = 1, следовательно, f () = 1 или g () = 1 и, значит, M_f или М_g; откуда следует, что (M_f M_g). Обратный случай (M_f M_g). Тогда M_f или М_g и, следовательно, f () = 1 или g () = 1. Поэтому f ()g () = 1 и Г (f g). Аналогично доказываются и остальные два равенства. D

Замечание. Во избежание путаницы обращаем внимание читателя на различия объектов в доказанных нами теоремах.

1. В теореме 3-4 фигурировали алгебры со следующими основными множествами:

U ={a₁, ..., а_n} — множество произвольной природы и любой конечной мощности n;

B(U) — множество подмножеств U мощности 2ⁿ;

В_n — множество двоичных векторов длины n также мощности 2ⁿ.

В теореме 3-5 участвуют:

то же множество U, но с дополнительным условием n = 2^m (m — любое натуральное число);

В_m — конкретное множество U с этим же условием: |В_m| = 2^m;

множество Р₂(m) логических функций m переменных;

|Р₂(m)| = ;

B(В_m) — множество подмножеств В_m; |B(В_m)| = .

2. Множества В_n и В_m, хотя и имеют одну и ту же природу (состоят из двоичных наборов), использовались в теоремах 3-4 и 3-5 по-разному. В теореме 3-4 была использована структура элементов В_n, благодаря чему над ними оказались возможными поразрядные логические опера­ции. Подмножества В_n не рассматривались. В теореме 3-5 структура элементов В_n не учитывалась, само В_n было выбрано только для естест­венности и наглядности, зато рассматривалась B(В_n) — система под­множеств В_n.

Теоремы 3-4 и 3-5 указывают на тесную связь между множествами и логическими функциями и позволяют переходить от операций над множествами к операциям над функциями и обратно. В частности, они дают возможность непосредственно производить операции над функциями, заданными не формулами, а таблицами или единичными множествами. Из теорем 3-4 и 3-5 следует, что булевы операции над функциями, заданными таблицами, сводятся к поразрядным логическим операциям над столбцами значений функций. Пример приведенв табл. 3-4, содержащей две функции f и g и результаты булевых операций над ними.

Таблица 3-4

x1	x2	x3	f	g	fg	fg

 

В завершение отметим еще один факт, связывающий логические функции с основными понятиями теории множеств: если (f g) 1, то M_f M_g. Действительно, если (f g) 1, то из определения импли­кации (табл. 3-3, функция ) следует, что ни для какого набора не может быть одновременно f () = 1 и g () = 0, Поэтому если f () = 1, то g () = 1, т. е. если М_f, то М_g и, следовательно, M_f M_g. В таком случае говорят, что функция f имплицирует функ­цию g. При этом если f — элементарная конъюнкция, то f называется импликантом g, а если после удаления буквы f перестает быть импликантом g, то f называется простым импликантом g. Например, для функции х (у z) конъюнкции ху и хz — простые импликанты, а хуz — импликант, но не простой. Отметим, что любая конъюнкция любой ДНФ данной функции является импликантом этой функции.

ДНФ, интервалы и покрытия. Теоретико-множественная интерпре­тация булевой алгебры функций оказывается очень удобным языком для изучения дизъюнктивных нормальных форм (ДНФ) и построения методов их упрощения. Рассмотрим кратко основные понятия, связан­ные с ДНФ.

Если функция f (x₁, ..., х_m) представляется элементарной конъюнк­цией всех m переменных, то M_f содержит ровно один элемент множества В_m. Если же f — элементарная конъюнкция k переменных, где k < m, то M_f содержит 2^m-k двоичных наборов (так как m — k переменных, не вошедших в эту конъюнкцию, несущественны для f и могут прини­мать любые 2^m-k значений, не изменяя f). Множество M_f такой функ­ции f называется интервалом. Например, для m = 4 и f(x₁, х₂, х₃, x₄) = x₂M_f = {0100, 0110, 1100, 1110} и |M_f| = 2² = 4. В этом слу­чае говорят, что конъюнкция x₂(точнее, интервал покрывает множество M_f (и все его подмножества). Представление f в виде ДНФ соответствует представлению ее единичного множества в виде объеди-

Таблица 3-5

xz
y
xy

 

нения интервалов; в совокупности все конъюнкции ДНФ покрывают все единичное множество f. Верно и обратное: если все элементы неко­торого интервала М_k, принадлежат M_f, то существует ДНФ функции f, содержащая конъюнкцию k. В ча­стности, СДНФ функции f соответствует просто перечислению элементов M_f. Отношение покрытия между конъюнкциями ДНФ и элементами M_f наглядно задается таблицей покрытия, строки которой соответствуют конъюнкциям (т. е. интерва­лам), столбцы — элементам M_f, а на пересечении строки i со столбцом j стоит какая-либо отметка (например, 1), если i-я конъюнкция покры­вает j-й элемент M_f. Например, ДНФ F = хz / y/ ху соответствует таблица покрытия (табл. 3-5).

Из табл. 3-5 видно, что интервал М_ху покрывается объединением интервалов М_хz и М_y. Поэтому исключение ху из F не изменит единич­ного множества данной функции и получится теоретико-множественное доказательство соотношения (3-19). Еще более очевидное обоснование имеет закон поглощения х / ху = х: интервал М_ху всегда покрывается интервалом М_х. Этот закон в терминах ДНФ можно переформулиро­вать следующим образом: любой импликант k ДНФ, не являющийся простым, можно заменить простым импликантом k₀, покрывающим k; импликант k₀ получается из k вычеркиванием некоторых букв.

Таким образом, для любой функции f существует ДНФ F, состоя­щая только из простых импликантов. Ясно, что ДНФ F / k, где k — простой импликант f, не содержащийся в F, также представляет f. Поэтому дизъюнкция всех простых импликантов f, называемая сокращен­ной ДНФ, также будет представлять f.

Методы упрощения ДНФ (а их в настоящее время известно довольно много) состоят, как правило, из двух этапов. На первом этапе получают список всех простых импликантов, т. е. сокращенную ДНФ. Это можно сделать, например, при помощи эквивалентных преобразований. На втором этапе, используя таблицу покрытия (или аналогичные методы), удаляют “лишние” импликанты, покрываемые другими импликантами. ДНФ, из которой нельзя удалить ни одного импликанта, называется тупиковой.