lec10

Пусть A – высказывание. Обозначим:

fA – утверждение „A – ложно“, tA – утверждение „A – истинно“.

Здесь fA и tA (или f(A) и t(A)) называются помеченными формулами.

Вершинами семантической таблицы называются все помеченные формулы, встречающиеся в этой таблице.

Семантическая таблица – это дерево, вершинами которого является исследуемая формула и все ее подформулы.

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

Логическая связка – представление элементарных БФ: , , , , ↔ в исчислении высказываний. Каждой логической связке, выполняемой в соответствующей вершине для данной подформулы, сопоставляется

элементарная семантическая таблица в виде дерева, раскрывающего

логическую интерпретацию связки.	11

Элементарные семантические таблицы.

t(A)

f(A)

t(A B)

f(A B)

t(A)

f(A)

f(B)

t( A)

f( A)

t(B)

операция

f(A)

t(A)

операция

t(A B)

f(A B)

t(A)

t(B)

f(A)

операция

f(B)

t(A B)

f(A) t(B)

f(A B) t(A) f(B)

операция

12

Семантическая таблица для операции ↔

t(A ↔ B)

f(A) t(A)

f(B) t(B)

X ↔ Y = (A B) (B A)

t(A ↔ B)

f(B ↔ A)

t(A B)

f(A B)

f(B A)

t(B A)

t(A)

t(B)

f(A)

t(B)

f(B)

f(A)

t(B A)

t(B A)

f(A)

f(A)

t(B)

t(B)

f(B)

t(A)

f(B)

t(A)

13

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

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

Семантическая таблица называется замкнутой, если каждая

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

ееветви противоречивы.

14

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

Алгоритм построения семантической таблицы:

Шаг 1: Поместить помеченную формулу tK (или fK) в корень таблицы Далее по индукции …

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

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

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

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

15

Пример. 10.2. Доказательство по Бету закона Пирса.

t(((А→B)→A)→A) f((А→B)→A) t(A)

t(А→B)

f(А)

f(А) t(B)

Итог: Противоречивых ветвей нет для корня

.t., все ветви дерева .f. противоречивы. Значит закон Пирса – тавтология.

f(((А→B)→A)→A) t((А→B)→A)

f(A)

f(А→B) t(A) t(A) f(B)

16

Доказательство (вывод по Бету) высказывания K –

противоречивая семантическая таблица, в корне которой помещена fK.

Опровержение по Бету высказывания K – замкнутая противоречивая семантическая таблица, имеющая в качестве корня tK.

Высказывание K доказуемо по Бету, если существует доказательство K по Бету.

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

ⱶB K – K доказуемо по Бету

ⱶB (((А→ B)→ A)→ A)

17

Пример. 10.3. Доказательство по Бету высказывания K.

K = (А A) (B (C D))

					Определим условие истинности K:
t[(А A) (B (C D))]					Высказывание K истинно при
					некотором истинном означивании V.
t(А A)		t(B (C D))
					V1: B = t; A,C,D	t
t(А)		t(B)	t(C D)
						f
t( А)		V1
			t(C)		V : C = t; D = t; A,B t
					2	f
f(А)
			t(D)
			V2

18

Часть 3.

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

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

Аксиомы и правило заключения выводит высказывание σ из последовательности высказываний σ1, σ2,… σn.

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

A1: ϕ→(τ→ϕ)

A2: (ϕ→(τ→σ))→((ϕ→τ)→(ϕ→σ))

A3: ( ϕ→ τ)→(τ→ϕ)

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

20