Постановка задачи минимизации

Министерство образования и науки

Российской Федерации

 

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

Национальный исследовательский ядерный университет «МИФИ»

 

Волгодонский инженерно-технический институт – филиал НИЯУ МИФИ

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К выполнению индивидуального домашнего задания

(контрольной работы)

по курсу

«ДИСКРЕТНАЯ МАТЕМАТИКА»

для студентов специальностей:

230201 «Информационные системы и технологии»

220301 «Автоматизация технологических процессов и производств»

всех форм обучения

 

 

Волгодонск

 

УДК 681.3 (075.8)

Рецензент д.т.н., профессор В.В. Кривин

 

 

Составители: ст. преп. Цуверкалова О.Ф., ст. преп. Лифанская Л.И.

 

Метод. указ. к выполнению индивидуального домашнего задания (контрольной работы) по дисциплине «Дискретная математика» /ВИТИ НИЯУ МИФИ. Волгодонск, 2010. 26 с.

 

Предназначены для студентов очной, очно-заочной и заочной формы обучения специальности 230201 – Информационные системы и технологии, 220301 – Автоматизация технологических процессов и производств

 

 

ã ВИТИ НИЯУ МИФИ, 2010

ã О.Ф. Цуверкалова, 2010

 

ВВЕДЕНИЕ

Настоящие методические указания содержат краткое изложение основ булевой (двоичной) логики, а также варианты и пример выполнения индивидуального домашнего задания. Освоение изложенного материала поможет студентам при изучении таких курсов как «Информатика», «Архитектура ЭВМ» и др.

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

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

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

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

 

Рекомендуемая литература:

1. Цуверкалова О.Ф. Курс лекций по дисциплине «Дискретная математика»

2. Спирина М.С., Спирин П.А. Дискретная математика. М.: Издательский центр «Академия», 2004. – 368 с.

3. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. – 304 с.

4. Самсонов Б.Б., Плохов Е.М., Филоненков А.И. Компьютерная математика (основание информатики). – Ростов-на-Дону: «Феникс», 2002 г. – 512 с.

5. Шапорев С.Д. Математическая логика. – СПб.: «БХВ-Петербург», 2005, 416 с.

 

Методические указания

Логические функции

Пусть имеется функция, заданная на некотором множестве М. Функция называется логической, если она принимает значения в конечном множестве N. Если множество N содержит п элементов, то логическая функция называется
п -значной. Перечень всех символов, соответствующих области значений логической функции, называется алфавитом, а сами элементы множества N – буквами этого алфавита. Логическая функция называется однородной, если её аргументы принадлежат тому же множеству, что и значение функции. Однородная функция двух переменных может быть задана таблицей соответствия (матрицей), строки и столбцы которой соответствуют буквам алфавита. Таким образом можно определять функции одной и двух переменных.

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

Число всевозможных булевых функций п переменных быстро возрастает с увеличением п (при п = 3 оно равно 256, а при п = 5 превышает 4 миллиарда). Но функции одной и двух перемен­ных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при п = 2).

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

 

Таблица 1 – Булевы функции одной переменной

Две функции = 0 и = 1 представляют собой функции-константы (тождественный ноль и тождественная единица), так как они не изменяют своих значений при изменении аргумента. Функ­ция = х повторяет значения переменной х и потому просто сов­падает с ней.

Единственной нетривиальной функцией является , назы­ваемая отрицанием или инверсией. Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

Все 16 функций двух переменных приведены в табл. 2, где указаны условные обозначе­ния, названия и значения функции (в скобках даны встречающиеся в литературе варианты).

Таблица 2 - Булевы функции двух переменных

					Обозначение	Название
						Константа 0 (тождественный 0)
						Конъюнкция (логическое «и», произведение)
						Отрицание импликации
						Повторение первого аргумента
						Отрицание обратной импликации
						Повторение второго аргумента
						Сумма по модулю два (антиэквивалентность, неравнозначность)
						Дизъюнкция (логическое «или», логическая сумма)
						Стрелка Пирса (отрицание дизъюнкции, логическое «не-или»)
						Эквиваленция (равнозначность)
						Отрицание (инверсия) второго аргумента
						Обратная импликация
						Отрицание (инверсия) первого аргумента
						Импликация (следование)
						Штрих Шеффера (отрицание конъюнкции, логическое «не-и»)
						Константа 1 (тождественная 1)

 

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

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

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

