Лекция 3 Аналитическое представление булевых функций. Минимизация булевых функций

Холодильник

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

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

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

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

Определение. Конституентной единицы называются функция f(x₁,x₂…x_n) принимающая значение 1 только на единственном наборе. Конституента единицы записывается, как логическое произведение п различных булевых переменных, некоторые из них могут быть с отрицаниями например элементарное логическое произведение является конституентой единицы переменных х₁, х₂, х₃, х₄ принимает значение 1 на единственном наборе 1001, на остальных наборах, эта конституента единицы равна нулю.

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

В более общем виде это можно записать следующим образом:

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

Например. Выпишем СДНФ для функций, заданных таблицей (табл. 2.5)

Таблица 2.5

х1	х2	х3	f

Другая известная форма носит название совершенный конъюнктивной нормальной формы (СКНФ).

Определение. Конетитуенты нуля называется функция, принимающая значение 0 на единственном наборе.

Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента 0.

Например набору 0110 переменных х₁,х₂,х₃,х₄ соответствует конституента нуля СКНФ представляет как конъюнкция конституент нуля, соотвествующих нулевым набором функции.

Например. Для рассмотренных выше функций (Таблица 2.5) СКНФ

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

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

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

Таблица 2.6 Таблица 2.7

	х2
х 1

	х2
х 1

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

Таблица 2.8 Таблица 2.9

	х2	х2
х 1
		х 3	х 3

	х2	х2
х 1
		х 3	х 3

Для приведенных диаграмм характерно следующее:

1) Каждой клетке диаграммы соответствует свой набор;

2) Соседние наборы расположены рядом в строке либо в столбце.

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

Таблица 2.10

	х2	х2
х 1
		х 3	х 3

О паре единиц в правой части диаграммы можно сказать то же самое.

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

Основная литература: 1 [12-45]; 2 [15-38]; 3 [64-75]; 4 [115-164].

Дополнительная литература: 1 [22-59]; 2 [10-56].