Дискретка учебник

4.Составим функцию Патрика, перечисляя наборы по строкам карты Карно:

P = (K1 K2) (K1)(K1) (K1 K2) (K1) (K1 K3)

|

{z

}(K1

K3) (|K1)({z

3)(} 3)(

2)(| 2){z=

}1 2 3

поглощается K1

поглощается

K1

поглощается K1

|

{z

}

K

K

K K

K K K .

ядро

поглощается

K

1

| {z }

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

ДНФтуп(f) = ДНФмин(f) = ДНФядр(f) = ДНФсокр(f) = = K1 K2 K3 = x1 x2x4 x2x4;

r(ДНФсокр(f)) = 5.

Пример 6.4. Методом Карно минимизировать функцию

fe= (0101 1100 1101 1010).

Решение.

1. Заполним карту Карно, поменяв местами последние пары значений в каждой четверке и 3 и 4 четверку.

xy

0101 7→0110 - первая строка карты Карно

xy

1100 7→1100 - вторая строка карты Карно

xy

1101 7→1110 - четвертая строка карты Карно

xy

1010 7→1001 - третья строка карты Карно

2.Отметим на карте Карно максимальные интервалы. Учитывая, что крайние строки таблицы являются соседними, объединим 4 набора с двоичными номерами (0001), (0011), (1001) и (1011) в квадрат I1. Еще 6 пар рядом стоящих вершин ( с номерами (0001)

и(0101), (0100) и (0101), (0100) и (1100), (1100) и (1000), (1100)

и(1110), (1000) и (1001) соответственно) также образуют максимальные интервалы.

101

	x3x4	00 01 11	10
I2	@	- 1 1		I1
	00
	x1x@2	I3
I4				I6
	01	-1 1
I	11	-1	1	I7
5	10	1 1 1

3. Найдем простые импликанты и сокращенную ДНФ.

					(0001)
I	=				(0011)		↔	K	=			x
										x			4
1					(1001)			1	2
					(1011)

I2 = {

(0001)

}

↔

K2 =

1

3x4

(0101)

x

x

I3 = {

(0100)

}

↔

K3 =

1x2

3

(0101)

x

x

I4

= {

(0100)

}

↔

K4

= x2

3

4

(1100)

x

x

I5

= {

(1100)

}

↔

K5

= x1

3

4

(1000)

x

x

I6

= {

(1100)

}

↔

K6

= x1x2

4

(1110)

x

I7

= {

(1000)

}

↔

K7

= x1

2

3

(1001)

x

x

ДНФсокр(f) = K1 K2 K3 K4 K5 K6 K7 =

= x2x4 x1x3x4 x1x2x3 x2x3x4 x1x3x4 x1x2x4 x1x2x3.

102

4.Отметим вершины, покрытые только одним интервалом и найдем ядровую ДНФ.

	x3x4	00 01 11	10
I2	@	- 1 *1		I1
	00
	x1x@2	I3
I4				I6
	01	-1 1
I	11	-1	*1	I7
5	10	1 1 *1

Интервалы I1 и I6 содержат вершины, не покрытые другими интервалами, и являются ядровыми.

ДНФядр(f) = K1 K6 = x2x4 x1x2x4.

5. Функция Патрика для заданной функции:

P = (K1 K2) (K1)(K3 K4)(K2 K3) (K4 K5 K6)(K6)

( 5

1) =

1 6( 3

}

7) =

7|) ({z1

} 7) (

4|)(

2

{z3)(

5

K

поглощается K1

поглощается

K6

K

K K

K K K K K

K K

K K

= K1K6( |

2{z

}

K2K4 K3K3

3 4

)(K5 K7) =

K

3

поглощается K1

K

K K

|

{z

}

|

{z

}

|

{z

}

поглощается K3

K3

поглощается K3

=K1K6(K3 K2K4)(K5 K7) =

=K1K6(K3K5 K2K4K5 K3K7 K2K4K7) =

| {z }

ядро

= K1K3K5K6

K1K2K4K5K6

K1K3K6K7

K1K2K4K6K7 .

|

}

}

{zтуп 1}