- коммутативность
- ассоциативность
- дистрибутивность
- свойства констант
- свойства отрицания
-закон двойного отрицания
- законы де Моргана
- законы идемпотентности
- законы поглошения

Использование тождеств существенно упрощает запись логических формул.

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

На основе законов де Моргана выводится следующее положение: если и - двойственные формулы, то равносильна . Отсюда следует, что

=

т. е. двойственная формула выражается как отрицание формулы, полученной из исходной замещением каждой переменной ее отри­цанием. Таблица соответствия двойственной функции получается заменой аргументов и значений в исходной функции на противополож­ные, т. е. 0 заменяется на 1, а 1 - на 0. Если формулы и равносильны, то и двойственные им формулы и также равносильны.

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

Нормальные формы

Дизъюнктивная (конъюнктивная) нормальная форма - это дизъюнкция (конъюнкция) конечного числа различных членов, каждый из которых представляет собой конъюнкцию (дизъюнкцию) отдельных переменных или их отри­цаний, входящих в данный член не более одного раза.

Функция приводится к нормальной форме следующим путем:

1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным;

2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций);

3) полученное выражение упрощается и соответствии с тождествами и ( и ).

Пример:

- дизъюнктивная нормальная форма (ДНФ).

- конъюнктивная нормальная форма (КНФ).

Члены дизъюнктивной (конъюнктивной) нормальной формы, представляющие собой элементарные конъюнкции (дизъюнкции) k букв, называют минитермами (макстермами) k-го ранга. Так, в приведенных выше формах ху - минитерм второго ранга, хуz - минитерм третьего ранга, а - макстерм второго ранга.

Если исходная формула содержит другие операции, то они предварительно выражаются через дизъюнкцию, конъюнкцию и отри­цание, например:

Пример:

Если в каждом члене нор­мальной формы представлены все переменные (либо в прямом, либо в инверсном виде), то она называется совершенной нормальной формой.

Всякая нормальная форма может быть приведена к совершенному виду следующим образом. Если какой-либо член j дизъюнктивной (конъюнктивной) нормаль­ной формы не содержит переменной х, то она вводится тождест­венным преобразованием j = j() = j х Ú j (соответ­ственно j = j Ú =(j Ú х)(j Ú )).
В силу тождеств j Ú j = j и jj = j одинаковые члены, если они появляются, заменяются одним таким членом.

Можно показать, что любая булева функция, не являющаяся тождественным нулем (единицей), имеет одну и только одну совер­шенную дизъюнктивную (конъюнктивную) нормальную форму.

Продолжая второй пример, приведем данную функцию к совершенной дизъюнктивной нормальной форме (СДНФ):

Приведение к совершенной конъюнктивной нормальной форме (СКНФ) иллюстрируется следующим при­мером:

Для совокупности переменных выражение называют конституентой единицы, а выражение - конституентой нуля ( означает либо , либо ). Данная конституента единицы (нуля) обращается в единицу (нуль) только при одном соответствую­щем ей наборе значений переменных, который получается, если все переменные принять равными единице (нулю), а их отрицания - нулю (единице). Например, конституенте единицы соот­ветствует набор (1011), а конституенте нуля - набор (1001).

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

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

Пример. Функции, заданной таблицей

соответствуют совершенные нормальные формы:

Полученные выражения можно преобразовать к другому виду на основании свойств булевой алгебры.

 

1. 3 Алгебра Жегалкина

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

- коммутативность х + у = у + х; ху = ух;

- ассоциативность х + (у + z) = (х + у) + z; х(уz) = (ху)z;

- дистрибутивность умножения относительно сложения х(у + z) = ху + хz;

- свойства констант. ; ;

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

- закон приведения подобных членов при сложении х + х =0;

- закон идемпотентности для умножения хх = х.

Таким образом, в формулах алгебры Жегалкина, как и в буле­вой алгебре, не могут появляться коэффициенты при переменных и показатели степени. Существую следую­щие соотношения:

