Тема 3.2. Совершенные нормальные формы. Минимизация булевых функций в классе днф

1. Функции заданы таблицей истинности. Составить для них СДНФ и СКНФ

х а)	у	А1	А2
0	0	1	1
1	0	0	1
0	1	1	0
1	1	0	0

x б)	y	z	А1	А2
0	0	0	1	0
1	0	0	1	0
0	1	0	0	1
0	0	1	0	0
1	1	0	0	1
1	0	1	1	1
0	1	1	1	1
1	1	1	0	0

Решение:

При составлении СДНФ используем правило составления формулы по таблице истинности.

При составлении СКНФ используем равносильность

.

а) СДНФА₁ …

СКНФА₁ …

СДНФА₂ …

СКНФА₂ …

б) СДНФА₁ …

СКНФА₁ …

СДНФА₂ …

СКНФА₂ …

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

1)

2)

3)

4)

5)

6)

Решение :

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

При дополнении конъюнкции недостающей переменной x_i , используем равносильность:

………

При дополнении дизъюнкции недостающей переменной x_i , используем равносильность:

……….

1. Перейдем к основным операциям: …..

ДНФ ….

СДНФ …..

КНФ …..

СКНФ …….

2. Перейдем к основным операциям: …..

ДНФ ….

СДНФ …..

КНФ …..

СКНФ …….

3. Перейдем к основным операциям: …..

ДНФ ….

СДНФ …..

КНФ …..

СКНФ …….

4. Перейдем к основным операциям: …..

ДНФ ….

СДНФ …..

КНФ …..

СКНФ …….

5. Перейдем к основным операциям: …..

ДНФ ….

СДНФ …..

КНФ …..

СКНФ …….

6. Перейдем к основным операциям: …..

ДНФ ….

СДНФ …..

КНФ …..

СКНФ …….

3. Формула задана своей СДНФ :

1) .

2)

3)

Составьте множество N_f. Изобразите его вершинами соответствующего булева куба.

Решение:

Множество N_f – это множество векторов , на которых булева функция принимает значение ….

Т.к. функция зависит от трех переменных, то ей соответствует трехмерный- мерный булев куб.

1) , N_f ={….

Изобразим наборы в виде вершин куба:

2), N_f ={….

Изобразим наборы в виде вершин куба:

3) , N_f ={….

Изобразим наборы в виде вершин куба:

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

1) (001), (000), (100), (110)

2) (110), (100), (101), (001)

3) (100), (000), (010), (011)

4) (100), (101), (111), (011)

5) (011), (001), (101), (100)

6) (011), (111), (110), (100)

1)

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

Минимальная ДНФ …..

2)

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

Минимальная ДНФ …..

3)

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

Минимальная ДНФ …..

4)

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

Минимальная ДНФ …..

5)

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

Минимальная ДНФ …..

6)

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

Минимальная ДНФ …..

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

1) (001), (000), (100), (110)

2) (110), (100), (101), (001)

3) (100), (000), (010), (011)

4) (100), (101), (111), (011)

1)

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

ДНФ Куайна….

2)

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

ДНФ Куайна….

3)

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

ДНФ Куайна….

4)

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

ДНФ Куайна….

6.Заполнить нарту Карно для булевой функции

1) f(2,3,6,7,11,13,14,15)=1.

2) f(2,5,6,7,10,12,13,14) = 1.

Решение :

1) Обозначим переменные a, b, c, d. По номерам наборов запишем множество

N_f = {…

Заполним карту:

2) Обозначим переменные a, b, c, d. По номерам наборов запишем множество

N_f = {…

Заполним карту:

1)

2)

7. Булевы функции заданы картами Карно. Построить минимальные ДНФ

При построении минимальной ДНФ, объединяем ячейки карты к контуры – прямоугольники, в каждом из которых может быть …… ячеек. При этом число контуров должно ………..возможным, а размер контура ………... возможным.

Для каждого контура укажем соответствующую конъюнкцию.

1)

1			1
			1
	1	1	1
	1		1

2)

1			1
1	1		1
а
1		1	1

3 )

	1	1
	1
	1
1	1		1

4)

	1
1	1	1	1
	1		1
	1