Дискретная математика

Замечание.

Иногда простую импликанту булевой функции f определяют независимо от понятия о склейке как такую элементарную конъюнкцию в составе некоторой ДНФ, что удаление из неё любой переменной лишает её свойства быть импликантой функции f . Можно доказать, что эти два определения простой импликанты равносильны.

Отметим, что в процессе склейки любая элементарная конъюнкция в силу идемпотентности может использоваться любое число раз, так как

Пример.

Получить сокращенную ДНФ для СДНФ функции

61

vk.com/club152685050 | vk.com/id446425943

f x, y, z x y z x yz x yz xyz xy z xy z .

fx, y, z x y z x yz x yz xyz xy z xy z .

x y z x yz x yz x yz x yz xyz

xyz xy z xy z xy z

x y z z yz x x xz y y xy z z y z x x

x y yz xz xy y z .

Получили сокращенную ДНФ, в которой никакие дальнейшие склейки невозможны.

Конкретная булева функция может иметь не одну сокращенную ДНФ. Для функции в приведенном примере можно получить другую сокращенную ДНФ. Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы значений функции f .

Для получения минимальной ДНФ из сокращенной используется матрица Квайна (таблица 6), имеющая следующую структуру. Столбцы матрицы помечаются конъюнктами из СДНФ рассматриваемой функции, а строки – простыми импликантами сокращенной ДНФ. В матрице звёздочками (или каким-либо другим знаком) отмечаются те пересечения строк и столбцов, для которых импликанта «сохраняет» конъюнкт из СДНФ. Дело в том, что конъюнкт из СДНФ всегда может быть заменён импликантой или даже одной переменной по закону поглощения:

x x x y x x xyz ...

vk.com/club152685050 | vk.com/id446425943

В минимальную ДНФ выбирается минимальное число простых импликант, дизъюнкция которых «сохраняет» все конъюнкты из СДНФ.

Из таблицы видно, что для функции из приведенного примера три простых импликанты из пяти, полученных в сокращенной ДНФ, «сохраняют» все конъюнкты из СДНФ. Минимальная ДНФ равна

МДНФ f x, y, z x y xz y z .

Таким образом, алгоритм метода Квайна состоит в следующем:

1.Находим СДНФ заданной функции.

2.В СДНФ производим все возможные операции склеивания и поглощения. В результате получаем сокращенную ДНФ.

3.Строим матрицу Квайна и находим минимальный набор импликант,

которые совместно сохраняют наибольшее число конъюнктов из СДНФ. Если какой-либо конъюнкт из СДНФ не участвовал ни в одной склейке, то берем его в минимальную ДНФ.

§ 13. Карты Карно

Для булевых функций трех, четырех, пяти переменных процедура склейки

наглядно и просто выполняется на так называемых картах Карно.

Карта Карно - это двумерная табличная форма представления булевой

функции. Функции n переменных соответствует таблица, имеющая 2n клеток.

Каждая клетка соответствует конкретному конъюнкту из СДНФ заданной

функции.

Карта Карно для функции трех переменных имеет 23 8 клеток и

показана на рис. 1.

Обрамление карты показывает, какая клетка соответствует конкретному конъюнкту из СДНФ рассматриваемой функции. Четыре нижние клетки - это зона конъюнктов, содержащих x1 . Четыре верхние клетки - зона конъюнктов,

vk.com/club152685050 | vk.com/id446425943

центральные клетки - зона конъюнктов, содержащих x3 . Четыре боковые

клетки - зона конъюнктов, содержащих x3 .

x2

x2

x1

x1

x3 x3 x3

Рис. 1. Карта Карно для булевой функции трех переменных

Карта Карно устроена так, что соседние по вертикали и горизонтали клетки содержат конъюнкты, которые различаются по одной переменной. При этом в один из соседних конъюнктов эта переменная входит без отрицания, а в другой – с отрицанием. Таким образом, соседние клетки соответствуют склеивающимся конъюнктам.

Отметим, что конъюнкты, расположенные на противоположных концах одной и той же строки или одного и того же столбца, также являются склеивающимися.

