Примеры булевых функций — различия между версиями
| Строка 39: | Строка 39: | ||
x - тождественная функция | x - тождественная функция | ||
| − | ¬x - отрицание, также обозначается < | + | ¬x - отрицание, также обозначается <tex>\overline{x}</tex> |
1 - тождественная единица | 1 - тождественная единица | ||
| Строка 45: | Строка 45: | ||
Для двух переменных есть четыре набора переменных - {0,0}, {0,1}, {1,0} и {1,1}, для них определено 16 бинарных функций. | Для двух переменных есть четыре набора переменных - {0,0}, {0,1}, {1,0} и {1,1}, для них определено 16 бинарных функций. | ||
{| border="1" | {| border="1" | ||
| − | |- | + | |-align="center" bgcolor=#EEEEFF |
!x||y | !x||y | ||
| − | |0||∧||<tex>\nrightarrow</tex>||x||<tex>\nleftarrow</tex>||y||⊕||∨||↓||↔||¬y||←||¬x||→||∇||1 | + | |! 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||0||0||1||1||1||1||1||1||1||1 | |0||0||0||0||0||0||0||0||1||1||1||1||1||1||1||1 | ||
| − | |- | + | |-align="center" |
!0||1 | !0||1 | ||
|0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1 | |0||0||0||0||1||1||1||1||0||0||0||0||1||1||1||1 | ||
| − | |- | + | |-align="center" |
!1||0 | !1||0 | ||
|0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1 | |0||0||1||1||0||0||1||1||0||0||1||1||0||0||1||1 | ||
| − | |- | + | |-align="center" |
!1||1 | !1||1 | ||
|0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1 | |0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1 | ||
| − | |- | + | |-align="center" bgcolor=#EEEEFF |
!colspan="2"|Сохраняет 0 | !colspan="2"|Сохраняет 0 | ||
|1||1||1||1||1||1||1||1||0||0||0||0||0||0||0||0 | |1||1||1||1||1||1||1||1||0||0||0||0||0||0||0||0 | ||
| − | |- | + | |-align="center" bgcolor=#EEEEFF |
!colspan="2"|Сохраняет 1 | !colspan="2"|Сохраняет 1 | ||
|0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1 | |0||1||0||1||0||1||0||1||0||1||0||1||0||1||0||1 | ||
| − | |- | + | |-align="center" bgcolor=#EEEEFF |
!colspan="2"|Самодвойственная | !colspan="2"|Самодвойственная | ||
|0||0||0||1||0||1||0||0||0||0||1||0||1||0||0||0 | |0||0||0||1||0||1||0||0||0||0||1||0||1||0||0||0 | ||
| − | |- | + | |-align="center" bgcolor=#EEEEFF |
!colspan="2"|Монотонная | !colspan="2"|Монотонная | ||
|1||1||0||1||0||1||0||1||0||0||0||0||0||0||0||1 | |1||1||0||1||0||1||0||1||0||0||0||0||0||0||0||1 | ||
| − | |- | + | |-align="center" bgcolor=#EEEEFF |
!colspan="2"|Линейная | !colspan="2"|Линейная | ||
|1||0||0||1||0||1||1||0||0||1||1||0||1||0||0||1 | |1||0||0||1||0||1||1||0||0||1||1||0||1||0||0||1 | ||
Версия 09:21, 13 октября 2010
Содержание
Определение булевой функции
| Определение: |
| Булева функция - отображение Bn → B , где B={0, 1}. n - количество аргументов функции, также называется ее арностью. |
Для n переменных существует 2n различных наборов аргументов, и, соответственно, 22n различных функций от них.
Виды булевых функций
От нуля переменных(нульарные функции)
Для 0 переменных есть только один набор аргументов(пустое множество) и две функции - тождественный 0 и тождественная 1.
От одной переменной(унарные функции)
Для 1 переменной есть два набора аргументов - {0} и {1}. Для них определено четыре унарных функции.
| x | 0 | x | ¬x | 1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| Сохраняет 0 | 1 | 1 | 0 | 0 |
| Сохраняет 1 | 0 | 1 | 0 | 1 |
| Самодвойственная | 0 | 1 | 1 | 0 |
| Монотонная | 1 | 1 | 0 | 1 |
| Линейная | 1 | 1 | 1 | 1 |
0 - тождественный ноль
x - тождественная функция
¬x - отрицание, также обозначается
1 - тождественная единица
От двух переменных(бинарные функции)
Для двух переменных есть четыре набора переменных - {0,0}, {0,1}, {1,0} и {1,1}, для них определено 16 бинарных функций.
| x | y | 0 | ∧ | x | y | ⊕ | ∨ | ↓ | ↔ | ¬y | ← | ¬x | → | ∇ | 1 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| Сохраняет 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
| Самодвойственная | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | |
| Монотонная | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| Линейная | 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
x - первый проектор, также обозначается p1 или px
y - второй проектор, также обозначается p2 или py
⊕ - сложение по модулю 2, также обозначается x xor y, x≠y
∨ - дизъюнкия, логическое ИЛИ, также обозначается x or y, x+y , x | y
↓ - стрелка Пирса. Образует безызбыточный базис.
↔ - эквивалентность, также обозначается x=y
¬y - отрицание второго проектора
¬x - отрицание первого проектора
← - обратная ипликация, также обозначается x≥y
→ - импликация, также обозначается x≤y
∇ - штрих Шеффера. Образует безызбыточный базис.
1 - тождественная единица
