![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Тема: ТЕОРЕМА ПОЛНОТЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
Основные вопросы, рассматриваемые на лекции:
1. Лемма 1: |¾ S 1 A *
2. Доказатьельство леммы 1 индукцией по формулам
3. Теорема полноты исчисления высказываний
Краткое содержание лекционного материала
Предположим, что в состав формулы A входят только следующие пропозициональные переменные p 1,…, pn. Если дано некоторое распределение истинностных значений переменных p 1,…, pn, то примем следующее обозначение: , где i =1,…, n, и
Лемма 1. Имеет место следующее следствие системы S 1:
|¾ S 1 A *. (1)
Доказательство индукцией по формулам.
Если A = pi, i =1,…, n, то A *= pi *, и (1) верно по определению следствия.
Пусть A =Ø B. Тогда по индуктивному предположению
|¾ S 1 B *. (2)
Возможны два случая: B =И и B =Л.
Если B =И, A =Л, то A *=Ø A =ØØ B, B =И, B *= B, (1) следует из (2) и (P 4).
Если 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 8).
Если B =Л, то A =И, A *= A = B Þ C, B *=Ø B, (1) следует из (2) и (P 5).
Если C =И, то A =И, A *= A = B Þ C, C *= C, (1) следует из (3) и (P 1). ÿ
Теорема полноты. Если A – тавтология, то |¾ S 1 A.
Доказательство. Так как A – тавтология, то A *= A.
В силу леммы 2, |¾ S 1 A,
|¾ S 1 A.
В силу теоремы 4, |¾ S 1 pn Þ A,
|¾ S 1Ø pn Þ A.
Отсюда и из (P 6) следует, что |¾ S 1 A, и, аналогично получается, что
|¾ S 1 A, …,
|¾ S 1 A,
|¾ S 1 A, |¾ S 1 A. ÿ
Дата публикования: 2015-03-26; Прочитано: 154 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!