| {zтуп

2

| {zтуп

3}

| {zтуп

4

ДНФ

ДНФ

ДНФ

ДНФ

6.Убедимся, что ядровая ДНФ, найденная ранее, совпадает с дизъюнкцией импликант, стоящих перед скобками в функции Патрика:

ДНФядр(f) = K1 K6 = x2x4 x1x2x4.

7.Выпишем все тупиковые ДНФ и найдем их ранг. Укажем минимальные ДНФ заданной функции:

103

ДНФтуп1

(f) = ДНФмин1 (f) = K1

K3 K5 K6 =

=

2x4

1x2

3 x1

3

4 x1x2

4;

x

x

x

x

x

x

r1 = 11;

ДНФтуп2

(f) = K1 K2 K4 K5

K6 =

=

2x4

1

3x4 x2

3

4 x1

3

4 x1x2

4;

x

x

x

x

x

x

x

x

r2 = 14;

ДНФтуп3

(f) = ДНФмин2 (f) = K1

K3 K6 K7 =

=

2x4

1x2

3 x1x2

4 x1

2

3;

x

x

x

x

x

x

r3 = 11;

ДНФтуп4

(f) = K1 K2 K4 K6

K7 =

=

2x4

1

3x4 x2

3

4 x1x2

4 x1

2

3;

x

x

x

x

x

x

x

x

r4 = 14.

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

fe= (1101 1011 0000 0100).

Решение.

1. Заполним карту Карно.

xy

1101 7→1110

xy

1011 7→1011

xy

0000 7→0000 - четвертая строка карты Карно

xy

0100 7→0100 - третья строка карты Карно

104

2.Объединим наборы носителя в максимальные интервалы. Всего интервалов 7: шесть пар рядом стоящих вершин и один точечный интервал, покрывающий вершину (1101).

	x3x4	00		01	11	10
I1	@			1 1			I2
	00 - 1
	x1x@2
I3
	01 - 1				1 1 I4
I7	11	- 1				I@	I5
	10					@ I6

3. Найдем простые импликанты и сокращенную ДНФ.

{ }

I1 =

(0000)

↔

K1 =

1

2

3

(0001)

x

x

x

I2 = {

}

(0001)

↔

K2 =

1

2x4

(0011)

x

x

I3

= {

(0000)

}

↔

K3

=

1

3

4

(0100)

x

x

x

I4

= {

(0011)

}

↔

K4

=

1x3x4

(0111)

x

I5

= {

(0111)

}

↔

K5

=

1x2x3

(0110)

x

I6

= {

(0100)

}

↔

K6

=

1x2

4

(0110)

x

x

{}

I7 = (1101) ↔ K7 = x1x2x3x4

ДНФсокр(f) = K1 K2 K3 K4 K5 K6 K7 =

= x1x2x3 x1x2x4 x1x3x4 x1x3x4 x1x2x3 x1x2x4 x1x2x3x4.

105

4.Только вершина (1101) покрыта одним интервалом. Это значит, что ядровая ДНФ состоит только из одной простой импликанты.

I1 I3 I7

x3x4	00		01	11	10
@			1 1			I2
00 - 1
x1x@2
01 - 1				1	1 I4
11	- *1				@I	I5
10					@ I6

ДНФядр(f) = K7 = x1x2x3x4.

5.Составим функцию Патрика, записав произведения в порядке, соответствующем строкам карты Карно:

P=

=(K1 K3)(K1 K2)(K2 K4)(K3 K6)(K4 K5)(K5 K6)(K7) =

=K7(K1K1 K| 1K2 {zK1K}3 K2K3)(K2K3 K2K6 K3K4 K4K6)

поглощается K1

(

K4K5

K4K6 K5K5 K5K6

) =

=

7( 1

2 3)(

|2

{z3

}

2 6

3 4

K4K6)(

|

4

{z

6

}

K5) =

K K

поглощается

K5

K K

поглощается

K5

K K K K

K K

K K

= K7( K1K2K3

K1K2K6 K1K3K4 K1K4K6 K2K3

K2K3 |

6

{z

}

K2K3K4

K2K3K4K6 )(K5 K4K6) =

поглощается K2K3

K

=

|

}2 6

1|

{z

}

{z2

}

5

4 6

7({z1

3

4

1 4 |6

3

поглощается K2K3

поглощается K2K3

поглощается K2K3

K K ) =

K K K K

K K K

K K K

K K )(K

= K7(K1K2K5K6 K1K3K4K5

K1K4K5K6

K2K3K5

K1K2K4K6

K1K3K4K6

|

K1

{z

4 6

}

K2K3K4K6) =

поглощается

K1K4K6

|

{z

}

|

{z

}

K K

поглощается K1K4K6

поглощается K1K4K6

= K7 (K1K2K5K6 K1K3K4K5 K2K3K5

|{z}

ядро

K1K4K6 K2K3K4K6) =

106

= K1K2K5K6K7

K1K3K4K5K7

K2K3K5K7

|

}

|

}

|

