Т0 - класс функций, сохраняющих константу 0.
Т0 = { f(x1, ..., xn | f(0, ..., 0) = 0, n = 1, 2, ...}. Покажем, что Т0 является собственным подмножеством Р2, т.е. Т0 ¹ Æ и Т0 Ì Р (не совпадает с Р2). Для этого достаточно привести примеры функций, входящих в Т0, и примеры функций из Р2, не входящих в Т0: x1&x2, x1Úx2, xÎТ0 и x1|x2, x1 
x2, 
ÏТ0. Покажем далее, что [Т0] = Т0. Вложение Т0 Í [ Т0] очевидно, так как по определению формулы любая функция из Т0 является формулой над Т0 и, следовательно, принадлежит [Т0]. Покажем, что [Т0]Í Т0. Для этого надо показать, что Ф = f(f1, ..., fm) Î [ Т0], если все функции f, f1, f2, f3, ..., fm Î Т0. Надо заметить, что в формуле в качестве функции f1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т0, поэтому достаточно показать, что Ф = f (f 1, ..., fm) Î Т0. Для этого рассмотрим следующую функцию: Ф(0, ..., 0) = f (f 1(0, ..., 0), f 2(0, ..., 0), ...) = f(0, ..., 0) = 0.
Число функций, зависящих от n переменных и принадлежащих Т0, будет равно 
2) T1 – класс функций, сохраняющих константу 1.
T1 = {f(x1, ...) |f(1, 1, ...) = 1}; x1&x2, x1Úx2, xÎT1, х1Åх2, x1 x2ÏT1, следовательно Т1 – собственное подмножество Р2. 
Покажем, что [T1] Í T1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т1, можно рассмотреть Ф = f(f1, ..., fn) Î [T1], где f, f1, ..., fn Î T1. Найдем Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f1, ..., fn) Î T1, отсюда следует [T1] = T1.
Дата добавления: 2016-03-27; просмотров: 1379;