Вопросы к зачету часть1 (Вопросы к зачету (ответы)), страница 9

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

Лемма. Пусть ДНФ поглощает конъюнкцию и . Тогда поглощается ДНФ

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

Функции и называются ортогональными, если . Доказанная лемма позволяет при исследовании на поглощение некоторой конъюнкции не принимать во внимание ортогональные к ней конъюнкции.

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

(12)

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

Обратно, пусть и условие (12) не выполнено. Тогда для некоторого набора , . Так как то в не может входить отрицание какого-либо сомножителя из . Следовательно, в , а потому и в ДНФ входят лишь переменные, не входящие в . Пусть, например, в входят переменные а в Тогда

при любых значениях Так как не ортогональна , то а потому для некоторых имеем Таким образом, при :

что противоречит условию. При условие (12) тривиально.

Пример. Используя критерий поглощения, найти МДНФ для функции предыдущего примера.

Сокращенная ДНФ нашей функции имеет вид:

(13)

Выясним, какие из конъюнкций этой ДНФ не поглощаются дизъюнкцией остальных. Рассмотрим конъюнкцию Она не ортогональна лишь конъюнкциям которые не

поглощают ее, поскольку не выполняется условие (12):

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

каждая из конъюнкций поглощается остальными. Удаляя конъюнкции, поглощаемые остальными, получаем 4

ДНФ:

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

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

ТАБЛИЦА 1.

На пересечении строки с конъюнкцией , со столбцом с конъюнкцией ставим знак “+” в том и только том случае, когда поглощает , т. е. является частью . Далее, глядя на таблицу, мы должны выбрать из сокращенной ДНФ минимальное число конъюнкций, которые бы поглощали все конъюнкции совершенной ДНФ. В нашем случае мы замечаем, что конъюнкция поглощается только конъюнкцией . Значит, должна входить в любую тупиковую ДНФ функции . По тем же соображениям в любую тупиковую ДНФ входят . С другой стороны, из таблицы видно, что для поглощения

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

16. Доказательство теоремы о представлении двоичной функции в виде полинома Жегалкина.

Полином Жегалкина. Еще одно важное представление логических функций получается с использованием операций конъюнкции и суммирования по mod 2.

Отметим, что сумма по mod 2 обладает обычными свойствами: x₁ x₂= x₂ x₁(коммутативность), x₁ (x₂ x₃) = (x₁ x₂) x₃ (ассоциативность), x₁ (x₂ хз)= x₁x₂ x₁x₃ (дистрибутивность). На основе свойства ассоциативности можно рассматривать многоместную операцию Значение этой суммы равно 1 тогда и только тогда, когда в наборе значение x_2,… ,x_n переменных x_1,имеется нечетное число единиц. Заметим, что если в наборе значений переменных x_1,x_2,… ,x_n присутствует не более одной единицы, то совпадает с _.

Рассмотрим теперь произвольную функцию f(x₁, ..., x_n) 0 и выразим ее посредством с.д. н. ф.:

На каждом наборе (α_1,. . . ,α_n) в 1 обращается не более одной из конъюнкций x₁, ..., x_n, входящих в

с.д.н.ф. Поэтому внешняя дизъюнкция может быть заменена суммой по mod 2:

, ( такие что далее тоже

Далее, поскольку , то . Подставив вместо выражение , получим

Обычным образом раскрыв скобки и приведя подобные члены по правилу A А = 0, придем к представлению функции в виде полинома по mod 2:

где коэффициенты равны 0 или 1. Пустая конъюнкция считается равной 1, так что коэффициент, соответствующий пустому множеству индексов i₁, ..., i_s, представляет собой свободный член полинома. Указанное представление носит название полинома Жегалкина. Для функции, тождественно равной нулю, в качестве полинома берется 0.

Построим полином Жегалкина для функции, заданной таблицей 1.1. Имеем

f(x₁,х₂,x₃)= (x₁1) (x₂1) (x₃ 1) (x₁1)( x₁1) x₃x₁ (x₂1)(x₃1) x₁(x₂1) x₃ x₁x₂x₃

Для преобразования этого выражения могут быть использованы обычные приемы элементарной алгебры

(специфичным является лишь приведение подобных членов по правилу А А =0). В частности, применяя группировку членов и вынесение за скобки, получаем

f ( ) = ( ) ( ) ( )

( ) ( ) =

=( )( ) ( ) =

= ( )( ) = .

Теорема 1.3. Всякая логическая функция может быть представлена в виде полинома Жегалкина единственным образом.

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

Подсчитаем количество полиномов от переменных ,..., . Число различных конъюнкций ,..., совпадает с числом подмножеств множества {1, ...,n} и равно (пустому подмножеству соответствует пустая конъюнкция, равная 1). Полином задается множеством конъюнкций, входящих в него с коэффициентом 1 (пустому множеству конъюнкций соответствует полином, равный 0). Число полиномов определяется числом этих множеств и составляет .

Всякой функции от n аргументов соответствует некоторый полином Жегалкина, и разным функциям отвечают разные полиномы. Поскольку число функций от n аргументов совпадает с числом полиномов, то если бы какая-либо функция имела несколько полиномов, для некоторых функций полиномов не хватило бы. Теорема доказана.

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