Алексеев В.Б. Лекции по дискретной математике, страница 2

Перебирая таким образом все функцииалгебры логики, получим, что система B также полна. Лемма доказана.Теорема 4. Следующие системы являются полными в P2:1) {x ∨ y, x };2) {x ⋅ y, x };3) {x | y};4) {x · y, x ⊕ y , 1}.Доказательство. 1) Известно (теорема 3), что система A = {x ∨ y, x ⋅ y, x } полна. Покажем, что полна система B = {x ∨ y, x}. Действительно, из закона де Моргана x ⋅ y = x ∨ y по-лучаем, что x ⋅ y = x ∨ y , то есть конъюнкция выражается через дизъюнкцию и отрицание, ивсе функции системы A выражаются формулами над системой B.

Согласно лемме 2 системаB полна.2) Аналогично пункту 1: x ∨ y = x ⋅ y ⇔ x ∨ y = x ⋅ y и из леммы 2 следует истинностьутверждения пункта 2.3) x | x = x , x ⋅ y = x | y = (x | y ) | (x | y ) и согласно лемме 2 система полна.4) x = x ⊕ 1 и согласно лемме 2 система полна.Теорема доказана.§4. Теорема Жегалкина о представимости функции алгебры логики полиномом.Определение 1. Монотонной конъюнкцией от переменных x1,…, xn называется любоевыражение вида xi1 ⋅ xi2 ⋅ xi3 " xis , где s ≥ 1, 1 ≤ ij ≤ n ∀j = 1, 2, …, s, все переменные различны(ij ≠ ik, если j ≠ k); либо просто 1.6Определение 2.

Полиномом Жегалкина над x1, …, xn называется выражение видаK1 ⊕ K2 ⊕ K3 ⊕ … ⊕ Kl,где l ≥ 1 и все Kj суть различные монотонные конъюнкции над x1, …, xn; либо константа 0.Теорема 5 (теорема Жегалкина). Любую функцию алгебры логики f (x1, …, xn) можноединственным образом выразить полиномом Жегалкина над x1, …, xn.Доказательство. 1) Докажем существование полинома. Система {x · y, x ⊕ y, 1} полна,следовательно, любую функцию алгебры логики f (x1, …, xn) можно реализовать формулойнад {x · y, x ⊕ y, 1}.a) Пользуясь дистрибутивностью, раскрываем все скобки в этой реализации и получаем, что f (x1, …, xn) = K1′ ⊕ K2′ ⊕ … ⊕ Kl′, где любая Ki′ — конъюнкция переменныхи единиц.b) Преобразуем все полученные конъюнкции в элементарные, пользуясь при этомкоммутативностью и соотношениями x · x = x, 1 · 1 = 1 и A · 1 = A.

Очевидно, всеконъюнкции станут монотонными.c) Преобразуем полученную сумму в полином Жегалкина, пользуясь при этом соотношениями A ⊕ A = A и A ⊕ 0 = A. В результате получим либоK i1 ⊕ K i2 ⊕ K i3 ⊕ ! ⊕ K im ,либо константу 0.Существование доказано.2) Докажем единственность представления. Подсчитаем число различных всевозможных монотонных конъюнкций от n переменных. Для этого составим таблицу видаx1 x2 x4x2 x31x1100x2110x3010x41,00где каждой переменной соответствует единица, если она присутствует в монотонной конъюнкции и ноль в противном случае. При этом константе единице поставим в соответствиенулевой набор.

Очевидно, что построенное отображение биективно. Следовательно, всегоразличных монотонных конъюнкций от n переменных — 2n. Построим аналогичное биективное отображение между всевозможными суммами монотонных конъюнкций и векторамидлины 2n — числа конъюнкций. Для этого составим таблицу видаxy x y 1xy + 1 1 0 0 1 ,00 0 0 0где под соответствующей монотонной конъюнкцией стоит единица, если она входит в данную сумму, и ноль, если не входит. При этом константе ноль ставится в соответствие нулевой набор.

