О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

. . , xn ), 0, 1}:_f=xσ1 1 · . . . · xσk k f (σ1 , . . . , σk , xk+1 , . . . , xn ).(3)(σ1 ,...,σk )5 Возьмём произвольный набор αe = (α1 , . . . , αn ) и найдём значение формулы на этом наборе. В томслучае, когда (α1 , . . . , αk ) = (σ1 , .

. . , σk ), имеем ασ1 1 · . . . · ασk k f (σ1 , . . . , σk , αk+1 , . . . , αn ) = f (eα). Если (σ1 , . . . , σk ) 6=6= (α1 , . . . , αk ), то ασ1 1 · . . . · ασk k f (σ1 , . . . , σk , αk+1 , . . . , αn ) = 0. Следовательно, расписав (3) по всем наборам,получим 0 ∨ . . . ∨ 0 ∨ f (x1 , . . . , xn ) ∨ 0 ∨ . . . ∨ 0 = f (x1 , .

. . , xn ). Рассмотрим два частных случая для числа k.1◦ k = 1. f (x1 , . . . , xn ) = x1 f (0, x2 , . . . , xn ) ∨ x1 f (1, x2 , . . . , xn ).2◦ k = n. Для дизъюнкции надо брать лишь наборы σe = (σ1 , . . . , σn ), для которых f (eσ ) = 1, так как всеостальные дизъюнкты обнулятся:_f (x1 , .

. . , xn ) =xσ1 1 . . . xσnn .σe: f (eσ)=1Это формула для f над {¬ & ∨}. Она называется совершенной дизъюнктивной нормальной формой (СДНФ).Пример 4.1. x → y = x y ∨ x ∨ xy, x ⊕ y = xy ∨ xy, x ∼ y = x y ∨ xy, где x ∼ y = (1001).1.5. Полнота систем функцийОпределение. Система F называется полной, если любая функция из P2 выражается формулой над F .Теорема 1.2 (Достаточное условие полноты).

Пусть дана полная система F , и любая функция из Fвыражается формулой над системой G. Тогда G — полная. Пусть F = {f1 , f2 , . . . } и Fi — формулы над G, выражающие функции fi соответственно. Возьмёмпроизвольную функцию f ∈ P2 , тогда существует формула F0 над F , выражающая эту функцию. Заменим вформуле каждую из функций fi на соответствующую ей формулу Fi , и получим формулу над G, выражающуюфункцию f . Значит, любая функция из P2 выражается формулой над G, поэтому система G — полная. Теорема 1.3. Из любой полной системы можно выделить конечную полную подсистему. Пусть F — полная система (возможно, бесконечная), тогда существуют формулы над F , выражающиефункции ¬, &, ∨. В каждую из этих формул входит конечное число функций из F , значит, эти функции образуютконечную подсистему G. Так как функции ¬, &, ∨ выражаются формулами над G, а {¬ & ∨} — полная система,то G будет конечной полной подсистемой.

Используя достаточное условие полноты, построим ещё несколько полных систем:1. {& ¬}. Действительно, конъюнкция и отрицание у нас есть. Так как x1 ∨ x2 = x1 &x2 , то и дизъюнкциятоже есть. Значит, система полная.2. {∨ ¬}. Аналогично, так как x1 &x2 = x1 ∨ x2 .3. {⊕ & 1}. Конъюнкция уже есть, отрицание выразим так: x =x ⊕ 1. Значит, система полная.4. {/} — штрих Шеффера: x = x/x, а x1 &x2 = x1 /x2 = (x1 /x2 ) (x1 /x2 ). Значит, система является полной.5. {↓} — стрелка Пирса — тоже полная система. Доказательство — аналогично предыдущему.1.6. Полиномы ЖегалкинаРассмотрим конъюнкции вида xi1 . . .

xik , где все i1 , . . . , ik — различны. Также будем рассматривать конъюнкции длины 1 (т. е. переменные) и константу 1 (конъюнкцию длины 0).Определение. Сумма по модулю 2 попарно различных коньюнкцийXxi1 . . . xik(i1 ,...,ik )называется полиномом Жегалкина. Пустой полином Жегалкина по определению выражает нулевую функцию.Степенью полинома называется максимальная длина конъюнкций переменных, входящих в него.Теорема 1.4 (Жегалкина). Любая функция алгебры логики представима в виде полинома Жегалкинаединственным образом с точностью до перестановки слагаемых и перестановки множителей в слагаемых.

