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'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.
'''Пример КНФ:'''
{{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>
=== Схемы из функциональных элементов ===
{{main|Реализация булевой функции схемой из функциональных элементов}}
{{Определение
|definition =
'''Схема из функциональных элементов, логическая схема''' (англ. ''logic diagram'') {{---}} размеченный ориентированный граф без циклов, в некотором базисе <tex>B</tex>, в котором:
1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса <tex>B</tex>). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса <tex>B</tex>.
}}
Отождествление переменных осуществляется при помощи ветвления проводников.
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
'''Некоторые логические элементы:'''
{| class = "wikitable" border = "1"
!-align="center" |И
!-align="center" |ИЛИ
!-align="center" |НЕ
!Штрих Шеффера
!Стрелка Пирса
|-
|[[Image:AND_logic_element.png]]
|[[Image:OR_logic_element.png]]
|[[Image:NOT_logic_element.png]]
|[[Image:NAND_logic_element.png]]
|[[Image:NOR_logic_element.png]]
|}
== См. также ==
* [[Cумматор]]
* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций. Теорема Поста о полной системе функций]]
== Примечания ==
<references/>
== Источники информации ==
