Алексеев В.Б. Лекции по дискретной математике (1083733), страница 3
Текст из файла (страница 3)
Так, например, наборы (0, 0, 1) и (0, 1, 0) несравнимы.Определение 2. Функция алгебры логики f (x1, …, xn) называется монотонной, если для~любых двух сравнимых наборов α~ и β выполняется импликация~~α~ ≤ β ⇒ f (α~ ) ≤ f β .()Класс M всех монотонных функций.Классу M принадлежат функции 0 , 1 , x , xy , x ∨ y, m (x, y, z) = xy ∨ yz ∨ zx.Классу M не принадлежат функции x , x | y , x ↓ y , x ⊕ y , x ~ y , x → y.Теорема 11. Класс M замкнут.Доказательство.
Поскольку тождественная функция монотонна, достаточно проверитьлишь случай суперпозиции функций. Пусть f (x1, …, xn) ∈ M, для любого j gj (y1, …, ym)∈M иΦ (y1, …, ym) = f (g1 (y1, …, ym), …, gn (y1, …, ym)).~~Рассмотрим произвольные наборы α~ = (α1 ,!,α m ), β = (β1 ,!, β m ) такие, что α~ ≤ β . Обозначим()~gi (α~ ) = γ i , g i β = δ i .()~Тогда для любого i имеем gi ∈ M и gi (α~ ) ≤ gi β , то есть ∀i (γ i ≤ δ i ) . Обозначим~γ~ = (γ 1 , γ 2 ,!, γ n ), δ = (δ 1 , δ 2 ,!, δ n ).()~~Тогда по определению γ~ ≤ δ и, в силу монотонности функции f, f (γ~ ) ≤ f δ . Но~~Φ(α~ ) = f (γ 1 ,!, γ n ) = f (γ~ ) , Φ β = f (δ 1 ,!, δ n ) = f δ ,()()()()~~и неравенство f (γ~ ) ≤ f δ ⇔ Φ(α~ ) ≤ Φ β , следовательно, Ф ∈ M. Теорема доказана.§8.
Лемма о несамодвойственной функции.Лемма (о несамодвойственной функции). Из любой несамодвойственной функции алгебры логики f (x1, …, xn), подставляя вместо всех переменных функции x и x, можно получить φ (x) ≡ const.10()Доказательство. Пусть f ∉ S. Тогда f x1 ,!, xn ≠ f (x1 ,!, xn ) ⇒ ∃σ~ = (σ 1 ,!, σ n ) :()()f σ 1 ,!, σ n ≠ f (σ 1 ,!, σ n ) ⇔ f σ 1 ,!, σ n = f (σ 1 ,!, σ n ).Построим функцию φ (x) так: φ (x) = f (x ⊕ σ1, …, x ⊕ σn). Действительно,ϕ (0) = f (σ1, …, σn), ϕ (1) = f σ 1 ,!σ nи φ (0) = φ (1) ⇒ φ (x) = const.
Заметим, что подстановка удовлетворяет условию теоремы, так x, σ = 0как x ⊕ σ = . Лемма доказана. x ,σ = 1()§9. Лемма о немонотонной функции.Лемма (о немонотонной функции). Из любой немонотонной функции алгебры логикиf (x1, …, xn), подставляя вместо всех переменных функции x, 0, 1, можно получить функциюϕ (x ) ≡ x .Доказательство. Пусть f ∉ M. Тогда существуют такие наборы α~ = (α1 ,!,α n ) и~~~~β = (β1 ,!, β n ) , что α~ < β (то есть ∀j (αj ≤ βj) и α~ ≠ β ) и f (α~ ) > f β . Выделим те разряды~i1, …, ik наборов α~ и β , в которых они различаются. Очевидно, в наборе α~ эти разряды~равны 0, а в наборе β — 1. Рассмотрим последовательность наборовα~0 ,α~1 ,α~2 ,!,α~k~таких, что α~ = α~0 < α~1 < α~2 < ! < α~k = β , где α~i +1 получается из α~i заменой одного из нулей,расположенного в одной из позиций i1, …, ik, на единицу (при этом наборы α~i и α~i +1 — со~седние).
Поскольку f (α~ ) = 1 , а f β = 0 , среди наборов α~0 ,α~1 ,α~2 ,!,α~k найдутся два соседних α~i и α~i +1 , такие что f (α~i ) = 1 и f (α~i+1 ) = 0 . Пусть они различаются в r-ом разряде:α~i = (α1 ,α 2 ,!,α r −1 ,0,α r +1 ,!,α n ), α~i+1 = (α1 ,α 2 ,!,α r −1 ,1,α r +1 ,!,α n ) . Тогда определим функциюφ (x) так: φ (x) = f (α1, α2, …, αr – 1, x, αr + 1, …, αn). Действительно, тогда ϕ (0) = f (α~i ) = 1 ,ϕ (1) = f (α~i+1 ) = 0 и ϕ (x ) ≡ x . Лемма доказана.()()§10. Лемма о нелинейной функции.Лемма (о нелинейной функции). Из любой нелинейной функции алгебры логикиf (x1, …, xn), подставляя вместо всех переменных x, x , y, y , 0, 1, можно получить φ (x, y) = x·yили ϕ (x, y ) = x ⋅ y .Доказательство. Пусть f (x1, …, xn) ∉ L. Рассмотрим полином Жегалкина этой функции.Из её нелинейности следует, что в нём присутствуют слагаемые вида xi1 ⋅ xi2 ⋅ ! . Не ограничивая общности рассуждений, будем считать, что присутствует произведение x1 · x2 · ….
Таким образом, полином Жегалкина этой функции выглядит так:f (x1, …, xn) = x1 · x2 · P1 (x3, …, xn) ⊕ x1 · P2 (x3, …, xn) ⊕ x2 · P3 (x3, …, xn) ⊕ P4 (x3, …, xn),причем P1 (x3, …, xn) ≠ 0.Иначе говоря, ∃ a3, a4, …, an ∈ E2 = {0, 1} такие, что P1 (a3, a4, …, an) = 1. Рассмотрим вспомогательную функцию f (x1, x2, a3, a4, …, an) = x1 x2 · 1 ⊕ x1 · b ⊕ x2 · c ⊕ d. Тогда функцияf (x ⊕ с, y ⊕ b, a3, a4, …, an) = (x ⊕ c)(y ⊕ b) ⊕ (x ⊕ c)b ⊕ (y ⊕ b)c ⊕ d = xy, bc ⊕ d = 0= xy ⊕ x · b ⊕ y · c ⊕ b · c ⊕ x · b ⊕ b · c ⊕ y · c ⊕ b · c ⊕ d = xy ⊕ (bc ⊕ d) = . xy, bc ⊕ d = 1Лемма доказана.11§11.
Теорема Поста о полноте системы функций алгебры логики.Теорема 12 (теорема Поста). Система функций алгебры логики A = {f1, f2, …} являетсяполной в P2 тогда и только тогда, когда она не содержится целиком ни в одном из следующих классов: T0, T1, S, L, M.Доказательство. Необходимость. Пусть A — полная система, N — любой из классовT0, T1, S, L, M и пусть A ⊆ N. Тогда [A] ⊆ [N] = N ≠ P2 и [A] ≠ P2. Полученное противоречиезавершает обоснование необходимости.Достаточность. Пусть A ⊄ T0, A ⊄ T1, A ⊄ M, A ⊄ L, A ⊄ S. Тогда в A существуют функцииf0 ∉ T0, f1 ∉ T1, fM ∉ M, fL ∉ L, fS ∉ S. Достаточно показать, что [A] ⊇ [f0, f1, fM, fL, fS] = P2.
Разобьём доказательство на три части: получение отрицания, констант и конъюнкции.a) Получение x . Рассмотрим функцию f0 (x1, …, xn) ∉ T0 и введём функцию φ0 (x) == f0 (x, x, …, x). Так как функция f0 не сохраняет нуль, φ0 (0) = f (0, 0, …, 0) = 1. Возможны два случая: либо ϕ 0 (x ) = x , либо φ0 (x) ≡ 1. Рассмотрим функциюf1 (x1, …, xn) ∉ T1 и аналогичным образом введём функцию φ1 (x) = f1 (x, x, …, x).
Таккак функция f1 не сохраняет единицу, φ1 (1) = f (1, 1, …, 1) = 0. Возможны также дваслучая: либо ϕ1 (x ) = x , либо φ1 (x) ≡ 0. Если хотя бы в одном случае получилось искомое отрицание, пункт завершён. Если же в обоих случаях получились константы,то согласно лемме о немонотонной функции, подставляя в функцию fM ∉ M вместовсех переменных константы и тождественные функции, можно получить отрицание.Отрицание получено.b) Получение констант 0 и 1. Имеем fS ∉ S.
Согласно лемме о несамодвойственнойфункции, подставляя вместо всех переменных функции fS отрицание (которое получено в пункте a) и тождественную функцию, можно получить константы:[fS, x ] ∋ [0, 1]. Константы получены.c) Получение конъюнкции x · y. Имеем функцию fL ∉ L. Согласно лемме о нелинейнойфункции, подставляя в функцию fL вместо всех переменных константы и отрицания(которые были получены на предыдущих шагах доказательства), можно получитьлибо конъюнкцию, либо отрицание конъюнкции.
Однако на первом этапе отрицаниеуже получено, следовательно, всегда можно получить конъюнкцию:[fL, 0, 1, x ] ∋ [xy, xy ]. Конъюнкция получена.В результате получено, что [ f 0 , f1 , f M , f L , f S ] ⊇ [x , xy ] = P2 . Последнее равенство следуетиз пункта 2 теоремы 4. В силу леммы 2 достаточность доказана.§12. Теорема о максимальном числе функций в базисе алгебры логики.Определение. Система функций алгебры логики A ⊆ P2 называется базисом (в P2), если1) [A] = P2;2) ∀f ∈ A ([A \ {f}] ≠ P2).Теорема 13.
Максимальное число функций в базисе алгебры логики равно 4.Доказательство. 1) Докажем, что из любой полной системы можно выделить полнуюподсистему, содержащую не более четырёх функций. Действительно, если A — полная система ([A] = P2), то согласно теореме Поста в ней существуют пять функций f0 ∉ T0, f1 ∉ T1,fS ∉ S, fM ∉ M, fL ∉ L. По теореме Поста система функций {f0, f1, fS, fM, fL} полна. Рассмотримфункцию f0 (x1, …, xn) ∉ T0 (f0 (0, 0, …, 0) = 1). Возможны два случая:a) f0 (1, 1, …, 1) = 1 ⇒ f0 ∉ S ⇒ [f0, f1, fL, fM] = P2 и система {f0, f1, fL, fM} полна.b) f0 (1, 1, …, 1) = 0 ⇒ f0 ∉ M, T1 ⇒ [f0, fL, fS] = P2 и система {f0, fL, fS} полна.122) Покажем, что существует базис алгебры логики из четырёх функций. Действительно,рассмотрим систему функций {0, 1, x · y, x ⊕ y ⊕ z}.
Эта система функций полная, так как0 ∉ T1, S, 1 ∉ T0, x · y ∉ L, x ⊕ y ⊕ z ∉ M (0 ⊕ 0 ⊕ 1 = 1, 0 ⊕ 1 ⊕ 1 = 0). Однако, любая её подсистема не полна:{0, 1, x · y} ⊆ M{0, 1, x ⊕ y ⊕ z} ⊆ L{0, xy, x ⊕ y ⊕ z} ⊆ T0{1, xy, x ⊕ y ⊕ z} ⊆ T1.Теорема доказана.§13. Теорема о предполных классах.1 . Предполные классы.Определение. Пусть A ⊆ P2. A называется предполным классом, если1) [A] ≠ P2;2) ∀f∈P2 ( f∉A ⇒ [A∪{f}] = P2).Теорема 14. В P2 предполными являются лишь следующие 5 классов: T0, T1, S, L, M.Доказательство.
1) Покажем сначала, что ни один из этих пяти классов не содержится вдругом. Для этого достаточно для каждого из пяти вышеперечисленных классов указать четыре функции, принадлежащие данному классу, но не принадлежащие остальным четырем:∉∈T0 T1LMT00xyx⊕yT1 1xyx⊕y⊕1L 1 0x⊕yM 1 0xyxS x x xy ⊕ yz ⊕ zxS01002) Докажем, что все классы — T0, T1, S, L, M являются предполными.
Действительно,пусть N ∈ {T0 , T1 , L, M , S} и f ∉ N. Тогда система N ∪ {f} не содержится ни в одном из пятиклассов Поста (так как N не содержится в четырёх из них, а f не содержится в N). Следовательно, система N ∪ {f} — полная и N — предполный класс.3) Пусть A — предполный класс. Тогда [A] ≠ P2 ⇒ ∃ N∈{T0, T1, L, M, S}: A ⊆ N. ЕслиA ≠ N, то ∃ f (f ∈ N, f ∉ A): A ∪ {f} ⊆ N ⇒ [A ∪ {f}] ≠ P2. Полученное противоречие завершает доказательство.2 . Результаты Поста.1) В P2 существует ровно счётное число замкнутых классов.2) В любом замкнутом классе существует конечный базис.§14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
