МЛОИ

Булевская функция в общем случае может содержать n аргументов: y=f(x1,x2,…,xn).
Как и математические функции, булевские функции могут задаваться: словесно, таблично или аналитически. Мы будем использовать последние два способа задания булевских функций: табличный (в виде таблиц истинности) и аналитический (в виде формул логики высказываний). Одна и та же функция может, естественно, задаваться по-разному.

1.2. Булевские функции одной переменной
Булевских функций от одной переменной всего 4. Эти функции и задающие их формулы логики высказываний приведены в следующей таблице:
x
0
1
Формулы логики высказываний, задающие функции
?1
0
0
?1(x) = 0 (константа 0)
?2
0
1
?2(x) = x (совпадает с переменной х)
?3
1
0
?3(x) = ?x (является отрицанием переменной х)
?4
1
1
?4(x) = 1 (константа 1)

1.3. Булевские функции двух переменных

Булевских функций от двух переменных всего насчитывается 16. Все они представлены в следующей таблице:
x
0
0
1
1
Формулы логики высказываний, задающие функции
y
0
1
0
1

f1
0
0
0
0
f1(x,y) = 0 (константа 0)
f2
0
0
0
1
f2(x,y) = x&y (конъюнкция)
f3
0
0
1
0
f3(x,y) = ?(x?y) (отрицание импликации)
f4
0
0
1
1
f4(x,y) = x (совпадает с переменной x)
f5
0
1
0
0
f5(x,y) = ?(y?x) (отрицание обратной импликации)
f6
0
1
0
1
f6(x,y) = y (совпадает с переменной y)
f7
0
1
1
0
f7(x,y) = x?y (строгая дизъюнкция)
f8
0
1
1
1
f8(x,y) = x?y (дизъюнкция)
f9
1
0
0
0
f9(x,y) = ?x??y (конъюнкция отрицаний)
f10
1
0
0
1
f10(x,y) = x?y (эквиваленция)
f11
1
0
1
0
f11(x,y) = ?y (отрицание y)
f12
1
0
1
1
f12(x,y) = y?x (обратная импликация)
f13
1
1
0
0
f13(x,y) = ?x (отрицание x)
f14
1
1
0
1
f14(x,y) = x?y (импликация)
f15
1
1
1
0
f15(x,y) = ?(x?y) (отрицание конъюнкции)
f16
1
1
1
1
f16(x,y) = 1 (константа 1)

Естественно, многие из перечисленных функций могут быть заданы другими, но равносильными формулами логики высказываний.

1.4. Булевские функции n переменных

Областью определения такой булевской функции будет n-тая декартова степень множества {0,1}, то есть всевозможные двоичные наборы длины n вида , где ?i?{0,1}. Число таких всевозможных наборов (n-ок) составляет 2n.
Область значений булевской функции от n переменных — это множество {0,1}.
В дальнейшем мы будем рассматривать только всюду определенные булевские функции, то есть область определения таких функций совпадает с n-той декартовой степенью множества {0,1}.
Булевские функции от большего числа переменных могут быть так же заданы таблично, или с помощью формул логики высказываний, или в виде суперпозиции (взаимной подстановки) булевских функций одной и/или двух переменных.
Например, булевская функция y=f(x,y,z), задаваемая формулой логики высказываний x&y ? ?x&?y ? z может быть задана в виде следующей суперпозиции функций от одной и двух переменных: y=f8(f8(f2(x,y),f9(x,y)),?2(z)).