Полные системы функций. Теорема Поста о полной системе функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Замкнутые классы булевых функций)
(использован вики-шаблон, переформулированы определения, исправлены мелкие ошибки, источники литературы, ссылка на "полные сис. функ.")
Строка 1: Строка 1:
 
== Полная система функций ==
 
== Полная система функций ==
Система булевых функций называется ''полной'', если можно построить их [[Суперпозиции|суперпозицию]], тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.
+
Система [[Определение булевой функции|булевых функций]] называется ''полной'', если можно построить их [[Суперпозиции|суперпозицию]], тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.
  
 
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
 
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
Строка 11: Строка 11:
  
 
== Критерий Поста ==
 
== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории [[Определение булевой функции|булевых функций]], устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом в 1941г.
+
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом в 1941г.
  
 
== Замкнутые классы булевых функций ==
 
== Замкнутые классы булевых функций ==
* Класс функций <tex>T_0</tex>, сохраняющих константу 0:
+
Класс функций <tex>T_0</tex>.
 +
{{Определение
 +
|definition=Говорят, что функция сохраняет константу 0, если <tex>f(0, 0, \dots, 0) = 0</tex>.
 +
}}
  
<tex>f(0, 0, \dots, 0) = 0</tex>
 
  
Функция сохраняет 0 тогда, и только тогда, когда первое значение в ее таблице истинности равно 0.
+
Класс функций <tex>T_1</tex>.
 +
{{Определение
 +
|definition=Говорят, что функция сохраняет константу 1, если <tex>f(1, 1, \dots, 1) = 1</tex>.
 +
}}
  
* Класс функций <tex>T_1</tex>, сохраняющих константу 1:
 
  
<tex>f(1, 1, \dots, 1) = 1</tex>
+
Класс самодвойственных функций <tex>S</tex>.
 +
{{Определение
 +
|definition=Говорят, что функция самодвойственна, если <tex>f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}</tex>. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.
 +
}}
  
Функция сохраняет 1 тогда, и только тогда, когда последнее значение в ее таблице истинности равно 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,b_n)</tex>.
 +
}}
  
* Класс самодвойственных функций <tex>S</tex>:
+
Класс линейных функций <tex>L</tex>.
 
+
{{Определение
<tex>f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}</tex>
+
|definition=Говорят, что функция линейна, если существуют такие <tex>a_0, a_1, a_2, \dots, a_n</tex>, где <tex>a_i \in \{0, 1\}, \forall i=\overline{1,n}</tex>, что для любых <tex>x_1, x_2, \dots, x_n</tex> имеет место равенство:
 
+
:<tex>f(x_1, x_2, \dots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\dots\oplus a_n\cdot x_n</tex>.
Пусть <tex>a(i)</tex>  — i-я строка таблицы истинности <tex>f(i)</tex>. В таких обозначениях функция <tex>f(i)</tex> является самодвойственной тогда, и только тогда, когда <tex>a(i)=\overline{a(N+1-i)}</tex>, где <tex>N — </tex> количество строк в таблице истинности. Т. е. функция является самодвойственной, если значения, расположенные в таблице истинности симметрично относительно центра, не равны.
+
}}
 
+
Очевидно, что количество линейных функций от <tex>n</tex> переменных равно <tex>~2^{n+1}</tex>.
* Класс монотонных функций <tex>M</tex>:
 
 
 
<tex>\forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1,\dots,b_n)</tex>
 
 
 
Функция является монотонной тогда, и только тогда, когда для любых параметров функции, изменение некоторых из них с <tex>0</tex> на <tex>1</tex> не приводит к уменьшению ее значения. Примером монотонной функции от двух переменных является <tex>and</tex>. Примером немонотонной булевой функции от двух переменных является <tex>xor</tex>, т. к. для значений <tex>(0, 1)</tex> функция принимает значение <tex>1</tex>, а, при замене первого параметра на <tex>1</tex>, функция уменьшает свое значение.
 
 
 
* Класс линейных функций <tex>L</tex>:
 
 
 
<tex>f(x_1,\dots,x_n)=a_0\oplus a_1x_1\oplus\dots\oplus a_nx_n,a_i\in\{0,1\}</tex>
 
 
 
Очевидно, что количество линейных функций от <tex>n</tex> переменных всего <tex>~2^{n+1}</tex>.
 
  
 
Функция является линейной тогда, и только тогда, когда в ее полиноме [[Полином_Жегалкина|Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].
 
Функция является линейной тогда, и только тогда, когда в ее полиноме [[Полином_Жегалкина|Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].
Строка 101: Строка 100:
 
В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' {{---}} полная система функций, что и требовалось доказать.
 
В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''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>.
 +
  
 
== Источники ==
 
== Источники ==
Строка 108: Строка 114:
 
* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]
 
* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]
 
* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]
 
* [http://en.wikipedia.org/wiki/Post%27s_lattice Post's lattice]
 +
* [http://www.mielt.ru/dir/cat14/subj266/file299/view1397.html Лекции по дискретной математике]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Булевы функции]]
 
[[Категория: Булевы функции]]

Версия 10:23, 16 октября 2011

Полная система функций

Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством [math]P_2[/math].

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

  • Функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math];
  • Самодвойственные функции [math]S[/math];
  • Монотонные функции [math]M[/math];
  • Линейные функции [math]L[/math].

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.

Критерий Поста

Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом в 1941г.

Замкнутые классы булевых функций

Класс функций [math]T_0[/math].

Определение:
Говорят, что функция сохраняет константу 0, если [math]f(0, 0, \dots, 0) = 0[/math].


Класс функций [math]T_1[/math].

Определение:
Говорят, что функция сохраняет константу 1, если [math]f(1, 1, \dots, 1) = 1[/math].


Класс самодвойственных функций [math]S[/math].

Определение:
Говорят, что функция самодвойственна, если [math]f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}[/math]. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.


