Задания для самостоятельной работы к разд. 4.1.3

1. Получить булевы формулы для функций: , , .

2. С помощью эквивалентных преобразований привести к ДНФ формулу:

;

;

.

3. Представить в виде совершенной ДНФ следующие функции:

; .

4. С помощью преобразований вида , перейти от заданной ДНФ к совершенной, если:

; ; .

5. С помощью соотношений вида преобразовать ДНФ из предыдущей задачи в КНФ.

6. Построить совершенную КНФ для каждой из функций задачи 3.

7. Доказать эквивалентность формул и .

, .

, .

8. Сколько существует линейных функций от переменных?

9. Построить полиномы для функции:

; ;

; ;

; .

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

, , .

11. Для нахождения полинома Жегалкина иногда используют метод неопределенных коэффициентов, состоящий в следующем. Рассматривается полином в виде (4.26) и для каждого набора составляется уравнение . Решение этих уравнений дает коэффициенты полинома . Например, задана логическая функция , ее полином имеет вид

Составим систему уравнений.

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

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

; ;

; .

Разработайте алгоритм построения бинарного графа логической функции заданной в ДНФ.

4.1.4 Минимизация булевых функций

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

Например, функция штрих Шеффера может быть представлена двумя формулами над множеством связок : и . Первой формуле соответствует схема, представленная на рис.4.4, второй – на рис.4.5¹⁾. Схема, соответствующая второй формуле, содержит на один элемент меньше, чем схема, соответствующая первой формуле, следовательно, она более предпочтительна. Задача поиска формулы, соответствующей наиболее простой схеме (задача минимизации логической функции), представляет большой практический интерес.

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

Дадим основные определения.

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

Рангом элементарной конъюнкции называется число переменных в данной конъюнкции.

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

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

Логическая функция называется импликантом функции , если для всякого набора значений аргументов выполнено неравенство . Это условие может быть эквивалентно переписано в виде

.

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

В качестве примера рассмотрим функцию .

Функция является импликантом, ибо

(мы воспользовались соотношением .

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

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

Утверждение. Любая логическая функция эквивалентна дизъюнкции всех своих простых импликантов.

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

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

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

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

Все методы минимизации практически отличаются лишь на первом этапе – этапе получения сокращенной ДНФ. Второй этап - получение минимальной (или одной из тупиковых) ДНФ идентичен для всех методов.

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