Пусть дана некоторая переключательная функция от четырёх аргументов. Таблица истинности для неё имеет следующий вид:
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 назовём преобразованной таблицей.
Способ, установления соответствия между строками исходной таблицы и клетками преобразованной таблицы назовём способом преобразования.
Понятно, что множество клеток преобразованной таблицы соответствует множеству позиций в столбце значений. Способ преобразования таблицы определяет, каким образом осуществляется это соответствие. Этот способ своеобразно как бы заменяет собой тело таблицы истинности. В самом деле, тело таблицы определяет, каким образом при тех или иных значениях аргумента функция принимает значение, стоящее в той или иной позиции столбца значений.
А теперь представим себе, что нам дана не только некоторая переключательная функция от четырёх аргументов, но и некоторое логическое выражение.
Приведём пример:
Употреблять мы можем в том и только том случае, когда мы имеем некоторую логическую функцию F(x1,x2,x3,x4), заданную своей таблицей истинности, и некоторое логическое выражение. Пусть функция F(x1,x2,x3,x4) задана таблицей 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.
Исходная таблица:
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 |
Преобразованная таблица.
0 | 1 | 1 | 0 |
0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 |
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) |
Преобразовывать таблицу истинности, чтобы получить карту Карно.
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:
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.
Теперь ищите минимальное их количество произведений. Потом расписывайте дизъюнкцию этих конъюнкций. Получаете тупиковую дизъюнктивную нормальную форму для функции, которую уже невозможно будет более упростить.
Например.
x20 | 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.
И ещё одно очень важно
замечание: первый и последний столбец- это два рядом стоящих столбца.
Точно также верхняя и нижняя строка- это две соседних строки.
Вот такой пример:
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).
Индексы | Номера | Результат склеивания | ||
I | 0001(1) | 00-1 0-01 -001 | 0--1 -0-1 0--1 -0-1 | |
II | 0011(3) 0101(5) 1001(9) | 0-11 -011 01-1 10-1 | ||
III | 0111(7) 1011(11) |
На следующем этапе производим склеивание различных наборов, руководствуясь приведенной выше формулировкой алгоритма. Подлежащие склеиванию пары чисел указаны стрелками. При склеивании не совпадающие в числах разряды отмечаются прочерками. Например склеивание чисел 0001 и 0011 дает число 00-1. Результат склеивания выписывается в следующий столбец таблицы 7, так же разделяемый на строки с индексами, отличающимися на единицу. После склеивания всех групп первого столбца таблицы переходят ко второму столбцу, вписывая результат склеивания в третий столбец. При объединении наборов второго и последующих столбцов таблицы, возможно склевать только числа содержащие прочерки в одноименных разрядах. Склеивание продолжается до тех пор, пока образование нового столбца станет невозможным.
По окончании склеивания приступают к построению импликантной таблицы (таблица 8), записывая в нее в качестве простых импликант наборы, содержащиеся в последнем столбце таблицы 7. В качестве простых импликант в таблице 8 так же вписываются наборы из других столбцов таблицы 7, не принимавшие участия в склеивании. Если импликанта, содержащаяся в I-той строке таблицы, составляет некоторую часть конституенты I-го столбца на пересечении I-той строки и I-го столбца ставится символ *. С целью получения минимальной формы ФАЛ из таблицы 8. необходимо выбрать минимальное число строк, чтобы для каждого столбца, среди выбранных строк нашлась хотя бы одна, содержащая в этом столбце символ *.
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() |
Полученная после минимизации ФАЛ записывается в следующем виде: