61
правка
Изменения
Нет описания правки
!colspan="6"|Таблица истинности
|-align="center"
! <tex>x_1</tex> || <tex>x_2</tex> || <tex>...\ldots</tex> || <tex>x_n</tex> || <tex>f(x_1,x_2,...\ldots,x_n)</tex>
|-align="center"
| <tex>0</tex> || <tex>0</tex> || <tex>...\ldots</tex> || <tex>0</tex> || <tex>f(0,0,...\ldots,0)</tex>
|-align="center"
| <tex>1</tex> || <tex>0</tex> || <tex>...\ldots</tex> || <tex>0</tex> || <tex>f(1,0,...\ldots,0)</tex>
|-align="center"
| <tex>0</tex> || <tex>1</tex> || <tex>...\ldots</tex> || <tex>0</tex> || <tex>f(0,1,...\ldots,0)</tex>
|-align="center"
| <tex>1</tex> || <tex>1</tex> || <tex>...\ldots</tex> || <tex>0</tex> || <tex>f(1,1,...\ldots,0)</tex>
|-align="center"
| <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex>
|-align="center"
| <tex>0</tex> || <tex>1</tex> || <tex>...\ldots</tex> || <tex>1</tex> || <tex>f(0,1,...\ldots,1)</tex>
|-align="center"
| <tex>1</tex> || <tex>1</tex> || <tex>...\ldots</tex> || <tex>1</tex> || <tex>f(1,1,...\ldots,1)</tex>
|}
</center>
|}
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
{| style="width:15cm9cm"
|-
| <tex>x \land \overline{x}=0</tex> || <tex>x \lor \overline{x}=1</tex>
|}
{| style="width:15cm"
|-
| <tex>\overline{x \land y}=\overline{x}\lor\overline{y}</tex>
|| <tex>\overline{x}\land\overline{y}=\overline{x\lor y}</tex> || (законы де Моргана)
|}
<tex>x \land (y\lor z)=(x \land y)\lor (x \land z)</tex><br />
=== Суперпозиции ===
{{main|Суперпозиции}}
{{Определение
|definition =
'''Суперпозиция функций, композиция функций''' (англ. ''function composition'') {{---}} функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
}}
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.
=== Полнота системы, критерий Поста ===
{{main|Теорема Поста о полной системе функций}}
{{Определение
|definition=
'''Замыкание множества функций''' (англ. ''сlosure'') {{---}} подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества.
}}
{{Определение
|id=def1
|definition=
Множество булевых функций называется '''полной системой''' (англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.
}}
Американский математик Эмиль Пост <ref> [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D1%82,_%D0%AD%D0%BC%D0%B8%D0%BB%D1%8C_%D0%9B%D0%B5%D0%BE%D0%BD Эмиль Пост]</ref> сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
* функции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>,
* самодвойственныые функции <Tex>S</Tex>,
* монотонные функции <Tex>M</Tex>,
* линейные функции <Tex>L</Tex>.
Набор булевых функций <tex>K</tex> является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
== Представление булевых функций ==
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов.
}}
Любая булева формула, благодаря использованию закона двойного отрицания, закона де Моргана и закон закона дистрибутивности, может быть записана в ДНФ.
'''Примеры ДНФ:'''
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закон закона дистрибутивности может быть записана в ДНФКНФ.
'''Пример КНФ:'''
Полином Жегалкина имеет следующий вид:
<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0} x_2 \oplus \ldots \oplus a_{00\ldots01} x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11..1\ldots1} x_1 x_2 \ldots x_n </tex>
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.
* [[Cумматор]]
* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций. Теорема Поста о полной системе функций]]
== Примечания ==
<references/>
== Источники информации ==