Если в СДНФ заданной функции присутствует какой-либо конъюнкт, то в соответствующую этому конъюнкту клетку заносим единицу. Обрамление карты помогает найти эту клетку. На рис. 2 для примера заполнена карта для СДНФ функции

f x1, x2 , x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3

64

vk.com/club152685050 | vk.com/id446425943

Рис. 2. Заполненная карта Карно для булевой функции трех переменных f x1, x2 , x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3

Пример 1. Пусть булева функция задана картой Карно на рис. 2, т. е. на карте единицами заполнены те клетки, которые соответствуют конъюнктам из СДНФ заданной функции. Найдем МДНФ этой функции.

На рисунке 3 прямоугольники, покрывающие единицы, показывают, какие склейки проведены и какие импликанты получены в результате склеек. Рассмотрим все склейки подробно.

x2

x2

Рис. 3. Карта Карно, на которой показаны прямоугольники, соответствующие склейкам, рассмотренным в примере 1 для функции

f x1, x2 , x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 .

65

vk.com/club152685050 | vk.com/id446425943

Склеим два конъюнкта в левом нижнем углу. Как видно из обрамления, они различаются по переменной x3 . Склейка на карте показывается

прямоугольником, покрывающим две клетки в левом нижнем углу. Обрамление показывает, какая импликанта получается в результате склейки. Прямоугольник в левом нижнем углу – это пересечение зоны конъюнктов,

содержащих x1 , и зоны конъюнктов, содержащих x2 . Он соответствует импликанте x1 x2 . Вертикальная ось симметрии прямоугольника показывает, что склейка произошла по переменной x3 , так как слева от оси конъюнкт

содержит x3 , а справа - x3 .

Если бы мы проводили склейку аналитически, то этой склейке соответствовало бы равенство: x1 x2 x3 x1 x2 x3 x1 x2 .

Склеим два конъюнкта в правом нижнем углу. Как видно из обрамления, они также различаются по переменной x3 . Склейка на карте показывается

прямоугольником, покрывающим две клетки в правом нижнем углу. Обрамление показывает, какая импликанта получается в результате склейки. Прямоугольник в правом нижнем углу – это пересечение зоны конъюнктов, содержащих x1 , и зоны конъюнктов, содержащих x2 . Он соответствует

импликанте x1 x2 . Вертикальная ось симметрии прямоугольника показывает, что склейка произошла по переменной x3 , так как слева от оси конъюнкт

содержит x3 ., а справа - x3 .

Если бы мы проводили склейку аналитически, то этой склейке соответствовало бы равенство: x1 x2 x3 x1 x2 x3 x1 x2 .

По обрамлению карты видно, что две полученные импликанты x1 x2 и x1 x2 тоже различаются по одной переменной x2 , и их можно склеить. Эта

склейка на карте показывается прямоугольником, покрывающим четыре нижние клетки карты. Обрамление показывает, какая импликанта получается в результате склейки. Прямоугольник, покрывающий четыре нижние клетки - это зона конъюнктов, содержащих x1 . Он соответствует импликанте x1 . Вертикальная ось симметрии прямоугольника показывает, что склейка

произошла по переменной x2 , так как слева от оси импликанта содержит x2 .., а справа - x2 . Если бы мы проводили склейку аналитически, то этой склейке соответствовало бы равенство: x1 x2 x1 x2 x1 .

66

vk.com/club152685050 | vk.com/id446425943

Отметим сразу, что импликантам x1 x2 и x1 x2 , содержащим по два вхождения переменных, соответствуют прямоугольники площадью 2 клетки, а импликанте x1 , содержащей одно вхождение переменной, соответствует

прямоугольник площадью 4 клетки. Таким образом, чтобы с помощью склеек уменьшить число вхождений переменных в ДНФ, надо покрывать единицы прямоугольниками максимальной площади. При этом стороны этих прямоугольников, если их измерять количеством клеток, должны быть равны целочисленной степени двойки. Прямоугольники всегда должны иметь оси симметрии, разделяющие одинаковое количество клеток с единицами. С одной стороны от оси симметрии находятся конъюнкты или импликанты, содержащие переменную без отрицания, а с другой стороны – конъюнкты или импликанты, содержащие эту же переменную с отрицанием. Для функции трех переменных возможные конфигурации прямоугольников таковы: 2 1, 1 2, 2 2, 4 1.

