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

 

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении n -го дифференциала dⁿf (x): было введено понятие первого дифференциала df (x), а затем n -й дифференциал определялся как первый дифференциал от d ^{(n –1)} f (x).

Определение 1. Пусть М Ì P ₂, тогда:

1) каждая функция f (x ₁,..., x _n)Î M называется формулой над M;

2) пусть g (x ₁,..., x_m)Î M, G ₁,..., G_m – либо переменные, либо формулы над M. Тогда выражение g (G ₁... G_n) – формула над M.

Формулы будем обозначать заглавными буквами: N [ f ₁,..., f_s ], имея в виду функции, участвовавшие в построении формулы, или N (х ₁,..., x_k) имея в виду переменные, вошедшие в формулу. G_i – формулы, участвовавшие в построении g (G ₁,..., G_n), называются подформулами.

Пример 1. Пусть N ={(x ₁& x ₂), (x ₁Ú x ₂), (` x)}, тогда ((х ₁& х ₂)Ú х ₃) – формула над N.

Сопоставим каждой формуле N (x ₁,..., x_n) функцию f (x ₁,..., x_n)Î P ₂. Сопоставление будем производить в соответствии с индуктивным определением формулы.

1) Пусть N (x ₁,..., x_n)= f (x ₁,..., x_n), тогда формуле N (x ₁,..., x_n) сопоставим функцию f (x ₁,..., x_n).

2) Пусть N (x ₁,..., x_n)= g (G ₁,..., G_m), где каждое G_i – либо формула над M, либо переменная, тогда по индуктивному предположению каждому G_i сопоставлена либо функция f_i Î P ₂, либо переменная х_i, которую можно считать тождественной функцией. Таким образом, каждой формуле G_i сопоставлена функция f_i (), причем: { }Í { x ₁,..., x _n}, т.к. в формуле N (x ₁,..., x_n) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции f_i зависят от переменных (x ₁,..., x_n), причем какие-то переменные могут быть фиктивными. Тогда N (x ₁,..., x_n) = g (G ₁,..., G_m) = g (f ₁(x ₁,..., x_n),..., f_m (x ₁,.., x_n)). Сопоставим этой формуле функцию h (x ₁,..., x_n) следующим образом: пусть (a ₁,..., a_n) – произвольный набор переменных (x ₁,..., x_n). Вычислим значение каждой функции f_i на этом наборе, пусть f (a ₁,..., a_n)= b_i, затем найдем значение функции g (x ₁,..., x_m) на наборе (b ₁,..., b_m) и положим h (a ₁,..., a_n) = g (b ₁,..., b_m) = g (f ₁(a ₁,..., a_n),..., f_m (a ₁,..., a_n)). Так как каждое f_i (x ₁,..., x_n) есть функция, то на любом наборе (a ₁,..., a_n) она определяется однозначно, g (x ₁,..., x_m) – тоже функция, следовательно, на наборе (b ₁,..., b_n) она определяется однозначно, где h (x ₁,..., x_n) есть функция, определенная на любом наборе (a ₁,..., a_n).

Множество всех формул над M обозначим через < M >.

Определение 2. Две формулы N и D из < M > называются равными N = D или эквивалентными N ~ D, если функции, реализуемые ими, равны.

Пример 2. Доказать эквивалентность формул:

( & (х ₂Å x ₃))~().

x 1	x 2	x 3	x 2Å x 3	&	x 2 x 3	x 3 x 2	&	Ú x 1

 

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

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

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

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

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

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