Изменения

Перейти к: навигация, поиск

Примеры булевых функций

4873 байта добавлено, 02:40, 8 октября 2011
Отмена правки 10931 участника Melnik (обсуждение)
==Определение булевой функции==
{{Определение
|definition =
[[Определение булевой функции|Булева функция]] - отображение B<sup>n</sup> &rarr; B , где B={0, 1}. n - количество аргументов функции, также называется ее арностью.
}}
Для n переменных существует 2<sup>n</sup> различных наборов аргументов, и, соответственно, 2<sup>2<sup>n</sup></sup> различных функций от них.
==Виды булевых функций==
===От нуля переменных(нульарные функции)===
Для нуля переменных есть только один набор аргументов(пустое множество) и две функции - тождественный 0 и тождественная 1.
===От одной переменной(унарные функции)===
Для одной переменной есть два набора аргументов - {0} и {1}. Для них определено четыре унарных функции.
{| border="1"
|-align="center" bgcolor=#FFF8DC
!x
|! width="12%" | 0
|! width="12%" | x
|! width="12%" | &not;x
|! width="12%" | 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
 
<tex>\nrightarrow</tex> - отрицание импликации
 
x - первый проектор, также обозначается p<sub>1</sub> или p<sub>x</sub>
 
<tex>\nleftarrow</tex> - отрицание обратной импликации
 
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 - тождественная 1
78
правок

Навигация