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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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