Карты Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

 

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

• Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули.

Алгоритм минимизации по методу карт Карно:

... Смотреть решение »

Метод квайна (Куайна)

• Определение. Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.
• Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.
• Всякий импликант функции f есть часть функции f.
• Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.
• Определение.Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.
• Утверждение. Всякая функция f реализуется своей  сокращенной ДНФ.
• Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
• Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.

Алгоритм Куайна построения сокращенной ДНФ
1.    Получить СДНФ функции.
2.    Провести все операции неполного склеивания.
3.    Провести все операции поглощения.

Пример. Минимизировать функцию f=1111010010101111.
Решение.
1.   ... Смотреть решение »

Двойственные функции

• Определение. Двойственной для функции f(x1, x2, …, xn) называется функция$f^*(x_1, x_2,..., x_n)=\overline{f\left ( \bar{x_1}, \bar{x_2},... \bar{x_n} \right )}$

Пример. Построить функцию, двойственную данной:

$1.\,  f=x\vee y;$
$2. \, f=x\rightarrow y.$

Решение.

$1. f^*=\overline{\bar{x}\vee \bar{y}}=\bar{\bar{x}}\wedge\bar{\bar{y}} ;$
$2. f^*=\overline{\bar{x}\rightarrow \bar{y}}=\overline{\bar{\bar{x}} \vee  \bar{y}}=\bar{\bar{\bar{x}}}\wedge \bar{\bar{y}}=\bar{x}\wedge y.$

• Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.
• Утверждение. Если функция f(x1, x2, …, xn) самодвойственна, то функция $\bar{f}  тоже самодвойственна.
• Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.
• Противоположными называются те наборы, которые в сумме дают двоичный код числа (2ⁿ-1).

Пример. Выяснить являются ли функции самодвойственными:

$1.\,  f=\left ( \bar{x} \approx y\right )\rightarrow \bar{z};$
$2\, f ... Смотреть решение »