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

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

Элементами являются конъюнкция или дизъюнкция.

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

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

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

Используют совершенные ДНФИ КНФ

Их особенности: 1.Все элементы члены формы им одинаковый ранг. 2.Элементные члены содержат все логические переменные (имеют полный ранг).

Пример:

СКНФ

X3X2X1F

X1vX2vX3 0 0 0 0 __ __

0 0 1 1 X1&X2 &X3

0 1 0 1 X1 &X2 &X3

0 1 1 1 X1 &X2 &X3

X1vX2vX3 1 0 0 0

X1vX2vX31 0 1 0

X1vX2vX3 1 1 0 0

1 1 1 1 X1 &X2 &X3

Минтермом называется логическая функция которая принимает значение 1 на первом наборе логической переменной.

Макстеры логическая функция которая принимает значение 0 на первом наборе.

Правило записи СДНФ

1. Отмечаем наборы логических переменных на которых функция принимает единичные значения (функция истина).

2. Составляем элементарные конъюнкции для этих наборов по правилу:

Если логическая переменная на этом наборе = 1, то она входит в конъюнкцию так, как она есть.

Если логическая переменная = 0, то она входит с отрицанием.

3. Полученные конъюнкции объединяются операцией дезъюнкции:

В результате получим СДНФ

___ ___ __ __ ___

F=X1 &X2 &X3vX1 &X2 &X3vX1 &X2 &X3vX1 &X2 &X3

Правило записи СКНФ

1. Отмечаем макстерами логические функции.

2. Составление элементов дизъюнкций для каждого отмеченного набора по правилу:

Если переменная =0, то записывается так как есть.

Если переменная =1, то записывается с инверсией.

3. Полученные элементы дизъюнкции объединяют операцией конъюнкции.

___ __ __ ___ ___

F=X1 v X2 v X3 & X1 v X2 v X3 & X1 v X2 v X3 & X1 v X2 v X3

Минимизация логических функций

Цель – получение minформы логической функции.Метод Вейна – Корно

Целесообразно использовать при количестве логических переменных не более четырех.

Используем диаграмму Вейга и Карты Карто.

_ _ _

b b a a a a _

a b 1 1 0 1 1 1 d

ab 1 1 b 1 1

c c _ 1 _ d

c b 1 d

c c

c

Составляется так, что соседние клетки соответствуют состоянию ментермом.

Исходная логическая функция представляется в виде СДНФ. В клетке таблицы, соответствующим минтермом логической функции заносят 1; в оставшиеся клетке 0. В заполненной таблице заключаем в прямоугольный контур все 1, затем записывают минимальную функцию в виде ДНФ.

При определение контура необходимо соблюдать следующие правила.

1. Контур должен быть прямоугольным.

2. Внутри контура должны быть клетки с записанными только 1.

3. Число клеток в контуре должно быть целой степенью двойки.

4. Одни и те же клетки могут входить в различные контуры.

5. При определение контура самая нижняя и верхняя строки а также первый и последний столбец считать соседними.

Для каждого контура записываем элементы конъюнкции, которые объединяем операцией дизъюнкции.

При записи элемента конъюнкции оптимального контура нужно исключить переменные, которые входят в контур в прямом и инверсном виде (используем правило поглощения).

Необходимо стремиться чтобы контуры были как можно >, а их число как можно <.

Пример: _ _ _ _ _ _ _ _ _ _ _ _ _ _

1. F=a&b&c&d v a&b&c&d v a&b&c&d v a&b&c&d v a&b&c&d v a&b&c&d v a&b&c&d = b&c v a&c v a&b&d _ _ _ _ _ _ _ _ _ _ _

2. F=a&b&c v a&b&c v a&b&c v a&b&c v a&bvc=cva&b