Нормальные формы формул алгебры высказываний бывают двух типов: дизъюктивные и конъюктивные, в каждом из этих типов выделен класс совершенных форм.
Алгоритм построения ДНФ:
1. Перейти к булевым операциям.
2. Перейти к формуле с тесными отрицаниями, т.е. к формуле, в которой отрицания находятся не выше, чем над переменными.
3. Раскрыть скобки.
4. Повторяющейся слагаемые взять по одному разу.
5. Применить законы поглощения и полупоглощения.
![]() |
Пример. Найти ДНФ формулы
►
◄
Конъюнктивная нормальная форма (КНФ) – двойственное для ДНФ понятие, поэтому ее легко построить по схеме:
.
![]() |
Пример. Найти КНФ формулы
► ~
~
.◄
Совершенную дизъюнктивную нормальную форму СДНФ можно строить, используя следующий алгоритм:
1. = 1. алгоритма ДНФ
2. = 2. алгоритма ДНФ
3. = 3. алгоритма ДНФ
4. = 4. алгоритма ДНФ
5. Опустить тождественно ложные слагаемые, т. е. слагаемые вида
.
6. Пополнить оставшиеся слагаемые недостающими переменными
7. Повторить пункт 4.
Пример. Найти СДНФ формулы.
► ~
.◄
Для построения СКНФ можно пользоваться следующей схемой:
Пример. Найти СДНФ формулы.
► ~
.◄
Известно (теоремы 2.11, 2.12), что СДНФ и СКНФ определены формулой однозначно и, значит, их можно строить по таблице истинности формулы [1].
►Схема построения СДНФ и СКНФ по таблице истинности приведена ниже, для формулы ~
:
![]() | ![]() | ![]() | ![]() ![]() | |
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. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и булевых множеств, представляющих комплексы кубов.
Представление функции в виде комплексов кубов менее наглядно, однако его важнейшие достоинства состоят в том, что снимаются ограничения по числу переменных и облегчается кодирование информации при использовании вычислительных машин.