Класс монотонных функций [math]M[/math].

Определение:
Говорят, что функция монотонна, если [math]\forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1,\dots,b_n)[/math].


Класс линейных функций [math]L[/math].

Определение:
Говорят, что функция линейна, если существуют такие [math]a_0, a_1, a_2, \dots, a_n[/math], где [math]a_i \in \{0, 1\}, \forall i=\overline{1,n}[/math], что для любых [math]x_1, x_2, \dots, x_n[/math] имеет место равенство:
[math]f(x_1, x_2, \dots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\dots\oplus a_n\cdot x_n[/math].

Очевидно, что количество линейных функций от [math]n[/math] переменных равно [math]~2^{n+1}[/math].

Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса.

Формулировка и доказательство критерия

Теорема:
Система булевых функций F является полной тогда и только тогда, когда она не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math], т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Доказательство:
[math]\triangleright[/math]

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным.

Докажем достаточность этого утверждения.

Рассмотрим функцию, несохраняющую 0 — [math]f_0[/math]. [math]f_0(0) = 1[/math]. [math]f_0(1)[/math] может принимать два значения:

а) [math]f_0(1) = 1[/math], тогда [math]f_0(x, x, x, \ldots, x) = 1[/math].

б) [math]f_0(1) = 0[/math], тогда [math]f_0(x, x, x, \dots, x) = \neg x[/math].

Рассмотрим функцию, несохраняющую 1 — [math]f_1[/math]. [math]f_1(1) = 0[/math]. [math]f_1(0)[/math] может принимать два значения:

а) [math]f_1(0) = 0[/math], тогда [math]f_1(x, x, x, \ldots, x) = 0[/math].

б) [math]f_1(0) = 1[/math], тогда [math]f_1(x, x, x, \ldots, x) = \lnot x[/math].

Возможны 4 варианта:

1) Мы получили функцию НЕ. Используем несамодвойственную функцию [math]f_s[/math].

По определению найдется такой вектор [math]x_0[/math], что [math]f_s(x_0) = f_s(\lnot x_0)[/math]. [math]x_0 = (x_{01}, x_{02}, ..., x_{0k})[/math].

Возьмем [math]f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})[/math], где [math]x^{x_{0i}} = x[/math], при [math]x_{0i} = 1[/math] и [math]x^{x_{0i}} = \lnot x[/math], при [math]x_{0i} = 0 [/math].

Нетрудно заметить, что [math]f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}[/math]. Таким образом мы получили одну из констант.

2)Мы получили НЕ и [math]0[/math]. [math]\lnot 0 = 1[/math].

3)Мы получили НЕ и [math]1[/math]. [math]\lnot 1 = 0[/math].

4)Мы получили [math]1[/math] и [math]0[/math].

Рассмотрим немонотонную функцию [math]f_m[/math]. Существуют такие [math]x_1, x_2, \ldots, x_n[/math], что [math]f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) = 1[/math], [math]f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0[/math], зафиксируем все [math]x_1, x_2, \ldots, x_n[/math], тогда [math]f_m(x_1, x_2, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x[/math].

В итоге имеем три функции: НЕ, [math]0[/math], [math]1[/math].

Используем нелинейную функцию [math]f_l[/math]. Среди нелинейных членов [math]f_l[/math], выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назовем [math]x_1[/math] и [math]x_2[/math], а все элементы, не входящие в данный член, сделаем равными 0. Тогда [math]f_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1][/math], где в квадратных скобках указаны члены, которые могут и не присутствовать.

Рассмотрим несколько вариантов:

  1. Присутствует член [math]~1[/math]. Возьмем отрицание от [math]f_l[/math] и член [math]~1[/math] уберется.
  2. Присутствуют 3 члена, без [math]~1[/math]: [math]f_l = x_1 \land x_2 \oplus x_1 \oplus x_2[/math]. Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции ИЛИ.
  3. Присутствуют 2 члена, без [math]~1[/math]. Построив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить И, через НЕ и [math]f_l[/math].
  4. Присутствует 1 член. Выразим И, через НЕ и [math]f_l[/math].
В итоге получаем функцию НЕ, а также либо функцию И, либо функцию ИЛИ, но НЕ образует базис и с той и с другой функциями. Из того, что через функции F можно выразить базис, следует, что F — полная система функций, что и требовалось доказать.
[math]\triangleleft[/math]

Примеры полных систем булевых функций от двух переменных

Широко известна полная система функций [math]\left\{\land,\lor,\neg\right\}[/math]. Однако, эта система функций не является безызбыточной, т. к. функцию [math]\land[/math] можно выразить через [math]\lor[/math] и [math]\neg[/math]. Система функций [math]\left\{\lor,\neg\right\}[/math] безызбыточная, т. к. функция [math]\lor[/math] является несамодвойственной и нелинейной, а функция [math]\neg[/math] не сохраняет 0, не сохраняет 1 и немонотонна. Система функций [math]\left\{\land,\lor,\neg\right\}[/math] используется для представления функций в СДНФ и СКНФ.

Также существуют полные системы функций, состоящие только из одной функции. Это [math]\triangledown[/math] и [math]\downarrow[/math].


Источники