Изменения

Перейти к: навигация, поиск

Полные системы функций. Теорема Поста о полной системе функций

537 байт добавлено, 10:23, 16 октября 2011
использован вики-шаблон, переформулированы определения, исправлены мелкие ошибки, источники литературы, ссылка на "полные сис. функ."
== Полная система функций ==
Система [[Определение булевой функции|булевых функций ]] называется ''полной'', если можно построить их [[Суперпозиции|суперпозицию]], тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории [[Определение булевой функции|булевых функций]], устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом в 1941г.
== Замкнутые классы булевых функций ==
* Класс функций <tex>T_0</tex>. {{Определение|definition=Говорят, сохраняющих что функция сохраняет константу 0: , если <tex>f(0, 0, \dots, 0) = 0</tex>.}}
<tex>f(0, 0, \dots, 0) = 0</tex>
Функция Класс функций <tex>T_1</tex>. {{Определение|definition=Говорят, что функция сохраняет 0 тогдаконстанту 1, если <tex>f(1, 1, и только тогда\dots, когда первое значение в ее таблице истинности равно 01) = 1</tex>.}}
* Класс функций <tex>T_1</tex>, сохраняющих константу 1:
Класс самодвойственных функций <tex>S</tex>.{{Определение|definition=Говорят, что функция самодвойственна, если <tex>f(1\overline{x_1}, 1\dots,\overline{x_n})=\overline{f(x_1, \dots, 1x_n) = 1}</tex>. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.}}
Функция сохраняет 1 тогдаКласс монотонных функций <tex>M</tex>.{{Определение|definition=Говорят, что функция монотонна, если <tex>\forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1, и только тогда\dots, когда последнее значение в ее таблице истинности равно 1b_n)</tex>.}}
* Класс самодвойственных линейных функций <tex>SL</tex>:. <tex>f(\overline{x_1},\dots,\overline{x_n})Определение|definition=\overline{f(x_1Говорят,\dotsчто функция линейна,x_n)}если существуют такие </tex> Пусть <tex>a(i)</tex> — i-я строка таблицы истинности <tex>f(i)</tex>. В таких обозначениях функция <tex>f(i)</tex> является самодвойственной тогдаa_0, a_1, и только тогдаa_2, когда <tex>a(i)=\overline{a(N+1-i)}dots, a_n</tex>, где <tex>N — </tex> количество строк в таблице истинности. Т. е. функция является самодвойственной, если значения, расположенные в таблице истинности симметрично относительно центра, не равны. * Класс монотонных функций <tex>M</tex>: <tex>\forall i (a_i\le b_i) in \Rightarrow f(a_1{0,1\dots},a_n)\le f(b_1,forall i=\dotsoverline{1,b_n)n}</tex> Функция является монотонной тогда, и только тогда, когда что для любых параметров функции, изменение некоторых из них с <tex>0</tex> на <tex>1</tex> не приводит к уменьшению ее значения. Примером монотонной функции от двух переменных является <tex>and</tex>. Примером немонотонной булевой функции от двух переменных является <tex>xor</tex>, т. к. для значений <tex>(0x_1, 1)</tex> функция принимает значение <tex>1</tex>x_2, а\dots, при замене первого параметра на <tex>1x_n</tex>, функция уменьшает свое значение.имеет место равенство:* Класс линейных функций <tex>L</tex>: <tex>f(x_1, x_2,\dots,x_n)=a_0\oplus a_1x_1a_1\cdot x_1\oplusa_2\dotscdot x_2 \oplus a_nx_n,a_i\indots\{0,1oplus a_n\}cdot x_n</tex>.}}Очевидно, что количество линейных функций от <tex>n</tex> переменных всего равно <tex>~2^{n+1}</tex>.
Функция является линейной тогда, и только тогда, когда в ее полиноме [[Полином_Жегалкина|Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].
В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' {{---}} полная система функций, что и требовалось доказать.
}}
 
== Примеры полных систем булевых функций от двух переменных ==
 
Широко известна [[Представление функции формулой, полные системы функций|полная система функций]] <tex>\left\{\land,\lor,\neg\right\}</tex>. Однако, эта система функций не является безызбыточной, т. к. функцию <tex>\land</tex> можно выразить через <tex>\lor</tex> и <tex>\neg</tex>. Система функций <tex>\left\{\lor,\neg\right\}</tex> безызбыточная, т. к. функция <tex>\lor</tex> является несамодвойственной и нелинейной, а функция <tex>\neg</tex> не сохраняет 0, не сохраняет 1 и немонотонна. Система функций <tex>\left\{\land,\lor,\neg\right\}</tex> используется для представления функций в [[СДНФ|СДНФ]] и [[СКНФ|СКНФ]].
 
Также существуют полные системы функций, состоящие только из одной функции. Это <tex>\triangledown</tex> и <tex>\downarrow</tex>.
 
== Источники ==
* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]
* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]
* [http://www.mielt.ru/dir/cat14/subj266/file299/view1397.html Лекции по дискретной математике]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции]]
Qwerty787788
81
правка
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/11259»

Навигация