Представимость. Так как {⊕ & 1} — полная система, то любая функция представима формулой над{⊕ & 1}. Приведём эту формулу к полиному Жегалкина:1◦ Раскроем все скобки, применив дистрибутивный закон (A ⊕ B)C = AC ⊕ BC. Тогда формула приведётсяк сумме конъюнкций A1 ⊕ · · · ⊕ As .2◦ Так как xx = x, то, если в каком-либо произведении встречаются повторяющиеся переменные, можнооставить только один экземпляр.3◦ Уничтожим лишние единицы: x&1 = x, поэтому если в каком-либо произведении встречаются единицы,можно их убрать (лишь в случае произведения только из единиц оставим одну единицу).64◦ Приведём подобные: x⊕x = 0, значит, если есть повторяющиеся слагаемые, оба экземпляра можно убрать.Если пропадут все слагаемые, это будет пустой полином.В итоге мы получим полином Жегалкина.

Тем самым представимость доказана.Единственность. Поскольку в любое произведение любая переменная может входить или не входить, товсего различных произведений из n переменных будет 2n , но из них нужно убрать нулевое произведение идобавить константу 1, т.

е. всего рассматриваемых нами произведений будет тоже 2n . Так как в полиноме любоепроизведение может присутствовать или не присутствовать, всего различных полиномов (включая пустой) будетnровно 22 , т. е. столько же, сколько всех функций в P2 (n).

Поэтому, если какая-нибудь функция представимав виде двух различных полиномов Жегалкина, то какая-то функция не будет представима в этом виде, чтоневозможно. 1.7. Замкнутые классы функцийОпределение. Замыканием системы F называется множество [F ], состоящее из всех функций, выражаемыхформулой над F . Система F называется замкнутой, если F = [F ].Свойства операции замыкания:1◦ F ⊆ [F ].2◦ F1 ⊆ F2 ⇒ [F1 ] ⊆ [F2 ].3◦ [F 1∪ F2 ] ⊇ [F1 ] ∪ [F2 ].4◦ [F ] = [F ].5◦ Если F — полная система, то [F ] = P2 .Определение.

Функции, представимые полиномами Жегалкина первой степени, называются линейными.Линейные функции имеют вид x1 ⊕ · · · ⊕ xk ⊕c, где c ∈ B. Их множество обозначается через L. Оно, очевидно,является замкнутым. Это множество нетривиально, т. е. L 6= ∅, L 6= P2 .Лемма 1.5 (О нелинейной функции). Из любой нелинейной функции, подставляя вместо некоторыхпеременных константы, и, может быть, отрицание переменных, и, может быть, навешивая отрицание нарезультат, можно получить конъюнкцию двух переменных. Пусть f (x1 , .

. . , xn ) ∈/ L, тогда в её полиноме Жегалкина есть произведение длины больше 1. Возьмёмсамое короткое из них, переставим его на первое место: f (x1 , . . . , xn ) = x1 . . . xp ⊕ . . . , p > 2.Каждое другое нелинейное произведение содержит хотя бы одну переменную, отличную от x1 , . . . , xp .

Вместо этих переменных, кроме x1 , . . . , xp , подставим 0, тогда все остальные нелинейные конъюнкции обратятсяв 0, и останется f (x1 , . . . , xp , 0, . . . , 0) = x1 . . . xp ⊕ l(x1 , . . . , xp ), где l(x1 , . . . , xp ) — линейная функция от переменных x1 , . . . , xp . Оставим первые две переменные, а вместо остальных (если они есть) подставим 1, получим f (x1 , x2 , 1, . . .

, 1, 0, . . . , 0) = x1 x2 ⊕ l(x1 , x2 ) = x1 x2 ⊕ αx1 ⊕ βx2 ⊕ γ. Сделаем следующую подстановку:вместо x1 подставим x1 ⊕ β (это будет либо x1 , либо x1 ), x2 заменим на x2 ⊕ α и прибавим ко всей функции (αβ ⊕ γ), т. е. либо ничего не изменим, либо навесим отрицание на результат. В итоге получится следующая функция: (x1 ⊕ β)(x2 ⊕ α) ⊕ α(x1 ⊕ β) ⊕ β(x2 ⊕ α) ⊕ γ ⊕ (αβ ⊕ γ). После раскрытия скобок получимx1 x2 ⊕ αx1 ⊕ βx2 ⊕ αβ ⊕ αx1 ⊕ αβ ⊕ βx2 ⊕ αβ ⊕ γ ⊕ αβ ⊕ γ = x1 x2 . Следствие 1.1. Если f ∈/ L, то & ∈ {f, 0, 1, ¬} .Рассмотрим ещё два замкнутых класса:1◦ Класс T0 функций, таких, что f (0, .

. . , 0) = 0. Очевидно, что это множество нетривиально.Утверждение 1.6. Класс T0 замкнут. Сами переменные принадлежат этому множеству: если f (x) = x, то f (0) = 0. Поэтому достаточнодоказать, что если f (x1 , . . . , xn ) ∈ T0 и f1 , . . . , fn ∈ T0 , то и f (f1 , . . . , fn ) ∈ T0 . Поскольку fi (0, . . . , 0) = 0, тоf f1 (0, . . . , 0), . . . , fn (0, . . . , 0) = f (0, .

. . , 0) = 0. Следовательно, класс T0 замкнут. 2◦ Класс T1 функций, таких, что f (1, . . . , 1) = 1. Этот класс тоже нетривиален и замкнут.Определение. Функция f ∗ (x1 , . . . , xn ) := f (x1 , . . . , xn ) называется двойственной к f (x1 , . . . , xn ). Функцияf называется самодвойственной, если f ∗ = f .Пример 7.1. x∗ = x = x, x∗ = x = x, (x1 x2 )∗ = x1 x2 = x1 ∨ x2 , (x1 ∨ x2 )∗ = x1 x2 , 0∗ = 0 = 1, 1∗ = 1 = 0.Множество самодвойственных функций обозначается через S.

