V,не}, { Λ,Å,не}, { Λ,Å,1}, { Λ,не}, {V,не}.

Иногда удобно строить ФПСБФ при наличии констант, то есть булевых функций "константа 0", "константа 1". Как следует из таблицы, функция "константа 0" несамодвойственна и не сохраняет 1; функция "константа 1" несамодвойственна и не сохраняет 0. Вместе с тем константы являются линейными и монотонными функциями. Отсюда непосредственно (на основании теоремы о функциональной полноте) вытекает следующее: система булевых функций является ослабленно функционально полной, если она содержит хотя бы одну нелинейную и хотя бы одну немонотонную булеву функцию. Примерами ослабленных ФПСБФ могут служить следующие системы:

{ Λ,Å}, { Λ,~}, { V, Å}, {V,~}, {®}

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

Базис может быть избыточным и минимальным.

Минимальный базис – такой, что удаление одной (любой) функции превращает систему ФАЛ в неполную. Иначе говоря, функционально полный базис – это набор операций алгебры логики (и соответствующих им элементов), позволяющих построить любую функцию алгебры логики.

Функционально полным базисом является базис И, ИЛИ, НЕ. В то же время он функционально избыточен. Удаление из него элемента И или ИЛИ превращает его в минимальный базис.

Для примера рассмотрим базис, образованный, например, элементами И и НЕ. В этом базисе реализуем функцию ИЛИ, тем самым докажем функциональную полноту выбранного базиса (рис.14).

.

Минимизация ФАЛ

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

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

Булева функция g(x₁,...,x_n) называется импликантой булевой функции f(x₁,...,x_n), если для любого набора переменных, на котором g=1, справедливо f=1.

Таблица 12

Импликанта g булевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f.

Из примера видно, что импликанты g₃ = x₁x₂ и g₅ = x₂x₃ являются простыми импликантами функции f. Импликанты g₁, g₂, g₄, g₆ не являются простыми, так как их части являются импликантами функции f, например g₁ является частью g₃. Приведем без доказательства два утверждения, полезные при получении минимальной ДНФ.

1. Дизъюнкция любого числа импликант булевой функции f также является импликантой этой функции.

2. Любая булева функция f эквивалентна дизъюнкции всех своих простых импликант. Такая форма представления булевой функции называется сокращенной ДНФ.

Перебор всех возможных импликант для булевой функции f из рассмотренного примера дает возможность убедиться, что простых импликант всего две: g₃ и g₅. Следовательно, сокращенная ДНФ функции f имеет вид

f= g₃ + g₅ = x₁x₂ + x₂x₃.

Как видно из табл. 12, импликанты g₃, g₅ в совокупности покрывают своими единицами все единицы функции f. Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, удаление которых не приводит к изменению значений функции на всевозможных значениях ее переменных. Такие простые импликанты назовем лишними.

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

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

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

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

Метод Квайна

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

На первом этапе выполняется переход от функции, заданной в форме СДНФ, к сокращенной ДНФ. Это основано на использовании следующих соотношений:

1) соотношение неполного склеивания

, где и - две конъюнкции, а F - любое элементарное произведение;

2) соотношение поглощения

.

Справедливость обоих соотношений легко проверяется. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью. Для доказательства достаточно показать, что произвольная простая импликанта р = x_i1x_i2 ... x_in может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания)

по всем недостающим переменным x_ik, ..., x_im исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f, поскольку р - ее импликанта.

В результате выполнения склеивания получается конъюнкция n-1 ранга, а конъюнкции и остаются в исходном выражении и участвуют в сравнении с другими членами СДНФ. Таким образом, удается снизить ранг термов.

Склеивание и поглощение выполняются до тех пор, пока имеются члены, не участвовавшие в попарном сравнении. Термы, подвергшиеся операции склеивания, отмечаются. Неотмеченные термы представляют собой простые импликанты и включаются в сокращенную ДНФ. Все отмеченные конъюнкции ранга n-1 подвергаются вновь операции склеивания до получения термов n-2 ранга и так далее до тех пор, пока количество неотмеченных конъюнкций больше 2. В результате выполнения первого этапа получена сокращенная ДНФ.

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

Для формирования тупиковых ДНФ строится импликантная таблица (матрица), строки которой отмечаются простыми импликантами сокращенной ДНФ, а столбцы − конституентами единицы исходной СДНФ. В строке напротив каждой простой импликанты ставится метка под теми наборами (конституентами единицы), на которых она принимает значение 1. Соответствующие конституенты поглощаются (покрываются) данной простой импликантой.

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

f_СДНФ= V (1,2,5,6,7)=x₁x₂x₃+ x₁x₂x₃+ x₁x₂x₃+ x₁x₂x₃+ x₁x₂x_3.

^{1 2 3 4 5}

Выполним операцию склеивания:

1 – 3 (x₁) x₂x₃ 1

2 – 4 (x₁) x₂x₃ 2

3 – 5 (x₂) x₁x₃ 3

4 – 5 (x₃) x₁x₂ 4

В результате выполнения первого шага склеивания получаем четыре новые конъюнкции, простых импликант не выявлено. Полученные конъюнкции более не склеиваются и образуют сокращенную ДНФ.

f_{сокр СДНФ}=x₂x₃+ x₂x₃+ x₁x₃+ x₁x₂ .

Для выявления обязательных простых импликант и формирования на их основе минимального покрытия строится импликантная таблица (табл. 13). В строках импликантной таблицы записываются простые импликанты, а в столбцах − конституенты единицы. Звездочка ставится, если простая импли-канта покрывает конституенту.

Таблица 13

		x1x2x3	X1x2x3	x1x2x3	x1x2x3	x1x2x3
	x2x3	*		*
	x2x3		*		*
	x1x3			*		*
	x1x2				*	*

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