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

 

Пусть 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¢.