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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Определение 1. Замыканием системы функций Σ называется
множество всех логических функций, представимых формулами над
Σ.
Замыкание Σ обозначается [Σ].
Пример 1. Если Σ = Λ, то [Σ] = Λ.
Для Σ = {1, ⊕} замыканием служит множество [Σ] = {c
0
⊕
⊕ x
i
1
⊕ x
i
2
⊕ . . . ⊕ x
i
k
| 1 6 i
1
< i
2
< . . . < i
k
6 n, c
0
= 0 или 1} =
= {f(x
1
, x
2
, . . . , x
n
) | f(x
1
, x
2
, . . . , x
n
) = c
0
⊕ c
1
x
1
⊕ c
2
x
2
⊕ . . . ⊕ c
n
x
n
,
где c
i
∈ {0, 1} }.
Функции из [Σ] в последнем примере называются линейными
функциями. Обоснованием такого названия служит то обстоятельство,
что операция ⊕ является сложением по модулю 2, а сами функции
действительно линейны в арифметике вычетов по модулю 2.
Упражнение 1. Докажите свойства замыкания:
1) Σ ⊂ [Σ]; 2) [[Σ]] = [Σ];
3) если Σ
1
⊂ Σ
2
, то [Σ
1
] ⊂ [Σ
2
];
4) [Σ
1
] ∪ [Σ
2
] ⊂ [Σ
1
∪ Σ
2
].
Определение 2. Система функций Σ называется функционально
полной, если [Σ] = Λ, т.е. если любая логическая функция представима
формулой над Σ.
Иными словами, система функций {f
1
, f
2
, . . .} полна (слово «фун-
кционально» часто опускается), если любая логическая функция явля-
ется результатом суперпозиций функций этой системы.
Полная система функций Σ называется (функциональным) бази-
сом, если никакое собственное подмножество Σ
1
⊂ Σ, Σ
1
6= Σ не явля-
ется полной системой.
Пример 2. Σ
(1)
= Λ — полная система (это тривиальный факт).
Σ
(2)
= {¬, ∧, ∨} — полная система (ввиду существования для каж-
дой логической функции ДНФ или КНФ).
Следующее утверждение позволит нам расширить круг полных
систем.
Теорема 1. Если Σ
0
— функционально полная система и все
функции из Σ
0
представимы формулами над системой Σ, то Σ также
функционально полна.
/ Пусть h — произвольная логическая функция. По предположе-
нию, она представима формулой над Σ
0
. Запишем это следующим об-
разом: h = F[f
1
, f
2
, . . .], (f
i
∈ Σ
0
). В силу другого условия f
i
=
= G
i
[g
1
, g
2
, . . .], (g
i
∈ Σ) для любого f
i
∈ Σ
0
. Подставляя эти выра-
жения в формулу F , получим
h = F [G
1
[g
1
, g
2
, . . .], G
2
[g
1
, g
2
, . . .], . . .] = H[g
1
, g
2
, . . .],
28

Страницы