http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Fad+Oleg&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T16:47:05ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81122Участник:Fad Oleg2021-06-27T13:22:54Z<p>Fad Oleg: </p>
<hr />
<div>== Представление булевых функций ==<br />
<br />
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:<br />
* Как построить по данной функции представляющую её формулу?<br />
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?<br />
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?<br />
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?<br />
<br />
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.<br />
<br />
=== Дизъюнктивная нормальная форма (ДНФ) ===<br />
<br />
{{main|ДНФ}}<br />
{{Определение<br />
|definition =<br />
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.<br />
}}<br />
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.<br />
<br />
'''Примеры ДНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.<br />
<br />
<tex>f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) </tex>.<br />
<br />
=== Конъюнктивная нормальная форма (КНФ) ===<br />
<br />
{{main|КНФ}}<br />
{{Определение<br />
|definition =<br />
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.<br />
}}<br />
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.<br />
<br />
'''Пример КНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex><br />
<br />
<tex>f(x,y,z,t) = (x \lor t) \land (y \lor \neg{t}) \land (\neg{t} \lor \neg{z}) \land (\neg{x} \lor \neg{y} \lor z)</tex><br />
<br />
<tex>f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x})</tex><br />
<br />
=== Полином Жегалкина ===<br />
<br />
{{main|Полином Жегалкина}}<br />
{{Определение<br />
|definition =<br />
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. <br />
}}<br />
Полином Жегалкина имеет следующий вид:<br />
<br />
<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\ldots1} x_1 x_2 \ldots x_n </tex><br />
<br />
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.<br />
<br />
'''Примеры:'''<br />
<br />
<tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex><br />
<br />
<tex>f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex><br />
<br />
<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><br />
<br />
===Тождественные функции. Выражение функций друг через друга===<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''. <br />
<br />
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.<br />
{{Пример<br />
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
}}<br />
=== Подстановка одной функции в другую ===<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
{{Пример<br />
|example=Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
}}<br />
=== Отождествление переменных ===<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
{{Пример<br />
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
}}<br />
=== Схемы из функциональных элементов ===<br />
{{main|Реализация булевой функции схемой из функциональных элементов}}<br />
{{Определение<br />
|definition =<br />
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:<br />
<br />
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);<br />
<br />
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.<br />
}}<br />
Отождествление переменных осуществляется при помощи ветвления проводников.<br />
<br />
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.<br />
<br />
'''Некоторые логические элементы:'''<br />
<br />
{| class = "wikitable" border = "1"<br />
!-align="center" |И<br />
!-align="center" |ИЛИ<br />
!-align="center" |НЕ<br />
!Штрих Шеффера<br />
!Стрелка Пирса<br />
|-<br />
|[[Image:AND_logic_element.png]]<br />
|[[Image:OR_logic_element.png]]<br />
|[[Image:NOT_logic_element.png]]<br />
|[[Image:NAND_logic_element.png]]<br />
|[[Image:NOR_logic_element.png]]<br />
|}<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81121Участник:Fad Oleg2021-06-27T13:22:26Z<p>Fad Oleg: /* Тождественные функции. Выражение функций друг через друга */</p>
<hr />
<div>== Представление булевых функций ==<br />
<br />
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:<br />
* Как построить по данной функции представляющую её формулу?<br />
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?<br />
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?<br />
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?<br />
<br />
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.<br />
<br />
=== Дизъюнктивная нормальная форма (ДНФ) ===<br />
<br />
{{main|ДНФ}}<br />
{{Определение<br />
|definition =<br />
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.<br />
}}<br />
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.<br />
<br />
'''Примеры ДНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.<br />
<br />
<tex>f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) </tex>.<br />
<br />
=== Конъюнктивная нормальная форма (КНФ) ===<br />
<br />
{{main|КНФ}}<br />
{{Определение<br />
|definition =<br />
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.<br />
}}<br />
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.<br />
<br />
'''Пример КНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex><br />
<br />
<tex>f(x,y,z,t) = (x \lor t) \land (y \lor \neg{t}) \land (\neg{t} \lor \neg{z}) \land (\neg{x} \lor \neg{y} \lor z)</tex><br />
<br />
<tex>f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x})</tex><br />
<br />
=== Полином Жегалкина ===<br />
<br />
{{main|Полином Жегалкина}}<br />
{{Определение<br />
|definition =<br />
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. <br />
}}<br />
Полином Жегалкина имеет следующий вид:<br />
<br />
<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\ldots1} x_1 x_2 \ldots x_n </tex><br />
<br />
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.<br />
<br />
'''Примеры:'''<br />
<br />
<tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex><br />
<br />
<tex>f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex><br />
<br />
<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><br />
<br />
===Тождественные функции. Выражение функций друг через друга===<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''. <br />
<br />
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.<br />
{{Пример<br />
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
}}<br />
<br />
=== Подстановка одной функции в другую ===<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
{{Пример<br />
|example=Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
}}<br />
=== Отождествление переменных ===<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
{{Пример<br />
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
}}<br />
=== Схемы из функциональных элементов ===<br />
{{main|Реализация булевой функции схемой из функциональных элементов}}<br />
{{Определение<br />
|definition =<br />
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:<br />
<br />
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);<br />
<br />
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.<br />
}}<br />
Отождествление переменных осуществляется при помощи ветвления проводников.<br />
<br />
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.<br />
<br />
'''Некоторые логические элементы:'''<br />
<br />
{| class = "wikitable" border = "1"<br />
!-align="center" |И<br />
!-align="center" |ИЛИ<br />
!-align="center" |НЕ<br />
!Штрих Шеффера<br />
!Стрелка Пирса<br />
|-<br />
|[[Image:AND_logic_element.png]]<br />
|[[Image:OR_logic_element.png]]<br />
|[[Image:NOT_logic_element.png]]<br />
|[[Image:NAND_logic_element.png]]<br />
|[[Image:NOR_logic_element.png]]<br />
|}<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81120Участник:Fad Oleg2021-06-27T13:21:00Z<p>Fad Oleg: </p>
<hr />
<div>== Представление булевых функций ==<br />
<br />
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:<br />
* Как построить по данной функции представляющую её формулу?<br />
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?<br />
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?<br />
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?<br />
<br />
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.<br />
<br />
=== Дизъюнктивная нормальная форма (ДНФ) ===<br />
<br />
{{main|ДНФ}}<br />
{{Определение<br />
|definition =<br />
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.<br />
}}<br />
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.<br />
<br />
'''Примеры ДНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.<br />
<br />
<tex>f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) </tex>.<br />
<br />
=== Конъюнктивная нормальная форма (КНФ) ===<br />
<br />
{{main|КНФ}}<br />
{{Определение<br />
|definition =<br />
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.<br />
}}<br />
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.<br />
<br />
'''Пример КНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex><br />
<br />
<tex>f(x,y,z,t) = (x \lor t) \land (y \lor \neg{t}) \land (\neg{t} \lor \neg{z}) \land (\neg{x} \lor \neg{y} \lor z)</tex><br />
<br />
<tex>f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x})</tex><br />
<br />
=== Полином Жегалкина ===<br />
<br />
{{main|Полином Жегалкина}}<br />
{{Определение<br />
|definition =<br />
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. <br />
}}<br />
Полином Жегалкина имеет следующий вид:<br />
<br />
<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\ldots1} x_1 x_2 \ldots x_n </tex><br />
<br />
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.<br />
<br />
'''Примеры:'''<br />
<br />
<tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex><br />
<br />
<tex>f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex><br />
<br />
<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><br />
<br />
===Тождественные функции. Выражение функций друг через друга===<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''. Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.<br />
{{Пример<br />
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
}}<br />
=== Подстановка одной функции в другую ===<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
{{Пример<br />
|example=Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
}}<br />
=== Отождествление переменных ===<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
{{Пример<br />
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
}}<br />
=== Схемы из функциональных элементов ===<br />
{{main|Реализация булевой функции схемой из функциональных элементов}}<br />
{{Определение<br />
|definition =<br />
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:<br />
<br />
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);<br />
<br />
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.<br />
}}<br />
Отождествление переменных осуществляется при помощи ветвления проводников.<br />
<br />
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.<br />
<br />
'''Некоторые логические элементы:'''<br />
<br />
{| class = "wikitable" border = "1"<br />
!-align="center" |И<br />
!-align="center" |ИЛИ<br />
!-align="center" |НЕ<br />
!Штрих Шеффера<br />
!Стрелка Пирса<br />
|-<br />
|[[Image:AND_logic_element.png]]<br />
|[[Image:OR_logic_element.png]]<br />
|[[Image:NOT_logic_element.png]]<br />
|[[Image:NAND_logic_element.png]]<br />
|[[Image:NOR_logic_element.png]]<br />
|}<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81119Участник:Fad Oleg2021-06-27T13:19:37Z<p>Fad Oleg: /* Тождественные функции. Выражение функций друг через друга */</p>
<hr />
<div>== Представление булевых функций ==<br />
<br />
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:<br />
* Как построить по данной функции представляющую её формулу?<br />
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?<br />
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?<br />
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?<br />
<br />
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.<br />
<br />
=== Дизъюнктивная нормальная форма (ДНФ) ===<br />
<br />
{{main|ДНФ}}<br />
{{Определение<br />
|definition =<br />
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.<br />
}}<br />
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.<br />
<br />
'''Примеры ДНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.<br />
<br />
<tex>f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) </tex>.<br />
<br />
=== Конъюнктивная нормальная форма (КНФ) ===<br />
<br />
{{main|КНФ}}<br />
{{Определение<br />
|definition =<br />
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.<br />
}}<br />
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.<br />
<br />
'''Пример КНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex><br />
<br />
<tex>f(x,y,z,t) = (x \lor t) \land (y \lor \neg{t}) \land (\neg{t} \lor \neg{z}) \land (\neg{x} \lor \neg{y} \lor z)</tex><br />
<br />
<tex>f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x})</tex><br />
<br />
=== Полином Жегалкина ===<br />
<br />
{{main|Полином Жегалкина}}<br />
{{Определение<br />
|definition =<br />
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. <br />
}}<br />
Полином Жегалкина имеет следующий вид:<br />
<br />
<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\ldots1} x_1 x_2 \ldots x_n </tex><br />
<br />
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.<br />
<br />
'''Примеры:'''<br />
<br />
<tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex><br />
<br />
<tex>f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex><br />
<br />
<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><br />
<br />
===Тождественные функции. Выражение функций друг через друга===<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''. Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.<br />
{{Пример<br />
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
}}<br />
<br />
=== Подстановка одной функции в другую ===<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
{{Пример<br />
|example=Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
}}<br />
=== Отождествление переменных ===<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
{{Пример<br />
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
}}<br />
=== Схемы из функциональных элементов ===<br />
{{main|Реализация булевой функции схемой из функциональных элементов}}<br />
{{Определение<br />
|definition =<br />
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:<br />
<br />
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);<br />
<br />
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.<br />
}}<br />
Отождествление переменных осуществляется при помощи ветвления проводников.<br />
<br />
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.<br />
<br />
'''Некоторые логические элементы:'''<br />
<br />
{| class = "wikitable" border = "1"<br />
!-align="center" |И<br />
!-align="center" |ИЛИ<br />
!-align="center" |НЕ<br />
!Штрих Шеффера<br />
!Стрелка Пирса<br />
|-<br />
|[[Image:AND_logic_element.png]]<br />
|[[Image:OR_logic_element.png]]<br />
|[[Image:NOT_logic_element.png]]<br />
|[[Image:NAND_logic_element.png]]<br />
|[[Image:NOR_logic_element.png]]<br />
|}<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81118Участник:Fad Oleg2021-06-27T13:15:19Z<p>Fad Oleg: </p>
<hr />
<div>== Представление булевых функций ==<br />
<br />
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:<br />
* Как построить по данной функции представляющую её формулу?<br />
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?<br />
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?<br />
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?<br />
<br />
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.<br />
<br />
=== Дизъюнктивная нормальная форма (ДНФ) ===<br />
<br />
{{main|ДНФ}}<br />
{{Определение<br />
|definition =<br />
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.<br />
}}<br />
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.<br />
<br />
'''Примеры ДНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.<br />
<br />
<tex>f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) </tex>.<br />
<br />
=== Конъюнктивная нормальная форма (КНФ) ===<br />
<br />
{{main|КНФ}}<br />
{{Определение<br />
|definition =<br />
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.<br />
}}<br />
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.<br />
<br />
'''Пример КНФ:'''<br />
<br />
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex><br />
<br />
<tex>f(x,y,z,t) = (x \lor t) \land (y \lor \neg{t}) \land (\neg{t} \lor \neg{z}) \land (\neg{x} \lor \neg{y} \lor z)</tex><br />
<br />
<tex>f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x})</tex><br />
<br />
=== Полином Жегалкина ===<br />
<br />
{{main|Полином Жегалкина}}<br />
{{Определение<br />
|definition =<br />
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. <br />
}}<br />
Полином Жегалкина имеет следующий вид:<br />
<br />
<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\ldots1} x_1 x_2 \ldots x_n </tex><br />
<br />
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.<br />
<br />
'''Примеры:'''<br />
<br />
<tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex><br />
<br />
<tex>f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex><br />
<br />
<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><br />
<br />
===Тождественные функции. Выражение функций друг через друга===<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''.<br />
{{Пример<br />
|example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>.<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
}}<br />
=== Подстановка одной функции в другую ===<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
{{Пример<br />
|example=Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
}}<br />
=== Отождествление переменных ===<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
{{Пример<br />
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
}}<br />
=== Схемы из функциональных элементов ===<br />
{{main|Реализация булевой функции схемой из функциональных элементов}}<br />
{{Определение<br />
|definition =<br />
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:<br />
<br />
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);<br />
<br />
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.<br />
}}<br />
Отождествление переменных осуществляется при помощи ветвления проводников.<br />
<br />
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.<br />
<br />
'''Некоторые логические элементы:'''<br />
<br />
{| class = "wikitable" border = "1"<br />
!-align="center" |И<br />
!-align="center" |ИЛИ<br />
!-align="center" |НЕ<br />
!Штрих Шеффера<br />
!Стрелка Пирса<br />
|-<br />
|[[Image:AND_logic_element.png]]<br />
|[[Image:OR_logic_element.png]]<br />
|[[Image:NOT_logic_element.png]]<br />
|[[Image:NAND_logic_element.png]]<br />
|[[Image:NOR_logic_element.png]]<br />
|}<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81117Участник:Fad Oleg2021-06-27T12:41:40Z<p>Fad Oleg: /* Тождественные функции. Выражение функций друг через друга. */</p>
<hr />
<div>== Представление булевых функций ==<br />
<br />
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:<br />
* Как построить по данной функции представляющую её формулу?<br />
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?<br />
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?<br />
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?<br />
<br />
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций<br />
<br />
==Тождественные функции. Выражение функций друг через друга==<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''.<br />
<br />
{{Пример<br />
|example=Выразим следующие функции через функции <tex>\{\land, \lor, \lnot \} </tex>.<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
}}<br />
<br />
== Подстановка одной функции в другую ==<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
<br />
'''Пример:'''<br />
<br />
Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
<br />
== Отождествление переменных ==<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
<br />
'''Пример:'''<br />
<br />
<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81115Участник:Fad Oleg2021-06-26T22:57:39Z<p>Fad Oleg: /* Представление функции формулой */</p>
<hr />
<div>== Представление булевых функций ==<br />
<br />
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <tex>\Sigma = \{f_1,\ldots,f_n\}</tex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <tex>\Sigma</tex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:<br />
* Как построить по данной функции представляющую её формулу?<br />
* Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?<br />
** В частности: существует ли способ приведения произвольной формулы к эквивалентной её ''канонической'' форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?<br />
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?<br />
<br />
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций<br />
<br />
==Тождественные функции. Выражение функций друг через друга.==<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''.<br />
<br />
'''Примеры выражения функций через функции <tex>\{\land, \lor, \lnot \} </tex>.'''<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
<br />
== Подстановка одной функции в другую ==<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
<br />
'''Пример:'''<br />
<br />
Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
<br />
== Отождествление переменных ==<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
<br />
'''Пример:'''<br />
<br />
<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81109Участник:Fad Oleg2021-06-26T12:43:40Z<p>Fad Oleg: </p>
<hr />
<div>== Представление функции формулой ==<br />
<br />
{{Определение<br />
|definition=<br />
Если выбрать некоторый набор [[Определение булевой функции|булевых функций]] <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''.<br />
}} <br />
Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex><br />
<br />
==Тождественные функции. Выражение функций друг через друга.==<br />
<br />
{{Определение<br />
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.<br />
}}<br />
<br />
Приведение тождественной функции есть '''выражение булевой функции через другие'''.<br />
<br />
'''Примеры выражения функций через функции <tex>\{\land, \lor, \lnot \} </tex>.'''<br />
<br />
<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><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex><br />
<br />
<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><br />
<br />
== Подстановка одной функции в другую ==<br />
<br />
{{Определение<br />
|definition =<br />
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br />
<br />
<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><br />
}}<br />
<br />
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.<br />
<br />
При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки:<br />
<br />
{|<br />
|1. <tex> x_{1}, \ldots, x_{i-1}</tex><br />
|{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex><br />
|-<br />
|2. <tex> x_{i}, \ldots, x_{i+m-1} </tex><br />
|{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex><br />
|-<br />
|3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex><br />
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex><br />
|}<br />
<br />
'''Пример:'''<br />
<br />
Исходные функции:<br />
#<tex> f(a,b) = a \vee b </tex><br />
#<tex> g(a) = \neg a </tex><br />
<br />
<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>.<br />
<br />
== Отождествление переменных ==<br />
{{Определение<br />
|definition=<br />
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:<br />
<br />
<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><br />
}}<br />
<br />
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.<br />
<br />
'''Пример:'''<br />
<br />
<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br />
<br />
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br />
<br />
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.<br />
<br />
==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно.<br />
<br />
<tex> x \mid y = \lnot \left ( x \land y \right )</tex><br />
<br />
<tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81103Участник:Fad Oleg2021-06-25T11:01:36Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81102Участник:Fad Oleg2021-06-25T06:06:15Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81101Участник:Fad Oleg2021-06-25T06:04:18Z<p>Fad Oleg: /* Стандартный базис */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Тогда, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81100Участник:Fad Oleg2021-06-25T06:00:29Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Тогда, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> <br />
<br />
(доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81099Участник:Fad Oleg2021-06-25T05:58:41Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<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> — классы Поста.<br />
<br />
Тогда, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81097Участник:Fad Oleg2021-06-24T23:00:17Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81094Участник:Fad Oleg2021-06-24T22:17:26Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81093Участник:Fad Oleg2021-06-24T21:58:05Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X \subseteq P_2</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X \subseteq P_2</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, что последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81092Участник:Fad Oleg2021-06-24T21:54:37Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X \subseteq P_2</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X \subseteq P_2</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81091Участник:Fad Oleg2021-06-24T21:53:18Z<p>Fad Oleg: /* Теоремы о числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X \subseteq P_2</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> - безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> - полная, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X \subseteq P_2</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81090Участник:Fad Oleg2021-06-24T21:48:14Z<p>Fad Oleg: /* Стандартный базис */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразить через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>.<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X \subseteq P_2</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> - безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> - полный, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X \subseteq P_2</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81089Участник:Fad Oleg2021-06-24T21:44:45Z<p>Fad Oleg: /* Стандартный базис */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
'''Пример:'''<br />
<br />
Выразим через стандартный базис обратную импликацию(<tex>x \leftarrow y</tex>).<br />
<br />
<tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X \subseteq P_2</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> - безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> - полный, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X \subseteq P_2</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81088Участник:Fad Oleg2021-06-24T21:29:32Z<p>Fad Oleg: </p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.<br />
}}<br />
<br />
'''Замечание:'''<br />
<br />
По [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теоремы о числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре.<br />
|proof = Рассмотрим произвольный безызбыточный базис <tex> X \subseteq P_2</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные):<br />
<br />
<tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex><br />
<br />
Тогда, так как <tex>X</tex> - безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> - полный, то <tex>\left | X \right | \le 5</tex><br />
<br />
Рассмотрим <tex>f_0</tex>. Возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу и немонотонная, т.е.<br />
<br />
<tex> f_0 = f_1 = f_m </tex>. Тогда <tex>\left | X \right | \le 3</tex>.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная, т.е.<br />
<br />
<tex> f_0 = f_s </tex>. Тогда <tex>\left | X \right | \le 4</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X \subseteq P_2</tex>, что <tex>\left | X \right | = k</tex>.<br />
|proof=Приведём примеры базисов для каждого <tex>k</tex>:<br />
<br />
<tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>;<br />
<br />
<tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>;<br />
<br />
<tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>;<br />
<br />
<tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>;<br />
<br />
Докажем, последняя система является базисом:<br />
<br />
<tex> 0 \notin T_1</tex>;<br />
<br />
<tex> 1 \notin T_0</tex>;<br />
<br />
<tex> x\land y \notin L\ и\ S</tex>;<br />
<br />
<tex> x\oplus y\oplus z \notin M</tex> (доказывается с помощью таблицы истинности).<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81084Участник:Fad Oleg2021-06-20T13:38:31Z<p>Fad Oleg: /* Стандартный базис */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
Тождественность функций можно доказать с помощью таблицы истинности.<br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса.<br />
}}<br />
<br />
'''Замечание:'''по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теорема о максимальном числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре<br />
|proof = Рассмотрим произвольный базис, в котором число булевых функций равно числу [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция<br />
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.<br />
<br />
В любом случае, функция <tex>f</tex> будет не принадлежать сразу двум классам Поста. Тогда исходный базис - избыточный, и его можно сократить до четырёх функций.<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81083Участник:Fad Oleg2021-06-20T13:02:17Z<p>Fad Oleg: /* Полнота стандартного базиса */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса.<br />
}}<br />
<br />
'''Замечание:'''по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теорема о максимальном числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре<br />
|proof = Рассмотрим произвольный базис, в котором число булевых функций равно числу [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция<br />
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.<br />
<br />
В любом случае, функция <tex>f</tex> будет не принадлежать сразу двум классам Поста. Тогда исходный базис - избыточный, и его можно сократить до четырёх функций.<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81082Участник:Fad Oleg2021-06-20T12:56:28Z<p>Fad Oleg: /* Теорема о максимальном числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. <br />
}}<br />
<br />
'''Замечание:'''по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теорема о максимальном числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре<br />
|proof = Рассмотрим произвольный базис, в котором число булевых функций равно числу [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция<br />
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.<br />
<br />
В любом случае, функция <tex>f</tex> будет не принадлежать сразу двум классам Поста. Тогда исходный базис - избыточный, и его можно сократить до четырёх функций.<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81081Участник:Fad Oleg2021-06-19T13:04:17Z<p>Fad Oleg: /* Полнота стандартного базиса */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]]<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. <br />
}}<br />
<br />
'''Замечание:'''по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теорема о максимальном числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре<br />
|proof = Очевидно, что число булевых функций в базисе не превышает число [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция<br />
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.<br />
<br />
В любом случае, функция <tex>f</tex> будет не принадлежать сразу двум классам Поста.<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81078Участник:Fad Oleg2021-06-16T22:57:35Z<p>Fad Oleg: /* Теорема о максимальном числе функций в базисе */</p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. <br />
}}<br />
<br />
Однако, по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, так как базисами являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теорема о максимальном числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре<br />
|proof = Очевидно, что число булевых функций в базисе не превышает число [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция<br />
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.<br />
<br />
В любом случае, функция <tex>f</tex> будет не принадлежать сразу двум классам Поста.<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81074Участник:Fad Oleg2021-06-16T21:00:18Z<p>Fad Oleg: </p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. <br />
}}<br />
<br />
Однако, по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис является избыточным, так как базисами являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Теорема о максимальном числе функций в базисе==<br />
{{Теорема<br />
|statement = Максимально возможное число булевых функций в базисе — четыре<br />
|proof = Очевидно, что число булевых функций в базисе не превышает число [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция<br />
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:<br />
<br />
1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.<br />
<br />
2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.<br />
<br />
В любом случае, функция <tex>f</tex> будет не принадлежать двум классам Поста.<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81071Участник:Fad Oleg2021-06-16T20:17:44Z<p>Fad Oleg: </p>
<hr />
<div>==Стандартный базис==<br />
<br />
{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Теорема<br />
|id = theor1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. <br />
}}<br />
<br />
Однако, по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис не является базисом ''(забавно)'', так как базисами являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81070Участник:Fad Oleg2021-06-16T20:16:10Z<p>Fad Oleg: </p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Теорема<br />
|id = theor1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. <br />
}}<br />
<br />
Однако, по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
Следовательно, стандартный базис не является базисом ''(забавно)'', так как базисами являются подмножества системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81062Участник:Fad Oleg2021-06-16T19:47:32Z<p>Fad Oleg: /* Полнота стандартного базиса */</p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|id = prop1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. А учитывая, что, по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81061Участник:Fad Oleg2021-06-16T19:20:55Z<p>Fad Oleg: </p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|id = prop1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что, по [[Множества|закону де Моргана]]:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81036Участник:Fad Oleg2021-06-15T11:53:09Z<p>Fad Oleg: </p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|id = prop1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что, по закону де Моргана:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
Категория: Дискретная математика и алгоритмы<br />
<br />
Категория: Булевы функции</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81035Участник:Fad Oleg2021-06-15T11:51:34Z<p>Fad Oleg: </p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
==Полнота стандартного базиса==<br />
<br />
{{Утверждение<br />
|id = prop1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что, по закону де Моргана:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
}}<br />
<br />
==Источники==<br />
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Булевы функции ]]</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81034Участник:Fad Oleg2021-06-15T11:24:12Z<p>Fad Oleg: </p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' — система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
{{Утверждение<br />
|id = prop1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что, по закону де Моргана:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
}}</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81033Участник:Fad Oleg2021-06-15T11:11:39Z<p>Fad Oleg: </p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' - система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
{{Утверждение<br />
|id = prop1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что, по закону де Моргана:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
}}</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81029Участник:Fad Oleg2021-06-14T22:21:03Z<p>Fad Oleg: </p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|definition = '''Стандартный базис''' - система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
<br />
Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что по закону де Моргана:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:<br />
<br />
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex><br />
<br />
<tex> x \rightarrow y = \lnot x \lor y </tex><br />
<br />
<tex> 0 = x \land \lnot x </tex><br />
<br />
{{Утверждение<br />
|id = prop1<br />
|statement = Стандартный базис является полной системой булевых функций<br />
|proof = Данное утверждение является следствием существования [[СДНФ]]<br />
}}</div>Fad Oleghttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Fad_Oleg&diff=81027Участник:Fad Oleg2021-06-14T21:57:41Z<p>Fad Oleg: Новая страница: «{{Определение |id = def1 |neat = 1 |definition = '''Стандартный базис''' - полная система булевых функций:…»</p>
<hr />
<div>{{Определение<br />
|id = def1<br />
|neat = 1<br />
|definition = '''Стандартный базис''' - полная система булевых функций: <br />
<tex>\{\land, \lor, \lnot \} </tex><br />
}}<br />
Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что по закону де Моргана:<br />
<br />
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex><br />
<br />
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex><br />
<br />
полными являются даже системы:<br />
<br />
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)<br />
<br />
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)<br />
<br />
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и логической константы 0, т. к. все остальные операции являются их отрицаниями:</div>Fad Oleg