Элементы математической логики. Фролов И.С. - 36 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

α
i
1
= α
i+1
1
, . . . , α
i
j−1
= α
i+1
j−1
, α
i
j
= 0 < α
i+1
j
= 1,
α
i
j+1
= α
i+1
j+1
, , . . . , α
i
n
= α
i+1
n
.
Положим F (x) = f(α
i
1
, . . . , α
i
j−1
, x, α
i
j+1
, . . . , α
i
n
). Тогда F (0) =
= f(α
i
1
, . . . , α
i
n
) = 1, F (1) = f(α
i+1
1
, . . . , α
i+1
n
) = 0, т.е. F (x) = x.
Лемма 3. Если f — нелинейная функция, то из нее путем под-
становки констант 0 и 1 и функций вида x и x, а также, быть может,
путем применения к ней ¬ можно получить функцию x
1
∧ x
2
.
Пусть f /∈ L. Если представить f в форме многочлена Же-
галкина, то в нем непременно найдется циклическое слагаемое вида
x
i
1
x
i
2
. . . x
i
k
(k > 2). Без ограничения общности можно считать, что
i
1
= 1, i
2
= 2. Положим x = x
1
, y = x
2
и представим функцию f в
виде xyf
1
(x
3
, . . . , x
n
) ⊕ xf
2
(x
3
, . . . , x
n
) ⊕ yf
3
(x
3
, . . . , x
n
) ⊕ f
4
(x
3
, . . . , x
n
),
причем f
1
6≡ 0. Выберем α
3
, . . . , α
n
так, чтобы f
1
(α
3
, . . . , α
n
) = 1. Рас-
смотрим функцию h(x, y) = f(x, y, α
3
, . . . , α
n
) = xy ⊕ αx ⊕ βy ⊕ γ, где
α, β, γ ∈ {0, 1}. В зависимости от значений α, β и γ возможны 8 случаев:
α β γ h(x, y) Эквив.булева ф-ла Реализация x ∧ y
0 0 0 xy x ∧ y x ∧ y = h(x, y)
0 0 1 xy ⊕ 1 ¬(x ∧ y) x ∧ y = ¬h(x, y)
0 1 0 xy ⊕ y ¬x ∧ y x ∧ y = h(¬x, y)
0 1 1 xy ⊕ y ⊕ 1 x ∨ ¬y x ∧ y = ¬h(¬x, y)
1 0 0 xy ⊕ x x ∧ ¬y x ∧ y = h(x, ¬y)
1 0 1 xy ⊕ x ⊕ 1 ¬x ∨ y x ∧ y = ¬h(x, ¬y)
1 1 0 xy ⊕ x ⊕ y x ∨ y x ∧ y = ¬h(¬x, ¬y)
1 1 1 xy ⊕ x ⊕ y ⊕ 1 ¬(x ∨ y) x ∧ y = h(¬x, ¬y)
В каждом случае можно получить функцию x ∧ y.
Доказательство теоремы.
Необходимость. Пусть система Σ функционально полна. Тогда
[Σ] = Λ, но если бы Σ содержалась в одном из указанных замкнутых
классов (обозначим его Σ
0
), то в силу свойств замыкания [Σ] ⊂ [Σ
0
] =
= Σ
0
6= Λ.
Достаточность. Пусть система Σ целиком не содержится ни в од-
ном из пяти указанных замкнутых классов. Тогда в Σ найдется функ-
ция f
1
, не сохраняющая 0, функция f
2
, не сохраняющая 1, несамодвой-
ственная функция f
3
, немонотонная функция f
4
, нелинейная функция
f
5
. Без ограничения общности можно считать, что все эти функции
зависят от одних и тех же переменных x
1
, . . . , x
n
.
Докажем, что из этих функций можно получить константы 0 и 1,
отрицание и конъюнкцию.
35

Страницы