78
правок
Изменения
Отмена правки 10931 участника Melnik (обсуждение)
==Определение булевой функции==
{{Определение
|definition =
[[Определение булевой функции|Булева функция]] - отображение B<sup>n</sup> → 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%" | ¬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 - тождественная функция
¬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%" | ∧
|! width="5%" | <tex>\nrightarrow</tex>
|! width="5%" | x
|! width="5%" | <tex>\nleftarrow</tex>
|! width="5%" | y
|! width="5%" | ⊕
|! width="5%" | ∨
|! width="5%" | ↓
|! width="5%" | ↔
|! width="5%" | ¬y
|! width="5%" | ←
|! width="5%" | ¬x
|! width="5%" | →
|! width="5%" | ∇
|! 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
∧ - конъюнкция, логическое И, также обозначается x and y, x&y , x·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>
⊕ - сложение по модулю 2, также обозначается x xor y, x≠y
∨ - дизъюнкия, логическое ИЛИ, также обозначается x or y, x+y , x | y
↓ - стрелка Пирса. Образует безызбыточный базис.
↔ - эквивалентность, также обозначается x=y
¬y - отрицание второго проектора
¬x - отрицание первого проектора
← - обратная импликация, также обозначается x≥y
→ - импликация, также обозначается x≤y
∇ - штрих Шеффера. Образует безызбыточный базис.
1 - тождественная 1
