Изменения
Нет описания правки
|}
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
{| style="width:15cm9cm"
|-
| <tex>x \land \overline{x}=0</tex> || <tex>x \lor \overline{x}=1</tex>
|}
{| style="width:15cm"
|-
| <tex>\overline{x \land y}=\overline{x}\lor\overline{y}</tex>
|| <tex>\overline{x}\land\overline{y}=\overline{x\lor y}</tex> || (законы де Моргана)
|}
<tex>x \land (y\lor z)=(x \land y)\lor (x \land z)</tex><br />
Множество булевых функций называется '''полной системой''' (англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.
}}
Американский математик Эмиль Пост <ref> [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D1%82,_%D0%AD%D0%BC%D0%B8%D0%BB%D1%8C_%D0%9B%D0%B5%D0%BE%D0%BD Эмиль Пост]</ref> сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
* функции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>,
Набор булевых функций <tex>K</tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
== Представление булевых функций ==
Полином Жегалкина имеет следующий вид:
<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0} x_2 \oplus \ldots \oplus a_{00\ldots01} x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11..1\ldots1} x_1 x_2 \ldots x_n </tex>
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.
<tex>f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 </tex>
===Тождественные функции. Выражение функций друг через друга===
{{Определение
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.
}}
Приведение тождественной функции есть '''выражение булевой функции через другие'''.
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.
{{Пример
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.
<tex> x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )</tex>
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex>
<tex>\langle x, y, z \rangle = \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \lor z \right )</tex>
}}
=== Подстановка одной функции в другую ===
{{Определение
|definition =
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:
<center><tex>h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})</tex></center>
}}
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:
{|
|1. <tex> x_{1}, \ldots, x_{i-1}</tex>
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex>
|-
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex>
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex>
|-
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex>
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex>
|}
{{Пример
|example=Исходные функции:
#<tex> f(a,b) = a \vee b </tex>
#<tex> g(a) = \neg a </tex>
<tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>.
}}
=== Отождествление переменных ===
{{Определение
|definition=
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:
<center><tex>h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{i}, x_{j+1}, \ldots, x_{n})</tex></center>
}}
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.
{{Пример
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.
}}
=== Схемы из функциональных элементов ===
{{main|Реализация булевой функции схемой из функциональных элементов}}
|[[Image:NOR_logic_element.png]]
|}
==Стандартный базис==
{{Определение
|id = def1
|definition = '''Стандартный базис''' — система булевых функций:
<tex>\{\land, \lor, \lnot \} </tex>
}}
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex>
<tex> x \rightarrow y = \lnot x \lor y </tex>
<tex> 0 = x \land \lnot x </tex>
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.
<tex> x \mid y = \lnot \left ( x \land y \right )</tex>
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex>
Тождественность функций можно доказать с помощью таблицы истинности.
'''Пример:'''
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex>
==Полнота стандартного базиса==
{{Утверждение
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.
}}
'''Замечание:'''
По [[Множества|закону де Моргана]]:
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
==Теоремы о числе функций в базисе==
{{Теорема
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex>, где <tex> T_0, T_1, S, M, L</tex> — классы Поста.
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex>
Рассмотрим <tex>f_0</tex>. Возможны два случая:
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.
}}
{{Теорема
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.
|proof=Приведём примеры базисов для каждого <tex>k</tex>:
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;
Докажем, что последняя система является базисом:
<tex> 0 \notin T_1</tex>;
<tex> 1 \notin T_0</tex>;
<tex> x\land y \notin L\ и\ S</tex>;
<tex> x\oplus y\oplus z \notin M</tex>
(доказывается с помощью таблицы истинности).
}}
== См. также ==
