Учебное пособие 1161

Алгоритм 4 (табличный способ приведения к СКНФ)

1.Составляется таблица истинности данной ПФ.

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

3.Образуется конъюнкция всех полученных элементарных дизъюнкций, которая и составляет СКНФ.

Пример. Рассмотрим ПФ X Y Z с таблицей истинности

По таблице истинности в соответствии с вышеизложенными алгоритмами выпишем СДНФ и СКНФ

СКНФ: (X Y Z) (X Y Z) (X Y Z)

СДНФ:

X Y Z X Y Z X Y Z X Y Z X Y Z

Примеры решения задач

Задача 1. Привести ПФ X Y Z к совершенным нормальным формам.

30

Решение. Для приведения к совершенным нормальным формам воспользуемся алгоритмами 3 и 4. Построим таблицу истинности и на ее основе составим СДНФ и СКНФ.

СДНФ : X Y Z X Y Z X Y Z X Y Z

СКНФ :

( X Y Z ) ( X Y Z ) ( X Y Z ) ( X Y Z )

Задача 2. Построить ПФ, задающую булеву функцию, которая принимает значение 1 только на наборах (0, 0, 0), (0, 0, 1), (0, 1, 0).

Решение. Так как известны наборы, на которых булева функция принимает значение 1, то для ее построения будем использовать СДНФ. Каждому набору поставим в соответствие элементарную конъюнкцию и составим СДНФ.

Набору (0, 0, 0) поставим в соответствие элементарную

X Y Z X Y Z X Y Z .

Это и есть ПФ, которая задает булеву функцию.

31

Задание 3. Доказать равносильность с помощью совершенных нормальных форм

(X Y ) X (X Y) X .

Решение. Единственность совершенных нормальных форм является основой для доказательства равносильности ПФ. Составим, например, СКНФ для ПФ, стоящих в левой и правой частях выражения.

СКНФ1:

(X Y) X (X Y) X (X Y) X ((X

Y) X) (X ((X Y)) ((X Y) X)

(X X Y) (X Y X) (X X Y) (X Y)

X (X Y) (X (Y Y)) (X Y) (X Y)

(X Y).

СКНФ2:

(X Y) X (X Y) (Y X) X (X Y) (Y

X) X (X Y) (Y X) (X (Y Y)) (X Y) Так

(Y X) (X Y) (X Y) (X Y) (Y X) (X Y).

как СКНФ1 и СКНФ2 совпадают, то исходные ПФ равно-

сильны.

Задача 4. Доказать равносильность

(X Y ) X (X Y) X .

Решение.

Способ 1. Составим таблицы истинности для ПФ, стоящих в левой и правой части выражения и сравним их.

Как видим, таблицы истинности ПФ совпадают, следовательно, они равносильны.

Способ 2. Для доказательства равносильности двух ПФ составим новую формулу вида

F((X Y) X) ((X Y) X

идокажем, что она является тавтологией. Для этого составим еe таблицу истинности

Способ 3. Чтобы доказать равносильность двух ПФ, приведем их к одной и той же более простой ПФ с помощью равносильных преобразований.

(X Y) X (X Y) X (X Y) X ((X

Y) X) (X (X Y)) ((X Y) X) (X (X

Y)) (X Y X) (X (X Y)) (X Y) X

(X X) (Y X) X Y.

(X Y) X (X Y) (Y X) X (X Y) (Y

X) X ((X Y) X) (Y X) X (Y X) (XY) (X X) X Y.

Таким образом,

(X Y) X (X Y) X X Y .

33

Задачи и упражнения

1. Привести к совершенным нормальным формам ПФ.

а) X Y X X Y ;

б) X (X Y); в) X Y Z .

2. Построить ПФ, задающую булеву функцию, которая принимает значение 1 только на наборах, указанных в сле-

в) (X Y) Y X .

4. Определить дизъюнктивное разложение по переменной Y следующих ПФ:

а) (X Y) (X Y),

б) (X Y) X Y ,

в) (X Z Y) X .

5. Доказать равносильность

а) (X Y) X (X Y) X ,

б) (X Y) (X Y) (X Y) X ,

в)(Y X Z) (X Y) (X Z) X Y Z X Z. 6. Упростить следующие ПФ, используя равносильные

преобразования:

