О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 3
Текст из файла (страница 3)
. , fn ) ∈ M. Будем считать, что f1 , . . . , fn — функции от одного наборапеременных y1 , . . . , ym , иначе добавим их как несущественные. В силу монотонности функций fi для любыхe т. е. f1 (eдвух наборов αe = (α1 , . . . , αm ) 6 (β1 , . .
. , βm ) = βe будем иметь, что fi (eα) 6 fi (β),α), . . . , fn (eα) 6e . . . , fn (β)e , но так как f монотонна, то f f1 (ee . . . , fn (β)e ⇒ f (f1 , . . . , fn ) ∈ M. f1 (β),α), . . . , fn (eα) 6 f f1 (β),Лемма 1.10 (о немонотонной функции). Из любой немонотонной функции, подставляя вместо некоторых ее переменных константы, можно получить отрицание.e такие, Пусть f (x1 , . . . , xn ) ∈/ M. Тогда существуют два набора αe = (α1 , . .
. , αn ) 6 (β1 , . . . , βn ) = β,eeeчто f (eα) f (β), т. е. f (eα) = 1 и f (β) = 0. Поэтому наборы αe и β разные. Переставим те переменные,по которым они отличаются, на первые места, тогда эти наборы превратятся в (0, 0, . . . , 0, αm+1 , . . . , αn ) и| {z }m(1, 1, . . . , 1, βm+1 , . . . , βn ). Будем последовательно заменять в наборе с нулями в начале эти нули на единицы,| {z }mтогда рано или поздно наступит момент, при котором значение функции сменится на противоположное, поскольку на наборе с единицами значение функции противоположное.
Значит, зафиксировав все переменные,кроме той, на которой произошла смена значения, мы получим отрицание. 1.8. Критерий Поста полноты систем функцийОпределение. Базис системы функций F — такая подсистема B ⊆ F, что F ⊆ [B], и ни одной функциииз B выкинуть нельзя.Теорема 1.11 (Критерий Поста). Система F полна тогда и только тогда, когда она не содержитсяцеликом ни в одном из классов T0 , T1 , L, S, M.
Необходимость. Если F целиком содержится в каком-либо из этих классов, то и [F ] содержится в нёми потому не совпадает с P2 , а значит, система F неполная.8Достаточность. Так как F * T0 , то найдется f0 ∈ F, не лежащая в T0 . Аналогично в F найдутся f1 ∈/ T1 ,fL ∈/ L, fS ∈/ S, fM ∈/ M. Сейчас мы получим из них константы, отрицание и конъюнкцию. Поскольку f0 ∈/ T0 ,имеем f (0, . . . , 0) = 1. Положим ϕ(x) := f (x, .
. . , x) ⇒ ϕ(0) = 1. Если ϕ(1) = 1, то это константа 1, а функцияψ(x) := f1 (ϕ(x), . . . , ϕ(x)) — константа 0. Если же ϕ(1) = 0, то ϕ(x) = x, и по лемме о несамодвойственнойфункции при помощи отрицания можно получить обе константы. По лемме о немонотонной функции из fM , имеяконстанты, можно получить отрицание. По лемме о нелинейной функции при помощи констант и отрицанияможно получить конъюнкцию. Таким образом, мы выделили в F полную подсистему, а значит, [F ] = P2 . Следствие 1.3. Из любой полной системы можно выделить полную подсистему, состоящую из 5 функций. Достаточно взять функции f0 , f1 , fL , fS , fM .
Теорема 1.12. Можно обойтись и 4 функциями, но меньшего количества в общем случае уже не хватит. Докажем, что 4 функций достаточно. В случае, когда ϕ(x) = 1 (здесь ϕ — функция из предыдущейтеоремы), это несамодвойственная функция, и можно обойтись без fS . Если же ϕ(x) = x, это немонотоннаяфункция, можно обойтись без fM .Приведём пример базиса из 4 функций: F = {0, 1, x1 x2 , x1 ⊕ x2 ⊕ x3 }.
Имеем 1 ∈/ T0 , 0 ∈/ T1 , x1 x2 ∈/ L, 0 ∈/S, x1 ⊕ x2 ⊕ x3 ∈/ M. Функция x1 ⊕ x2 ⊕ x3 немонотонная, т.к. из неё можно получить отрицание: x = 1 ⊕ 0 ⊕ x.Она самодвойственная, т.к. (x1 ⊕ x2 ⊕ x3 )∗ = x1 ⊕ 1 ⊕ x2 ⊕ 1 ⊕ x3 ⊕ 1 ⊕ 1 = x1 ⊕ x2 ⊕ x3 . Отсюда следует, что[F ] = P2 , но ни одну функцию из F выкинуть нельзя, так как все, кроме 0, входят в T1 ; все, кроме 1, входят вT0 ; все, кроме x1 x2 , входят в L; и все, кроме x1 ⊕ x2 ⊕ x3 , входят в M. Лемма 1.13. Для любых двух классов среди T0 , T1 , L, S, M существует функция, принадлежащая одномуи не принадлежащая другому.T0 T1 L SM Просто предъявим требуемые функции для всех пяти классов. ВT00& 0 x1 ⊕ x2таблице в каждой клетке стоит функция, принадлежащая классу строкиT11& 1 x1 → x2и не принадлежащая классу столбца.
Функцию ψ определим следующимL101 x1 ⊕ x2образом: ψ(x1 , x2 , x3 ) := (0, 0, 0, 1, 0, 1, 1, 1). Проверим её свойства: очевидSxxψxно, что она самодвойственная (вспомните определение!). Она нелинейная,M10& 1так как ψ(0, x2 , x3 ) = x2 x3 . Теорема 1.14. Пусть A = [A], A 6= P2 ⇒ A содержится в одном из пяти классов T0 , T1 , L, S, M. Пусть A не содержится ни в одном из этих классов. По критерию Поста A = [A] = P2 . Противоречие. Определение. F называется предполным классом, если F = [F ] 6= P2 и ∀ f ∈/ F имеем {F , f } = P2 .Теорема 1.15. В P2 существует ровно 5 предполных классов T0 , T1 , L, S, M, и других нет.
Докажем, что любой из этих классов (например, S) – предполный. Первые два условия, очевидно,выполнены. По предыдущей лемме в нём есть функции, не принадлежащие T0 , T1 , L, M соответственно, а тогда∀ f∈/ S в системе S ∪ {f } есть функции, не принадлежащие ни одному из этих классов. Значит, S — предполныйкласс.Теперь докажем, что других предполных классов нет. Допустим, A = [A] 6= P2 , и A не совпадает ни с однимиз этих пяти классов.
Тогда по предыдущей теоремеh A содержитсяв одном из них (обозначим его через X ).iA 6= X , A ⊆ X ⇒ ∃ f ∈/ A, f ∈ X ⇒ A ∪ {f } ⊆ X ⇒ A ∪ {f } ⊆ X 6= P2 . Значит, система A ∪ {f } неполная, атогда по определению A — не предполный класс. Теорема 1.16 (E. Post). В P2 имеется счётное множество замкнутых классов.12. k-значная логика2.1. Функции k-значной логикиАналогично функциям двузначной логики можно определить функции k-значной логики. Значения переменных и самих функций лежат в множестве {0, 1, . .
. , k − 1}. Множество всех таких функций обозначается черезPk . Аналогично эти функции можно задавать таблицей:1 Доказательстваэтой теоремы в нашем курсе не будет.9x10α1k−1..................xn0f (x1 , . . . , xn )f (0, . . . , 0)...f (α1 , . . . , αn )...f (k − 1, .
. . , k − 1)αnk−1Количество различных наборов значений равно k n , на каждом наборе функция может принимать k значений,nследовательно, всего функций будет pk (n) = k k . Понятия формулы, значения формулы, существенной зависимости, полноты и т.д. вводятся также, как в булевой алгебре. Однако есть и существенные отличия. Приведёмодно из них. В двузначной логике имеет место следующееУтверждение 2.1. Пусть f (x1 , . . . , xn ) и g(y1 , .
. . , ym ) существенно зависят от всех своих переменных.Тогда функция h(x1 , . . . , xn−1 , y1 , . . . , ym ) := f x1 , . . . , xn−1 , g(y1 , . . . , ym ) также существенно зависит от всехсвоих переменных. Все переменные равноправны, поэтому достаточно доказать утверждение для x1 и ym . Переменная x1 —существенная для f , поэтому найдутся наборы αe0 = (0, α2 , . . . , αn ) и αe1 = (1, α2 , .
. . , αn ), такие, что f (eα0 ) 6=e такой, что g(β)e = αn . Значит, f 0, α2 , . . . , αn−1 , g(β)e =6= f (eα1 ). Но так как g 6= const, то найдётся набор β,e . Значит, h существенно зависит от x1 . Поскольку f существенно= f (eα0 ) 6= f (eα1 ) = f 1, α2 , . .
. , αn−1 , g(β)зависит от xn , то найдутся наборы γe0 = (γ1 , . . . , γn−1 , 0) и eγ1 = (γ1 , . . . , γn−1 , 1), такие, что f (eγ0 ) 6= f (eγ1 ). Аналогично найдутся δe0 = (δ1 , . . . , δm−1 , 0) и δe1 = (δ1 , . . . , δm−1 , 1), такие, что g(δe0 ) 6= g(δe1 ). Тогда h обнаруживаетсущественную зависимость от ym на наборах (γ1 , . . .
, γn−1 , δ1 , . . . , δm−1 , 0) и (γ1 , . . . , γn−1 , δ1 , . . . , δm−1 , 1). Это утверждение перестаёт быть верным в k-значной логике при k = 3. Рассмотримфункцию ϕ(x, y) == (0, 0, 0, 0, 0, 0, 0, 0, 1), которая равна 1 только на наборе (2, 2). Тогда ϕ x, ϕ(y, z) — константа 0, потому чтодля любых y и z имеем ϕ(y, z) 6= 2.Интересными для рассмотрения функциями в k-значной логике являются:• Константы 0, 1, . . . , k − 1;• Тождественная функция x;• Аналоги отрицания x + 1 (mod(k) и N (x) := k − 1 − x;(1, x = σ;k − 1, x = σ;и jσ (x) :=• Аналоги функции x : Jσ (x) :=0, x 6= σ0,x 6= σ• Аналоги конъюнкции min(x1 , x2 ) (далее — &) и x1 x2 (mod k);• Аналоги дизъюнкции max(x1 , x2 ) (далее — ∨) и x1 + x2 (mod k).σ2.2.
Полнота систем функций в PkУтверждение 2.2. Система {0, 1, . . . , k − 1 J0 (x), . . . , Jk−1 (x) min(x1 , x2 ) max(x1 , x2 )} — полная. В Pk имеет место аналог СДНФ:_Jσ1 (x1 )& . . . &Jσn (xn )&f (σ1 , . . . , σn ).f (x1 , . . . , xn ) =(σ1 ,...,σn )Действительно, подставим (α1 , . . . , αn ) в f и проверим равенство. Если (α1 , . . . , αn ) = (σ1 , . . . , σn ), то имеем Jσ1 (α1 )& . . . &Jσn (αn )&f (σ1 , . . . , σn ) = f (σ1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
