Формульное задание функций алгебры логики
Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении n -го дифференциала dnf (x): было введено понятие первого дифференциала df (x), а затем n -й дифференциал определялся как первый дифференциал от d (n –1) f (x). Определение 1. Пусть М Ì P 2, тогда: 1) каждая функция f (x 1,..., x n)Î M называется формулой над M; 2) пусть g (x 1,..., xm)Î M, G 1,..., Gm – либо переменные, либо формулы над M. Тогда выражение g (G 1... Gn) – формула над M. Формулы будем обозначать заглавными буквами: N [ f 1,..., fs ], имея в виду функции, участвовавшие в построении формулы, или N (х 1,..., xk) имея в виду переменные, вошедшие в формулу. Gi – формулы, участвовавшие в построении g (G 1,..., Gn), называются подформулами. Пример 1. Пусть N ={(x 1& x 2), (x 1Ú x 2), (` x)}, тогда ((х 1& х 2)Ú х 3) – формула над N. Сопоставим каждой формуле N (x 1,..., xn) функцию f (x 1,..., xn)Î P 2. Сопоставление будем производить в соответствии с индуктивным определением формулы. 1) Пусть N (x 1,..., xn)= f (x 1,..., xn), тогда формуле N (x 1,..., xn) сопоставим функцию f (x 1,..., xn). 2) Пусть N (x 1,..., xn)= g (G 1,..., Gm), где каждое Gi – либо формула над M, либо переменная, тогда по индуктивному предположению каждому Gi сопоставлена либо функция fi Î P 2, либо переменная хi, которую можно считать тождественной функцией. Таким образом, каждой формуле Gi сопоставлена функция fi ( Множество всех формул над M обозначим через < M >. Определение 2. Две формулы N и D из < M > называются равными N = D или эквивалентными N ~ D, если функции, реализуемые ими, равны. Пример 2. Доказать эквивалентность формул: (
Упрощение записи формул: 1) внешние скобки можно отпускать; 2) приоритет применения связок возрастает в следующем порядке: ~, 3) связка – над одной переменной сильнее всех связок; 4) если связка – стоит над формулой, то сначала выполняется формула, затем отрицание; 5) если нет скобок, то операции ~ и
|
), причем: { 
}Í { x 1,..., x n}, т.к. в формуле N (x 1,..., xn) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции fi зависят от переменных (x 1,..., xn), причем какие-то переменные могут быть фиктивными. Тогда N (x 1,..., xn) = g (G 1,..., Gm) = g (f 1(x 1,..., xn),..., fm (x 1,.., xn)). Сопоставим этой формуле функцию h (x 1,..., xn) следующим образом: пусть (a 1,..., an) – произвольный набор переменных (x 1,..., xn). Вычислим значение каждой функции fi на этом наборе, пусть f (a 1,..., an)= bi, затем найдем значение функции g (x 1,..., xm) на наборе (b 1,..., bm) и положим h (a 1,..., an) = g (b 1,..., bm) = g (f 1(a 1,..., an),..., fm (a 1,..., an)). Так как каждое fi (x 1,..., xn) есть функция, то на любом наборе (a 1,..., an) она определяется однозначно, g (x 1,..., xm) – тоже функция, следовательно, на наборе (b 1,..., bn) она определяется однозначно, где h (x 1,..., xn) есть функция, определенная на любом наборе (a 1,..., an).
& (х 2Å x 3))~(
).
x 3
