Элементарные логические операции (функции)

Функция , определенная на множестве

и принимающая значения из множества {0, 1}, называется функцией алгебры логики или булевой функцией.

Очевидно, что для задания функции достаточно указать, какое значение принимает функция при каждом из наборов значений аргументов, то есть выписать таблицу:

x1 x2 ... xn-1 xn	f(x1, x2, ... xn-1, xn)
0 0 ... 0 0 0 0 ... 0 1 0 0 ... 1 1 ...................... 1 1 ... 1 1	f(0, 0, ... , 0, 0) f(0, 0, ... , 0, 1) f(0, 0, ... , 1, 1) ...................... f(1, 1, ... , 1, 1)

Таблица 2.A.

Легко видеть, что n переменных в совокупности принимают 2ⁿ различных значений. Для удобства мы употребляем стандартное расположение наборов значений переменных: если набор рассматривать как двоичную запись числа, то их расположение соответствует естественному расположению чисел 0, 1, ... , 2^n-1. Каждая функция f(x₁, x₂, ... , x_n) определяет отображение B²B² ... B²B². Поэтому естественно интерпретировать f как символ, обозначающий это отображение, а x₁, x₂, ... , x_n как названия столбцов. В этом случае функции f(x₁, x₂, ... , x_n) и f(y₁, y₂, ... , y_n) будут задавать одно и то же отображение, а их таблицы будут отличаться только, быть может, названиями столбцов. Обозначим через P₂ множество всех функций алгебры логики над алфавитом U, содержащее также и константы 0 и 1. Если зафиксировать n переменных x₁, x₂, ... , x_n , то различные таблицы будут отличаться лишь значениями в правом столбце. Поэтому справедливо следующее утверждение.

Теорема 2.1. Число p₂(n) всех функций из P₂, зависящих от переменных x₁, x₂, ... , x_n , равно .

Здесь следует обратить внимание на одно обстоятельство. Число функций алгебры логики, зависящих от заданных n аргументов, конечно. Поэтому, если нужно выяснить, обладают ли функции из этого конечного множества каким-либо свойством, достаточно осуществить перебор функций из данного множества. Однако числа p₂(n) с ростом n быстро растут:

p₂(1) = 4, p₂(2) = 16, p₂(3) = 256, p₂(4) = 65536, ... .

Таким образом, уже при сравнительно небольших значениях n (n  6) перебор становится практически неосуществимым даже с использованием вычислительной техники. С ростом числа аргументов n таблица, задающая функцию, сильно усложняется. Так при n = 64 для заполнения такой таблицы со скоростью 10⁹ строк в секунду понадобится около 300 лет. Поэтому несмотря на простоту табличного задания функций алгебры логики, такой инструмент исследования функций крайне неэффективен, если не бесполезен, при больших значениях n. Необходимость разработки аналитического задания и методов исследования функций алгебры логики очевидна.

Переменная x_i (1 i  n) функции f(x₁, x₂, ... ,x_i-1, x_i, x_i+1, ... , x_n) из P₂ называется существенной, если можно указать такие наборы

и

значений переменных, что . В противном случае переменную x_i называют несущественной или фиктивной переменной функции f(x₁, x₂, ... , x_i-1, x_i, x_i+1, ... , x_n).

Две функции и называются равными, если множества их существенных переменных совпадают и на любых двух наборах и , различающихся быть может только значениями несущественных переменных, значения функций одинаковы:. Если и - равные функции, то одну из них можно получить из другой путем добавления и/или изъятия несущественных переменных. 

Построение аналитической теории функций алгебры логики начнем с элементарных функций (операций).

Данные операции (функции) часто употребляются в математической логике и кибернетике и играют такую же роль, как, например, x + y в арифметике, x² в алгебре, sin(x) и e^x в анализе, поэтому их можно считать элементарными функциями.

Определим логические или булевские операции (функции) над элементарными высказываниями или логическими (булевскими) переменными.

1. Константы (нульместные операции):

0 - тождественный нуль (тождественная ложь),

