Определение. Формула G(x₁,…,x_n) называется логическим следствием формул F₁(x₁,…,x_n),…,F_k(x₁,…,x_n), если для любой интерпретации j с областью М и любых a₁,…,a_nÎM из истинности высказываний (jF₁)(a₁,…,a_n),…,(jF_k)(a₁,…,a_n) следует истинность высказывания (jG)(a₁,…,a_n).

Приведем примеры. Пусть F₁=("x)(P(x)®Q(x)&R(x)), F₂=P(c), G=Q(c). Покажем, что формула G является логическим следжствием формул F₁ и F₂. Возьмем интерпретацию j с областью М такую, что высказывания jF₁ и jF₂ истинны. Элемент j(c) обозначим буквой b. Истинность jF₂ означает, что высказывание (jP)(b) истинно. А истинность высказывания jF₁ означает, что для любого элемента xÎM истинно высказывание (jP)(x)®(jQ)(x)&(jR)(x). Поскольку это высказывание истинно для любого х, то, в частности, истинно для x=b. Мы видим, что истинна импликация (jP)(b)®(jQ)(b)&(jR)(b) и ее посылка (jP)(b). Из таблицы истинности импликации следует истинность заключения (jQ)(b)&(jR)(b). Следовательно, истинно высказывание (jQ)(b). А это и есть jG. Мы доказали, что если истинны высказывания jF₁ и jF₂, то истинно высказывание jG, т.е. что G –логическое следствие F₁ и F₂.

В качестве второго примера докажем нелогичность рассуждения о первокурсниках. Мы записали это рассуждение в виде последовательности формул Н₁,Н₂, и Н₃. Для доказательства нелогичности рассуждения надо найти интерпретацию j, при которой формулы Н₁ и Н₂ истинны, а формула Н₃ ложна. Пусть множество М состоит из трех элементов 2,3,4. Символы С, Л и П проинтерпретируем следующим образом:

(jС)(х)=«х – простое число»,

(jЛ)(х)=«х – четное число»,

(jП)(х)=’’х>4»,

т.е. П интерпретируется как тождественно ложный предикат. Тогда формулы Н₁ и Н₂ истинны, поскольку посылки импликаций этих формул ложны при любом х. А формула Н₃ ложна. Чтобы убедиться в этом достаточно взять х=2. Следовательно, рассуждение о первокурсниках нелогично.

Определение. Множество формул

K={F₁(x₁,…,x_l),…,F_m(x₁,…,x_l)}

называется выполнимым, если существует интерпретация j с областью М и элементы a₁,…,a_lÎM такие, что все высказывания (jF₁)(a₁,…,a_l),…,(jF_m)(a₁,…,a_l) истинны.

Множество формул K = { F₁=("x)($y)(P(y)&Q(x,y)), F₂=("y)Q(c,y), F₃=ØP(c) } выполнимо. Возьмем в качестве области интерпретации множество натуральных чисел N. Символы P,Q и C проинтерпретируем следующим образом:

(jP)(u)=«u – простое число»,

(jQ)(u,v)=«u меньше или равно v»,

(j(C)=1.

Тогда высказывание jF₁ означает, что для любого натурального числа х найдется простое число y, которое не меньше х, высказывание jF₂ означает, что 1 –наименьшее натуральное число, а высказывание jF₃ означает, что 1 – непростое число. Ясно, что все эти высказывания истинны, и поэтому множество формул K выполнимо.

Понятия логического следствия и выполнимости в логике первого порядка связаны точно так же, как и в логике высказываний.

Теорема 3.2. Формула G(x₁,…,x_n) является логическим следствием формул F₁(x₁,…,x_n),…,F_k(x₁,…,x_n) тогда и только тогда, когда множество формул {F₁(x₁,…,x_n),…,F_k(x₁,…,x_n),ØG(x₁,…,x_n)} невыполнимо.

Доказательство теоремы 3.2 аналогично доказательству теоремы 1.2 и поэтому не приводится.