Первые два тождества позволяют перейти от любой формулы булевой алгебры к соответствующей ей формуле алгебры Жегал­кина, а с помощью третьего тождества осуществляется обратный переход.

Пример.

Через операции алгебры Жегалкина можно выразить все другие булевы функции:

.

Любая булева функция приводится к каноническому многочлену, члены которого не содержит числовых коэффициентов и линейны относительно любой из переменных (переменные входят только в первой степени). Действительно, если привести данную функцию к совершенной нормальной форме и заменить все дизъюнкции через суммы по модулю 2, а отрицание переменных представить в соответствии с тождеством , то после раскрытия скобок получим некоторое алгебраическое выражение. Оно приводится к канониче­скому многочлену на основе соотношений х + х = 0 и хх = х. Такое представление всегда возможно и единственно (с точностью до по­рядка расположения членов).

Пример.

(1 + х + у) (1 + ху) + (х + ху) у = 1 + х + у + ху + хху + уху + ху + хуу =

= 1 + х + у + ху + ху + ху + ху + + ху = 1 + х + у + ху.

Так как эта формула является тождественной единицей, то она невыполнима.

Преимущество алгебры Жегалкина состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций, используя опыт преобразования обычных алгебраических выраже­ний. Ее недостаток по сравнению с булевой алгеброй - сложность формул, что особенно сказывается при значительном числе перемен­ных, например:

х Ú у Ú z = х + у + z + ху + хz + уz + хуz.

Контактные схемы

В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей х ₁ и x ₂. Ключи управляются кнопками с двумя состояния­ми: кнопка нажата (1) и кнопка отпущена (0). Если в исходном со­стоянии ключ разомкнут, то при нажатии кнопки он замыкается. Ключ может быть сконструирован и так, что в исходном состоянии он замкнут, тогда нажатие кнопки означает его размыкание, т. е. приводит к противоположному результату. Поэтому нормально за­мкнутые ключи обозначим через и .

При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х ₁ и x ₂,а со­стояние лампочки - со значением функций этих переменных.

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

а)

б)

в)

Рисунок 1

 

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

 

а)

б)

Рисунок 2

 

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

 

Рисунок 3

 

Задача анализа контактной схемы состоит в построении соответствующей ей булевой функции. Для параллельно-последовательных схем эта задача решается на основе того, что параллельное соединение контактов соответствует дизъюнк­ции, а последовательное соединение — конъюнкции переменных, которыми эти контакты обозначены в схеме. Например, для двух­полюсной контактной схемы (рис. 4)

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

Интересно отме­тить, что эта функция реализует операцию сложения по модулю 2 трех двоичных переменных, т. е. у = х ₁ + х ₂+ х ₃,в чем можно убедиться по таблицам соответствующих функций.

 

Рисунок 4

Рисунок 5

 

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

Пусть, например, функция задана таблицей соответствия, приве­денной ниже.

На основе ее в совершенной дизъюнктивной нор­мальной форме строится схема в виде параллельного соединения ветвей, каждая из которых представляет собой последовательное соединение контактов, соответствующих переменным конституент единицы (рис. 6а).

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

Этому выражению соответствует схема рис. 6б, которая со­держит на два контакта меньше. Еще проще мостиковая схема (рис. 5), которая реализует ту же функцию.

 

а)

б)

Рисунок 6

 

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

Логические схемы

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

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

Таблица 3 - Логические элементы, реализующие булевы функции

Функция	Нормальная форма	Контактная схема	Графическое изображение элемента	Название элемента
Отрицание				Инвертор
Конъюнкция				Совпадение
Дизъюнкция				Разделение
Импликация				Разделение с запретом
Эквиваленция				Равнозначность
Отрицание импликации				Совпадение с запретом
Сумма по модулю 2				Неравнозначность
Штрих Шеффера				Разделение с двумя запретами
Стрелка Пирса				Совпадение с двумя запретами

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

 

а)

б)

Рисунок 7

Корректно построенные схемы должны удовлетворять следующим условиям:

1) не допускать замкнутых контуров, которые могут привести к неоднозначности сигналов на входах элементов;

