Материал: Методичка Дзержинский

Определение:

Вершина семантической таблицы называется особой, если она встречается как корень в некоторой атомарной семантической таблице.

Иначе – вершина называется обычной.

Определение:

Ветвь семантической таблицы называется противоречивой, если для некоторого высказывания а помеченные вершины ta и fa содержатся в данной ветви.

Определение:

Семантическая таблица называется замкнутой, если каждая ее непротиворечивая ветвь не содержит обычных вершин.

Семантическую таблицу называют противоречивой, если все ее ветви противоречивы.

Индуктивное определение семантической таблицы

Построим семантическую таблицу высказывания следующим образом:

Шаг 1 Поместить помеченную формулу tk ( fk ) в корень таблицы

Далее по индукции.

Шаг n. Пусть построена семантическая таблица Tn

Шаг n+1. Расширить таблицу Tn до Тn+1 ,при этом использовать некоторую вершину таблицы Tn ,которая в дальнейшем использоваться не будет. Из всех обычных вершин Tn , ближайших к корню ,выбрать самую левую, и обозначить ее за х . К концу каждой непротиворечивой ветви присоединить атомарную таблицу, имеющую корнем х.

При этом х становится особой вершиной . В результате получается таблица Tn+1 .

Построение заканчивается ,когда все непротиворечивые ветви не содержат обычных вершин.

Пример: Закон Пирса

(((А→ B)→ A)→ A) ƒ(((А→ B)→ A)→ A)

|

26

ƒ((А→ B)→ A)

|

ƒ(A)

|

t(А) or ƒ(A→B)

| |

t(А)

|

ƒ(B)

|

Вывод: закон Пирса - тавтология. t(((А→ B)→ A)→ A)

|

ƒ((А→ B)→ A) or tA

|

t(А→ B)

|

t( А)

|

ƒА

|

ƒА or tB

Противоречивых ветвей нет. Значит закон Пирса-тавтология.

Определение:

Доказательством или выводом по Бету высказывания k называется противоречивая семантическая таблица ,в корне которой помещена ƒk.

Определение:

Замкнутая противоречивая семантическая таблица, имеющая в качестве корня tk. Называется опровержением по Бету высказывания k .

Определение:

Говорят ,что высказывание доказуемо по Бету ,если существует доказательство по Бету.

Обозначение:

27

| b K K доказуемо по Бету

| b (((А→ B)→ A)→ A)

Пример 1:

K=(А ʌ А)ᴠ(B v (C ʌ D))

Определим условие истинности K.

t((А ʌ А)ᴠ(B v(C ʌ D)))

Высказывание k истинно при истинном означивании V.

V1 (B)=t, V2(C)=t, V2(D)=t.

V1(А)=tǁƒ

V1(C)=tǁƒ

V1(B)=tǁƒ

Аксиоматическая система вывода

Логика высказываний ,подобно другим математическим системам может быть представлена как аксиоматическая система с логическими аксиомами и правилами вывода. Аксиомы – это некоторые тавтологии ,правило вывода R выводит высказывание σ из последовательности высказываний σ1, σ2,… σn

Определение: каждое высказывание следующего вида является аксиомой

1.ϕ→(τ→ϕ)

2.(ϕ→(τ→σ))→((ϕ→τ)→(ϕ→σ))

28

3.(ɿϕ→ɿτ)→(τ→ϕ)

Высказывания ϕ, τ, σ могут быть произвольными. Все эти аксиомы являются тавтологиями.

Определение: Правило вывода Modus Ponens(Правило заключения) утверждает, что высказывания τ выводится из высказываний ϕ и ϕ→τ

ϕ

ϕ,ϕ→τ | τ

ϕ и ϕ→τ называются гипотезами, а τ -заключением

Новые высказывания получаются при помощи этих трех аксиом и “правила заключения” !

Пример: как можно применить аксиомы и правило вывода для вывода формулы логики высказывания

A→A

Сначала возьмем первую аксиому и вместо ϕ ставим А; вместо τ = B→A получим А→((В→А)→А)

Вторую аксиому запишем ,заменив в ней ϕ на А , τ на (В→А) ;

σ на А (А→((В→А)→А))→((А→(В→А))→(А→А))

из этих двух высказываний по правилу вывода получаем

(А→(В→А))→(А→А)

Используя вновь первую аксиому в виде

А→(В→А) по правилу вывода выводим высказывание А→А.

Следовательно высказывание А→А выводимо в нашей аксиоматической системе.

Следующая теорема позволяет производить в высказываниях замену одних подформул на другие, логически им эквивалентные .

Теорема (о подстановке эквивалентных формул)

Пусть высказывание σ↔ σ1 выводимо в логике высказываний , σ – подформул высказывания ϕ, и высказывание ϕ1 получено в результате подстановки в высказывание ϕ вместо некоторых вхождений формулы σ эквивалентной ей формулы σ1. Тогда высказывание ϕ↔ϕ1 , также выводимо в

29

логике высказываний. Формально это записывается так : | σ↔ σ1 <=> | ϕ↔ ϕ1

Дадим формальное определение доказательства высказывания аксиоматическим методом .

Пусть S – множество высказываний.

Доказательством или выводом из S называется такая конечная последовательность высказываний σ1,σ2,….., σn , что для каждого I 1 ≤ I ≤ n верно:

а) σi принадлежит S или б) σi – аксиома или

в) σi получено из σj и σk где 1 ≤ j, k≤ j

по правилу заключения

Высказывание σ называется: доказуемым или выводимым из множества высказываний S, если существует такое доказательство σ1, σ2,… σn из S,что σn совпадает с σ. Для обозначения выводимости высказывания σ из множества высказывания S будем использовать запись S | σ .

Высказывание σ называется доказуемым или выводимым ,если | σ ,то есть σ выводимо в аксиоматической системе при помощи правила заключения из аксиом.

Отметим ,что если S пустое множество ,то понятия выводимого из множества S высказывания совпадает с понятием выводимого высказывания

.Заметим что если σ выводимо из бесконечного множества S ,то σ выводимо из некоторого конечного подмножества ,так как доказательство всегда конечно . Следующая Теорема является основной в теории доказательств

Теорема дедукции .

Пусть S - множество высказываний .

K, L – высказывания .Тогда S ᴜ { k } | L <=> S | (K→L)

На эту теорему мы в дальнейшем будем часто ссылаться . Отметим , что :Если высказывания σ и (σ→τ) доказуемы по Бету то σ и (σ→τ) логически истинны ,следовательно , τ также логически истинно и доказуемо по Бету . Каждая тавтология может быть доказана из аксиом последовательным применением правила заключения. Наши аксиомы будучи логическими истинными высказываниями , доказуемомы по Бету. Используя правило вывода мы из логически истинных высказываний получаем также логически истинные

30