Пример 4. Пусть функция g(x1,x2) задана таблицей и существенно зависит от обеих переменных

x 1	x 2	g

Пусть функция g (x ₁, x ₂) задана таблицей и существенно зависит от обеих переменных. Построим функцию f (x ₁, x ₂, x ₃), которая получается из g (x ₁, x ₂) введением фиктивной переменной х ₃:

x 1	x 2	x 3	f

К наборам (х ₁, х ₂) мы добавим х ₃=0, получим наборы вида: (a ₁, a ₂,0), на этих наборах функцию f положим равной g (a ₁, a ₂), затем добавим наборы вида (a ₁, a ₂,1), функцию f (a ₁, a ₂,1) положим равной g (a ₁, a ₂).

Особую роль играют константы 0 и 1, которые не имеют существенных переменных и которые можно рассматривать как функции от пустого множества переменных.

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

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

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

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

2) пусть g (G ₁,..., G_m)Î M, G ₁,..., G_m – либо переменные, либо формулы над M. Тогда выражение g (G ₁... G_m) – формула над 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) если нет скобок, то операции ~ и выполняются в последнюю очередь.