Важнейшие теоремы и следствия

Теорема о разложении. Пусть дана функция п переменных.

Для |-й переменной можно произвести разложение и записать.

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

Доказательство. Поскольку в любой конкретной ситуации дискретная переменная принимает одно издвух значений — 1 или 0, то из двух членов в формуле (13) останется один член, тождественно равный исходной функции (12).

Пусть х, = 1, тогда.

1 -/(х" х_ъ …, 1,…, х") + 0 -/(х" х₂,…, 0,…, х") =/(х), так как в первом члене вместо х, подставлен I.

Пусть X/ = 0, тогда.

так как во втором члене вместо х, подставлена константа 0.

Пример 1. Дана функция / = ab + ас + Ьс.

Выполним разложение по а

Дальнейшие преобразования с использованием закона Де Моргана приводят к результату.

Выполним разложение по b:

Дальнейшие преобразования приводят к тождественному результату:

Следствие 1. Для каждого члена в выражении (12) можно повторить разложение по другой переменной у.

После повторения процедуры разложения по всем п переменным будет получена булева сумма 2″ минтермов, умноженных на константы 1 или 0, что соответствует записи функции в СДНФ.

Пример 2. Дана функция

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

Напомним, что операция неравнозначности © соответствует сложению двоичных чисел, поэтому 1(c)1= 0; 1(c)0 = 1; 0 (c)1 = 1; 0 © 0 = 0. Следовательно,

Окончательно в СДНФ имеем/= abc + abc.

Пример 3. Дана функция.

Требуется записать ее в СДНФ.

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

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

Покажем это на примерах (14) и (15). Для функции (14) получим таблицу истинности 8, для функции (15) — табл. 9.

Нетрудно видеть, что/= т_] + т-_: = abc + abc.

Следовательно,/= т₀ + т₂ + т_} = x_tx₂ + х, х₂ + х_{х₂

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

Таблица 8.

Таблица истинности для функции (14).

Таблица 9.

Таблица истинности для функции (15).

Например, задача состоит в создании (синтезе) автомата принятия решения по большинству голосов участников голосования а, 6, с. Возможны состояния автомата отражены в таблице истинности 10. Решение (А = 1) принимается при условии: нет а, есть Ь, есть с; есть а, нет Ь, есть с; есть а, есть 6, нет с; есть я, есть Л, есть с.

Таблица 10.

Таблица истинности мажоритарного автомата

Получается логическая функция для работы автомата в виде.

На рис. 14 показаны соответствующие реализации в базисе «И—ИЛ И—НЕ» и в виде релейной схемы с замыканием и размыканием контактов.

Рис. 14. Автомат голосования по мажоритарному принципу: а — реализация в базисе «И—ИЛИ—НЕ»; б — релейная реализация Следует отметить, что предложенная реализация автомата нецелесообразна ввиду громоздкости. Синтез автомата заключается не только в получении логической функции, но и в ее преобразовании к виду, соответствующему минимальному количеству элементов. Рассматриваемые теоремы помогают эту процедуру выполнить.

Теорема о склеивании. Пусть имеется два соседних минтерма /и, и т_р отличающихся друг от друга состоянием переменной х_к. Дизъюнкция соседних мин гермов равна импликанте, нс содержащей переменную х_к.

Обозначим как х₂ неопределенное состояние переменной (0 или 1). Если т₁ = (х" х_к,…, х"), то /и, = (х,…, х_к,… х").

Доказательство.

/и, — + /и, = х" …, х_к, …, х_я + х" …, х_к, …, х" = (х" …, х") (х_к +х_к) =

= х, …, х" …, х," где 1 * к.

Пример 4. Х|Х₂х, + х, х, х, = х, х, (х₂ + х₂) = х, х₃

Существует аналогичная теорема о склеивании соседних макстермов в их логическом произведении (конъюнкции).

Релейная интерпретация теорем о склеивании на примере функций двух переменных приведена на рис. 15.

Рис. 15. Релейная интерпретация теоремы о склеивании: а — для операции дизъюнкции; б — для операции конъюнкции Воспользуемся теоремой о склеивании для минимизации функции (16).

Естественно, вместо схем на рис. 14 получается более простая реализация. Теорема о помещении. Конъюнктивная импликанта /;, поглощает минтсрм или другую импликанту большей размерности в операции сложения: р_[ + р₂ =/>, Доказательство. Пусть имеются две импликанты —/?, и р₂ так, что размерность dim/;, < dim/), Следовательно, импликанта есть часть импликанты р_ъ т. е.

где у — конъюнктивное дополнение. Например, р_{ = ab, p₂ = abcde. Следовательно, р₂ = Р' cde, у = cde. Запишем логическую сумму

В нашем примере.

ab + abcde = ab (1 + cde) = ab.

В общем виде подР, р₂ и у можно понимать функции, при этом остается справедливым Р+ р₂⁼ Р. _.

Например, / = (a + bc) + (a + bc)[x_x + х₂). Здесь/?, = (а + Ьс),.

Аналогично доказывается двойственная теорема о поглощении дизъюнктивных импликант и макстермов в их произведении. Пусть/*, имеет размерность dim/*, < dim/*₂ Например, /*, = а + Ь

Логическое произведение.

где г, — общая часть в двух импликантах; 6 — добавка в более длинной импликанте по отношению к короткой импликанте.

Действительно, /*, (/*, + 6) = /*,+ /*, 6. В силу выражения (17) справедливо.

Проиллюстрируем сказанное примером:

Полезны некоторые поглощения двух переменных, легко доказываемые законом дистрибутивности, которые приведены ниже, на рис. 16, вместе с их релейными схемами.

Рис. 16. Интерпретация примеров поглощения в виде релейных схем для функций: f=a + ab (a);f= (а + b)a (6)f= a + cib (e);f= а (а + b) (г).