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