7-Тема. Практическое занятие

Рис. 7.2. Карта Карно для функций трех переменных
Метки расставлены таким образом, что от столбца к столбцу в них происходит изменение ровно в одном символе. Ячейки карты Карно соответствуют восьми минтермам, которые можно постро­ить из трех булевых переменных. Если нам дано булево выражение в дизъюнктивной нормальной форме, то в ячейки, соответствующие минтермам, участвующим в ней, мы записываем цифру 1.
Например, карта Карно булева выражения изображена на рис. 7.3.

	1	1
			1

Рисунок 7.3. Карта Карно выражения

Затем предлагается «группировать» пары «соседних» единиц в Кар­те Карно (похожих на ту, которая выделена на рис. 7.3). Такая пара в нашем примере только одна. Она соответствует именно тем мин- термам, которые мы объединили в сделанных ранее алгебраических преобразованиях.

Вообще говоря, при какой-то разметке карты Карно (отвечаю­щей требованию, при котором метки соседних столбцов отличились только одним символом) может оказаться, что возможность груп­пировки минтермов будет скрыта.
Например, на карте Карно (рис. 7.4) выражения не видно, что члены и можно сгруппировать.

1			1
	1

Рисунок 7.4. Неудачное обозначение столбцов карты Карно выражения

Переобозначая столбцы с соблюдением основного требования, мы получим альтернативную карту Карно (рис. 9.5). На ней уже члены для группировки стоят рядом.

		1	1
1

Рисунок 7.5. Альтернативная карта Карно выражения

Следовательно,

Пример 7.6. Упростите булево выражение

Решение. Обратим внимание на рис. 7.6, где изображена соответ­ствующая карта Карно.

1	1
1	1	1

Рисунок 7.6. Карта Карно выражения
Из нее следует, что в данном выражении есть группа из четырех минтермов:
,
которую мы обозначим через (А), и группа из двух минтермов:
.
Ее мы обозначим через (Б).
Сначала поработаем над группой (А).


Теперь займемся группой (Б).

Таким образом, исходное выражение упрощается до¹ .
Пример 9.7. Упростите булеву функцию


Решение. Заполним таблицу истинности функции (табл. 7.9).

Таблица 7.9

0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

По таблице строим дизъюнктивную нормальную форму функции f:

.
Ее карта Карно показана на рис. 7.7.

		1
		1	1

Рисунок7.7.Карта Карно выражения

Из карты Карно видно, что в нашем выражении присутствуют две пары минтермов для группировки: и . После их упрощения получаются функции: и .Следовательно, исходная функция сводится к выражению ..
Наглядный способ поиска минтермов для группировки, который предоставляет карта Карно, можно обобщить на булевы функции четырех, пяти и даже шести переменных. Однако при этом возни­кают трехмерные диаграммы и дополнительные осложнения делают метод малопроизводительным. Есть и другие способы упрощения булевых выражений. Особенно привлекателен метод Куина-Мак-Класки. Он довольно систематичный (см., например, [2]) и приме­ним к функциям любого количества булевых переменных.


Варианты заданий для индивидуального решения
(каждый студент решает пример под тем номером, который соответствует его номеру в списке журнала)

7. Изобразите карту Карно булева выражения с дизъюнктивной

нормальной формой

и найдите его упрощенную версию.
8. Найдите дизъюнктивную нормальную форму булевой функции f(p,q,r ) с таблицей истинности — табл. 9.12.


Таблица 9.12

p	q	r	f
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Изобразите ее карту Карно и упростите функцию f .