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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

I. Построим константы.
Рассмотрим функцию ϕ(x) = f
1
(x, . . . , x). Поскольку f
1
не сохра-
няет 0, ϕ(0) = f
1
(0, . . . , 0) = 1. Если ϕ(1) = 1, то ϕ(x ) есть константа 1, а
так как f
2
не сохраняет 1, то f
2
(1, . . . , 1) = 0 и ψ(x) = f
2
(ϕ(x), . . . , ϕ(x))
есть константа 0.
Если же ϕ(1) = 0, то ϕ(x) = x. Так как теперь x находится в
нашем распоряжении, в силу леммы 1 из несамодвойственной функции
f
3
можно получить константу, а затем также с помощью x и другую
константу.
II. Построим при помощи констант 0, 1 и немонотонной функции
f
4
функцию x, используя лемму 2.
III. Построим при помощи констант 0, 1, функции x и нелинейной
функции f
5
функцию x
1
∧ x
2
, используя лемму 3.
Таким образом, мы реализовали функции x и x
1
∧x
2
при помощи
формул над Σ. Но {¬, ∧} — полная система, следовательно, и система
Σ полна.
Пример 12. Система {1, 0, m, ∧}, где функция m задана форму-
лой m(x
1
, x
2
, x
3
) = x
1
⊕x
2
⊕x
3
, функционально полна. Действительно,
имеем: 1 /∈ T
0
, 0 /∈ T
1
, 0 /∈ S, m /∈ M, ∧ /∈ L. Удаление любой из функций
приводит к неполной системе, так как {0, m, ∧} ⊂ T
1
, {1, m, ∧} ⊂ T
0
,
{1, 0, ∧} ⊂ M, {1, 0, m} ⊂ L.
Упражнение 6. Покажите, что {d}, где d(x
1
, x
2
, x
3
, x
4
) = x
1
x
4
∨ x
2
x
3
, — пол-
ная система. Проверьте выполнение условий критерия полноты и выразите основ-
ные логические связки через функцию d.
36

Страницы