Элементы общей алгебры. Алгебра логики. Понятия алгебры логики, страница 6

Постоянные импликанты	Конституенты
	xyz
xy	X	X
yz	X		X
		X			X
			X	X
				X		X
					X	X

Итак F имеет 2 тупиковые ДНФ с одинаковым числом букв (одна из них в таблице выделена подчеркиванием, другая – полужирным шрифтом):

Пример. Найти минимальную ДНФ для , которая равна 1 на 1, 3, 5, 7, 14 и 15 наборах.

Решение: Запишем номера наборов в двоичном коде:

0001 0011 0101 0111 1110 1111 

выпишем соответствующие им конституенты:

Выполним первое склеивание:

Выполним второе склеивание:

Составляем импликантную матрицу:

Импли-канты	Конституенты
	X	X	X	X
				X		X
					X	X

Итак, существует одна тупиковая ДНФ

Дизъюнктивные нормальные формы (ДНФ)

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

Пример:  ; ; , xyz –будут элементарными произведениями, а , хуÚ - нет , т.к. в них есть знак дизъюнкции или общее отрицание.

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

Теорема №1. Элементарное произведение равно 1 на одном наборе если переменным без отрицания из этого набора присвоены 1 и переменным с отрицанием – присвоены 0.

Пример: Элементарное произведение  равно единице только на наборе  x₁=0   x₂ = x₃ = 1   т.к.   Этот набор единственный. Действительно для набора 0,0,1 имеем

Теорема №2 Для любого набора значений переменных существует только одно их элементарное произведение, которое равняется единице.

Теорема №3Элементарное произведение всех n переменных, входящих в функцию F, является конституентой единицы.

Теорема№4 Число конституент единицы для n переменных равняется 2ⁿ.

В соответствии с теоремой №1, чтобы представить конституенту единицы от n переменных которая будет равняться единице на m-том наборе, нужно представить число m в виде двоичного числа и в конъюнкции переменных, взять с отрицанием те переменные, которым в двоичном коде соответствуют нули.

Пример: Записать конституенту единицы для 17^го набора.

Представим число 17 в виде двоичного числа 10001. Запишем конъюнкцию пяти переменных  x₁ x₂ x₃ x₄ x₅  и возьмем с отрицанием те переменные, которым соответствуют нули - это элементарное произведение будет конституентой единицы. 17^го набора.

Дизъюнкция конституент единицы, которая равняется единице на тех же самых наборах, что и заданная функция, называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции.

Теорема №5 Любая логическая функция (кроме ”константы ноль”) может быть единственным образом представлена в СДНФ.

Задача представления функций в СДНФ (запись логических функций “по единицам”):

3.  Выписать по числу единиц в логической функции произведения всех аргументов от 1^го до n^го и соединить их знаком дизъюнкции.

4.  Записать под каждом аргументом его значение в соответствующем данному произведению наборе, равное 1 или 0 и над аргументами равными 0 поставить  знаки отрицания.

Пример. Представить в СДНФ логическую функцию пяти аргументов F=F(x₁ x₂ x₃ x₄ x₅) которая равняется единице на наборах с номерами 5,14,16 и 31 и нулю на остальных наборах.

1.Выписываем четыре произведения и соединим их знаками дизъюнкции

Ú    Ú     Ú   

2. Под ними расставим наборы значений переменных в двоичной форме записи

00101 01110 10000 11111

тогда  F=`ÚÚÚ

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

Функция j называется импликантой функции F , если она равна 0 на тех наборах, где равна нулю F. При этом j может равняться нулю там, где F=1, но не наоборот.

В случае, если j является импликантой для F, то говорят, что j входит в функцию F (j Ì F).

Пример: В таблице заданы функции

F = F(х₁,х₂,х₃) j = j(х₁,х₂,х₃) Z = Z(х₁,х₂,х₃)      

№ набора	х1	х2	х3	F	j	Z
0	0	0	0	1	1	0
1	0	0	1	0	0	0
2	0	1	0	1	0	0
3	0	1	1	1	1	0
4	1	0	0	0	0	1
5	1	0	1	0	0	0
6	1	1	0	1	0	0
7	1	1	1	1	1	1

Какая из функций будет импликантой к F?

Ответ:  j Ì F, а  Z Ë F, т.к. на 4^ом наборе F=0, а Z=1.

Теорема №6.Любая конституента единицы, которая входит в СНДФF является её импликантой

Теорема № 7.“Константа ноль” является импликантой любой функции.

Теорема № 8.Любая функция будет импликантой “константы единицы”.

Две логические функции называются сравнимыми, если для них выполняются условия j₁ Ì j₂ и  j₂ Ì j₁.

Элементарное произведение, полученное путём исключения из начального элементарного произведения одной или нескольких переменных, называется его собственной частью.

Пример: Дано элементарное произведение  , его собственными частями будут произведения: ;  ;  xz,  x;  ; z.