А.Д. Поспелов, В.Б. Алексеев - Дискретная математика, страница 2

Следствие доказано.Теорема 2 (о совершенной конъюнктивной нормальной форме). Для любой функцииалгебры логики f (x1, x2, …, xn), отличной от тождественной единицы, справедливопредставлениеf (x1 ,!, xn ) =&(σ 1 ,σ 2 ,!,σ n )(xσ11)∨ x2σ 2 ∨ ! ∨ xnσ n .f (σ 1 ,σ 2 ,!,σ n )= 0§3. Полные системы. Примеры полных систем (с доказательством полноты).Определение.

Множество функций алгебры логики A называется полной системой(в P2), если любую функцию алгебры логики можно выразить формулой над A.Теорема 3. Система A = {∨, &, ¬} является полной.Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то fвыражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишьдизъюнкция, конъюнкция и отрицание. Если же f ≡ 0, то f = x ⋅ x . Теорема доказана.Лемма 2. Если система A — полная, и любая функция системы A может быть выраженаформулой над некоторой другой системой B, то B — также полная система.Доказательство.

Рассмотрим произвольную функцию алгебры логики f (x1, …, xn) и двесистемы функций: A = {g1, g2, …} и B = {h1, h2, …}. В силу того, что система A полна, функция f может быть выражена в виде формулы над ней: f (x1 ,!, xn ) = ℑ[g1 , g 2 ,!], гдеg i = ℜ i [h1 , h2 ,!], то есть функция f представляется в виде f (x1 ,!, xn ) = ℑ[ℜ1 , ℜ 2 ,!], иначеговоря, может быть представлена формулой над B. Перебирая таким образом все функцииалгебры логики, получим, что система 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, …}.