Склеим два конъюнкта, расположенные в двух соседних клетках по вертикали. Как видно из обрамления, они различаются по переменной x1 .

Склейка на карте показывается прямоугольником 1 2, покрывающим две соседние по вертикали клетки. Обрамление показывает, какая импликанта получается в результате склейки. Данный прямоугольник – это пересечение

зоны конъюнктов, содержащих x2 , и зоны конъюнктов, содержащих x3 . Он соответствует импликанте. x2 x3 Горизонтальная ось симметрии прямоугольника показывает, что склейка произошла по переменной x1 ., так как

выше оси конъюнкт содержит x1 ., а ниже - x1 .

Если бы мы проводили склейку аналитически, то этой склейке

Никакие другие склейки для заданной функции невозможны. Составляем дизъюнкцию полученных импликант и получаем МДНФ заданной функции.

МДНФ= x1 x2 x3 .

Карта Карно для функции 4-х переменных показана на рис. 4. Она

содержит 24 16 клеток. Обрамление карты помогает заносить конъюнкты из СДНФ заданной функции в соответствующие им клетки и, наоборот, записывать СДНФ, если функция задана картой Карно. Для примера приведены 3 конъюнкта некоторой СДНФ функции 4-х переменных и указаны соответствующие им клетки на карте Карно.

67

vk.com/club152685050 | vk.com/id446425943

x3

Рис.4. Карта Карно для булевой функции четырех переменных. Для примера показаны клетки, соответствующие трем конкретным конъюнктам.

Пример 2. Найти МДНФ булевой функции 4-х переменных, заданной картой Карно на рис. 5.

x4 x4 x4

Рис. 5. Карта Карно, задающая булеву функцию, которая рассматривается в примере 2.

68

vk.com/club152685050 | vk.com/id446425943

По карте видно, что СДНФ заданной функции состоит из 11 конъюнктов, т. е. содержит 11 4 44 вхождений переменных.

Покрываем единицы минимальным числом максимальных по площади прямоугольников или квадратов со сторонами, равными степени 2 (Рис. 6).

x4 x4 x4

Рис. 6. Карта Карно, на которой показаны прямоугольники, соответствующие склейкам для нахождения МДНФ булевой функции из примера 2.

Прямоугольник площадью клеток расположен в зоне конъюнктов, содержащих x4 , и соответствует импликанте x4 , которая является результатом склейки восьми конъюнктов по переменным x1, x2 , x3 .Это видно по обрамлению карты. Вертикальная ось симметрии прямоугольника

Горизонтальная ось симметрии прямоугольника показывает, что произошла

из которых состоит прямоугольник 2 4, тоже имеют оси симметрии. Их горизонтальные оси симметрии показывают, что склейки произошли по переменной x2 .

69

четырех конъюнктов по переменным x3 и x4 . Это также видно по обрамлению карты. Вертикальная ось симметрии прямоугольника показывает, что произошла склейка по переменной x3 , а вертикальные оси двух прямоугольников (площадью 2 клетки) слева и справа показывают склейки по переменной x4 .

Составляем дизъюнкцию полученных импликант и получаем МДНФ, равную x4 x1 x3 x1 x2 , которая содержит 5 вхождений переменных.

В результате минимизации число вхождений переменных в заданной функции уменьшено с 44 до 5.

Таким образом, для нахождения МДНФ любой булевой функции с помощью карты Карно следует выполнить следующие действия:

1.Привести функцию к СДНФ.

2.Заполнить единицами клетки, соответствующие конъюнктам, которые содержатся в СДНФ данной функции.

3.Покрыть единицы минимальным числом максимальных по площади прямоугольников со сторонами, равными степени двойки.

4.Записать полученные импликанты и те конъюнкты, которые не участвовали в склейках, и составить их дизъюнкцию.

§14. Полиномы Жегалкина

По таблице булевых функций можно проверить следующие свойства