2.3. Элементарные булевы функции

Подобно тому, как в математическом анализе знакомство с основами начинают с изучения основных элементарных функций (sin, log, и т.д.), так и изучение теории булевых функций естественно начинать с изучения основных элементарных булевых функций.

Основные булевы операции – конъюнкция, дизъюнкция, инверсия.

2.3.1. Функции алгебры логики

Мы установили, что с точки зрения алгебры высказываний логические операции полностью характеризуются таблицами истинности. При этом можно забыть о том, что мы рассматриваем какие-то операции над высказываниями, и иметь дело лишь с самими таблицами.

Определение

Функцией алгебры логики от n переменных

(х₁, х₂, х_{3, … ,}х_n) называется функция f: , где Е₂:={0,1}. (или булева функция).

Таким образом, как аргументы функции, так и сама функция принимают только два значения: 1и 0.

Множество булевых функций от n переменных обозначим P_n, где P_n := {f(f: )}.

Функцию от n переменных f(х₁, х₂, х_{3, … ,}х_n) можно задать ее таблицей истинности (см. выше).

Легко заметить, число различных двоичных наборов длины n – упорядоченных наборов (α₁, α₂, ...,α_n) из 0 и 1 – конечно.

х1	х2	х3	…	хn-1	xn	f(х1, х2, х3, … ,хn)
0 1 … 1 1	0 0 … 1 1	0 0 ... 1 1	... ... ... ... ....	0 0 ... 1 1	0 0 ... 1 1	f(0,0, ...,0,0) f(1,0, ...,0,0) ..................... f(1,1, ...,1,0) f(1,1, ..., 1,1)

У нас имеется некоторое количество «основных» логических операций (отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность). Они позволяют получить из простых высказываний сложные. При этом вместо простых высказываний можно брать уже построенные сложные. В результате появляется возможность применять при построении сложных высказываний многоступенчатые конструкции, многократно использующие введенные логические операции.

Назовем формулами логические операции, которые получаются комбинированием конечного числа указанных выше основных логических операций.

Пример : P : «Влажность большая»; Q: «Температура высокая»; С: «Мы чувствуем себя хорошо».

Тогда предложение: «Если влажность большая и температура высокая, то мы не чувствуем себя хорошо» можно записать в виде

(P^Q) .

Таким образом, составное высказывание может выражать довольно сложную мысль (является формулой).

Определение: Формулы в логике высказываний определяются следующим образом:

1. Атом есть формула.

2. Если G – формула, то - формула.

3. Если G и Н – формулы, то (G^H), (GvH), (G H) и (G H) – формулы.

4. Никаких формул, кроме порожденных применением указанных выше правил, нет.

Легко видеть, что такие выражения, как (P→) и (Pv), не являются формулами.

Для всякой формулы можно построить истинностную таблицу, последовательно пользуясь истинностными таблицами для основных операций.

Естественно считать равносильными формулы, которым соответствуют одинаковые истинностные таблицы.

Определение

Пусть U и В – две формулы высказываний, а

А₁, А₂, …, А_n – набор простых высказываний, входящих по крайней мере, в одну из формул U и В. Формулы U и В называются равносильными, если при всех значениях истинности А₁, А₂, …, А_n значения истинности U и В совпадают.

Равносильность U и В обозначается посредством обычного значка равенства:

U = В.

Примеры:

1) AvA = A; 2) (Av ) ^ B = B; 3) Av = Bv

4) Av(A^B) = A (доказать!).

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

В этом случае, простые высказывания, входящие лишь в одну из формул, входят в нее фиктивным образом, т.е. истинность этой формулы не зависит от истинности этих простых высказываний.

Оказывается, что любую логическую операцию (с точностью до равносильности) можно выразить через основные операции; более того, для этого даже достаточно дизъюнкции, конъюнкции и отрицания.