МЛОИ

Учитывая принципиальную возможность выразить булевскую функцию от любого числа переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных, мы чаще будем использовать либо табличный способ задания таких функций, либо с помощью формул логики высказываний.
Табличный способ задания булевских функций от одной и двух переменных (см. приведенные выше таблицы, определяющие эти функции) наводит на некоторые соображения:
число наборов истинностных значений, на которых определена булевская функция от n переменных, составляет 2n (при n=1 это число составляет 2, при n=2 — 4);
значение каждой булевской функции от n переменных представляет собой двоичный набор длины 2n;
каждая булевская функция отличается от любой другой булевской функции с тем же числом переменных своим значением хотя бы на одном из таких наборов
А отсюда можно сделать предположение о том, число N различных булевских функций от n переменных равно числу различных двоичных наборов длины 2n, то есть:
При n=1 это число равно 4, при n=2 — 16, n=3 — 256, n=4 — 65536 и т.д.

1.5. Полные системы булевских функций

В предыдущем пункте было отмечено, что можно выразить любую булевскую функцию от n переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных. В свою очередь эти функции задаются формулами, содержащими логические операции: отрицание(?), конъюнкцию (&),строгую дизъюнкцию (?), дизъюнкцию(?), импликацию(?), эквиваленцию (?).
Но как известно из логики высказываний, операции логики высказываний строгая дизъюнкция (?), импликация (?), эквиваленция (?) могут быть выражены через дизъюнкцию (?), конъюнкцию (&) и отрицание (?).
В свою очередь, дизъюнкция (?) может быть выражена через конъюнкцию (&) и отрицание (?), а конъюнкция (&) — через дизъюнкцию (?) и отрицание (?).
Таким образом, конъюнкция и отрицание, а также дизъюнкция и отрицание, образуют полную систему логических связок, то есть через эти операции могут быть выражены все остальные.
Более того, можно определить логическую операцию, через которую выражаются все шесть операций: отрицание (?), конъюнкция (&), дизъюнкция (?), строгая дизъюнкция (?), импликация (?), эквиваленция (?). Таковой, например, является операция, соответствующая сложному союзу «не А или не В» («или» соединительное). Эта операция обозначается символом ?(например, А?В) и получила название штрих Шеффера. Штрих Шеффера определяется с помощью следующей таблицы:

X
Y
X?Y
Л
Л
И
Л
И
И
И
Л
И
И
И
Л

Как легко видеть, штрих Шеффера представляет собой отрицание конъюнкции: X?Y ? ?X??Y ? ?(X&Y).
Можно убедиться, что ?X ? X?X.
А отсюда: X&Y ? ?( X?Y) ? (X?Y) ?( X?Y).
Таким образом, через штрих Шеффера могут быть выражены конъюнкция и отрицание, а значит и все остальные операции логики высказываний. То есть система логических связок, содержащая единственную операцию — штрих Шеффера, является полной.