Билет 20

«Построение минимальной ДНФ с помощью таблицы Карно. Пример».

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

Метод Карно построения минимальной ДНФ.

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

Таблица строится так. Записываются строки со всевозможными комбинациями переменных (вт.ч. и отрицательных). Последний столбец – столбец значений булевой функции.

Алгоритм нахождения минимальной ДНФ.

1. Вычеркиваем все строки, где функция не равна СДНФ (т. е 0)

2. Вычеркиваем в оставшихся строках все переменные, которые были вычеркнуты.

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

4. Из каждой строки возьмем по одному элементу и составим из них ДНФ.

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

Итого получилась таблица:

			xy
			xy	y z
				y z	x z
					x z

(x y) (y z) ( x z) – минимальная ДНФ.

Поиск по сайту: