МЛОИ

Есть еще одна логическая операция, аналогичная штриху Шеффера и называемая стрелкой Пирса. Она обозначается символом ? и представляет собой отрицание дизъюнкции (или конъюнкцию отрицаний): X?Y ? ?(X?Y) ? ?X&?Y.
Можно убедиться, что ?X ? X?X.
А отсюда: X?Y ? ?( X?Y) ? (X?Y) ? ( X?Y).
Таким образом, через стрелку Пирса могут быть выражены дизъюнкция и отрицание, а значит и все остальные операции логики высказываний. То есть система логических связок, содержащая единственную операцию — стрелку Пирса, является полной.
Систему булевских функций будем называть функционально полной, если любую булевскую функцию можно выразить в виде суперпозиции (взаимной подстановки) функций из этой системы.
В соответствии с высказанными выше соображениями о полноте системы логических связок и задании булевских функций формулами логики высказываний, можно сделать вывод о функциональной полноте следующих систем булевских функций:
S0 = {?3(x), f2(x,y), f8(x,y)} — отрицание, конъюнкция, дизъюнкция.
S1 = {?3(x), f2(x,y)} — отрицание, конъюнкция.
S2 = {?3(x), f8(x,y)} — отрицание, дизъюнкция.
S3 = {f15(x,y)} — отрицание конъюнкции (штрих Шеффера).
S4 = {f9(x,y)} — отрицание дизъюнкции (стрелка Пирса).
S5 = {?3(x), f14(x,y)} — отрицание, импликация.
В последующем мы увидим, что с точки зрения проектирования вычислительных устройств особый интерес представляют S3 и S4.
Общий критерий функциональной полноты системы булевских функций, выражающий необходимые и достаточные условия, носит название критерия Поста-Яблонского.1 Его изложение выходит, к сожалению, за рамки настоящего пособия.

2. Булевы алгебры
Со школы читатель привык к слову алгебра. При этом под алгеброй, как правило, понимается раздел математики, посвященный изучению свойств числовых (арифметических) операций (сложение, вычитание, умножение, деление, возведение в степень, извлечение корня и т.д.), выражений, тождеств, уравнений и т.п.
Но, вообще говоря, слово алгебра в математике понимается значительно шире.
А именно: Алгеброй называют множество объектов любой природы с определенными и замкнутыми на этом множестве операциями.
Если какая-либо операция ? определена на множестве Q и результат ее также принадлежит этому множеству, то говорят, что операция ? замкнута на этом множестве, или множество замкнуто относительно операции ?. Например, множество натуральных чисел N замкнуто относительно операций сложения и умножения натуральных чисел, но не замкнуто относительно операций вычитания и деления, которые могут в качестве результата давать значения, не принадлежащие множеству натуральных чисел (вычитание – отрицательные числа, а деление – дробные).
С этой точки зрения, арифметика – это алгебра с операциями сложения и умножения, замкнутыми на множестве натуральных чисел. Если к числу операций добавить вычитание, то, строго говоря, это уже не будет алгебра.