Теорема 2.3. О разложении функции по переменным



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Теорема 2.3. О разложении функции по переменным



 


Пусть f(x1, ..., xn) Î P2. Тогда для любого m: 1 ≤ m ≤ n допустимо представление

f(x1, ..., xm, xm+1, ..., xn) = ,

где дизъюнкция берется по всем наборам из 0 и 1, которое называется разложением функции f по переменным x1, ..., xn.

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

 

Пример 2.12. m = 1, запишем разложение по переменным х:

f(x1, ..., xn)= = f(0, x2 , …,xnx1f(1, x2,...,xn). (2.1)

 

Пример 2.13.m=2, запишем разложение по переменным х и :

f(x1,x2,…xn) = =

=

= .

Если f(x1, x2) = x1 Å x2, то последняя формула дает x1 Å x2 = x2Ú x1 .

 

Доказательство. Для доказательства возьмем произвольный набор (a1, ..., a n) и покажем, что левая и правая части формулы (2.1) принимают на этом наборе одинаковые значения. Слева имеем f(a1, ..., an). Cправа : .

Дизъюнкция берется по всевозможным наборам (s1, ..., sm). Если в этих наборах хотя бы одно si ¹ ai (1≤im), то = 0 и , следовательно, ненулевой член будет только на наборе (s1, ..., sm) = (a1, ..., am), тогда = f(a1, ..., an).

 

Следствие 2.1. Любую функцию f(x1, ..., xn), не равную тождественно нулю, можно представить в виде: , причём единственным образом. Этот вид называется совершенной дизъюнктивной нормальной формой функции f(x1, ..., xn) и записывается СДНФ.

 

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

Замечание. – элементарная конъюнкция ранга n по числу входящих переменных; предполагается, что при i ¹ j , хi ¹ хj. СДНФ для f(x1, ..., xn) дизъюнкция элементарных конъюнкций ранга n. Если функция представлена в виде дизъюнкций элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньше n, то такая форма называется дизъюнктивной нормальной формой (ДНФ).

Cледствие 2.2. Любая функция алгебры логики может быть представлена в виде формулы через отрицание, & и Ú.

а) Если f ≡ 0, то f(x1, ..., xn) = & .

б) Если f(x1, ..., xn) ¹ 0 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки , &, Ú. СДНФ дает алгоритм представления функции в виде формулы через &, Ú, .

 

Пример 2.14. Пусть функция f(x1, x2, x3) задана таблицей истинности (2.19). Запишем ее в виде СДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому

f(x1,x2, x3) = x10 & x21 & x30 Ú x11 & x20 & x30 Úx11&x21 & x31 = = &x2& Úx1& & Úx1&x2&x3.

Таблица 2.19

x1 x2 x3 f  
               

Следствие 2.3. Мы умеем представлять функцию в виде . Нельзя ли представить ее в виде ? Пусть функция f(x1, ..., xn) ¹ 1 тождественно. Тогда функция f* ¹ 0 тождественно, и ее можно представить в виде

По принципу двойственности заменим & на Ú и наоборот; получим (2.2)

называется элементарной дизъюнкцией ранга n. Представление функции в виде (2.2) называется совершенной конъюнктивной нормальной формойили в краткой записи – СКНФ. СКНФ для f(x1, ..., xn) – конъюнкция элементарных дизъюнкций ранга n. КНФ для f(x1, ..., xn) – конъюнкция элементарных дизъюнкций, где ранг хотя бы одной элементарной дизъюнкции меньше n.

Пример 2.15. Пусть f(x1, x2, x3) = x1 (x2 (x3 ~ x1)). Представим ее в виде СКНФ, для этого получим таблицу истинности (табл.2.20).

Функция равна нулю только на наборе (1, 1, 0), поэтому

f(x1 x2 x3)=x1 Úx2 Úx3 =x10Úx20Úx31= Ú Ú x3.

 

Таблица 2.20

x1 x2 x3 x3~x1 x2 (x3~x1) f
1 1 1 1 1 1 1

 

2.5. Полнота, примеры полных систем

Определение 2.9. Система функций {f1, f2, ..., fs, ...}ÌP2 называется полной в Р2, если любая функция f(x1, ..., xn) Î P2 может быть записана в виде формулы через функции этой системы.

 

Полные системы

1. P2 – полная система.

2. Система M={x1&x2, x1Úx2, } – полная система, так как любая функция алгебры логики может быть записана в виде формулы через эти функции.

 

Пример 2.16. Неполные системы: { }, {0,1}.

Лемма (достаточное условие полноты)

Пусть система U = {f1, f2, ..., fs, ...} полна в Р2. Пусть B = {g1, g2, ..., gk, ...} – некоторая система из Р2, причем любая функция fi Î U может быть выражена формулой над B, тогда система B полна в Р2.

Доказательство. Пусть h(x1, ..., xn) Î P2; так как U полна в Р2, то h(x1, ..., xn) =N[f1, ..., fs, ...] = N[L1[g1, ..., gk], ..., Ls[g1, ..., gk], ...] = U[g1, ..., gk]. Здесь мы воспользовались тем, что для любого i n fi может быть выражена формулой над B, поэтому fi=Li[gi, ..., gk].

3. Система {x1Úx2, } полна в P2.

Возьмем в качестве полной в Р2 системы U={x1Úx2, , x1&x2}, B={x1Úx2, }. Надо показать, что x1&x2 представляется формулой над B. Действительно, по правилу Де Моргана получим x1&x2= .

С помощью этой леммы докажем полноту еще ряда систем.

4. Система {x1&x2, } – полна в Р2.

5. Система {x1|x2} полна в Р2. Для доказательства возьмем в качестве полной в Р2 системы U = {x1&x2, } и выразим х1&х2 и через х1|x2 :

= x1 | x1, x1 & x2 = = (x1|x2)|(x1|x2).

6. Система {x1 x2} полна в Р2. U = {x1Úx2, }, = x1 x1, x1Úx2 = = = (x1 x2) (x1 x2).

7. Система {x1&x2, x1Åx2, 0, 1}, U = {x1&x2, }, = x1Å1.

Следствие 2.4. Полином Жегалкина.

f(x1, ..., xn) Î P2, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x1&x2, x1Åx2, 0, 1} полна в Р2. В силу свойства x &

& (yÅz)=xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ...х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина

где , s = 0, 1, ..., n, причем при s = 0 получаем свободный член а0.

 



Последнее изменение этой страницы: 2016-07-14; просмотров: 166; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.158.251.104 (0.027 с.)