Правило де Моргана

Сложение по mod 2

1 х = x0 x = xx x = 1

x x x ... x = х – при нечетном числе членов, 0 - при четном числе членов

x₁ x₂ ... x_n = x₁ & x₂&... & x_n

x₁ x₂ ... x_n = x₁ & x₂ &... & x_n

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

Х1	Х2	Х1 Х2	X1 & X2

Операция поглощения:

Х XY = X или в общем виде X X*f(X,Y,Z...) = X;

Операция полного склеивания:

XY XY = X (по Y)XY XY = Y (по Х)

Операция неполного склеивания:

XY XY = Х XY XY

3. Лекция: Совершенные дизъюнктивные и конъюнктивные нормальные формы ФАЛ

Страницы: 1 | 2 | 3 | вопросы |»

| учебники | для печати и PDA | ZIP

Если Вы заметили ошибку - сообщите нам, или выделите ее и нажмите Ctrl+Enter

В лекции дано определение совершенной дизъюнктивной и конъюнктивной нормальных форм. Представлены правила записи функции по нулям и единицам. Дано понятие функциональной полноты, поставлена задача минимизации функции. Сформулирована теорема Квайна.

Введем понятие степени:

Х

=Х, если =1;

=Х, если =0.

Рассмотрим конъюнкцию вида:

Х₁¹ * Х₂² * Х₃³... Х_n ⁿ

Существует 2ⁿ наборов вида < ₁, ₂,... _n >. Поставим в соответствие каждой конъюнкции (*) номер набора i и образуем дизъюнкцию всех конъюнкций:

_iA(Х₁¹ * Х₂² * Х₃³... Х_nⁿ)

Теорема (без доказательства):

Любая ФАЛ, зависящая от 'n' аргументов, может быть представлена в форме:

F(Х₁, Х₂,... Х_i... Х_n)= Х₁¹ * Х₂²... Х_iⁱ F(₁, ₂,... _i, X_i+1,...X_n)

Из этой теоремы вытекает ряд важных следствий:

1. Она дает возможность перейти от табличного задания функции к аналитической форме и сделать обратный переход.
2. Устанавливает так называемую функциональную полноту связок (базиса) ", , -", т.к. позволит построить в этом базисе произвольную ФАЛ от произвольного числа аргументов.

Примечание:

1. Если in, то соответствующая форма функции называется дизъюнктивной нормальной (ДНФ).
2. Если i=n, то каноническая форма функции носит название совершенной ДНФ (СДНФ). Дизъюнкции берутся по тем наборам, на которых функция f(X₁,X₂,...,X_n)=1

Пример: ДНФ

f(Х₁, Х₂, Х₃)= Х₁ Х₂ Х₃ Х₁Х₂ Х₃

Пример: СДНФ

f(Х₁, Х₂, Х₃)= Х₁Х₂ Х₃ Х₁Х₂ Х₃

В ДНФ в каждый член любая переменная входит в прямом виде или с отрицанием.

Аналогичная теорема справедлива и для представления функции в конъюктивной нормальной форме (КНФ):

f(Х₁, Х₂,..., Х_n)=&(Х₁¹ Х₂² ... Х_iⁱ) f(₁, ₂,... _i, X_i+1...X_n)

или при представлении в совершенной КНФ (СКНФ):

f(Х₁, Х₂,…, Х_n)=&(Х₁¹ Х₂² Х₃³... Х_nⁿ)

где: & означает, что конъюнкции берется по тем наборам, на которых

f(Х₁, Х₂,... Х_n)=0.

Дадим на основании этих теорем правило перехода от табличной формы функции к СДНФ и СКНФ.

Переход от табличной формы функции к СДНФ или правило записи функции по единицам:

1. Выбрать те наборы аргументов, на которых f(Х₁, Х₂,... Х_n)=1.
2. Выписать все конъюнкции для этих наборов. Если при этом Х_i имеет значение '1', то этот множитель пишется в прямом виде, если '0', то с отрицанием.
3. Все конъюнктивные члены соединить знаком дизъюнкции .

Пример:

f(Х₁, Х₂)= Х₁Х₂ Х₁Х₂ Х₁Х₂

X1	Х2	f(Х1, Х2)

Правило перехода от табличной формы задания функции к СКНФ или правило записи функции по нулям.

1. Выбрать те наборы аргументов, на которых f(Х₁, Х₂,... Х_n)=0.
2. Если при этом Х_i имеет значение '0', то остается без изменений. Если '1', то с отрицанием.
3. Все дизъюнктивные члены соединить знаком конъюнкции.

Пример:

f(Х₁, Х₂)= (Х₁ Х₂) (Х₁ Х₂)

X1	Х2	f(Х1, Х2)

Пример:

X1	Х2	Х3	f(Х1, Х2, Х3)

СДНФ f(Х₁, Х₂, Х₃)= Х₁Х₂Х₃ Х₁Х₂Х₃ Х₁Х₂Х₃ Х₁Х₂Х₃ Х₁Х₂Х₃

СКНФ f(Х₁, Х₂, Х₃)= (Х₁ Х₂ Х₃) & (Х₁ Х₂ Х₃) & (Х₁ Х₂ Х₃)

Рассмотрим способ получения СДНФ из СКНФ и обратно.

Из таблицы 2.1 с помощью способа записи функции по нулям следует, что СКНФ той же функции дизъюнкции будет иметь вид:

f(Х₁, Х₂)= Х₁ Х₂

X1	Х2	f(Х1, Х2)

Итак, имеем две формы одной и той же функции:

f(Х₁, Х₂)= Х₁Х₂ Х₁Х₂ Х₁Х₂ =Х₁Х₂

Итак, видно, что общее число членов в этих двух формах равно сумме нулей и единиц функции, то есть равно 2ⁿ.

Если в исходной форме функции, записанной в СКНФ или СДНФ, содержится z членов, то в другой ее форме (т.е. СДНФ или СКНФ) их будет (2ⁿ- z).

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

f(Х₁, Х₂)= Х₁ Х₂

f(Х₁, Х₂)_СДНФ= Х₁Х₂ Х₁Х₂ Х₁Х₂

т.е. получили СДНФ.

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

Дата добавления: 2014-01-06