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

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

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

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

Пример: Допустим, что 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 × 1 = x. (по переменной у).

2 Неполного склеивания x×у Ú x× = x Úx×у Ú x×

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

x×у Ú x = x (1Úу) = х×1 = х

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

Пример: х×- простая импликанта функции четырёх аргументов х, у, z, u. Тогда В результате двукратного применения операции развертывания получили СДНФ.

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

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

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

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

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

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

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

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

Пример: Найти сокращенную ДНФ для функции .

Решение: Развернем СДНФ для F и пронумеруем конституенты F=.

1 2 3 4 5 6

Затем выполняем операции неполного склеивания.

Номерa склеиваемых конституент

Результат

склеивания

Склеиваемая

переменная

1 –2

1 – 3

2 – 5

3 – 4

4 – 6

5 – 6

Дальнейшее склеивание невозможно и

Произведения входят в начальную F, значит - будут лишними.

Таким образом, сокращенная ДНФ это далеко не всегда минимальная ДНФ, т.к. хоть она и состоит из простых импликант, но среди них могут быть и лишние.

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

Тупиковых функций в общем случае может быть несколько, и они могут иметь разное число букв.

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

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

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