Математика \ Дискретная математика

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

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

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

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

ÙÙÙ Ù

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

00101 01110 10000 11111

тогда F=`ÙÙ ÙÙ

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

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

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

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

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

№ набора	х₁	х₂	х₃	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?

Ответ: ни та ни другая, т.к. первая функция равна нулю на наборах 2 и 6, а вторая - на наборах0, 2, 3 и 6. На этих наборах F=1, что противоречит определению имплиценты.

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

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

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

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

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

Элементарные суммы, которые входят в данную функцию СКНФ, а никакая их собственная часть не входит самостоятельно в виде произведения, называется простыми имплицентами.

Пример: Допустим, что j = x₁ +x₂ +x₃+ и x₂+ входят в F = F(x₁,x₂,x₃,x₄), а x₂и самостоятельно не входят в F. Тогда j не будет простой имплицентой, а x₂+ - будет, т. к. x₂+ÌjÌF, но x₂ËF и ËF.

Теорема № 9. Любую функцию можно представить в виде укороченной КНФ.

Операции склеивания, поглощения и развёртывания в КНФ.

1 Полное склеивание (x+×у)×(x+)= x, т.к. (x+у)×(x+)=х+х +ху+у =х+x×(у+) = x . (по переменной у).

2 Неполного склеивания (x+×у)×(x+)=х×(x+×у)×(x+)

3 Поглощения x×(x+у)=xи x×(x+) = x, т.к.

x×(x+у)=x+ху=х(1+у) и x×(x+) = x+х =х×(1+ )=х

4 Операция развертывания превращает простую имплиценту в дизъюнкцию конституент нуля.

Пример: х+- простая имплицента функции четырёх аргументов х, у, z, u. Тогда

В результате двукратного применения операции развертывания получили СКНФ.

Минимизация логических функций в СКНФ

Теорема Квайна Если в СКНФ логической функции выполнить все операции поглощения, то будет получена сокращенная КНФ для этой функции, т.е. дизъюнкция всех ее простых имплицент.

Особенностью метода Квайна является то, что сначала КНФ преобразовывают к виду СКНФ, а потом выполняют все операции.

Метод минимизации Квайна:

4. В СКНФ выполняются все операции неполного склеивания конституент нуля.

5. Происходит поглощение имплицентами всех конституент единицы, которые участвуют в неполном склеивании.

6. Совершаются операции неполного склеивания и поглощения имплицент с меньшим числом переменных (согласно пунктам 1 и 2).

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

Минимальной ДНФ называется тупиковая ДНФ, имеющая минимум букв.

Импликантная матрица используется для определения минимальной ДНФ. При её помощи находят наборы простых импликант, накрывающих все конституенты, а затем среди этих наборов находят такие, что имеют минимальное число букв. Такие наборы соединяют их знаками Ú.

Для рассмотренного ранее примера имеем: