назад

2.4 Минимизация СДНФ


2.4.1 Карты Карно

2.4.2 Метод Квайна-Мак'Класки

2.4.3 Системы функций алгебры логики

Карты Карно

Пусть дана некоторая переключательная функция от четырёх аргументов. Таблица истинности для неё имеет следующий вид:

 

Таблица 1
x1 x2 x3 x4 F(x1,x2,x3,x4)
0 0 0 0 F(0,0,0,0)
0 0 0 1 F(0,0,0,1)
0 0 1 0 F(0,0,1,0)
0 0 1 1 F(0,0,1,1)
0 1 0 0 F(0,1,0,0)
0 1 0 1 F(0,1,0,1)
0 1 1 0 F(0,1,1,0)
0 1 1 1 F(0,1,1,1)
1 0 0 0 F(1,0,0,0)
1 0 0 1 F(1,0,0,1)
1 0 1 0 F(1,0,1,0)
1 0 1 1 F(1,0,1,1)
1 1 0 0 F(1,1,0,0)
1 1 0 1 F(1,1,0,1)
1 1 1 0 F(1,1,1,0)
1 1 1 1 F(1,1,1,1)

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

Очевидно, что 16 значений этой функции, которые она принимает в 16 различных случаях в зависимости от аргументов, можно записать в таблице, состоящей из 4 строк и 4 столбцов, в клетках которой будут размещены исключительно только одни значения функции. Такую таблицу 4x4 назовём преобразованной таблицей.

Способ, установления соответствия между строками исходной таблицы и клетками преобразованной таблицы назовём способом преобразования.

Понятно, что множество клеток преобразованной таблицы соответствует множеству позиций в столбце значений. Способ преобразования таблицы определяет, каким образом осуществляется это соответствие. Этот способ своеобразно как бы заменяет собой тело таблицы истинности. В самом деле, тело таблицы определяет, каким образом при тех или иных значениях аргумента функция принимает значение, стоящее в той или иной позиции столбца значений.

А теперь представим себе, что нам дана не только некоторая переключательная функция от четырёх аргументов, но и некоторое логическое выражение.

  1. Исходная таблица(см. выше).
  2. Преобразованная таблица(см. выше).
  3. Способ преобразования(см. выше).
  4. Строками истинных значений в исходной таблице для некоторого логического выражения называется множество тех строк в теле исходной таблицы истинности, для каждой из которых при этих значениях аргументов это логическое выражение принимает значение логической единицы.
    Важное примечание:
    Речь идёт не о том, что сама функция F(x1,x2,x3,x4) принимает значение логической единицы при значениях аргументов, указанных в этих строках, а всего лишь на всего вот это самое логическое выражение принимает значение логической единицы при значениях аргументов, указанных в этих строках.
  5. Областью истинных значений в преобразованной таблице для некоторого логического выражения называется множество тех клеток в преобразованной таблице истинности, которые соответствуют при данном способе преобразования тем позициям столбца значений исходной таблицы, которые соответствуют строкам истинных значений в исходной таблице для данного логического выражения.

Приведём пример:

Употреблять мы можем в том и только том случае, когда мы имеем некоторую логическую функцию F(x1,x2,x3,x4), заданную своей таблицей истинности, и некоторое логическое выражение. Пусть функция F(x1,x2,x3,x4) задана таблицей 2:


Таблица 2
x1 x2 x3 x4 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

И пусть ещё дано некоторое логическое выражение: G(x1,x2,x3,x4)=x1&x2&x3&( ┐ x4 ), где ( ┐ x4 )- это отрицание аргумента x4.

Исходная таблица:
Таблица 3
x1 x2 x3 x4 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

Преобразованная таблица.
Таблица 4
0 1 1 0
0 0 0 0
0 0 0 0
0 0 0 0


