Совершенная дизъюнктивная нормальная форма.

Для начала введём ряд определений.

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

Элементарная конъюнкция, в которую включены все переменные функции, называется основной элементарной конъюнкцией.

Дизъюнкция нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой.

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

Любую логическую функцию можно представить в виде СДНФ.

Рассмотрим пример. Пусть функция дана в виде таблицы истинности (см. таблицу 10).

Таблица 10
X1	X2	Y

Запишем функцию в СДНФ. Для этого производятся следующие действия:

Если переменная равна 0, то она инвертируется. Если единице, то не инвертируется.

Из строки таблицы составляется основная элементарная конъюнкция.

Дизъюнкция полученных выражений составит СДНФ.

Выражение может быть упрощено, т.к. x&1=x, а x&0=0:

Т.е. для получения СДНФ достаточно взять только строки, где Y принимает значение, равное 1.

Совершенная конъюнктивная нормальная форма.

Введём определения по аналогии с предыдущими.

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

Элементарная дизъюнкция, в которую включены все переменные функции, называется основной элементарной дизъюнкцией.

Конъюнкция нескольких элементарных дизъюнкций называется конъюнктивной нормальной формой.

Если все элементарные дизъюнкции являются основными, то выражение носит название совершенной конъюнктивной нормальной формы (СКНФ).

Рассмотрим пример из предыдущего раздела.

СКНФ для него примет вид:

Или после упрощения:

Можно видеть, что для составления СКНФ берутся только строки, где функция принимает значение 0.

Принципы минимизации

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

Возможность поглощения следует из очевидных равенств

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

Исходной информацией для работы с картой Карно является таблица истинности минимизируемой функции. Таблица истинности содержит полную информацию о логической функции, задавая её значения на всех возможных 2^N наборах входных переменных X₁... X_N. Карта Карно также содержит 2^N клеток, каждая из которых ассоциируется с уникальным набором входных переменных X₁... X_N. Значения переменных расположены так, что бы менялась только одна переменная. Идея состоит в том, что если от изменения переменной не зависит значение функции, то она не используется.

На рис 4. представлено преобразование таблицы истинности в карту Карно.

 

Рис 4.

 

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

Принципы склейки

Склейку клеток карты Карно можно осуществлять по единицам (если необходимо получить ДНФ (см. рис 5)) или по нулям (если требуется КНФ (см. рис 6)).

Рис 5

Рис 6

Склеивание.

Склеивать можно только прямоугольные области с числом единиц (нулей) 2ⁿ, где n — целое число. Для карт Карно с числом переменных более четырёх могут получаться более сложные области, о чём будет сказано ниже.

Область, которая подвергается склейке, должна содержать только единицы (нули).

Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой (топологически карта Карно для четырёх переменных представляет собой тор) и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы (нули) они могут быть объединены в квадрат, как показано на рис. 5.

Все единицы (нули) должны попасть в какую-либо область.

С точки зрения минимальности ДНФ (КНФ) число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм. Терм размером 2ⁿ ячеек содержит N–n переменных).

Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию:

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

Построение по картам Карно СДНФ и/или СКНФ.

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

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

1. Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала ( целое число = 0… ) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули (см рис 5);

2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);

3. Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну;

4. Область должна быть как можно больше, а количество областей как можно меньше;

5. Области могут пересекаться;

6. Возможно несколько вариантов покрытия.

Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.

Рассмотрим пример, приведённый на рис 7:

Рис 7

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

Запишем получившуюся функцию.

Сначала красная область. Тут изменяется только одна переменная X3. Значит, она не будет участвовать в создании функции для этой области:

f₁=X₁&X₂&X₄

Аналогично для зелёной и синей.

f₂=(~X₁)&(~X₄)

f₃=(~X₂)&(~X₄)

Итого:

f₀= X₁&X₂&X₄ | (~X₁)&(~X₄) | (~X₂)&(~X₄)

Как можно видеть, получившаяся функция не зависит от X₃.

 

Карты Карно от функции пяти и более переменных.

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

Для функции пяти переменных можно найти выход, если построить 2 карты Карно, приняв одну из переменных сначала за 0, а потом за 1 и наложив их одну на другую. По получившейся трёхмерной карте можно построить минимальную функцию.

Блок-схемы.

При блок-схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий.

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

Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).

Операции обработки данных и носители информации изображаются на схеме соответствующими блоками. Большая часть блоков по построению условно вписана в прямоугольник со сторонами а и b. Минимальное значение а равно 10 мм, увеличение а производится на число, кратное 5 мм. Размер b=1,5 мм. Для отдельных блоков допускается соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в таблице.

Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводится параллельно линиям рамки. Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз. В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков. Из блока (кроме логического) может выходить только одна линия. Логический блок может иметь в качестве продолжения одни из двух блоков, и из него выходят две линии. Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.

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

Если при обрыве линии продолжение схемы находится на этом же листе, то на одном и другом конце линии изображается специальный символ соединитель — окружность диаметром 0,5 мм. Внутри парных окружностей указывается один и тот же идентификатор. В качестве идентификатора, как правило, используется порядковый номер блока, к которому направлена соединительная линия. Если схема занимает более одного листа, то в случае разрыва линии вместо окружности используется межстраничный соединитель. Внутри каждого соединителя указывается адрес — откуда и куда направлена соединительная линия. Адрес записывается в две строки: в первой указывается номер листа, во второй — порядковый номер блока.

Блок-схема должна содержать все разветвления, циклы и обращения к подпрограммам, содержащиеся в программе.

 

Условные обозначения блоков схем алгоритмов

 

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

 

Пример:

Рис 8