Очевидно, такое отображение биективно. Всего таких различных сумм будетnстолько, сколько существует различных булевых векторов длины 2n, то есть — 2 2 . Мы получили, что число различных полиномов Жегалкина совпадает с числом функций алгебрылогики. Поскольку отображение из множества полиномов во множество функций сюръективно, то оно и биективно, так как множества полиномов Жегалкина над n переменными ифункций алгебры логики от n переменных равномощны. Единственность доказана.7§5. Понятие замкнутого класса.

Замкнутость классов T0, T1 и L.1°. Понятие замкнутого класса.Определение 1. Пусть A ⊆ P2. Тогда замыканием A называется множество всех функций алгебры логики, которые можно выразить формулами над A.Обозначение: [A].Имеют место следующие свойства:1) [A] ⊇ A;2) A ⊇ B ⇒ [A] ⊇ [B], причём, если в левой части импликации строгое вложение, то изнего вовсе не следует строгое вложение в правой части — верно лишьA ⊃ B ⇒ [A] ⊇ [B];3) [[A]] = [A].Определение 2. Система функций алгебры логики A называется полной, если [A] = P2.Определение 3. Пусть A ⊆ P2.

Тогда система A называется замкнутым классом, если замыкание A совпадает с самим A: [A] = A.Утверждение. Пусть A — замкнутый класс, A ≠ P2 и B ⊆ A. Тогда B — неполная система(подмножество неполной системы будет также неполной системой).Доказательство. B ⊆ A ⇒ [B] ⊆ [A] = A ≠ P2 ⇒ [B] ≠ P2. Следовательно, B — неполнаясистема. Утверждение доказано.2°. Примеры замкнутых классов.Класс T0 = {f (x1, …, xn) | f (0, …, 0) = 0}.Классу T0 принадлежат, например, функции 0, x, xy, x ∨ y, x ⊕ y.Классу T0 не принадлежат функции 1, x , x → y, x | y, x ↓ y, x ~ y.Подсчитаем число функций в классе T0. Для этого построим следующую таблицу:x1 ! xn0 ! 0 0.n! ! ! }2 − 1Все функции, принадлежащие указанному классу, принимают на нулевом наборе нулевое значение.

Таким образом, всего функций в классе T0 столько, сколько существует булевых векторов длины 2n – 1 (первый разряд вектора длины 2n необходимо равен нулю), то естьnnT0 = 2 2 −1 = 12 2 2 .Теорема 6. Класс T0 —замкнутый.Доказательство. Пусть f (x1 ,!, xn ), g1 y11 ,!, y1m1 ,!, g n yn1 ,!, ynmn ⊆ T0 . Рассмотрим( ({)(()))()}функцию h( y1 ,!, y r ) = f g1 y11 ,!, y1m1 ,!, g n y n1 ,!, y nmn .

Среди переменных функций giмогут встречаться и одинаковые, поэтому в качестве переменных функции h возьмём всеразличные из них. Тогда h (0, …, 0) = f (g1 (0, …, 0), …, gn (0, …, 0)) = f (0, …, 0) = 0 , следовательно, функция h также сохраняет ноль. Рассмотрен только частный случай (без переменных в качестве аргументов). Однако, поскольку тождественная функция сохраняет ноль,подстановка простых переменных эквивалентна подстановке тождественной функции, теорема доказана.Класс T1 = {f (x1, …, xn) | f (1, 1, …, 1) = 1}.Классу T1 принадлежат функции 1, x, xy, x ∨ y, x → y, x ~ y.Классу T1 не принадлежат функции 0, x , x ⊕ y, x | y, x ↓ y.Теорема 7.

Класс T1 замкнут.Доказательство повторяет доказательство аналогичной теоремы для класса T0.8Класс L линейных функций.Определение 4. Функция алгебры логики f (x1, …, xn) называется линейной, еслиf (x1, …, xn) = a0 ⊕ a1 x1 ⊕ … ⊕ an xn, где ai ∈ {0, 1}.Иными словами, в полиноме линейной функции нет слагаемых, содержащих конъюнкцию.Классу L принадлежат функции 0, 1, x = x ⊕ 1 , x ~ y, x ⊕ y.Классу L не принадлежат функции xy, x ∨ y, x → y, x | y, x ↓ y.Теорема 8. Класс L замкнут.Доказательство.

