Краткий курс лекций по Дискретной математике (стр. 7 )

Такую же формулу мы получили бы, строя СКНФА на наборах, при которых А ложна.

Преобразуем формулу:

2.Аналогичное задание для формулы

Таблица истинности имеет вид:

a	b	c	1	2	3	4
1	1	1	1	1	1	1
1	1	0	0	1	1	1
1	0	1	0	0	1	1
0	1	1	1	0	0	0
0	0	1	0	0	1	0
0	1	0	0	0	1	0
1	0	0	0	0	1	1
0	0	0	0	0	1	0

Составим СКНФА на наборах, при которых А=0:

Преобразуем формулу:

3.  Путем равносильных преобразований получить СКНФА.

Задачи для самостоятельного решения.

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

2. Найдите СДНФ для всякой тождественно ис­тинной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

3. Найдите СКНФ для всякой тождественно лож­ной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

4. Докажите равносильность формул и сравнением их совершенных нормальных форм (конъюнктивных или дизъюнктивных).

5. Найдите более простой вид формул, имеющих следующие совершенные нормальные формы:

Контрольные вопросы

1.  Перечислить свойства совершенства для ДНФ.

2.  Перечислить свойства совершенства для КНФ.

3.  Сколько для одной формулы можно составить СДНФ и СКНФ?

4.  Как по таблице истинности составить СДНФ?

5.  Связь между СДНФА и СКНФА.

6.  Как путем равносильных преобразований составить СДНФ и СКНФ формулы?

ЛЕКЦИЯ 8

ТЕМА: МИНИМИЗАЦИЯ В КЛАССЕ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ.

ПЛАН:

1.  Формула номера набора в таблице истинности.

2.  Понятие минимальной ДНФ. Метод минимизирующих карт.

3.  Метод Квайна.

4.  Метод Карно.

5.  Постановка задачи минимизации в геометрической форме.

6.  Сокращенная ДНФ.

7.  Тупиковая ДНФ. ДНФ Квайна.

Главная

1. Формула номера набора в таблице истинности.

Для удобства задания булевой функции введем формулу, связывающую номер набора в таблице истинности со значениями переменных в наборе: , n – количество переменных в функции, i – порядковый номер единицы или нуля в наборе. Рассмотрим пример: f() или f(3,5,6,7)=1. Найдем наборы при которых функция равна 1, тогда на остальных наборах функция равна 0: функция от трех переменных, значит, n =3,

3=21+20=23-2+23-3 : (011);

5=22+20=2 3-1+23-3 : (101);

7=22+21+20 = 2 3-1+2 3-2 + 2 3-3 :(111);

Для N =8 : (000).

Заметим, что предпоследний набор состоит из единиц, последний - из нулей.

2.Понятие минимальной ДНФ. Метод минимизирующих карт.

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

первое преобразование не выводит формулу из класса ДНФ, а последнее – выводит. Будем минимизировать формулы только в классе ДНФ.

ДНФ формулы А называется минимальной. Если она содержит наименьшее число вхождений переменных по сравнению с остальными ДНФ этой формулы.

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

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

Булева функция должна быть задана таблицей истинности или какой –либо совершенной нормальной формой. Составляют карту, которая имеет вид:

далее используют утверждение:

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

Опираясь на данное утверждение, получаем алгоритм построения минимальной ДНФ.

1.  Отметим в карте строки, в которых конъюнкция (в последнем столбце) не принадлежит СДНФ формулы;

2.  Вычеркнем все конъюнкции в этих строках и во всех остальных строках карты;

3.  В каждой строке выберем из оставшихся конъюнкций конъюнкции с наименьшим числом переменных, остальные вычеркнем;

4.  В каждой строке выберем по одному оставшемуся элементу и составим из них ДНФ;

5.  Из всех составленных ДНФ выберем минимальную.

Пример: Составим карту:

x	y	z	xy	xz	yz	xyz	-
x	y		xy	x	y	xy	+
x		z	x	xz	z	xz	+
	y	z	y	z	yz	yz	-
	y		y		y	y	-
		z		z	z	z	+
х			x	x		x	+
							-

Вычеркнем конъюнкции, отсутствующие в формуле и соответствующие строки. Вычеркнутые конъюнкции вычеркнуть и в остальных строках.

Составим всевозможные ДНФА, выбирая из каждой строки по одной оставшейся конъюнкции:

ДНФ2А является минимальной.

3.Метод Квайна.

Данный метод минимизации основан на применении свойства идемпотентности, поглощения и склеивания.

Рассмотрим этот метод на примере. Пусть заданы номера наборов из 4-х переменных, на которых функция равна единице : f(2,5,6,7,10,12,13,14) = 1. Необходимо составить СДНФ:

Далее упростить формулу, применив закон склеивания и идемпотентности, получим:

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

abcd
	1V	0	1V	0	1V	0	0	1V
	0	1V	0	1V	0	0	0	0
	0	1	0	0	0	0	1	0
	0	0	1	1	0	0	0	0
	0	0	0	0	0	1V	1V	0
	0	0	0	0	0	1	0	1

Выбранные ячейки отметим знаком «V». На последнем этапе минимизации получаем ДНФ: