Решение:

Данная функция задается следующей таблицей истинности:

Ее формула в СДНФ имеет вид:

=

˅.

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

Запишем члены функции в 1-й столбец таблицы, применим к ним закон склеивания, рассматривая последовательно 1-й член со всеми остальными, затем 2-й со всеми остальными и т.д. Результаты запишем во 2-й столбец таблицы, занумеруем их и укажем в скобках номера склеенных членов, а в 1-ом столбце склеившиеся члены пометим звездочками. Повторим эту процедуру с членами 2-го столбца и т.д. Те импликанты, которые не склеиваются, обведем рамочками, они являются простыми импликантами.

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	x1x2x3x4 *	(1,3) x1x2x4 *	(1,13) x2x4
2.	x1x2x3x4 *	(1,8) x2x3x4 *	(2,5) x2x4
3.	x1x2x3x4 *	(2,3) x1x2x3 *	(3,14) x2x3
4.	x1x2x3x4 *	(2,9) x2x3x4 *	(4,5) x2x3
5.	x1x2x3x4 *	(3,10) x2x3x4 *	(6,10) x1x2
6.	x1x2x3x4 *	(4,5) x1x2x3 *	(7,8) x1x2
7.	x1x2x3x4 *	(4,6) x1x2x4 *	(8,13) x1x4
8.	x1x2x3x4 *	(5,7) x1x2x4 *	(9,12) x1x4
9.	x1x2x3x4 *	(5,8) x1x3x4 *	(10,14) x1x3
10.	x1x2x3x4 *	(6,7) x1x2x3 *	(11,12) x1x3
11.		(6,9) x1x3x4 *
12.		(7,10) x1x3x4 *
13		(8,10) x1x2x4 *
14.		(9,10) x1x2x3 *

Составим таблицу, число строк которой равно числу найденных простых импликант, а число столбцов – числу членов СДНФ данной функции. В 1-й столбец записываются член функции, в 1-ю строку первичная импликанта. Если в член СДНФ входит первичная импликанта, то на пересечении их ставится метка .

	x1x2x3x4	x1x2x3x4	x1x2x3x4	x1x2x3x4	x1x2x3x4	x1x2x3x4	x1x2x3x4	x1x2x3x4	x1x2x3x4	x1x2x3x4
	(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)	(9)	(10)
x2x4	˅		˅					˅		˅
x2x3		˅	˅						˅	˅
x1x2				˅	˅	˅	˅
x1x4					˅		˅	˅		˅
x1x3						˅	˅		˅	˅

Т.к. в столбцах 1,2,4 составленной таблицы имеется всего одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной. Она не может быть исключена из минимальной формы функции, т.к. без нее не может быть получено покрытие всего множества импликант данной функции. Из таблицы меток исключаются строки и столбцы, на пересечении которых стоит эта единственная метка. Существенные импликанты запоминаем.

По закону поглощения меньшее количество меток в столбце может исключить большее. Так столбцы 1,2,4 входят соответственно в 3,8,10; в 9,10 и в 5,6,7, поэтому исключаем все эти столбцы из таблицы меток.

Из оставшихся существенных импликант записываем тупиковую форму, которая совпадает с минимальной формой данной функции:

f(x₁,x₂,x₃, x₄)_МДНФ = x₂x₄ ˅ x₂x₃ ˅ x₁x_2.

2. Метод Квайна-Мак-Класки.

=

˅.

Заменим исходные импликанты их кодами в двоичных переменных:

0101, 0110, 0111, 1000, 1001, 1010, 1011, 1101, 1110, 1111.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Все преобразования сделаем сразу в таблице:

Данная функция			Результаты 1-го склеивания			Результаты 2-го склеивания
Коды	группы		Коды	группы		Коды	группы
0101 0110 0111 1000 1001 1010 1011 1101 1110 1111	0-я	-	100- 10-0 01-1 -101 011- -110 10-1 1-01 101- 1-10 -111 1-11 11-1 111-	1-я	-101 -110 -111	-1-1 -11- 1—1 1-1- 10— -1-1 1—1 10— -11- 1-1-
	1-я	1000		2-я	1-01 1-10 1-11
	2-я	0101 0110 1001 1010		3-я	10-0 01-1 10-1 11-1
	3-я	0111 1011 1101 1110		4-я	100- 011- 101- 111-
	4-я	1111

Далее построим таблицу меток, в нее впишем исходные и первичные импликанты в виде двоичных кодов.

	1000	0101	0110	1001	1010	0111	1011	1101	1110	1111
-1-1		˅				˅		˅		˅
-11-			˅			˅			˅	˅
1—1				˅			˅	˅		˅
1-1-					˅		˅		˅	˅
10—	˅			˅	˅		˅

Обработку таблицы меток производим по методу Квайна.

Получаем: f = (-1-1) ˅ (-11-) ˅ (10--). Окончательно получаем минимальную форму данной функции:

f(x₁,x₂,x₃, x₄)_МДНФ = x₂x₄ ˅ x₂x₃ ˅ x₁x_2.

3. Метод карт Карно.

=

˅.

П

x₃

x₄

остроим карту Карно:

	1	1	1
x2	1	1	1
x1 1	1	1	1

После обработки карты получаем окончательный ответ:

f(x₁,x₂,x₃, x₄)_МДНФ = x₂x₄ ˅ x₂x₃ ˅ x₁x_2.

Сравнив, все результаты, полученные разными методами, убедившись, что они все одинаковы, запишем ответ задачи.

Ответ: f(x₁,x₂,x₃, x₄)_МДНФ = x₂x₄ ˅ x₂x₃ ˅ x₁x_2.

Задача №3. Записать формулу функции и минимизировать ее методом карт Карно.