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

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

Булева функция - отображение Bⁿ → B , где B={0, 1}. n - число переменных в функции, также называется ее арностью. Для n переменных существует 2ⁿ различных наборов аргументов, и, соответственно, 2²ⁿ различных функций от них.

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

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

Для 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 - отрицание, также обозначается [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	0
Линейн		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 - первый проектор, также обозначается p₁ или p_x

y - второй проектор, также обозначается p₂ или p_y

⊕ - сложение по модулю 2, также обозначается x xor y, x≠y

∨ - дизъюнкия, логическое ИЛИ, также обозначается x or y, x+y , x | y

↓ - стрелка Пирса. Образует безызбыточный базис.

↔ - эквивалентность, также обозначается x=y

¬y - отрицание второго проектора

¬x - отрицание первого проектора

← - обратная ипликация, также обозначается x≥y

→ - импликация, также обозначается x≤y

∇ - штрих Шеффера. Образует безызбыточный базис.

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