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

*********************************************
**  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)         **
*********************************************

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

2. Преобразованная таблица по ТНС (см. выше).

3. Способ преобразования по ТНС (см. выше).

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

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

*********************************************
**  x1  **  x2  **  x3  **  x4  *****  F(x1,x2,x3,x4)  ***
*********************************************
**  0    **  0   **   0    **   0   *****          0                **
**  0    **  0   **   0    **   1   *****          1                **
**  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   *****          0                **
**  1    **  0   **   0    **   0   *****          1                **
**  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&( not x4 ),
где ( not x4 )- это отрицание аргумента x4. Пусть читатель позволит мне и здесь такую слабость- не загружать лишний раз свой сайт лишними рисунками.
А теперь покажем здесь, как употребляется для этого случая терминология нашего сайта:

1. Исходная таблица:
Вот она, родимая:

*********************************************
**  x1  **  x2  **  x3  **  x4  *****  F(x1,x2,x3,x4)  ***
*********************************************
**  0    **  0   **   0    **   0   *****          0                **
**  0    **  0   **   0    **   1   *****          1                **
**  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   *****          0                **
**  1    **  0   **   0    **   0   *****          1                **
**  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                **
*********************************************
2. Преобразованная таблица. 
Ну тут мы с читателем можем немного помухлевать, причем так, как нам вздумается. Главное- расфасовать каким-то образом столбец значений по квадрату 4x4. 
Да много ли ума надо, чтобы записать в квадратике 4x4 четырнадцать нулей и две единицы?
Ну, допустим, мы сделаем вот так вот:

**********************
**  0  **  1  **  1  **  0  **
**  0  **  0  **  0  **  0  **
**  0  **  0  **  0  **  0  **
**  0  **  0  **  0  **  0  **
**********************

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

*************************************************** 
*** 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, а все остальные значения функции равны нулю. 
        Следует особо отметить, что одной позиции в столбце значений исходной таблицы соответствует одна и только одна клетка преобразованной таблицы; и одной клетке преобразованной таблицы соответствует одна и только одна позиция в столбце значений исходной таблицы. Т.е. установлено взаимнооднозначное соответствие между позициями в столбце значений исходной таблицы и клетками преобразованной таблицы.

 4. Строки истинных значений для логического выражения G(x1,x2,x3,x4)=x1&x2&x3&( not x4 ),
где ( not 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
not x4 =1
А это возможно, если:
x1=1
x2=1
x3=1
x4=0
Единственный вариант! Другого просто не дано! Стало быть, множество строк истинных значений для выражения G(x1,x2,x3,x4) состоит из единственной строки :
1 1 1 0.
Это- предпоследняя строка в теле таблицы истинности. Как на зло, в исходной таблице истиннности для функции F(x1,x2,x3,x4) этой строке соответствует логический нуль в столбце значений. Ну и что? Но ведь эта строка называется строкой истинных значений для функции G, а не для функции F !!!

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

      А теперь перейдем к самому красивому и почти самому главному: к тому, как надо преобразовывать таблицу истинности, чтобы получить карту Карно. Простите, за неимением времени я опишу это дело только для функции от четырёх аргументов. Итак:
        Опять пусть нам дана некоторая переключательная функция от четырёх аргументов. Таблица истинности для неё выглядит так:

*********************************************
**  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) *** 
    *      *** F(0,0,0,1) *** F(0,1,0,1) *** F(1,1,0,1) *** F(1,0,0,1) *** 
x4*    **** 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) *** 
            *************************************************** 

      Чтобы было более понятно, сделаем разными цветами:
                                                           x2
                                         ********************
                                                                                x1
                                                           ************************
            *************************************************** 
            *** F(0,0,0,0) *** F(0,1,0,0) *** F(1,1,0,0) *** F(1,0,0,0) *** 
    *      *** F(0,0,0,1) *** F(0,1,0,1) *** F(1,1,0,1) *** F(1,0,0,1) *** 
