Теорема о логическом следствии

Формула алгебры логики f является логическим следствием формулы алгебры логики g,тогда и только тогда, если g f.

Доказательство.

Пусть n - количество различных переменныхf, входящих в формулы g и f,и а n - мерный двоичный набор из 0 и 1.

Пусть gf ,покажем что .

Так какfявляется следствием из g,то на любом наборе а, если g(а)=1, то f(а)=1. Если же g(а)=0, то 0 f принимает значение 1 при любом значенииf (а).

Пусть g f,покажем, что gf.

f-следствие из g,если при любом наборе а,из g(а)=1 следует f(а)=1.

Пусть а,такой набор, что g(а)=1, тогда из того, что g f-тождественно истинная формула, её значение на наборе а должно равняться 1, а это для операции импликации может быть лишь тогда, когда f (а)=1.

Теорема доказана.

Аналогичным образом доказывается и более общая теорема.

Обобщённая теорема о логическом следствии

f₁,f₂,…,f_mf тогда и только тогда, если f₁ f₂ ... f_mf

Множество формул алгебры логики { f₁,f₂,…,f_m } называется непротиворечивым,если существует по крайней мере один такой набор значений переменных, входящих в эти формулы, что все формулы из множества на этом наборе равны 1.

Множество формул алгебры логики { f₁,f₂,…,f_m } называется противоречивым,если при всяком наборе значений переменных, входящих в эти формулы, по крайней мере одна из формул принимает значение 0.

Отсюда, { } -непротиворечиво, если f₁ f₂ ... f_m=1по крайней мере на одном наборе и противоречиво, если f₁ f₂ ... f_m=0для любого набора значений переменных.