Лекция № 10

Тема: ТЕОРЕМА ПОЛНОТЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

Основные вопросы, рассматриваемые на лекции:

1. Лемма 1: |¾ _{S 1} A ^*

2. Доказатьельство леммы 1 индукцией по формулам

3. Теорема полноты исчисления высказываний

Краткое содержание лекционного материала

Предположим, что в состав формулы A входят только следующие пропозициональные переменные p ₁,…, p_n. Если дано некоторое распределение истинностных значений переменных p ₁,…, p_n, то примем следующее обозначение: , где i =1,…, n, и

Лемма 1. Имеет место следующее следствие системы S ₁:

|¾ _{S 1} A ^*. (1)

Доказательство индукцией по формулам.

Если A = p_i, i =1,…, n, то A ^*= p_i ^*, и (1) верно по определению следствия.

Пусть A =Ø B. Тогда по индуктивному предположению

|¾ _{S 1} B ^*. (2)

Возможны два случая: B =И и B =Л.

Если B =И, A =Л, то A ^*=Ø A =ØØ B, B =И, B ^*= B, (1) следует из (2) и (P ₄).

Если A ^*= A =Ø B, B =Л, B ^*=Ø B, то (1) есть (2).

Пусть A = B Þ C. Тогда по индуктивному предположению верно (2) и

|¾ _{S 1} C ^*. (3)

Возможны три случая: B =И и C =Л; B =Л; C =И.

Если B =И и C =Л, то A =Л, A ^*=Ø A =Ø(B Þ C), B ^*= B, C ^*=Ø C, (1) следует из (2) и (P ₈).

Если B =Л, то A =И, A ^*= A = B Þ C, B ^*=Ø B, (1) следует из (2) и (P ₅).

Если C =И, то A =И, A ^*= A = B Þ C, C ^*= C, (1) следует из (3) и (P ₁). ÿ

Теорема полноты. Если A – тавтология, то |¾ _{S 1} A.

Доказательство. Так как A – тавтология, то A ^*= A.

В силу леммы 2, |¾ _{S 1} A, |¾ _{S 1} A.

В силу теоремы 4, |¾ _{S 1} p_n Þ A, |¾ _{S 1}Ø p_n Þ A.

Отсюда и из (P ₆) следует, что |¾ _{S 1} A, и, аналогично получается, что |¾ _{S 1} A, …, |¾ _{S 1} A, |¾ _{S 1} A, |¾ _{S 1} A. ÿ