Примеры булевых функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 5 участников)
Строка 1: Строка 1:
==Определение булевой функции==
+
[[Категория: Удалить]]
{{Определение
 
|definition =
 
[[Определение булевой функции|Булева функция]] - отображение B<sup>n</sup> &rarr; B , где B={0, 1}. n - количество аргументов функции, также называется ее арностью.
 
}}
 
Для n переменных существует 2<sup>n</sup> различных наборов аргументов, и, соответственно, 2<sup>2<sup>n</sup></sup> различных функций от них.
 
==Виды булевых функций==
 
===От нуля переменных(нульарные функции)===
 
Для 0 переменных есть только один набор аргументов(пустое множество) и две функции - тождественный 0 и тождественная 1.
 
===От одной переменной(унарные функции)===
 
Для 1 переменной есть два набора аргументов - {0} и {1}. Для них определено четыре унарных функции.
 
{| border="1"
 
|-align="center" bgcolor=#FFF8DC
 
!x
 
|! width="10%" | 0
 
|! width="10%" | x
 
|! width="10%" | &not;x
 
|! width="10%" | 1
 
|-align="center"
 
!0
 
|0||0||1||1
 
|-align="center"
 
!1
 
|0||1||0||1
 
|-align="center" bgcolor=#EEEEFF
 
!Сохраняет 0
 
|1||1||0||0
 
|-align="center" bgcolor=#EEEEFF
 
!Сохраняет 1
 
|0||1||0||1
 
|-align="center" bgcolor=#EEEEFF
 
!Самодвойственная
 
|0||1||1||0
 
|-align="center" bgcolor=#EEEEFF
 
!Монотонная
 
|1||1||0||1
 
|-align="center" bgcolor=#EEEEFF
 
!Линейная
 
|1||1||1||1
 
|}
 
0 - тождественный ноль
 
 
 
x - тождественная функция
 
 
 
&not;x - отрицание, также обозначается <tex>\overline{x}</tex>
 
 
 
1 - тождественная единица
 
===От двух переменных(бинарные функции)===
 
Для двух переменных есть четыре набора переменных - {0,0}, {0,1}, {1,0} и {1,1}, для них определено 16 бинарных функций.
 
{| border="1"
 
|-align="center" bgcolor=#FFF8DC
 
!x||y
 
|! width="5%" | 0
 
|! width="5%" | &and;
 
|! width="5%" | <tex>\nrightarrow</tex>
 
|! width="5%" | x
 
|! width="5%" | <tex>\nleftarrow</tex>
 
|! width="5%" | y
 
|! width="5%" | &oplus;
 
|! width="5%" | &or;
 
|! width="5%" | &darr;
 
|! width="5%" | &harr;
 
|! width="5%" | &not;y
 
|! width="5%" | &larr;
 
|! width="5%" | &not;x
 
|! width="5%" | &rarr;
 
|! width="5%" | &nabla;
 
|! width="5%" | 1
 
|-align="center"
 
!0||0
 
|0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1
 
|-align="center"
 
!0||1
 
|0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1
 
|-align="center"
 
!1||0
 
|0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1
 
|-align="center"
 
!1||1
 
|0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1
 
|-align="center" bgcolor=#EEEEFF
 
!colspan="2"|Сохраняет 0
 
|1||1||1||1||1||1||1||1||0||0||0||0||0||0||0||0
 
|-align="center" bgcolor=#EEEEFF
 
!colspan="2"|Сохраняет 1
 
|0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1
 
|-align="center" bgcolor=#EEEEFF
 
!colspan="2"|Самодвойственная
 
|0||0||0||1||0||1||0||0||0||0||1||0||1||0||0||0
 
|-align="center" bgcolor=#EEEEFF
 
!colspan="2"|Монотонная
 
|1||1||0||1||0||1||0||1||0||0||0||0||0||0||0||1
 
|-align="center" bgcolor=#EEEEFF
 
!colspan="2"|Линейная
 
|1||0||0||1||0||1||1||0||0||1||1||0||1||0||0||1
 
|}
 
 
 
 
 
0 - тождественный 0
 
 
 
&and; - конъюнкция, логическое И, также обозначается x and y, x&y , x&middot;y
 
 
 
x - первый проектор, также обозначается p<sub>1</sub> или p<sub>x</sub>
 
 
 
y - второй проектор, также обозначается p<sub>2</sub> или p<sub>y</sub>
 
 
 
&oplus; - сложение по модулю 2, также обозначается x xor y, x&ne;y
 
 
 
&or; - дизъюнкия, логическое ИЛИ, также обозначается x or y, x+y , x | y
 
 
 
&darr; - стрелка Пирса. Образует безызбыточный базис.
 
 
 
&harr; - эквивалентность, также обозначается x=y
 
 
 
&not;y - отрицание второго проектора
 
 
 
&not;x - отрицание первого проектора
 
 
 
&larr; - обратная ипликация, также обозначается x&ge;y
 
 
 
&rarr; - импликация, также обозначается x&le;y
 
 
 
&nabla; - штрих Шеффера. Образует безызбыточный базис.
 
 
 
1 - тождественная единица
 

Текущая версия на 19:06, 4 сентября 2022