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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Delete)
(Отмена правки 10931 участника Melnik (обсуждение))
Строка 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 и тождественная 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

Версия 02:40, 8 октября 2011

Определение булевой функции

Определение:
Булева функция - отображение Bn → B , где B={0, 1}. n - количество аргументов функции, также называется ее арностью.

Для n переменных существует 2n различных наборов аргументов, и, соответственно, 22n различных функций от них.

Виды булевых функций

От нуля переменных(нульарные функции)

Для нуля переменных есть только один набор аргументов(пустое множество) и две функции - тождественный 0 и тождественная 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 - отрицание, также обозначается [math]\overline{x}[/math]

1 - тождественная единица

От двух переменных(бинарные функции)

Для двух переменных есть четыре набора переменных - {0,0}, {0,1}, {1,0} и {1,1}, для них определено 16 бинарных функций.

x y 0 ∧ [math]\nrightarrow[/math] x [math]\nleftarrow[/math] 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

[math]\nrightarrow[/math] - отрицание импликации

x - первый проектор, также обозначается p1 или px

[math]\nleftarrow[/math] - отрицание обратной импликации

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 - тождественная 1

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Примеры_булевых_функций&oldid=10933»