![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Замыкание и замкнутые классыСодержание книги Поиск на нашем сайте
Определение 2.11. Пусть M Í Р 2. Замыканием М называется множество всех функций из P 2, которые можно выразить формулами над М. Замыкание М обозначается [ M ]. Определение 2.12. Множество функций М называется замкнутым классом, если [ M ]= M. Пример 2.19 1) P 2 – замкнутый класс. 2) Множество {1, x 1Å x 2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x 1 Å x 2}] = { f (x 1,..., xn) c 0 Å c 1 x 1 Å... Å cnxn }. Действительно, по определению формулы над М, функция f (G 1, x 3), где f есть сумма по модулю 2, G 1 – функция х 1 Å х 2, будет формулой над М: f (G 1, x 3) = (x 1 Å x 2) Å x 3. З амечание. В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному: М – полная система, если [ M ] = P 2. 3) A = { f (x 1,..., xn)| f (1, 1,..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g 1,..., gn Î A, т.е. f (1, 1,..., 1) = 0, g 1(1, 1,..., 1) = 0, тогда f (g 1,..., gn) Î [ A ]. Посмотрим, принадлежит ли функция f (g 1,..., gn) множеству А. f (g 1(1,..., 1), g 2(1,..., 1),..., gn (1,..., 1) = f (0,..., 0)), но f (0,..., 0) не обязано быть равным 0. Действительно, пусть g 1(x 1, x 2) = x 1 Å x 2, g 2(x) = x Î A. Возьмем g 2(g 1(x 1, x 2)) = x 1 Å x 2 Î [ A ], g 2(g 1(1, 1)) = 1 Å 1 = 0, следовательно, g 2(g 1(x 1, x 2)) Ï A, отсюда [ A ] ¹ A и А – незамкнутый класс.
Важнейшие замкнутые классы в Р2 1) Т0 - класс функций, сохраняющих константу 0 Т 0 = { f (x 1,..., xn)| f (0,..., 0) = 0, n = 1, 2,...}. Покажем, что Т 0 является собственным подмножеством Р 2, т.е. Т 0 ¹ Æ и Т 0 Ì Р (не совпадает с Р 2). Для этого достаточно привести примеры функций, входящих в Т 0, и примеры функций из Р2, не входящих в Т 0: x 1& x 2, x 1Ú x 2, x Î Т 0 и x 1| x 2, x 1 [ Т 0], если все функции f, f 1, f 2, f 3,..., f m Î Т 0. Надо заметить, что в формуле в качестве функции f 1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т 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 T 1 = { f (x 1,...) | f (1, 1,...) = 1}; x 1& x 2, x 1Ú x 2, x Î T 1, х 1Å х 2, x 1 Покажем, что [ T 1] Í T 1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т 1, можно рассмотреть Ф = f (f 1,..., fn) Î [ T 1], где f, f 1,..., fn Î T 1. Найдем Ф (1,..., 1) = f (f 1(1,..., 1),..., fn (1,..., 1)) = f (1,..., 1) = 1, следовательно, Ф = f (f 1,..., fn) Î T 1, отсюда следует [ T 1] = T 1. 3) S – класс самодвойственных функций S = { f (x 1,...)| f * = f }; x, 4) L – класс линейных функций L = { f (x 1,...)| f = c 0Å c 1 x 1Å...Å cnxn }; очевидно, L ¹ Æ, с другой стороны L ¹ P 2, так как x 1& x 2 Ï L. Заметим, что тождественная функция принадлежит L и | L (n)| = 2 n +1. Покажем, что [ L ] Í L. Рассмотрим Ф = f (f 1,..., fm), где f, f 1,..., fn Î L. Тогда Ф = а 0 Å а 1(с 10 Å с 11 х 1 Å...Å c 1 nxn 1) Å a 2(c 20 Å c 21 x 1 Å c 22 x 2Å...Å c 2 nxn 2)Å...Å an (cm 0 Å cm 1x1 Å... Å cmnxnm) = в 0 Å в 1 х 1 Å...Å вnхn Þ Ф Î L. 5) М – класс монотонных функций Определение 2.13. Набор Определение 2.14. Функция f (x 1,..., xn) называется монотонной, если для двух наборов Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М – замкнутый класс. Рассмотрим функцию Ф Î[ M ], Ф = f (f 1,..., fm), где f, f 1,..., fm Î M, причем можем считать, что все они зависят от n переменных. Пусть набор
Классы T 0, T 1, L, S, M пересекаются, но не совпадают, что видно из табл. 2.22, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит. Таблица 2.22
A ={ x,
|
||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-07-14; просмотров: 169; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.99.84 (0.009 с.) |