37
правок
Изменения
Нет описания правки
* Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
=== Дизъюнктивная нормальная форма (ДНФ) === {{main|ДНФ}}{{Определение|definition ='''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.}}Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ. '''Примеры ДНФ:''' <tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>. <tex>f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m}) </tex>. === Конъюнктивная нормальная форма (КНФ) === {{main|КНФ}}{{Определение|definition ='''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.}}Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ. '''Пример КНФ:''' <tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex> <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> <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> === Полином Жегалкина === {{main|Полином Жегалкина}}{{Определение|definition ='''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') {{---}} полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. }}Полином Жегалкина имеет следующий вид: <tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0} x_2 \oplus \ldots \oplus a_{00\ldots01} x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11\ldots1} x_1 x_2 \ldots x_n </tex> С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным. '''Примеры:''' <tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex> <tex>f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex> <tex>f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 </tex> ===Тождественные функции. Выражение функций друг через друга===
{{Определение
|definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения.
}}
Приведение тождественной функции есть '''выражение булевой функции через другие'''.
{{Пример
|example=Выразим следующие функции через функции систему функций <tex>\{\land, \lor, \lnot \} </tex>.
<tex> x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )</tex>
<tex>\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>
}}
=== Подстановка одной функции в другую ===
{{Определение
<center><tex>h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})</tex></center>
}}
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
|{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex>
|}
#<tex> f(a,b) = a \vee b </tex>
#<tex> g(a) = \neg a </tex>
<tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>.
}}=== Отождествление переменных ===
{{Определение
|definition=
<center><tex>h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{i}, x_{j+1}, \ldots, x_{n})</tex></center>
}}
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.
{{Пример
|example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция
<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.
}}
=== Схемы из функциональных элементов ===
{{main|Реализация булевой функции схемой из функциональных элементов}}
{{Определение
|definition =
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:
==Стандартный базис==
