ИПОВС - 6 семестр / Пособие / G1

будет частным случаем , а ( ) ( ) – частным случаем ( ) ( ) Так как уже доказано, то по modus ponens получим: , а отсюда .

Докажем теперь невыводимость секвенции | p p (закона исключённого третьего) в интуиционистской логике формально. Рассмотрим трёхзначное множество значений истинности 3 {0,1,1/ 2} в котором 0 интерпретируется как ложь, 1 – как истина, 1/ 2 – как

неопределённость. Определим логические	операции				на	3 следующим образом:
x y min(x, y), x y max(x, y), 1 1/ 2 0, 0 1,						1, если		x y,
					x y		если	x y.
Понятия оценки и интерпретации на 3						y,
	вводятся по аналогии с						. Назовем секвен-
цию | истинной при оценке , если maxB			(B)		(A),	и тождественно истинной в

трёхзначной логике, если она истинна при всех оценках. Можно проверить, что все правила НД, кроме RAA, корректны на 3 (то есть из тождественно истинных в 3 посылок получаются тождественно истинные заключения). Кроме того, аксиомы тождественно ис-

тинны. Значит, все выводимые в ИИВ формулы тождественно истинны в				3. Однако,
формула p p тождественно истинной не			является, так как при	( p) 1/ 2
		( p p) 1/ 2 1/ 2 1/ 2 1. Значит, формула	p p невыводима в ИИВ.

Замечание. Существуют тождественно истинные в трёхзначной логике, но невыводимые в ИИВ формулы. Например, p p, ( p q) ( p q). Более того, никакой конечный набор значений истинности не полон для ИИВ.

1.8.1.Задачи для самостоятельного решения

1.Доказать выводимость в ИИВ формулы ( ).

2.Доказать невыводимость в ИИВ формул:

a.p p;

b.( q p) ( p q);

c.( p q) ( p q);

d.p p.

25