2.2. Формульное задание функций алгебры логики

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении 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))~( ) .

X2ÅX3

X2 X3

X3 X2

ÚX1

Упрощение записи формул:

1) внешние скобки можно отпускать;

2) приоритет применения связок возрастает в следующем порядке: ~, , Ú,&;

3) связка – над одной переменной сильнее всех связок;

4) если связка – стоит над формулой, то сначала выполняется формула, затем отрицание;

5) если нет скобок, то операции ~ и выполняются в последнюю очередь.

Теорема о замене подформул на эквивалентные

Пусть NÎ<M> и имеет вид: N(X1, ..., Xn) = G(G1, ...Gi, ...,Gm). Пусть подформула Gi~Gi¢, тогда формула N(X1, ..., Xn) = G(G1, ...,Gi,...,Gm) эквивалентна формуле N¢(X1, ..., Xn) = G(G1¢, ..., Gi¢, ...,G¢M).

Доказательство. Формулы N и N¢ эквивалентны, если реализуют одну и ту же функцию. Согласно построению функции, реализующей формулу имеем:

N(X1, ..., Xn) = G(F1(X1, ..., Xn ), ..., Fi(X1, ..., Xn), ..., Fm(X1, ..., Xn)),

N¢ (X1, ..., Xn)= g(F1¢ (X1, ..., Xn ), ..., Fi¢(X1, ..., Xn), ..., Fm¢ (X1, ..., Xn)).

По условию Gi~Gi¢, следовательно на наборе (A1, ..., AN) имеем Fi (A1, ..., AN) = = Fi¢(A1, ..., AN) следовательно, на любом наборе (A1, ..., AN)значения функции G(F1, ...,Fi, ...,Fm) и G(F1¢, ...,FI¢, ...,Fm¢) совпадают. Получим N~N¢.

Некоторые свойства элементарных функций

1. Идемпотентность & и Ú: Х&X=X , XÚX=X.

2. Коммутативность &,Ú,Å,|,~, .

3. Ассоциативность &,Ú,Å,~, поэтому в формулах вида Xyz можно не ставить никаких скобок.

4. Дистрибутивность:

А) & по отношению к Ú: X&(YÚZ)=XyÚXz ,

Б) Ú по отношению к &: XÚ(Y&Z)=(XÚY)&(XÚZ) ,

В) & по отношению к Å: X(YÅZ)=XyÅXz .

5. Инволюция : =Х .

6. Правило де Моргана: = & и = Ú .

7. Законы действия с 0 и 1:

XÚ0=X , XÚ1=1 , XÚ =1 , X&0=0 , X&1=X , X& =0 , XÅ1= , XÅ0=X.

8. Самодистрибутивность импликации: X (Y Z)=(X Y) (X Z).

Равенство всех этих формул доказывается по определению, т. е. по равенству функций, которые они реализуют.

Проверим для примера самодистрибутивность импликации : X (Y Z)=(X Y) (X Z).

Y Z

X (Y Z)

X Y

X Z

Следствия из свойств элементарных функций

1. Законы склеивания:

XyÚX =X(YÚ )=X 1=X (дистрибутивность & относительно Ú);

(XÚY)&(X )=X Y =XÚ 0=X (дистрибутивность Ú относительно &).

2. Законы поглощения:

XÚXy=X(1ÚY)=X 1=X; X&(XÚY)=XÚXy=X.

Свойства элементарных функций и теорема о замене подформул на эквивалентные позволяют упрощать формулы.

Пример 3:

Упростим формулы:

1. X2X3ÚX1 2X3 = X3(X2ÚX1 2) = x3((X2ÚX1)&(X2Ú 2)) = (X1ÚX2)X3.

2. X1Ú 1X2Ú 1 2X3Ú 1 2X3X4 = X1Ú 1(X2Ú 2 3X4) = X1Ú 1(X2ÚX3Ú 2 3X4) = (X1Ú 1)(X1ÚX2ÚX3Ú 2 3Х4) = X1Ú(X2ÚX3)Ú( )X4 = X1Ú(X2ÚХ3Ú( ))(X2ÚX3ÚX4) = X1ÚX2ÚX3ÚX4.

< Предыдущая		Следующая >