Очевидно, что S нетривиально.Утверждение 1.7. Класс S замкнут. Ясно, что переменные входят в S, поэтому нам опять достаточно доказать, что если f (x1 , . . . , xn ) ∈ Sи f1 , . . . , fn ∈ S, то и f (f1 , . . . , fn ) ∈ S. Можно считать, что у всех функций fi одинаковый набор переменных,поскольку если это не так, то недостающие переменные можно добавить как несущественные. Пусть этот набор —7y1 , . . . , ym . Пусть g(y1 , .

. . , ym ) = f f1 (y1 , . . . , ym ), . . . , fn (y1 , . . . , ym ) . Тогдаg ∗ (y1 , . . . , ym ) = f f1 (y 1 , . . . , ym ), . . . , fn (y 1 , . . . , y m ) = f f1 (y 1 , . . . , y m ), . . . , fn (y 1 , . . . , y m ) == f f1∗ (y1 , . . . , ym ), . . . , fn∗ (y1 , .

. . , ym ) = f ∗ f1∗ (y1 , . . . , ym ), . . . , fn∗ (y1 , . . . , ym ) = g(y1 , . . . , ym ),поскольку f, f1 , . . . , fn ∈ S. Замечание. Пусть f (x1 , . . . , xn ) ∈ S, тогдаf (x1 , . . . , xn ) = f (x1 , . . . , xn ) ⇔ f (x1 , . . . , xn ) = f (x1 , . . . , xn ) ⇔ f (x1 , . . . , xn ) = f (x1 , . . . , xn ),т. е. на противоположных наборах переменных значения функции противоположны.Лемма 1.8 (О несамодвойственной функции). Пусть f (x1 , . . .

, xn ) ∈/ S, тогда, подставляя в неё вместо переменной xi переменную x или x, можно получить константу. Поскольку f (x1 , . . . , xn ) ∈/ S, то существует пара противоположных наборов (α1 , . . . , αn ) и (α1 , . . . , αn ):f (α1 , . . . , αn ) = f (α1 , . . . , αn ). Заменим xi на xi ⊕αi , т. е. вместо xi поставим либо xi , либо xi , и получим функциюh(x) = f (x ⊕ α1 , .

. . , x ⊕ αn ), а поскольку h(0) = f (α1 , . . . , αn ), h(1) = f (α1 , . . . , αn ), получаем, что h(0) = h(1),т. е. h(x) является константой. Следствие 1.2. Если f ∈/ S, то {0, 1} ⊂ {f, ¬} . По лемме одна из констант уже есть. С помощью отрицания можно получить и вторую константу. Введём правило сравнения наборов. Будем говорить, что (α1 , . . . , αn ) 6 (β1 , . . .

, βn ), если αi 6 βi , i = 1, n.При этом мы считаем, что 0 6 0, 0 6 1, 1 6 1, но 1 0. Теперь мы можем упорядочить (частично!) все наборы:(0, . . . , 0) 6 (α1 , . . . , αn ) 6 (1, . . . , 1).Определение. Функция f (x1 , . . . , xn ) называется монотонной, если ∀ (α1 , . . . , αn ) 6 (β1 , . . . , βn ) имеемf (α1 , . . . , αn ) 6 f (β1 , . .

. , βn ). Множество всех монотонных функций обозначается M.Пример 7.2. Функции 0, 1, x, x1 x2 монотонны (это видно из таблицы), а функции x, x1 x2 — нет.Как мы видим из примеров, множество функций M нетривиально.Утверждение 1.9. Класс M замкнут. Переменные принадлежат этому множеству, значит, достаточно доказать, что из f (x1 , . . . , xn ) ∈ Mи f1 , . . . , fn ∈ M следует, что f (f1 , . .

Характеристики

Список файлов лекций