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

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

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

Пример: Допустим, что j = x1 x2 x3  и  x2 входят в F = F(x1,x2,x3,x4), а  x2  и    самостоятельно не входят в F. Тогда j не будет простой импликантой, а x2 - будет, т. к.  x2ÌjÌF,  но  x2Ë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. Тогда    В результате двукратного применения операции развертывания получили СДНФ.

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

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

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

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

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

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

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

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

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

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

  1 2       3      4 5      6

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

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

Результат

склеивания

Склеиваемая

переменная

1 –2

1 – 3

2 – 5

3 – 4

4 – 6

5 – 6

xy

yz

x

z

z

x

y

y

z

x

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

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

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

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

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

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

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

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

Постоянные импликанты

Конституенты

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

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

Конъюнктивные нормальные формы.

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

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

Пример: ; ;  будут элементарными суммами, а выражения ;  - нет.

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

Пример: Набор  на котором  равна нулю будет 100, т. к. .

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

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

Теорема № 3. Элементарная сумма всех n переменных, что входят в F, есть конституентой нуля.

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

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

Решение: Так как 17 в двоичной форме записи выглядит как 10001, токонституента нуля -

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

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

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

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

Скачать файл