{zтуп

1

{zтуп 2

{zтуп

3}

ДНФ

ДНФ

ДНФ

K1K4K6K7

K2K3K4K6K7 .

|

|

}

{zтуп 4}

{zтуп

5

ДНФ

ДНФ

6.

ДНФядр(f) = K7 = x1x2

3x4

x

7.Выпишем все тупиковые ДНФ и найдем их ранг. Среди всех тупиковых ДНФ найдем минимальные ДНФ :

ДНФтуп1

ДНФтуп2

ДНФтуп3

ДНФтуп4

ДНФтуп5

(f) = K1 K2 K5 K6 K7 =

x1x2x3 x1x2x4 x1x2x3 x1x2x4

r1 = 16;

(f) = K1 K3 K4 K5 K7 =

x1x2x3 x1x3x4 x1x3x4 x1x2x3

r2 = 16;

(f) = ДНФмин1 (f) = K2 K3 K5 K7 x1x2x4 x1x3x4 x1x2x3

r3 = 13;

(f) = ДНФмин2 (f) = K1 K4 K6 K7 x1x2x3 x1x3x4 x1x2x4

r4 = 13;

(f) = K2 K3 K4 K6 K7 =

x1x2x4 x1x3x4 x1x3x4 x1x2x4

r4 = 16.

x1x2x3x4;

x1x2x3x4;

=

x1x2x3x4;

=

x1x2x3x4;

x1x2x3x4;

107

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

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

1.fe1 = (1010 0111 1010 0000);

2.fe2 = (1011 1010 1110 1010);

3.fe3 = (1101 1011 1100 1010);

4.fe4 = (1110 0110 1110 0110);

5.fe5 = (0010 0010 0111 1110);

6.fe6 = (1010 1110 0011 0001);

7.fe7 = (1100 1010 1101 0010);

8.fe8 = (1110 0110 0100 0111);

9.fe9 = (0011 0011 1100 0101);

10.ff10 = (0000 0111 0000 1110).

Ответы к задачам для самостоятельного решения

Ответы к задачам 1 ÷ 8 см. в предыдущей главе на стр. 86.

9.ДНФсокр(f9) = x1x2x3 x1x3x4 x2x3x4 x1x2x4 x1x3;

ДНФядр(f9) = x1x2x3 x1x3; ;

ДНФтуп1 (f9) = x1x2x3 x1x3x4 x2x3x4 x1x3; r(ДНФтуп1 ) = 11;

ДНФтуп2 (f9) = ДНФмин(f9) = x1x2x3 x1x2x4 x1x3; r(ДНФтуп2 ) = r(ДНФмин) = 8.

108

10. ДНФсокр(f10) = x1x2x4 x2x3x4 x1x2x3 x2x3x4 x1x2x3 x1x2x4;

ДНФядр(f10) − отсутствует;

ДНФтуп1 (f10) = x1x2x4 x1x2x3 x1x2x3 x1x2x4;

r(ДНФтуп1 ) = 12;

ДНФтуп2 (f10) = ДНФмин1 (f10) = x1x2x4 x2x3x4 x1x2x3;

r(ДНФтуп2 ) = r(ДНФмин1 ) = 9;

ДНФтуп3 (f10) = x1x2x4 x2x3x4 x2x3x4 x1x2x4;

r(ДНФтуп3 ) = 12;

ДНФтуп4 (f10) = x2x3x4 x1x2x3 x2x3x4 x1x2x3;

r(ДНФтуп4 ) = 12;

ДНФтуп5 (f10) = ДНФмин2 (f10) = x2x3x4 x1x2x3 x1x2x4;

r(ДНФтуп1 ) = r(ДНФмин2 ) = 9.

109

Глава 7

Основные замкнутые классы

7.1Замыкание. Замкнутые множества

Определение 7.1. Замыканием множества К функций алгебры логики называется совокупность всех функций из P2, являющихся суперпозициями функций из множества К. Замыкание множества К обозначается [K].

Определение 7.2. Множество К называется функционально замкнутым, если замыкание множества совпадает с самим множеством:

[K] = K.

Замкнутые множества называют также замкнутыми классами.

Пример 7.1.

а) Класс K1 = {1, x1&x2}. Его замыканием является множество

[K1] = {1, a1x1&a2x2& . . . &aixi& . . . &anxn; n = 1, 2, . . . i . . . ;

ai {0, 1}; i = 1, n}.

Класс K1 не замкнут, так как f1 = x1&x2&x3 [K1], но f1 / K1.

б) Класс K2 = {1, x1 x2}. Его замыканием является множество

[K2] = {1, a1x1 a2x2 . . . aixi . . . anxn; n = 1, 2, . . . i . . . ;

ai {0, 1}; i = 1, n}.

Класс K2 также не замкнут, так как f2 = x1 x2 x3 [K2], но f2 / K2.

110