Нормальные формы формул алгебры высказываний бывают двух типов: дизъюктивные и конъюктивные, в каждом из этих типов выделен класс совершенных форм.
Алгоритм построения ДНФ:
1. Перейти к булевым операциям.
2. Перейти к формуле с тесными отрицаниями, т.е. к формуле, в которой отрицания находятся не выше, чем над переменными.
3. Раскрыть скобки.
4. Повторяющейся слагаемые взять по одному разу.
5. Применить законы поглощения и полупоглощения.
Пример. Найти ДНФ формулы
►
◄
Конъюнктивная нормальная форма (КНФ) – двойственное для ДНФ понятие, поэтому ее легко построить по схеме:
.
Пример. Найти КНФ формулы
► ~ ~
.◄
Совершенную дизъюнктивную нормальную форму СДНФ можно строить, используя следующий алгоритм:
1. = 1. алгоритма ДНФ
2. = 2. алгоритма ДНФ
3. = 3. алгоритма ДНФ
4. = 4. алгоритма ДНФ
5. Опустить тождественно ложные слагаемые, т. е. слагаемые вида
.
6. Пополнить оставшиеся слагаемые недостающими переменными
7. Повторить пункт 4.
Пример. Найти СДНФ формулы.
► ~
.◄
Для построения СКНФ можно пользоваться следующей схемой:
Пример. Найти СДНФ формулы.
► ~
.◄
Известно (теоремы 2.11, 2.12), что СДНФ и СКНФ определены формулой однозначно и, значит, их можно строить по таблице истинности формулы [1].
►Схема построения СДНФ и СКНФ по таблице истинности приведена ниже, для формулы ~ :
~ | ||||
1 0 1 0 1 1 0 1 | СДНФ; СКНФ. |
2.2. Задание.
2.2.1 Ниже приведены логические выражения. Максимально упростите выражения своего варианта, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравните ваше упрощенное выражение с исходным.
2.2.2. Выяснить вопрос о равносильности f1 и f 2 путем сведения их к СДНФ (табл. 1).
2.2.3. Найти двойственную функцию для f3 по обобщенному и булевому принципу (табл.1). Сравнить полученные результаты.
№ | f1 | f2 | f3 |
2.3. Контрольные вопросы.
2.3.1. Дайте определение высказывания.
2.3.2. Перечислите основные операции над высказыванием.
2.3.3. Что такое таблица истинности?
2.3.4. Составить таблицы истинности для следующих формул:
~ ~ ;
~ ;
~ ~ ~ ;
~ ~ ~ ~ .
2.3.5. Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак « » в формулах:
;
;
;
;
~ .
2.3.6. Применяя равносильные преобразования, доказать тождественную истинность формул:
;
;
;
.
2.3.7. Найти двойственные формулы:
)
.
2.3.8. Привести к совершенной ДНФ (СДНФ) форме следующие формулы:
~
2.3.9. Привести к совершенной КНФ (СКНФ) форме следующие формулы:
~
~
Лабораторная работа № 3
Тема: «Минимизация булевых функций. Логические схемы»
Цель: Приобретение практических навыков работы с методами минимизации булевых функций.
3.1. Теоретические сведения [1].
Минимальные формы
Как было показано в [1], любая булева функция представима в совершенной нормальной форме (дизъюнктивной или конъюнктивной). Более того, такое представление является первым шагом перехода от табличного задания функции к ее аналитическому выражению. В дальнейшем будем исходить из дизъюнктивной формы, а соответствующие результаты для конъюнктивной формы получается на основе принципа двойственности [1].
Каноническая задача синтеза логических схем в булевом базисе сводится к минимизации булевых функций, т.е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. При каноническом синтезе предполагается, что на входы схемы подаются как сигналы , так и их инверсий .
Формула, представленная в дизъюнктивной нормальной форме, упрощается многократными применением операции склеивания и операции поглощения и (дуальные тождества для конъюнктивной нормальной формы имеют вид: и ). Здесь под и можно понимать любую формулу булевой алгебры. В результате приходим к такому аналитическому выражению, когда дальнейшие преобразования оказываются уже невозможными, т.е. получаем тупиковую форму.
Среди тупиковых форм находится и минимальная дизъюнктивная форма, причем она может быть неединственной. Чтобы убедиться в том, что данная тупиковая форма является минимальной, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.
Пусть, например, функция задана в совершенной нормальной дизъюнктивной форме:
.
Группируя члены и применяя операцию склеивания, имеем .
При другом способе группировки получим:
.
Обе тупиковые формы не являются минимальными. Чтобы получить минимальную форму, нужно догадаться повторить в исходной формуле один член (это всегда можно сделать, так как ). В первом случае таким членом может быть . Тогда . Добавив член , получим: . Перебрав все возможные варианты, можно убедиться, что две последние формы являются минимальными.
Работа с формулами на таком уровне подобна блужданию в потемках. Процесс поиска минимальных форм становится более наглядным и целеустремленным, если использовать некоторые графические и аналитические представления и специально разработанную для этой цели символику.
Многомерный куб
Каждой вершине -мерного куба можно поставить в соответствие конституенту единицы. Следовательно, подмножество отмеченных вершин является отображением на -мерном кубе булевой функции от переменных в совершенной дизъюнктивной нормальной форме. На рис. 3.1 показано такое отображение для функции из п.3.7.
Рис.3.1 Отображение на трехмерном кубе функции, представленной в СДНФ
Для отображения функции от переменных, представленной в любой дизъюнктивной нормальной форме, необходимо установить соответствие между ее минитермами и элементами -мерного куба.
Минитерм ( -1)-го ранга можно рассматривать как результат склеивания двух минитермов -го ранга (конституент единицы), т.е. , На -мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты , соединяющим эти вершины, ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом, минитермам ( -1)-го порядка соответствуют ребра -мерного куба. Аналогично устанавливается соответствие минитермов ( -2)-го порядка - граням -мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).
Элементы -мерного куба, характеризующиеся измерениями, называют -кубами. Так, вершины являются 0-кубами, ребра – 1-кубами, грани – 2-кубами и т.д. Обобщая приведенные рассуждения, можно считать, что минитерм ()-го ранга в дизъюнктивной нормальной форме для функции переменных отображается -кубом, причем каждый -куб покрывает все те -кубы низшей размерности, которые связаны с его вершинами. В качестве примера на рис. 3.2 дано отображение функции трех переменных. Здесь минитермы и соответствуют 1-кубам (), а минитерм отображается 2-кубом ().
Рис.3.2 Покрытие функции
Итак, любая дизъюнктивная нормальная форма отображается на -мерном кубе совокупностью -кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность -кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим -кубам минитермов является выражение данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность -кубов (или соответствующих им минитермов) образует покрытие функции.
Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число -кубов которого было бы поменьше, а их размерность - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием. Например, для функции покрытие на рис. 3.3 соответствует минимальным формам и .
Рис. 3.3 Покрытия функции .
слева – ; справа –
Отображение функции на -мерном кубе наглядно и просто при . Четырехмерный куб можно изобразить, как показано на рис. 3.4, где отображены функция четырех переменных и ее минимальное покрытие, соответствующее выражению . Использование этого метода при требует настолько сложных построений, что теряется все его преимущества.
Рис. 3.4 Отображение функции на четырехмерном кубе
Карты Карно
В другом методе графического отображения булевых функций используются карты Карно, которые представляют собой специально организованные таблицы соответствия. Столбцы и строки таблицы соответствуют всевозможным наборам значений не более двух переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных. Благодаря этому и соседние клетки таблицы по горизонтали и вертикали отличаются значением только одной переменной. Клетки, расположенные по краям таблицы, также считаются соседними и обладают этим свойством. На рис. 3.5 показаны карты Карно для двух, трех, четырех переменных.
Рис. 3.5 Карты Карно для двух, трех и четырех переменных
Как и в обычных таблицах истинности, клетки наборов, на которых функция принимает значение 1, заполняются единицами (нули обычно не вписываются, им соответствуют пустые клетки). Например, на рис. 3.6, а показана карта Карно для функции, отображение которой на четырехмерном кубе дано на рис. 3.4. Для упрощения строки и столбцы, соответствующие значениям 1 для некоторой переменной, выделяются фигурной скобкой с обозначением этой переменной.
а б
Рис. 3.6 Отображение на карте Карно функции четырех переменных
(а) и ее минимального покрытия (б)
Между отображениями функции на n -мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте Карно s -кубу соответствует совокупность 2 соседних клеток, размещенных в строке, столбце, квадрате или прямоугольнике (с учетом соседства противоположных краев карты). Поэтому все положения, изложенные в выше (см. п. многомерный куб), справедливы для карт Карно. Так, на рис. 3.6, б показано покрытие единиц карты, соответствующее минимальной дизъюнктивной форме рассматриваемой функции.
Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие s -куб, дают минитер (n–s) -го ранга, в который входят те (n–s) переменные, которые сохраняют одинаковые значения на этом s -кубе, причем значении 1 соответствуют сами переменные, а значениям 0 – их отрицания. Переменные, которые не сохраняют свои значения на s -кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в дизъюнктивной нормальной форме (крайняя правая является минимальной) (рис. 3.7).
Рис. 3.7 Способы считывания с карты Карно дизъюнктивной нормальной формы булевой функции (слева направо: ; ;
Пример. Получить минимальные формы для функции
Пример. Получить минимальную форму для функции, заданной на карте.
Использование карт Карно требует более простых построений по сравнению с отображением на n -мерном кубе, особенно в случае четырех переменных. Для отображения функций пяти переменных используется две карты Карно на четыре переменные, а для функции шести переменных – четыре таких карты. При дальнейшем увеличении числа переменных карты Карно становятся практически непригодными.
Известные в литературе карты Вейча отличаются только другим порядком следования наборов значений переменных и обладают теми же свойствами, что и карты Карно.
Комплекс кубов
Несостоятельность графических методов при большом числе переменных компенсируется различными аналитическими методами представления булевых функций. Одним из таких представлений является комплекс кубов, использующий терминологию многомерного логического пространства в сочетании со специально разработанной символикой.
Комплекс кубов К(у) функции определяется как объединение множеств Кs(у) всех ее s -кубов (s=0.1,…, n), т. е. , причем некоторые из Кs(у) могут быть пустыми. Для записи s -кубов и минитермов функции от n переменных используются слова длины n, буквы которых соответствуют всем n переменным. Входящие в минитерм переменные называются связанными и представляются значениями, при которых минитерм равен единице (1 для и 0 для ). Не входящие в минитерм переменные являются свободными и обозначаются через . Например, 2-куб функции пяти переменных, соответствующий минитерму запишем как (). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице. Очевидно, в записи s -куба всегда имеется s свободных переменных. Если все n переменных свободны, что соответствует n -кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функций, не равных тождественно единице Ø.
Множество всех s -кубов записывается как совокупность слов, соответствующих каждому s -кубу. Для удобства будем располагать слова s -кубов в столбцы, а их совокупность заключать в фигурные скобки. Например, комплекс кубов, соответствующий представлению функции на трехмерном кубе (рис. 3,10а), выражается как , где
; ; .
Для сравнения на рис. 3.8 изображен комплекс кубов в принятых обозначениях.
Рис. 3.8 Комплекс кубов функции трех переменных (а) и его символическое представление (б)
Комплекс кубов образует максимальное покрытие функции. Исключая из него все те s -кубы, которые покрываются кубами высшей размерности, получаем покрытия, соответствующие тупиковым формам. Так, для рассматриваемого примера (рис. 3.8) имеем тупиковое покрытие
,
которое соответствует функции . В данном случае это покрытие является и минимальным.
Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов , а операция конъюнкции - пересечению комплексов кубов . Отрицанию функции соответствует дополнение комплекса кубов, т. е. , причем определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и булевых множеств, представляющих комплексы кубов.
Представление функции в виде комплексов кубов менее наглядно, однако его важнейшие достоинства состоят в том, что снимаются ограничения по числу переменных и облегчается кодирование информации при использовании вычислительных машин.