Минимизация логических (переключательных) функций

Два способа минимизации:

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

2. Минимизация с использованием карт Карно.

Примечание по первому методу:

Пусть дано некоторое логическое выражение в универсальном логическом базисе. Тогда мы действуем с этим выражением следующим образом:

- используем все те законы для раскрытия скобок и приведения подобных слагаемых, которые нам известны из курса арифметики, работая с логическим умножением и логическим сложением так же, как мы умеем это делать с соответствующими арифметическими операциями;

- вспоминаем о том, что для логических сложения и умножения справедливы обе дистрибутивности, т.е. не только дистрибутивность умножения относительно сложения, но и дистрибутивность сложения относительно умножения;

- вспоминаем законы поглощения и склеивания;

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

Относительно второго метода:

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

47. Минимизация переключательных функций с помощью СДНФ.

Пусть s(sigma) - параметр, равный 0 или 1. Введем обозначение

| x, если s=1,

x^s=|

| ~x, если s=0.

Тогда x^s=1, если x=s и x^s=0, если x=/=s (это легко проверить

подстановкой значений x,s in {0,1}).

Теорема Шеннона. Любая переключательная функция f(x1,...,xn) может

быть представлена в следующем виде:

f(x1,...,xk,xk+1,...,xn)=\/ x1^s1*...xk^sk*f(s1,...,sk,xk+1,...xn),

s1,...,sk

где k<=n, а дизъюнкция берется по всем 2^k наборам значений переменных

x1,...,xk. Это равенство называется РАЗЛОЖЕНИЕМ ПО ПЕРЕМЕННЫМ

x1,...,xk.

### n=4, k=2.

Разложение имеет вид:

f(x1,x2,x3,x4)=~x1~x2*f(0,0,x3,x4) \/ ~x1 x2*f(0,1,x3,x4) \/

x1~x2*f(1,0,x3,x4) \/ x1 x2*f(1,1,x3,x4).

Доказательство. Подставим в обе части равенства произвольный набор

всех переменных a1,..,ak,ak+1,..,an. Так как x^s=1 только когда x=s,

то среди 2^k конъюнкций x1^a1*..xk^ak в правой части в единицу обра-

тится только одна - та, в которой x1=a1,...,xk=ak, все остальные конъ-

юнкции будут равны 0. Поэтому получим:

f(a1,...,an)=a1^a1*...ak^ak*f(a1,...,ak,ak+1,..an)=f(a1,...,an), т.е.

тождество.

При k=n разложение принимает вид:

f(x1,...,xn)=\/ x1^s1*...xn^sn*f(s1,...,sn),

s1,...,sn

которое для f(x1,...,xn)=/=0 может быть преобразовано к виду

f(x1,...,xn)=\/ x1^s1*...xn^sn*f(s1,...,sn)=\/ x1^s1*...xn^sn,

s1,...,sn s1,...,sn

f(s1,...,sn)=1 f(s1,...,sn)=1

где дизъюнкция берется по всем наборам s1,...,sn, на которых функция

обращается в 1. Такое разложение называется СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ

НОРМАЛЬНОЙ ФОРМОЙ (СДНФ).

Свойства СДНФ:

- является дизъюнкцией s>=1 различных конъюнкций ранга n, где s -

число единичных наборов;

- каждому единичному набору s1,...,sn соответствует единственная

конъюнкция всех переменных, в которую xi входит с отрицанием, если

si=0, и без отрицания, если si=1; такая конъюнкция называется КОНСТИ-

ТУЕНТОЙ 1 и обозначается Kl, где l - десятичный эквивалент соответс-

твующего единичного набора;

- для любой ПФ представление в СДНФ единственно (с точностью до

порядка букв и конъюнкций);

- существует взаимно-однозначное соответствие между таблицами

функции и ее СДНФ: каждой конституенте 1 в СДНФ соответствует одна

строка в таблице истинности и одна клетка в карте Карно;

- единственная функция, не имеющая СДНФ - Константа 0.

- для любой ПФ, не являющейся константой 0, можно использовать за-

дание функции в виде списка номеров конституент 1 (единичных наборов):

f=\/1 (i1, i2, i3,..., is)

### ----------------- x2

----------------- x3

00 01 11 10

+--------+--------+--------+--------+

0|f(0,0,0)|f(0,0,1)|f(0,1,1)|f(0,1,0)| f=~x1*~x2*~x3 \/

| 1 | 0 | 1 | 0 | ~x1* x2* x3 \/

+--------+--------+--------+--------| x1*~x2* x3 \/

|1|f(1,0,0)|f(1,0,1)|f(1,1,1)|f(1,1,0)| x1* x2*~x3

| | 0 | 1 | 0 | 1 |

+--------+--------+--------+--------+ f=\/1 (0, 3, 5, 6)

x1

48. Соседние термы и операция склеивания. Контермы, минтермы и макстермы.

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

Например:

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

Конъюнктивным термом (контермом, элементарной конъюнкцией) называется конъюнкция любого числа первичных термов хРр, если каждый первичный терм с индексом р входит в нее не более одного раза. Любой контерм представляет собой функцию п переменных A,-j(j/), которую можно записать в виде Ki3{v)= f[(zpVzP).

где v - (хп,..., xi), ер = О или 1, ер = О или 1; ер < ер - для исключения неоднозначности нумерации контермов; i = еп...е\, j = еп... е\ - двоичные числа.

Xе" V х*р = { ХрР еСЛИ еР = ер * р \ 1, если ер ф ер (ер = ер),

поэтому функция Kij(v) будет представлять собой конъюнкцию г < га первичных термов хрр. Запишем, например, в явном виде контерм Ii\j(i>) трех переменных.

При использовании всех n аргументов для записи алгебраического выражения существует две формы структурных формул.

Совершенная дизъюнктивная нормальная форма (СДНФ) представляет собой дизъюнкцию минтермов.

Минтерм (минимальный терм, конституента единицы) есть логическое произведение всех переменных ПФ для наборов, на которых ПФ принимает значение 1.Если в наборе переменная равна 1, то в минтерм эта переменная входит без инверсии, если равна 0 - то с инверсией. Например, если на наборе x2 = 0, x1 = 1, x0 =1 ПФ принимает значение 1, то соответствующий минтерм m3 для третьего набора будет иметь вид m3 =x1 x0.

Пример: СДНФ для ПФ мажоритарного элемента.

y= m3m5m6m7

Совершенная конъюнктивная нормальная форма (СКНФ) представляет собой конъюнкцию макстермов.

Макстерм (максимальный терм, конституента нуля) есть логическая сумма всех переменных ПФ для наборов, на которых ПФ принимает значение 0. Если в наборе переменная равна 1, то в макстерм эта переменная входит с инверсией, если равна 0 - то без инверсии. Например, если на наборе x2 = 0, x1 = 0, x0 =1 ПФ принимает значение 0, то соответствующий макстерм M1 для первого набора будет иметь вид.

Пример: СКНФ для ПФ мажоритарного элемента.

y =M0M1M2M4 =()()()().

Минтермы (макстермы) называются соседними, если они отличаются формой представления только одной переменной (без инверсии, с инверсией).

49. Способы задания ПФ Диаграммы Вейча (ДВ).