Реляционные аналоги штриха Шеффера и стрелки Пирса

Избыточность Алгебры A

В формальной математической логике стандартным базисом для выражения всех возможных булевских функций является набор {NOT, AND, OR} (отрицание, дизъюнкция и конъюнкция). Известно, что этот набор традиционен, но избыточен, поскольку верны тождества A AND B NOT (NOT A OR NOT B) и A OR B NOT (NOT A AND NOT B). (Эти тождества легко проверяются по таблицам истинности операций.) Оказывается (и это тоже легко проверить, опираясь на определения операций), что аналогичные тождества справедливы для операций <NOT>, <AND> и <OR> Алгебры A. Тем самым, в наборе базовых операций Алгебры A можно оставить операции <AND> и <NOT> (или <OR> и <NOT>).

Более того, в алгебре логики существуют две операции, через каждую из которых выражаются все три «базовые» операции: «штрих Шеффера» – sh (A, B) NOT A OR NOT B – и «стрелка Пирса» – pi (A, B) NOT A AND NOT B.

Легко видеть, что

• sh (A, A) NOT A;
• sh (NOT A, NOT B) A OR B и
• NOT sh (A, B) A AND B.

Аналогично,

• pi (A, A) NOT A;
• pi (NOT A, NOT B) A AND B и
• NOT pi (A, B) A OR B.

Снова нетрудно проверить, что аналогичные тождества справедливы для реляционных вариантов штриха Шеффера (<sh> (r1, r2) <NOT> r1 <OR> <NOT> r2) и стрелки Пирса (<pi> (r1, r2) <NOT> r1 <AND> <NOT> r2).

Поэтому можно свести набор операций Алгебры A к трем операциям: <sh> (или <pi>), <RENAME> и <REMOVE>.

Дата добавления: 2015-04-29