Алгоритм «ниирта» графической минимизации булевых функций от 4-х и менее переменных.

1. Заполнить карту Карно (КК) нулями и единицами в соответствии с таблицей истинности или заданным алгебраическим выражением.

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

3. Каждому прямоугольнику Карно соответствует одна импликанта (логическое слагаемое), причём если в границах прямоугольника Карно какая-либо переменная принимает значения как 0, так и 1, то эта переменная склеивается, т.е. удаляется из импликанты.

Под прямоугольником Карно (этот термин пришлось ввести в 1977г.) для не более чем от 4-х аргументов, можно понимать любую, в том числе и разорванную, симметричную фигуру покрытия, количество клеток (элементарных прямоугольников Карно) в которой составляет целую степень двойки: 1, 2, 4, 8. Все клетки ПК являются соседними, т.е. закодированы соседними кодами. Два кода называются соседними, если они отличаются друг от друга только в одном разряде. Например, коды 1010 и 1011 являются соседними.

На нижеприведённом рисунке даны примеры КК и прямоугольников Карно для различного числа аргументов.

На КК для 4-х переменных представлены два прямоугольника Карно, один из которых (Р) является разорванной фигурой покрытия. На КК для 6 переменных изображены прямоугольники Карно A – G, K, M, N, большинство из которых также являются разорванными фигурами покрытия. Общее для всех свойство - симметричность по Лобанову [2 - 4], необходимое и достаточное условие для определения ПК.

В современной логике появились попытки представить ПК просто фигурой покрытия с 2ⁿ клетками КК. Пример фигур покрытия, содержащих 2³ клеток КК и не являющихся прямоугольниками Карно, представлен на следующем рисунке. Фигуры М и N не обладают симметричностью по Лобанову.

 

 

 

Решение задачи 1.1 с помощью карты Карно представлено на рисунке.

Из карты Карно получено соотношение:

f = x₄x₁ + x₄x₂ + x₄x₃ + x₃x₂x₁

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

f = x₄(x₁ + x₂ + x₃) + x₃x₂x₁

Смысл скобочной формулы прост: за абитуриента должны проголосовать либо все 3 члена комиссии, либо хотя бы один из них, но совместно с председателем.

Формы задания булевых функций.

Об одной форме задания булевых функций мы уже говорили - это таблица истинности. Иногда применяется более компактная запись, использующая двоичные, восьмеричные, десятичные или шестнадцатеричные эквиваленты наборов. Это так называемые обобщённые коды. Например, набор x₄x₃x₂’x₁’ может быть представлен обобщённым двоичным кодом 1100, десятичным эквивалентом которого является число 12. Удобнее всего 8-чные и 16-чные коды. Автором создана Паскаль-программа синтеза псевдослучайных кодов для задания произвольных булевых функций при проведении семинаров или контрольных работ. Эту программу можно разработать самостоятельно или найти её на сайте http://logicrus.ru [7].

Поскольку мы будем работать с функциями не более чем от 4-х переменных, то нам пригодится таблица перевода 10-чисел от 0 до 15 в двоичные коды.

 

 

Десятичное число	Двоичное число	Десятичное число	Двоичное число

 

Задание 1.

Найти минимальную форму полностью определённых булевых функций, заданных 10-чными рабочим наборами (число в скобках указывает количество переменных):

1-1) РН(4) = 0, 1, 5, 7 - 9, 13, 15

1-2) РН(4) = 4, 6, 8, 10, 13

1-3) РН(4) = 1 - 8

1-4) РН(4) = 7 - 15

1-5) РН(4) = 3 – 15

1-6) РН(3) = 1, 3, 5, 7