2) любой вход элемента должен быть связан только с одним входом схемы или выходом другого элемента;

3) выходы элементов, не являющиеся выходами схемы и не связанные со входами других элементов, считаются лишними и исключаются из схемы.

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

Как было показано ранее,любая булева функция представима в совершенной нормальной форме (дизъюнктивной или конъюнктивной). Более того, такое представление является первым шагом перехода от табличного задания функции к её аналитическому выражению. В дальнейшем будем исходить из дизъюнктивной формы, а соответствующие результаты для конъюнктивной формы получаются на основе принципа двойственности.

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

Многомерный куб

Каждой вершине n-мерного куба, можно поставить в соответствии конституенту единицы. Следовательно, подмножество отмеченных вершин является отражением на n–мерном кубе булевой функции от n переменных в совершенной дизъюнктивной нормальной форме. На рис. 8 показано такое отражение для функции .

Для отображения функции от n переменных, представленной в любой дизъюнктивной нормальной форме, необходимо установить соответствие между её минитермами и элементами n-мерного куба.

Минитерм -го ранга можно рассматривать как результат склеивания двух склеивания двух минитермов n-го ранга (конституент единицы), т.е. . На n-мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты , соединяющим эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом, минитермам -го порядка соответствует рёбра n-мерного куба. Аналогично устанавливается соответствие минитермов -го порядка граням n-мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).

Элементы n-мерного куба, характеризующиеся s измерениями, называют s-кубами. Так, вершины являются 0-кубами, рёбра – 1-кубами, грани – 2-кубами и т.д. Обобщая приведённые рассуждения, можно считать, что минитерм -го ранга в дизъюнктивной нормальной форме для функции n переменных отображается s-кубом, причём каждый s-куб покрывает все те s-кубы низшей размерности, которые связаны с его вершинами. В качестве примера на рис.9 дано отображение функции трёх переменных . Здесь минитермы и соответствуют 1-кубам , а минитерм отображается 2-кубом ().

 

Рисунок 8 Рисунок 9

 

Итак, любая дизъюнктивная нормальная форма отображается на n-мерном кубе совокупностью s-кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность s-кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим s-кубам минитермов является выражением данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность s-кубов (или соответствующих им минитермов) образует покрытие функции.

Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число s-кубов которого было бы поменьше, а их размерность s - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием. Например, для функции, представленной на рис. 8, покрытие на рис.10,а соответствует неминимальной форме , а покрытия на рис. 10,б и в – минимальным формам и .

а)

б)

в)

Рисунок 10

Карты Карно

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

 

Рисунок 11

 

Как и в обычных таблицах соответствия, клетки наборов, на которых функция принимает значение 1, заполняется единицами (нули обычно не вписывают, им соответствуют пустые клетки).

Между отображениями функции на n-мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте Карно s-кубу соответствует совокупность 2^s соседних клеток, размещённых в строке, столбце, квадрате или прямоугольнике (с учётом соседства противоположных краёв карты). Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие s-куб, дают минитерм -го ранга, в который входят те переменные, которые сохраняют одинаковые значения на этом s-кубе, причём значениям 1 соответствуют сами переменные, а значениям 0 – их отрицание. Переменные, которые не сохраняют свои значения на s-кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в дизъюнктивной нормальной форме (рис. 12).

Рисунок 12

Комплекс кубов

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

Комплекс кубов функции определяется как объединение множеств всех её s-кубов (s=0, 1,…, n), т.е. , причём некоторые из могут быть пустыми. Для записи s-кубов и минитермов функции от n переменных используются слова длины n, буквы которых соответствуют всем n переменным. Входящие в минитерм переменные называются связанными и представляются значениями, при которых минитерм равен единице (1 для и 0 для ). Не входящие в минитерм переменные являются свободными и обозначаются через х. Например, 2-куб функции пяти переменных, соответствующий минитерму , запишется как (). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице. Очевидно, в записи s-куба всегда имеется s свободных переменных. Если все n переменных свободны, что соответствует n-кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функции, не равных тождественно единице, .

