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

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

Пример 4.

Пример 3.

Пример 2.

Рассмотрим несколько функций двух переменных

x 1	x 2	(x 1& x 2)	f 3	f 15

Покажем, что (х ₁& x ₂) существенно зависит от х ₁. Рассмотрим наборы (0,1) и (1,1), здесь a ₂=1, f (0, a ₂)=0 и не равно f (1, a ₂)=1. Покажем, что х ₂ тоже существенная переменная. Рассмотрим наборы (1,0) и (1,1). Здесь a ₁=1, f (1,0)=0 и не равно f (1,1)=1. Для функции f ₃(x ₁, x ₂) покажем, что х ₂ – иктивная переменная, т.е. надо показать, что не существует наборов (a ₁,0) и (a ₁,1) таких, что f ₃(a ₁,0)¹ f ₃(a ₁,1). Пусть a ₁=0, т.е. рассмотрим наборы (0,0) и (0,1), f (0,0)= f (0,1)=0. Пусть a ₁=1, но f (1,0)= f (1,1)=1.

Для функции f ₁₅ и x ₁ и x ₂ являются фиктивными переменными. x ₁ – фиктивная переменная, если не существует наборов (0, a ₂) и (1, a ₂), таких, что f (0, a ₂)¹ f (1, a ₂). Если a ₂=0, то f (0,0)= f (1,0)=1. Пусть a ₂=1, тогда f (0,1)= f (1,1)=1.

Пусть х_i является фиктивной переменной для функции f (x ₁,..., x_i,..., x_n). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида: (a ₁,... a_{i– 1}, 1, a_{i +1},... a_n) или, наоборот, все строки вида: (a ₁,..., a_{i– 1}, 0, a_{i +1},... a_n) и столбец для переменной х_i. При этом получим таблицу для некоторой функции g (x ₁,..., x_{i –1}, x_{i +1},... x_n). Будем говорить, что функция g (x ₁,... x_{i –1}, x_{i +1},... x_n) получена из функции f (x ₁,..., x _i,... x_n) путем удаления фиктивной переменной х_i или f получена из g путем введения фиктивной переменной х_i.

Определение 4. Функции f ₁ и f ₂ называются равными, если f ₂ можно получить из f ₁ путем добавления или удаления фиктивной переменной.

x 1	x 2	f 3

Вычеркнули строки типа (a,1), т.е. (0,1) и (1,1) и столбец для х ₂.

Получили f ₃(x ₁ x ₂) = g (x ₁) = x ₁.

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, которые не имеют существенных переменных и которые можно рассматривать как функции от пустого множества переменных.

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

Пусть N Î< M > и имеет вид: N (x ₁,..., x_n) = g (G ₁,... G_i,..., G_m). Пусть подформула G_i ~ G_i ¢, тогда формула N (x ₁,..., x_n) = g (G ₁,..., G_i,..., G_m) эквивалентна формуле N ¢(x₁,..., x_n) = g (G ₁¢,..., G_i ¢,..., G ¢ _m).

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

N (x ₁,..., x_n) = g (f ₁(x ₁,..., x_n),..., f_i (x ₁,..., x_n),..., f_m (x ₁,..., x_n)),

N ¢ (x ₁,..., x_n)= g (f ₁¢ (x ₁,..., x_n),..., f_i ¢(x ₁,..., x_n),..., f_m ¢ (x ₁,..., x_n)).

По условию G_i ~ G_i ¢, следовательно на наборе (a ₁,..., a_n) имеем f_i (a ₁,..., a_n) = = f_i ¢(a ₁,..., a_n) следовательно, на любом наборе (a ₁,..., a_n)значения функции g (f ₁,..., f_i,..., f_m) и g (f ₁¢,..., f_i ¢,..., f_m ¢) совпадают. Получим N ~ N ¢.

Дата добавления: 2014-12-27