Дискретная математика (стр. 9 )

8.7. Минимизация неполностью определенных логических функций без использования карты Карно

Общий метод доопределения логических функций, обеспечивающий минимальное представление в классе дизъюнктивных форм, состоит в следующем.

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

Пример. Функция задана таблицей

x	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
y	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
z	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
t	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
f	1	–	–	–	0	1	0	0	1	0	–	–	1	–	–	1

= 0000 + 0001 + 0010 + 0011 + 0101 + 1000 + 1010 +

+ 1011 + 1100 + 1101 + 1110 + 1111

0 группа: 0000 *

1: 0001 * 0010 * 1000 *

2: 0011 * 0101 * 1010 * 1100 *

3: 1011 * 1101 * 1110 *

4: 1111 *

0 группа: 000- * 00-0 * -000 *

1: 00-1 * 001- * 0-01 -010 * 10-0 * 1-00 *

2: -011 * 101- * -101 110- * 1-10 * 11-0 *

3: 1-11 * 11-1 * 111- *

0 группа: 00-- 00-- -0-0 -0-0

1: -01- -01- 1--0 1--0 0-01

2: 1-1- 11-- 1-1- 11-- -101

0000	0101	1000	1100	1111
00--	Ö
-0-0	Ö		Ö
-01-
1--0			Ö	Ö
0-01		Ö
1-1-					Ö
11--				Ö	Ö
-101		Ö

= -0-0 + 11-- + 0-01 =

Контрольные вопросы

1. Сколько ячеек должно быть на карте Карно для функции пяти переменных?

2. Можно ли найти минимальную форму записи логической функции с помощью метода Квайна?

3. Можно ли приступить к кодированию нулями и единицами (метод Квайна – Мак-Класки) следующей формы записи логической функции?

4. Обязательно ли включать в контуры ячейки с прочерками при минимизации неполностью определенных логических функций?

5. Для какой из функций: или необходимо найти сокращенную нормальную форму при минимизации неполностью определенных логических функций?

9. Свойства логических функций

Функция f(x1, x2, ..., xi–1, xi, xi+1, ..., xn) называется существенно зависящей от аргумента xi, если хотя бы на одном наборе входных переменных

f(x1, x2, ..., xi–1, 0, xi+1, ..., xn) ¹ f(x1, x2, ..., xi–1, 1, xi+1, ..., xn)

Функция называется сохраняющей нуль, если она равна нулю на нулевом наборе данных.

f(x1, x2, ..., xn) = 0 при всех xi = 0, i = 1, 2, ..., n

Функция называется сохраняющей единицу, если она равна единице на единичном наборе данных.

f(x1, x2, ..., xn) = 1 при всех xi = 1, i = 1, 2, ..., n

Функция называется самодвойственной, если она принимает противоположные значения на противоположных наборах аргументов.

Функция называется монотонной, если выполняется условие

f(x1, x2, …, xn) ³ f(x1’, x2’, …, xn’) при всех xi ³ xi’, i = 1, 2, ..., n

Замечание: если ни одно из условий xi ³ xi’ для всех i от 1 до n или xi £ xi’ для всех i от 1 до n не выполняется, то говорят, что наборы xi и xi’ несравнимы. Пусть , , . Тогда , а и , а также и  будут несравнимыми.

Функция называется линейной, если ее можно представить линейным полиномом Жегалкина

,

где a0, a1, ..., an - константы, которые могут принимать значения 0 и 1.

Пример 1. Определим свойства функции логического умножения И

1.  Сохраняет нуль, так как f(0, 0) = 0.

2.  Сохраняет единицу, так как f(1, 1) = 1.

3.  Не является самодвойственной, так как .

4.  Монотонна, так как

f(1, 1)  f(0, 1),

f(1, 1)  f(1, 0),

f(1, 1)  f(0, 0),

f(0, 1)  f(0, 0),