Логические функции.

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

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

Логические функции могут быть заданы аналитически (с помощью логической формулы) или табличным способом.

Выясним количество логических функций для двух аргументов.

Совокупность значений логической формулы в последнем столбце трактуется как строка нулей и единиц (бинарная строка) длины n. Заметим, что существует ровно 2ⁿ различных бинарных строк длины n. Таблица истинности для логической формулы, включающей две переменные, содержит 4 строки. Таким образом, существует 16 различных логических функций от двух аргументов.

x	y	f1	f2	f3	f4	f5	f6	f7	f8
0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

x	y	f9	f10	f11	f12	f13	f14	f15	f16
0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

• f₁(x, y) = 0 - константа «ложь»
• f₂(x, y) = x ∧ y - конъюнкция
• f₃(x, y) = ¬ (x ⇒ y) - отрицание импликации
• f₄(x, y) = х - функция равна первому аргументу
• f₅(x, y) = ¬ (y ⇒ x) - отрицание обратной импликации
• f₆(x, y) = у - функция равна второму аргументу
• f₇(x, y) = x ⊕ y - разделительная (строгая дизъюнкция)
• f₈(x, y) = x ∨ y - дизъюнкция
• f₉(x, y) = x ↓ y - стрелка Пирса
• f₁₀(x, y) = x ≡ y - эквивалентность
• f₁₁(x, y) = ¬ y - отрицание второго аргумента
• f₁₂(x, y) = y ⇒ x - обратная импликация
• f₁₃(x, y) = ¬ x - отрицание первого аргумента
• f₁₄(x, y) = x ⇒ y - импликация
• f₁₅(x, y) = x | y - штрих Шеффера
• f₁₆(x, y) = 1 - константа «истина»

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