Поскольку тождественная функция — линейная, достаточно (как и втеоремах 6 и 7) рассмотреть только случай подстановки в формулы функций: пустьf (x1, …, xn) ∈ L и gi ∈ L. Достаточно доказать, что f (g1, …, gn)∈L. Действительно, если не учитывать слагаемых с коэффициентами ai = 0, то всякую линейную функцию можно представитьв виде xi1 ⊕ xi2 ⊕ ! ⊕ xik ⊕ a0 . Если теперь вместо каждого xi j подставить линейное выражение,то получится снова линейное выражение (или константа единица или нуль).§6. Двойственность. Класс самодвойственных функций, его замкнутость.1°.

Двойственность.Определение 1. Функцией, двойственной к функции алгебры логики f (x1, …, xn), называется функция f ∗ (x1 ,!, xn ) = f x1 ,!, xn .Теорема 9 (принцип двойственности). Пусть()( (),!, g (y()))Φ( y1 ,!, ym ) = f g1 y11 ,!, y1k1 ,!, g n yn1 ,!, ynkn .( (Тогда Φ ∗ ( y1 ,!, ym ) = f ∗ g1∗ y11 ,!, y1k1Доказательство. Рассмотрим((∗nn1)),!, ynk n .( ()())Φ ∗ ( y1 , ! y m ) = f g1 y11 , ! , y1k1 , ! , g n y n1 ,! , y nk n =))) ( ((g (y ,!, y ),!, g (y(())).))= f g1 y11 ,!, y1k1 ,!, g n yn1 ,!, ynkn = f g1∗ y11 , !, y1k1 ,!, g n∗ yn1 ,!, ynkn == f∗∗111∗n1k 1n1,!, ynk nТеорема доказана.Следствие.

Пусть функция Φ (y1, …, ym) реализуется формулой над A = {f1, f2, …}. Тогдаесли в этой формуле всюду заменить вхождения fi на fi*, то получится формула, реализующаяΦ* (y1, …, ym).Утверждение. Для любой функции алгебры логики f (x1, …, xn) справедливо равенствоf (x1, …, xn)=f** (x1, …, xn).[(Доказательство. f ∗∗ = f x1 ,! , xn)] = f (x ,!, x ) = f (x ,!, x ) , и утверждение доказано.∗1n1n2°. Класс S самодвойственных функций.Определение 2. Функция алгебры логики f (x1, …, xn) называется самодвойственной, еслиf (x1, …, xn) = f* (x1, …, xn).Иначе говоря, S = {f | f = f*}.Классу S принадлежат функции1, x + y + z ≥ 2x, x , x ⊕ y ⊕ z ⊕ a, m(x, y, z ) = xy ∨ yz ∨ zx = .0, x + y + z ≤ 19Классу S не принадлежат функции0 ( f (x ) ≡ 0 ⇒ f ∗ (x ) = f (x ) ≡ 1 ), 1, x ∨ y (поскольку (x ∨ y ) = x ∨ y = x ⋅ y ≠ x ∨ y ), xy.∗Теорема 10. Класс S замкнут.Доказательство.

Пусть f (x1, …, xn) ∈ S, ∀i g i yi1 ,!, yiki ∈ S , i = 1, 2, …, n и(( ()()))Φ = f g1 y11 ,!, y1k1 ,!, g n yn1 ,!, ynkn .Тогда из принципа двойственности следует, что( (()Φ ∗ = f ∗ g1∗ y11 ,!, y1k1 ,!, g n∗ yn1 ,!, ynkn)) = f (g1 (…), …, gn (…)).Таким образом, мы получили, что Φ = Φ* и Φ ∈ S. Теорема доказана.§7. Класс монотонных функций, его замкнутость.~Определение 1. Пусть α~ = (α1 ,α 2 ,! ,α n ) и β = (β1 , β 2 ,!, β n ) . Тогда~α~ ≤ β ⇔ ∀i (α i ≤ β i ) .Замечание. Существуют наборы, для которых неприменимо отношение упорядоченности, определённое выше.