|
|
| Строка 1: |
Строка 1: |
| − | ==Определение булевой функции==
| |
| − | {{Определение
| |
| − | |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
| |