1 - тождественная единица (тождественная истина).

2. Операции над одной переменной (одноместные, унарные операции):

отрицание, обозначается как или  x, читается “не x” или “отрицание x”. Эту операцию можно задать следующей таблицей, в которой указано, какое значение функции (операции) соответствует каждому из значений переменной x:

3. Операции над двумя переменными (двухместные, бинарные операции)

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

Функция x y называется конъюнкцией x и y, обозначается x y , или x&y , или xy , или xy , или min(x,y) и часто читается как “x и y”.

Функция x  y называется дизъюнкцией x и y, обозначается x  y или max (x,y) и часто читается как “x или y”.

Функция xy называется импликацией x и y, обозначается xy или x  y, часто читается как “x имплицирует y” или “из x следует y”.

Функция xy называется эквивалентностью (или эквиваленцией) x и y, обозначается xy, или x  y, или xy и часто читается “x эквивалентно y”.

Функция x+y называется суммой по модулю 2 (или булевой суммой) x и y, обозначается x+y, или xy и часто читается “x плюс y”.

Функция x|y называется штрихом (Шеффера) x и y, обозначается x|y и часто читается “x штрих y”, “не x или не y”. В технической литературе функция x|y называется обычно “не - и” или антиконъюнкцией, так как она равна отрицанию конъюнкции.

Функция xy называется стрелкой (Пирса) x и y, обозначается xy и часто читается “x стрелка y”, “ни x, ни y” или “не x и не y”. В технической литературе функция xy называется обычно “не - или” или антидизъюнкцией, так как она равна отрицанию дизъюнкции.

Символы операций, участвующие в обозначениях элементарных функций, называются логическими связками (или просто связками).

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

.

Очевидно, что не всякая последовательность символов переменных, знаков логических операций и скобок будет формулой алгебры логики. Так, например, последовательности   x+y, xy  z не могут рассматриваться как правильные формулы алгебры логики. Дадим индуктивное определение формулы.

Пусть U - множество переменных. Тогда множество формул алгебры логики над U определяется следующим образом:

1. Всякая переменная - формула.

2. Константы 0 и 1 - формулы.

3. Если А - формула, то  А (или в другой записи ) - формула.

4. Если А и В - формулы, то (АВ), (АВ), (АВ), (А+В), (АВ), (АВ), (АВ) - формулы.

5. Формулами являются те и только те выражения, которые могут быть получены из констант, переменных и логических связок за конечное число шагов 1- 4.

В пунктах 1 и 2 определены элементарные формулы, в пунктах 3 и 4 заданы правила образования из любых данных формул новых. Определения такого типа называются индуктивными определениями. Во всяком индуктивном определении имеются прямые пункты (п.п. 1-4) и косвенный пункт. В прямых пунктах задаются объекты, которые в дальнейшем именуются определяемым термином (в данном случае формулами алгебры высказываний). В косвенном пункте говорится, что такие объекты исчерпываются заданными в прямых пунктах. Среди прямых пунктов имеются базисные пункты (п. 1 и п. 2) и индуктивные пункты (в данном случае п. 3 и п. 4). В базисных пунктах прямо указываются объекты, которые в дальнейшем именуются определяемым термином. В индуктивных пунктах даются правила построения из любых объектов, определенных в базисных пунктах, новых объектов, которые также будут именоваться этим термином.

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

Две формулы А и В (или f₁ и f₂) будем называть равносильными (равными) и писать А=В (или f₁ = f₂ ), если они реализуют одну и туже фукнцию алгебры логики.

Очевидно, что если А - подформула формулы А, то при замене любого ее вхождения на равную формулу В формула А перейдет в формулу В, которая будет равна А.

Обычно принимаются следующие соглашения для сокращения записи формул:

• внешние скобки у формул опускаются;

• формула  А записывается как ;

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

• формула АВ записывается как АВ, или А&B, или АВ;

• связка  считается старше (сильнее) любой другой двухместной связки.

Эти соглашения позволяют, например, записать формулу

((((x)+y)z)((x( y)) z))

в виде

.