Множество всех s-кубов записывается как совокупность слов, соответствующих каждому s-кубу. Для удобства будем располагать слова s-кубов в столбцы, а их совокупность заключать в фигурные скобки. Например, комплекс кубов, соответствующий представлению функции на трёхмерном кубе (рис. 13, а), выражается как , где

; ;

Для сравнения на рис. 13, б изображён комплекс кубов в принятых обозначениях.

а)

б)

Рисунок 13

Комплекс кубов образует максимальное покрытие функции. Исключая из него все те s-кубы, которые покрываются кубами высшей размерности, получаем покрытия, соответствующие тупиковым формам. Так, для рассматриваемого примера (рис. 13) имеем тупиковое покрытие

которое соответствует функции . В данном случае это покрытие является и минимальным.

Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов , а операция конъюнкции - пересечению комплексов кубов . Отрицанию функции соответствует дополнение комплекса кубов, т.е. , причём определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и алгеброй множеств, представляющих комплексы кубов.

Постановка задачи минимизации

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

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

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

Куб сокращённого покрытия, который покрывает вершины данной функции, не покрываемые никакими другими кубами, не может оказаться избыточным и всегда войдёт в минимальное покрытие. Такой куб, как и соответствующая ему импликанта, называют экстремалью (существенной импликантой), а покрываемые им вершины – отмеченными вершинами. Множество экстремалей образует ядро покрытия. Ясно, что при переходе от сокращённого покрытия к минимальному прежде всего следует выделить все экстремали. Если множество экстремалей не образует покрытия, то оно дополняется до покрытия кубами из сокращённого покрытия.

Приведённые определения иллюстрируются на рис. 10, где сокращённое покрытие (рис. 10, а) и минимальные покрытия (рис. 10, б) и (рис.10, в) выражаются следующим образом:

; ;

Сокращённая форма представляет собой дизъюнкцию четырёх простых импликант, т.е. . Экстремалями являются простые импликанты и , которым соответствуют 1-кубы (10х) и (01х), а отмеченные вершины – и или соответственно (100) и (010).

1.10 Метод Квайна – Мак – Класки

Этот метод используется в случаях, когда функция задана в дизъюнктивной совершенной нормальной форме (или таблицей соответствия). Приведение к сокращённой форме осуществляется последовательным применением операции склеивания , где - конъюнкции переменных отличных от . Множеству конституент единицы, представленных в исходной форме, соответствует совокупность 0-кубов , а операции склеивания – объединение двух 0-кубов, которые отличаются только одной координатой. Результатом такого склеивания является 1-куб, в котором различные координаты исходных 0-кубов замещены символом . Сравнивая попарно все 0-кубы, получаем множество 1-кубов . Применяя к операцию склеивания, находим множество 2-кубов и т.д. Этот процесс продолжается до тех пор, пока получаемое из очередное не окажется пустым множество. В результате множество преобразуется в комплекс кубов , причём .

Для выделения из множества простых импликант при каждой операции склеивания, необходимо отмечать каким либо знаком (например, меткой ) те кубы, которые объединяются в кубы высшей размерности. Очевидно, неотмеченные кубы и образуют множество простых импликант . Чтобы уменьшить число сравниваемых пар при операции объединения целесообразно разбить множество на классы, в каждом из которых содержатся s-кубы с одинаковым числом единиц (или нулей), и упорядочить эти классы по возрастающему числу единиц. Так как объединяться могут только такие два s-куба, число единиц, в которых точно на одну больше или меньше, то достаточно ограничиться попарным сравнением s-кубов одного класса с s-кубами соседнего класса.

На втором шаге при извлечение экстремалей и образование минимального покрытия используется таблица покрытий. Её строки соответствуют простым импликантам, а столбцы – конституентам единицы дизъюнктивной совершенной нормальной формы данной функции, которые представляются 0-кубами (вершинами) комплекса кубов. В клетку таблицы записывается метка, если простая импликанта в данной строке покрывает вершину в данном столбце. Экстремалям соответствуют те строки таблицы, которые содержат единственную метку в каком-либо столбце. Удаляя строки экстремалей и все столбцы, в которых эти строки имеют метки, получаем более простую таблицу. На основе это