а) (X Y) (Y Z) (Z X),

б) X X Z X Z X Y ,

в) ((X Y) X) (X (X Y)).

34

5.МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

ВКЛАССЕ ДНФ

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

ДНФ называется минимальной, если она содержит по сравнению с другими эквивалентными ей формами минимальное количество символов (при подсчете символов учитывается каждое вхождение символа в формулу).

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

Введем понятие импликанты булевой функции. Элементарную конъюнкцию k назовем импликантой булевой функции f, если не существует такого двоичного набора переменных, при котором функция k принимает значение 1, а

функции f – значение 0, т.е. k f f .

Для того чтобы проверить является ли заданная элементарная конъюнкция импликантой функции f, следует всем переменным, входящим в эту конъюнкцию без отрицания, придать значение 1, а тем переменным, которые входят с отрицание – значение 0. При таких значениях переменных конъюнкция примет значение 1. Затем следует проверить, принимает ли функция f значение 1 при любых значениях остальных переменных.

35

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

Пример. Простыми импликантами функции

f (X Y) (X Y) являются функции X Y и X Y . Теорема. Дизъюнкция всех простых импликант буле-

вой функции равносильна этой функции.

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

Импликантная матрица заполняется следующим образом: под конституентами, в которые входит данная простая импликанта, ставится «+», иначе «-». Каждая из конституент равна 1 лишь для одного набора аргументов. Для этого набора аргументов будут равны 1 те простые импликанты, которые расположены в строках, отмеченных «+». Поэтому достаточно оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один «+».

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

36

склеиванием по переменной Х в СДНФ называется рав-

носильное преобразование типа

(X F) ( X F) F;

поглощением в СДНФ называется равносильное преобразование типа

(F X) F F.

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

Следующая последовательность шагов описывает метод Квайна минимизации булевой функции.

Шаг 1. Привести булеву функцию к СДНФ.

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

Шаг 3. Перейти от сокращенной ДНФ к минимальной, используя импликантную матрицу.

Примеры решения задач Задача 1. Определить МДФ для булевой функции

(X Z) (Y Z).

Решение. Для определения МДФ булевой функции воспользуемся методом Квайна. Приведем булеву функцию к СДНФ:

(X Z) (Y Z) (X Z) (Y Z) (Z Y )

(X Z) (Y Z) (Z Y) ((X Z) (Z Y))

(Y Z) (Z (X Y )) (Y Z) (Z Y) (Z Z)

(X Y Y) (X Y Z) (Z Y) (X Y Z)

(Z Y (X X)) (X Y Z) (X Y Z)

(X Y Z) (X Y Z).

37

Перейдем от СДНФ к ДНФ, используя операции склеивания и поглощения:

(X Y Z) (X Y Z) (X Y Z) (Y Z) (X Y Z).

Построим импликантную таблицу

Достаточно оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один “+”. Как видно, ни одно из слагаемых сокращенной формы исключить нельзя, поэтому

МДФ имеет вид (Y Z) (X Y Z).

Замечание. Минимизированная форма для булевой функции может быть не единственна. При этом количество символов в различных минимизированных формах должно быть одинаковым.

Задача 2. Минимизировать булеву функцию f(0,1,1)=f(1,0,0)=f(1,0,1)=0 методом Квайна.

Булева функция задана перечислением наборов, на которых она принимает значение 0. На остальных наборах она принимает значение 1.

1. Составим таблицу истинности для приведения булевой функции к СДНФ.

СДНФ примет вид

X Y Z X Y Z X Y Z

X Y Z X Y Z

2. Произведем с СДНФ все возможные склеивания, а затем и поглощения:

X Y Z X Y Z X Y Z X Y Z

X Y Z X Y Z X Y Z

X Y Z X Y Z X Y Z X Y ZX Y Z X Y Z X Y Y Z X Y X Z

Получили сокращенную СДНФ:

(X Y) (Y Z) (X Y) (X Z)

3. Перейдем от сокращенной СДНФ к минимальной, используя импликантную матрицу:

Достаточно оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один «+», поэтому вторую или четвертую строку в импликантной матрице можно отбросить. Данная булева функция имеет две различные минимизирован-

ные формы X Y X Y X Z и X Y Y Z X Y .

Задачи и упражнения

1. Минимизировать булевы функции методом Квайна