x4*   **** 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) *** 
            ***************************************************
      Вот мы и получили карту Карно. Да простит меня читатель, что эту таблицу я оформил не в виде рисунка, а в током затрапезном виде. Всё ещё впереди! Просто я заинтриговал посетителей сайта тем, что обещал про карты Карно рассказать. Значит, надо поскорее хоть что-нибудь выдать в этом плане.
      Как функцию мы задаём таблицей истинности, так мы её можем задать и своей картой Карно. (Позвольте предложить читателю два контрольных вопроса: 1. Каких фун4ций это касается? 2.Почему карту Карно можно использовать для этих функций, как однозначный способ задания функции? Будет время, я размещу на сайте ответ и на эти вопросы, и решение задач с файла balda.html, но пока читатель сам пусть потрудится)
      Вот мы и подходим к самому весёлому, ради чего всё это совершается.
      Зачем эта карта нужна? Для минимизации. Дело всё в том, что при помощи карты Карно мы получаем в готовом виде уже тупиковую форму для функции, т.е. такую форму, минимизировать которую уже больше невозможно. 
      Формы бывают двух видов:
- дизъюнктивная нормальная форма и
- конъюнктивная нормальная форма.
    Первая представляет собой логическую сумму 
логических произведений. Напоминаю, что логическая сумма- это дизъюнкция, потому и форма называется дизъюнктивной.
    Вторая представляет собой логическое произведение 
логических сумм. Напоминаю, что логическое произведение- это конъюнкция, потому и форма называется конъюнктивной.
      Другую ещё кое-какую терминологию добавим на сайт потом, а пока позвольте мне этим ограничиться. 
      А теперь я назову одну теорему, но доказывать её, с позволения читателя, я пока не буду.
Теорема.
      Пусть некоторая функция от четырёх аргументов 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 называется сам аргумент.
       Конъюнкцией ранга r называется логическое произведение r аргументов.
       Давайте зададимся таким вопросом: “Какие области истинных значений имеют конъюнкции рангов 1, 2, 3, 4?”
       Ответ так же гениально прост, как и вопрос:
Конъюнкция ранга 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    *** 
    *      ***   1  ***   1   ***   0    ***   0    *** 
x4*    ****   0  ***   0   ***   1    ***   1    *** 
      x3****   0  ***   0   ***   1    ***   1    *** 
            ********************************

     Как тут можно увидеть, здесь имеется два логических произведения, в областях истинных значений которых записаны единицы :
     Две единицы – это для произведения ( not x1 )*( not x3)*x4.
     Четыре единицы – это для произведения x1*x3.
     Даю рецепт. Как быстро написать произведение, область истинного значения которого заполнена единицами:
          Всегда танцуйте от x1 к x2, x3 и x4 по порядку индекса при переменной. Если единицы, рядом стоящие, не находятся одновременно все в области истинных значений ни для переменной xi (где i=1,2,3,4- последовательно пробегая значения), ни для её отрицания, то переменную xi пропускаем.
     Посмотрите здесь на конкретном примере:
     Для первого произведения мы берём x1 с отрицанием, пропускаем x2, берём x3 с отрицанием и x4 без отрицания. 
     Почему пропустили x2? Потому что одна из единиц стоит в области истинных значений для x1, а другая – в области истинных значений для (не x1). 
      Второе произведение пусть проверит сам читатель. А вдруг я ошибся?
     Таким образом, если здесь всё чисто, то этой карте Карно соответствует функция F(x1,x2,x3,x4)= ( not x1 )*( not x3)*x4+x1*x3.
     И ещё одно очень важно замечание: первый и последний столбец- это два рядом стоящих столбца. Точно также верхняя и нижняя строка- это две соседних строки.
Вот такой пример:
 

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

     На самом деле можно при помощи карт Карно получить и тупиковую конъюнктивную нормальную форму для функции. Для этого нужно составлять уравнение не для самой функции, а для её отрицания. Что представляет собой карта Карно для отрицания функции? Это карта Карно, получаемая, химически выражаясь,  из карты Карно самой функции реакцией замещения единиц на нули и нулей на единицы. 
      Получив тупиковую дизъюнктивную нормальную форму для отрицания функции, мы должны применить законы де Моргана и получить тупиковую уже конъюнктивную нормальную форму для самой функции. 
     Вот и всё!
     Но видите, как много у меня получилось? Сам этого не ожидал!
Когда рассказываешь, получается, почему-то короче, а когда пишешь, мысли текут, текут, текут и выходит очень длинно. Ведь я же умудрился рассказать это всё на занятии в десятом классе за 90 минут. И ещё кучу примеров привести. А что здесь? Много и длинно. Да ещё и долго загружается. Да ещё и не всё сказал… Но ждите! Я этот текст причешу, сделаю его более простым и понятным и разобью огроменный файл на несколько маленьких.

наверх