Ясно, что одной и той же исходной таблице может соответствовать много разных преобразованных таблиц. И это- одна из них.

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

    Таблица 5
    F(0,0,0,0) F(0,0,0,1) F(1,0,0,0) F(0,0,1,1)
    F(0,1,0,0) F(0,1,0,1) F(0,1,1,0) F(0,1,1,1)
    F(0,0,1,0) F(1,0,0,1) F(1,0,1,0) F(1,0,1,1)
    F(1,1,0,0) F(1,1,0,1) F(1,1,1,0) F(1,1,1,1)


    Это и называется способом преобразования таблицы
    Таких способов много, и это - один из них. Действительно, давшись таким способом преобразования, мы получим из исходной таблицы (см. пункт. 1) ту самую преобразованную таблицу (см. пункт 2).F(0,0,0,1)= F(1,0,0,0)=1, а все остальные значения функции равны нулю.
    Следует особо отметить, что одной позиции в столбце значений исходной таблицы соответствует одна и только одна клетка преобразованной таблицы; и одной клетке преобразованной таблицы соответствует одна и только одна позиция в столбце значений исходной таблицы. Т.е. установлено взаимнооднозначное соответствие между позициями в столбце значений исходной таблицы и клетками преобразованной таблицы.

  • Строки истинных значений для логического выражения G(x1,x2,x3,x4)=x1&x2&x3&( ┐ x4 ), где ( ┐ x4 )- это отрицание аргумента x4.

    Для того чтобы найти в исходной таблице истинности для функции F(x1,x2,x3,x4) строки истинных значений для функции G(x1,x2,x3,x4), мы должны определить, при каких аргументах G(x1,x2,x3,x4)=1.
    Выражение G(x1,x2,x3,x4) представляет собой конъюнкцию четырёх аргументов. Конъюнкция истинна тогда и только тогда, когда истинны все её операнды. В данном случае должны быть справедливы следующие формулы:
    x1=1
    x2=1
    x3=1
    ┐ x4 =1
    А это возможно, если:
    x1=1
    x2=1
    x3=1
    x4=0
    Множество строк истинных значений для выражения G(x1,x2,x3,x4) состоит из единственной строки :
          1 1 1 0.
    Это- предпоследняя строка в теле таблицы истинности.

  • Область истинных значений для логического выражения G(x1,x2,x3,x4) должна состоять из такого же количества клеток, сколько строк содержит множество строк истинных значений. А поскольку строк истинных значений у нас всего только одна таковая имеется, то и область истинных значений будет из одной клетки состоять. И где же эта клетка находится? Да там, где у нас размещается в соответствии с нашим способом преобразования позиция из столбца значений для строки
    1 1 1 0,
    т.е. там, где стоит F(1,1,1,0), а это четвёртая строка, третья позиция.

    Преобразовывать таблицу истинности, чтобы получить карту Карно.


    Таблица 6
    x1 x2 x3 x4 F(x1,x2,x3,x4)
    0 0 0 0 F(0,0,0,0)
    0 0 0 1 F(0,0,0,1)
    0 0 1 0 F(0,0,1,0)
    0 0 1 1 F(0,0,1,1)
    0 1 0 0 F(0,1,0,0)
    0 1 0 1 F(0,1,0,1)
    0 1 1 0 F(0,1,1,0)
    0 1 1 1 F(0,1,1,1)
    1 0 0 0 F(1,0,0,0)
    1 0 0 1 F(1,0,0,1)
    1 0 1 0 F(1,0,1,0)
    1 0 1 1 F(1,0,1,1)
    1 1 0 0 F(1,1,0,0)
    1 1 0 1 F(1,1,0,1)
    1 1 1 0 F(1,1,1,0)
    1 1 1 1 F(1,1,1,1)

    А теперь изберём для неё такой способ преобразования, чтобы в преобразованной таблице два последних столбца представляли собой область истинных значений для выражения G1(x1,x2,x3,x4)=x1, два средних столбца представляли собой область истинных значений для выражения G2(x1,x2,x3,x4)=x2, две нижних строки представляли собой область истинных значений для выражения G3(x1,x2,x3,x4)=x3, две средних строки представляли собой область истинных значений для выражения G4(x1,x2,x3,x4)=x4.

    Только для того, чтобы нам не спутать, что областью истинных значений чего является, пометим сами выражения над своими областями истинных значений в виде отрезочков:
    помечаем сверху над таблицей x1 и x2 и слева от таблицы x3 и x4:

                                                                  x2
                                                   ___________________
                                                                                   x1
                                                                   ______________________


    F(0,0,0,0) F(0,1,0,0) F(1,1,0,0) F(1,0,0,0)
    x4 | F(0,0,0,1) F(0,1,0,1) F(1,1,0,1) F(1,0,0,1)
    | | F(0,0,1,1) F(0,1,1,1) F(1,1,1,1) F(1,0,1,1)
    x3 | F(0,0,1,0) F(0,1,1,0) F(1,1,1,0) F(1,0,1,0)

    Как функцию мы задаём таблицей истинности, так мы её можем задать и своей картой Карно.

    Формы бывают двух видов:
    - дизъюнктивная нормальная форма и
    - конъюнктивная нормальная форма.

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

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

    Теорема:

    Пусть некоторая функция от четырёх аргументов F(x1,x2,x3,x4) задана своей картой Карно. И пусть имеется некоторое множество логических выражений:
    G1(x1,x2,x3,x4),
    G2(x1,x2,x3,x4),
    ::::::..
    GN(x1,x2,x3,x4),
    таких, что:

    1. В области истинных значений каждого из этих логических выражений в карте Карно, которой задана функция F(x1,x2,x3,x4), стоят единицы

    2. Во всех клетках карты Карно, которой задана функция F(x1,x2,x3,x4), не принадлежащих области истинных значений ни одной из этих функций стоят нули.

    Тогда для функции F(x1,x2,x3,x4), справедлива следующая формула: F(x1,x2,x3,x4)= G1(x1,x2,x3,x4)+G2(x1,x2,x3,x4)+...+GN(x1,x2,x3,x4).

    Конъюнкция ранга 1 имеет область истинных значений, состоящую из 8 рядом стоящих клеток; Конъюнкция ранга 2 имеет область истинных значений, состоящую из 4 рядом стоящих клеток; Конъюнкция ранга 3 имеет область истинных значений, состоящую из 2 рядом стоящих клеток; Конъюнкция ранга 4 имеет область истинных значений, состоящую из 1 "рядом стоящих" клеток (т.е. из одной клетки).

    Минимизации функции методом карт Карно.
    Итак, пусть некоторая функция задана своей картой Карно. Нам нужно найти как можно меньшее количество выражений
    G1(x1,x2,x3,x4),
    G2(x1,x2,x3,x4),
    ::::::..
    GN(x1,x2,x3,x4),
    представляющих собой логические произведения как можно меньших рангов, причем ни в коем случае ранг ни оного из них не должен быть выше четырёх, удовлетворяющих двум условиям (тем, которые написаны выше; я эти условия продублирую здесь):

    1. В области истинных значений каждого из этих логических произведений в карте Карно, которой задана функция F(x1,x2,x3,x4), стоят единицы.

    2. Во всех клетках карты Карно, которой задана функция F(x1,x2,x3,x4), не принадлежащих области истинных значений ни одного из этих логических произведений, стоят нули.

    В нахождении таких произведений и состоит метод минимизации по картам Карно. Как такие произведения по карте находить?
    8 рядом стоящих единиц - это область истинных значений для конъюнкции ранга 1.
    4 рядом стоящих единицы - это область истинных значений для конъюнкции ранга 2.
    2 рядом стоящих единицы - это область истинных значений для конъюнкции ранга 3.
    1 "рядом стоящую" единицу (т.е. одинокую, обособленную)- это область истинных значений для конъюнкции ранга 4.

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

    Например.

                                                                           x2
                                                                _______________
                                                                                   x1
                                                                   ____________________

    0 0 0 0
    x4 | 1 1 0 0
    | | 0 0 1 1
    x3 | 0 0 1 1

    Всегда начинайте от x1 к x2, x3 и x4 по порядку индекса при переменной. Если единицы, рядом стоящие, не находятся одновременно все в области истинных значений ни для переменной xi (где i=1,2,3,4- последовательно пробегая значения), ни для её отрицания, то переменную xi пропускаем.
    Посмотрите здесь на конкретном примере:
    Для первого произведения мы берём x1 с отрицанием, пропускаем x2, берём x3 с отрицанием и x4 без отрицания.

    Почему пропустили x2? Потому что одна из единиц стоит в области истинных значений для x1, а другая - в области истинных значений для (не x1).

    Второе произведение пусть проверит сам читатель. Таким образом, если здесь всё чисто, то этой карте Карно соответствует функция F(x1,x2,x3,x4)= ┐(x1 )*┐(x3)*x4+x1*x3.

    И ещё одно очень важно замечание: первый и последний столбец- это два рядом стоящих столбца. Точно также верхняя и нижняя строка- это две соседних строки.
    Вот такой пример:

                                                                                   x2
                                                                   _______________
                                                                                   x1
                                                                   ____________________

    0 0 1 0
    x4 | 0 0 0 0
    | | 0 0 0 0
    x3 | 0 0 1 1

    Объединяем здесь верхнюю и нижнюю единицы. Они нам дают x1*x2*(┐x4 ). Объединяем в нижней строке две крайние правые единицы. Они нам дают x1*x3*( ┐ x4 ). Формула для функции: x1*x2*(┐x4 )+ x1*x3*(┐x4 ). Эту же формулу можно переписать так: x1*(x2+x3)*( ┐ x4 ). По карте Карно мы получили тупиковую дизъюнктивную нормальную форму, а после преобразования- тупиковую Конъюнктивную нормальную форму.

    На самом деле можно при помощи карт Карно получить и тупиковую конъюнктивную нормальную форму для функции. Для этого нужно составлять уравнение не для самой функции, а для её отрицания. Что представляет собой карта Карно для отрицания функции? Это карта Карно, получаемая из карты Карно самой функции замещения единиц на нули и нулей на единицы.

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

    Минимизация ФАЛ методом Квайна-Мак-Класски.

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

    В результате реализации данного метода ФАЛ разлагается на простые импликанты. Под простой импликантой функции понимается всякое элементарное произведение, принимающее единичное значение на всех наборах аргументов, что и исходная ФАЛ, при исключении из которого хотя бы одного аргумента, уже не будет выполнятся данное условие.

    Алгоритм Квайна-Мак-Класски формулируется следующим образом: для того, чтобы два числа m и n являлись номерами двух склеивающихся между собой наборов, необходимо и достаточно, чтобы индексы данных чисел отличались на единицу, сами числа отличались на степень числа два и число с большим индексом было больше числа с меньшим индексом.

    Реализацию алгоритма рассмотрим на примере минимизации ФАЛ

    На первом этапе минимизации определяем номера и индексы каждого набора, записывая ФАЛ в виде

    Группируем наборы располагая их в порядке возрастания индексов (таблица 7).


    Таблица 7 - Минимизация ФАЛ методом Квайна-Мак-Класски
    ИндексыНомераРезультат склеивания
    I0001(1)00-1
    0-01
    -001
    0--1
    -0-1
    0--1
    -0-1
     
    II0011(3)
    0101(5)
    1001(9)
    0-11
    -011
    01-1
    10-1
    III0111(7)
    1011(11)

    На следующем этапе производим склеивание различных наборов, руководствуясь приведенной выше формулировкой алгоритма. Подлежащие склеиванию пары чисел указаны стрелками. При склеивании не совпадающие в числах разряды отмечаются прочерками. Например склеивание чисел 0001 и 0011 дает число 00-1. Результат склеивания выписывается в следующий столбец таблицы 7, так же разделяемый на строки с индексами, отличающимися на единицу. После склеивания всех групп первого столбца таблицы переходят ко второму столбцу, вписывая результат склеивания в третий столбец. При объединении наборов второго и последующих столбцов таблицы, возможно склевать только числа содержащие прочерки в одноименных разрядах. Склеивание продолжается до тех пор, пока образование нового столбца станет невозможным.

    По окончании склеивания приступают к построению импликантной таблицы (таблица 8), записывая в нее в качестве простых импликант наборы, содержащиеся в последнем столбце таблицы 7. В качестве простых импликант в таблице 8 так же вписываются наборы из других столбцов таблицы 7, не принимавшие участия в склеивании. Если импликанта, содержащаяся в I-той строке таблицы, составляет некоторую часть конституенты I-го столбца на пересечении I-той строки и I-го столбца ставится символ *. С целью получения минимальной формы ФАЛ из таблицы 8. необходимо выбрать минимальное число строк, чтобы для каждого столбца, среди выбранных строк нашлась хотя бы одна, содержащая в этом столбце символ *.

    Таблица 8 - Импликантная таблица минимизируемой ФАЛ
      
      

    Полученная после минимизации ФАЛ записывается в следующем виде: