Определение булевой функции — различия между версиями
Pavponn (обсуждение | вклад) (→Схемы из функциональных элементов) |
м (rollbackEdits.php mass rollback) |
||
(не показано 18 промежуточных версий 4 участников) | |||
Строка 18: | Строка 18: | ||
!colspan="6"|Таблица истинности | !colspan="6"|Таблица истинности | ||
|-align="center" | |-align="center" | ||
− | ! <tex>x_1</tex> || <tex>x_2</tex> || <tex> | + | ! <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" | |-align="center" | ||
− | | <tex>0</tex> || <tex>0</tex> || <tex> | + | | <tex>0</tex> || <tex>0</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(0,0,\ldots,0)</tex> |
|-align="center" | |-align="center" | ||
− | | <tex>1</tex> || <tex>0</tex> || <tex> | + | | <tex>1</tex> || <tex>0</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(1,0,\ldots,0)</tex> |
|-align="center" | |-align="center" | ||
− | | <tex>0</tex> || <tex>1</tex> || <tex> | + | | <tex>0</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(0,1,\ldots,0)</tex> |
|-align="center" | |-align="center" | ||
− | | <tex>1</tex> || <tex>1</tex> || <tex> | + | | <tex>1</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>0</tex> || <tex>f(1,1,\ldots,0)</tex> |
|-align="center" | |-align="center" | ||
| <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> | | <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> || <tex>\vdots</tex> | ||
|-align="center" | |-align="center" | ||
− | | <tex>0</tex> || <tex>1</tex> || <tex> | + | | <tex>0</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>1</tex> || <tex>f(0,1,\ldots,1)</tex> |
|-align="center" | |-align="center" | ||
− | | <tex>1</tex> || <tex>1</tex> || <tex> | + | | <tex>1</tex> || <tex>1</tex> || <tex>\ldots</tex> || <tex>1</tex> || <tex>f(1,1,\ldots,1)</tex> |
|} | |} | ||
</center> | </center> | ||
Строка 377: | Строка 377: | ||
|} | |} | ||
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты: | А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты: | ||
− | {| style="width: | + | {| style="width:9cm" |
|- | |- | ||
− | | <tex>x \land \overline{x}=0</tex> || <tex>x \lor \overline{x}=1</tex> | + | | <tex>x \land \overline{x}=0</tex> ||<tex>x \lor \overline{x}=1</tex> |
|} | |} | ||
{| style="width:15cm" | {| style="width:15cm" | ||
|- | |- | ||
| <tex>\overline{x \land y}=\overline{x}\lor\overline{y}</tex> | | <tex>\overline{x \land y}=\overline{x}\lor\overline{y}</tex> | ||
− | || <tex>\overline{x}\land\overline{y}=\overline{x\lor 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 /> | <tex>x \land (y\lor z)=(x \land y)\lor (x \land z)</tex><br /> | ||
Строка 397: | Строка 397: | ||
=== Суперпозиции === | === Суперпозиции === | ||
+ | {{main|Суперпозиции}} | ||
+ | {{Определение | ||
+ | |definition = | ||
+ | '''Суперпозиция функций, композиция функций''' (англ. ''function composition'') {{---}} функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных. | ||
+ | }} | ||
+ | Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций. | ||
− | + | Пусть нам дан некоторый набор булевых функций <tex>K</tex>. Получить новую функцию, являющеюся композицией функций из <tex>K</tex>, мы можем следующими способами: | |
+ | *Подстановкой одной функции в качестве некоторого аргумента для другой; | ||
+ | *Отождествлением аргументов функций. | ||
=== Полнота системы, критерий Поста === | === Полнота системы, критерий Поста === | ||
{{main|Теорема Поста о полной системе функций}} | {{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>, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. | ||
== Представление булевых функций == | == Представление булевых функций == | ||
Строка 421: | Строка 444: | ||
'''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов. | '''Дизъюнктивная нормальная форма (ДНФ)''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] задана как дизъюнкция некоторого числа простых конъюнктов. | ||
}} | }} | ||
+ | Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ. | ||
+ | |||
'''Примеры ДНФ:''' | '''Примеры ДНФ:''' | ||
Строка 434: | Строка 459: | ||
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов. | '''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов. | ||
}} | }} | ||
+ | Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ. | ||
+ | |||
'''Пример КНФ:''' | '''Пример КНФ:''' | ||
Строка 451: | Строка 478: | ||
Полином Жегалкина имеет следующий вид: | Полином Жегалкина имеет следующий вид: | ||
− | <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 | + | <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>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным. | ||
Строка 463: | Строка 490: | ||
<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> | <tex>f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 </tex> | ||
+ | ===Тождественные функции. Выражение функций друг через друга=== | ||
+ | |||
+ | {{Определение | ||
+ | |definition = '''Тождественные функции''' — функции, которые при любых одинаковых аргументах принимают равные значения. | ||
+ | }} | ||
+ | Приведение тождественной функции есть '''выражение булевой функции через другие'''. | ||
+ | |||
+ | Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие. | ||
+ | {{Пример | ||
+ | |example=Выразим следующие функции через систему функций <tex>\{\land, \lor, \lnot \} </tex>. | ||
+ | |||
+ | <tex> x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )</tex> | ||
+ | |||
+ | <tex> x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y</tex> | ||
+ | |||
+ | <tex>\langle x, y, z \rangle = \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \lor z \right )</tex> | ||
+ | }} | ||
+ | === Подстановка одной функции в другую === | ||
+ | |||
+ | {{Определение | ||
+ | |definition = | ||
+ | '''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>: | ||
+ | |||
+ | <center><tex>h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})</tex></center> | ||
+ | }} | ||
+ | Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя. | ||
+ | |||
+ | При подстановке функции <tex>g</tex> вместо <tex>i</tex>-того аргумента функции <tex>f</tex>, результирующая функция <tex>h</tex> будет принимать аргументы, которые можно разделить на следующие блоки: | ||
+ | |||
+ | {| | ||
+ | |1. <tex> x_{1}, \ldots, x_{i-1}</tex> | ||
+ | |{{---}} аргументы функции <tex>f</tex> до подставленного значения функции <tex>g</tex> | ||
+ | |- | ||
+ | |2. <tex> x_{i}, \ldots, x_{i+m-1} </tex> | ||
+ | |{{---}} используются как аргументы для вычисления значения функции <tex>g(y_{1}, \ldots, y_{m})</tex> | ||
+ | |- | ||
+ | |3. <tex> x_{i+m}, \ldots, x_{n+m-1} </tex> | ||
+ | |{{---}} аргументы функции <tex>f</tex> после подставленного значения функции <tex>g</tex> | ||
+ | |} | ||
+ | {{Пример | ||
+ | |example=Исходные функции: | ||
+ | #<tex> f(a,b) = a \vee b </tex> | ||
+ | #<tex> g(a) = \neg a </tex> | ||
+ | |||
+ | <tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>. | ||
+ | }} | ||
+ | === Отождествление переменных === | ||
+ | {{Определение | ||
+ | |definition= | ||
+ | '''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента: | ||
+ | |||
+ | <center><tex>h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{i}, x_{j+1}, \ldots, x_{n})</tex></center> | ||
+ | }} | ||
+ | Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>. | ||
+ | {{Пример | ||
+ | |example=<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция | ||
+ | |||
+ | <tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами | ||
+ | |||
+ | Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента. | ||
+ | }} | ||
=== Схемы из функциональных элементов === | === Схемы из функциональных элементов === | ||
{{main|Реализация булевой функции схемой из функциональных элементов}} | {{main|Реализация булевой функции схемой из функциональных элементов}} | ||
Строка 492: | Строка 580: | ||
|[[Image:NOR_logic_element.png]] | |[[Image:NOR_logic_element.png]] | ||
|} | |} | ||
+ | |||
+ | ==Стандартный базис== | ||
+ | |||
+ | {{Определение | ||
+ | |id = def1 | ||
+ | |definition = '''Стандартный базис''' — система булевых функций: | ||
+ | <tex>\{\land, \lor, \lnot \} </tex> | ||
+ | }} | ||
+ | |||
+ | Если рассматривать множество бинарных булевых функций <tex>P_2(2)</tex>, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания: | ||
+ | |||
+ | <tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex> | ||
+ | |||
+ | <tex> x \rightarrow y = \lnot x \lor y </tex> | ||
+ | |||
+ | <tex> 0 = x \land \lnot x </tex> | ||
+ | |||
+ | Функции <tex> \mid \ и \downarrow</tex> являются отрицаниями функций <tex> \land \ и \ \lor</tex> соответственно. | ||
+ | |||
+ | <tex> x \mid y = \lnot \left ( x \land y \right )</tex> | ||
+ | |||
+ | <tex> x \downarrow y = \lnot \left ( x \lor y \right )</tex> | ||
+ | |||
+ | Тождественность функций можно доказать с помощью таблицы истинности. | ||
+ | |||
+ | '''Пример:''' | ||
+ | |||
+ | Выразим через стандартный базис обратную импликацию <tex> \left (x \leftarrow y \right ) </tex>. | ||
+ | |||
+ | <tex>x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y </tex> | ||
+ | |||
+ | ==Полнота стандартного базиса== | ||
+ | |||
+ | {{Утверждение | ||
+ | |statement = Стандартный базис является [[Полные системы функций. Теорема Поста о полной системе функций|полной системой булевых функций]] | ||
+ | |proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше. | ||
+ | }} | ||
+ | |||
+ | '''Замечание:''' | ||
+ | |||
+ | По [[Множества|закону де Моргана]]: | ||
+ | |||
+ | <tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex> | ||
+ | |||
+ | <tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex> | ||
+ | |||
+ | Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы: | ||
+ | |||
+ | <tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля) | ||
+ | |||
+ | <tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля) | ||
+ | |||
+ | ==Теоремы о числе функций в базисе== | ||
+ | {{Теорема | ||
+ | |statement = Максимально возможное число булевых функций в безызбыточном базисе — четыре. | ||
+ | |proof = Рассмотрим произвольный безызбыточный базис <tex> X</tex>. Тогда по [[Полные системы функций. Теорема Поста о полной системе функций|теореме Поста]] <tex>X</tex> содержит следующие функции (не обязательно различные): | ||
+ | |||
+ | <tex>f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L</tex>, где <tex> T_0, T_1, S, M, L</tex> — классы Поста. | ||
+ | |||
+ | Значит, так как <tex>X</tex> — безызбыточный базис, а система <tex>\{f_0, f_1, f_s, f_m, f_l \}</tex> — полная, то <tex>\left | X \right | \le 5</tex> | ||
+ | |||
+ | Рассмотрим <tex>f_0</tex>. Возможны два случая: | ||
+ | |||
+ | 1. <tex> f_0(1, 1, \ldots, 1) = 0 </tex>, тогда <tex>f_0</tex> также не сохраняет единицу и немонотонная, т.е. | ||
+ | |||
+ | <tex> f_0 = f_1 = f_m </tex>. Значит, <tex>\left | X \right | \le 3</tex>. | ||
+ | |||
+ | 2. <tex> f_0(1, 1, \ldots, 1) = 1 </tex>, тогда <tex>f_0</tex> несамодвойственная, т.е. | ||
+ | |||
+ | <tex> f_0 = f_s </tex>. Значит, <tex>\left | X \right | \le 4</tex>. | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement= Для любого числа <tex>k, 1 \le k \le 4 </tex> найдётся базис <tex> X</tex>, что <tex>\left | X \right | = k</tex>. | ||
+ | |proof=Приведём примеры базисов для каждого <tex>k</tex>: | ||
+ | |||
+ | <tex>k = 1 \Rightarrow X = \{ \downarrow \}</tex>; | ||
+ | |||
+ | <tex>k = 2 \Rightarrow X = \{ \lnot, \land \}</tex>; | ||
+ | |||
+ | <tex>k = 3 \Rightarrow X = \{ \land, \oplus, 1\}</tex>; | ||
+ | |||
+ | <tex>k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}</tex>; | ||
+ | |||
+ | Докажем, что последняя система является базисом: | ||
+ | |||
+ | <tex> 0 \notin T_1</tex>; | ||
+ | |||
+ | <tex> 1 \notin T_0</tex>; | ||
+ | |||
+ | <tex> x\land y \notin L\ и\ S</tex>; | ||
+ | |||
+ | <tex> x\oplus y\oplus z \notin M</tex> | ||
+ | |||
+ | (доказывается с помощью таблицы истинности). | ||
+ | }} | ||
== См. также == | == См. также == | ||
Строка 499: | Строка 683: | ||
* [[Cумматор]] | * [[Cумматор]] | ||
* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций. Теорема Поста о полной системе функций]] | * [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций. Теорема Поста о полной системе функций]] | ||
+ | == Примечания == | ||
+ | <references/> | ||
== Источники информации == | == Источники информации == |
Текущая версия на 19:10, 4 сентября 2022
Определение: |
Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики, англ. Boolean function) от | переменных — отображение , где — булево множество.
Элементы булева множества
и обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается , а от n переменных — . Булевы функции названы так по фамилии математика Джорджа Буля.Содержание
Основные сведения
Определение: |
А́рность (англ. arity) функции — количество ее аргументов. |
Каждая булева функция арности
полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины . Число таких векторов равно . Поскольку на каждом векторе булева функция может принимать значение либо , либо , то количество всех n-арных булевых функций равно . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
Таблица истинности | |||||
---|---|---|---|---|---|
Практически все булевы функции малых арностей (
и ) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной (англ. dummy variable).Нульарные функции
При
количество булевых функций равно , первая из них тождественно равна , а вторая . Их называют булевыми константами — тождественный нуль и тождественная единица.Унарные функции
При
число булевых функций равно .Таблица значений булевых функций от одной переменной:
Функции от одной переменной | ||||
---|---|---|---|---|
0 | ||||
1 | ||||
Сохраняет 0 | ✓ | ✓ | ||
Сохраняет 1 | ✓ | ✓ | ||
Самодвойственная | ✓ | ✓ | ||
Монотонная | ✓ | ✓ | ✓ | |
Линейная | ✓ | ✓ | ✓ | ✓ |
Названия булевых функций от одной переменной:
Обозначение | Название |
---|---|
тождественный ноль, тождественная ложь, тождественное "НЕТ" | |
тождественная функция, логическое "ДА", "YES"(англ.) | |
отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.) | |
тождественная единица, тождественная истина, тождественное "ДА", тавтология |
Бинарные функции
При
число булевых функций равно .Таблица значений булевых функций от двух переменных:
Функции от двух переменных: | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
x | y | ||||||||||||||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Сохраняет 0 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||
Сохраняет 1 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||
Самодвойственная | ✓ | ✓ | ✓ | ✓ | |||||||||||||
Монотонная | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||||
Линейная | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
Названия булевых функций от двух переменных:
Обозначение | Другие обозначения | Название |
---|---|---|
тождественный ноль, тождественная ложь, тождественное "НЕТ" | ||
И И | 2И, конъюнкция | |
больше, инверсия прямой импликации | ||
ДА1 | первый операнд | |
меньше, инверсия обратной импликации | ||
ДА2 | второй операнд | |
сложение по модулю 2, не равно, ксор, исключающее «или» | ||
ИЛИ ИЛИ | 2ИЛИ, дизъюнкция | |
ИЛИ-НЕ ИЛИ-НЕ | НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса | |
равенство, эквивалентность | ||
НЕ2 | отрицание (негация, инверсия) второго операнда | |
больше или равно, обратная импликация (от второго аргумента к первому) | ||
НЕ1 | отрицание (негация, инверсия) первого операнда | |
меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму) | ||
И-НЕ И-НЕ | НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера | |
тождественная единица, тождественная истина, тождественное "ДА", тавтология |
Тернарные функции
При
число булевых функций равно . Некоторые из них определены в следующей таблице:Таблица истинности некоторых тернарных функций | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Названия булевых функций трех переменных:
Обозначения | Другие обозначения | Названия |
---|---|---|
3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса | ||
Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией | ||
Неравенство | ||
3-И-НЕ, штрих Шеффера | ||
И И И | 3-И, минимум | |
Равенство | ||
Тернарное сложение по модулю 2 | ||
И ИЛИ И ИЛИ И | переключатель по большинству, 3-ППБ, мажоритарный клапан | |
Разряд займа при тернарном вычитании | ||
Разряд переноса при тернарном сложении | ||
ИЛИ ИЛИ ИЛИ | 3-ИЛИ, максимум |
Представление функции формулой
Определение: |
Если выбрать некоторый набор булевых функций , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой (англ. formula). |
Например, если
, то функция представляется в видеТождественность и двойственность
Определение: |
Две булевы функции тождественны (англ. identical) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. |
Тождественность функций f и g можно записать, например, так:
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
(законы де Моргана) |
(дистрибутивность конъюнкции и дизъюнкции)
Определение: |
Функция | называется двойственной (англ. duality) функции , если .
Легко показать, что в этом равенстве
и можно поменять местами, то есть функции и двойственны друг другу. Из простейших функций двойственны друг другу константы и , а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Суперпозиции
Определение: |
Суперпозиция функций, композиция функций (англ. function composition) — функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных. |
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Пусть нам дан некоторый набор булевых функций
. Получить новую функцию, являющеюся композицией функций из , мы можем следующими способами:- Подстановкой одной функции в качестве некоторого аргумента для другой;
- Отождествлением аргументов функций.
Полнота системы, критерий Поста
Определение: |
Замыкание множества функций (англ. сlosure) — подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества. |
Определение: |
Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций. |
Американский математик Эмиль Пост [1] сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
- функции, сохраняющие константу и ,
- самодвойственныые функции ,
- монотонные функции ,
- линейные функции .
Набор булевых функций
является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций
. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре , который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:- Как построить по данной функции представляющую её формулу?
- Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
- В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
- Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ)
Определение: |
Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов. |
Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.
Примеры ДНФ:
.
.
Конъюнктивная нормальная форма (КНФ)
Определение: |
Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. |
Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.
Пример КНФ:
Полином Жегалкина
Определение: |
Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида | и , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или.
Полином Жегалкина имеет следующий вид:
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: теореме Поста является полным.
, который, в свою очередь, поПримеры:
Тождественные функции. Выражение функций друг через друга
Определение: |
Тождественные функции — функции, которые при любых одинаковых аргументах принимают равные значения. |
Приведение тождественной функции есть выражение булевой функции через другие.
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.
Пример: |
Выразим следующие функции через систему функций
| .
Подстановка одной функции в другую
Определение: |
Подстановкой (англ. substitution) функции | в функцию называется замена -того аргумента функции значением функции :
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции
вместо -того аргумента функции , результирующая функция будет принимать аргументы, которые можно разделить на следующие блоки:1. | — аргументы функции | до подставленного значения функции
2. | — используются как аргументы для вычисления значения функции |
3. | — аргументы функции | после подставленного значения функции
Пример: |
Исходные функции:
|
Отождествление переменных
Определение: |
Отождествлением переменных (англ. identification of variables) называется подстановка | -того аргумента функции вместо -того аргумента:
Таким образом, при отождествлении
переменных мы получаем функцию с количеством аргументов .Пример: |
Очевидно, в данном примере мы получили функцию — функция с отождествленными первым и вторым аргументами — проектор единственного аргумента. | — исходная функция
Схемы из функциональных элементов
Определение: |
Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе 1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные); 2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса ). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса . | , в котором:
Отождествление переменных осуществляется при помощи ветвления проводников.
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
Некоторые логические элементы:
И | ИЛИ | НЕ | Штрих Шеффера | Стрелка Пирса |
---|---|---|---|---|
![]() |
![]() |
![]() |
![]() |
![]() |
Стандартный базис
Определение: |
Стандартный базис — система булевых функций: |
Если рассматривать множество бинарных булевых функций , то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:
Функции
являются отрицаниями функций соответственно.
Тождественность функций можно доказать с помощью таблицы истинности.
Пример:
Выразим через стандартный базис обратную импликацию
.
Полнота стандартного базиса
Утверждение: |
Стандартный базис является полной системой булевых функций |
Данное утверждение - следствие теоремы об СДНФ. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше. |
Замечание:
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:
(конъюнктивный базис Буля)
(дизъюнктивный базис Буля)
Теоремы о числе функций в базисе
Теорема: |
Максимально возможное число булевых функций в безызбыточном базисе — четыре. |
Доказательство: |
Рассмотрим произвольный безызбыточный базис теореме Поста содержит следующие функции (не обязательно различные): . Тогда по, где — классы Поста. Значит, так как — безызбыточный базис, а система — полная, тоРассмотрим . Возможны два случая:1. , тогда также не сохраняет единицу и немонотонная, т.е.. Значит, . 2. , тогда несамодвойственная, т.е. . Значит, . |
Теорема: |
Для любого числа найдётся базис , что . |
Доказательство: |
Приведём примеры базисов для каждого :; ; ; ; Докажем, что последняя система является базисом: ; ; ; (доказывается с помощью таблицы истинности). |
См. также
- Специальные формы КНФ
- Сокращенная и минимальная ДНФ
- Пороговая функция
- Cумматор
- Полные системы функций. Теорема Поста о полной системе функций
Примечания
Источники информации
- Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
- Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
- Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
- Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
- Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
- Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
- Учебные пособия кафедры математической кибернетики ВМиК МГУ
- Булева функция — Википедия
- http://psi-logic.narod.ru/bool/bool.htm