Формульное задание функций алгебры логики
Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении 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( 
), причем:{ 
}Í{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).
Множество всех формул над M обозначим через <M>.
Определение 2. Две формулы N и D из <M> называются равными N=D или эквивалентными N~D , если функции, реализуемые ими, равны.
Пример 2.Доказать эквивалентность формул:
( 
&(х2Åx3))~( 
) .
| x1 | x2 | x3 | x2Åx3 | & | x2  x3
| x3 x2
| & | Úx1 |
|
Упрощение записи формул:
1) внешние скобки можно отпускать;
2) приоритет применения связок возрастает в следующем порядке: ~, , Ú,&;
3) связка – над одной переменной сильнее всех связок;
4) если связка – стоит над формулой, то сначала выполняется формула, затем отрицание;
5) если нет скобок, то операции ~ и выполняются в последнюю очередь.
Дата добавления: 2016-03-27; просмотров: 668;