1105140230

11

ROZDZIALI. RACHUNEK ZDAŃ

	Nazwa	Tautologia
1.	prawo podwójnej negacji	-'(-'P) <-> V
2.	prawo wyłączonego środka	~'(p A -ip)
3.	prawo braku trzeciej możliwości	p V ->p
4.	prawa de Morgana	->(p A 9) <-> (->p V -.g)
		-’(pVg) <-> (-p A ->g)

Prawa de Morgana pozwalają na wyrażenie alternatywy za pomocą koniunkcji oraz negacji: (p V q)    —«(—ip A ~>q). W podobny sposób możemy wyrazić koniunk-

cję za pomocą alternatywy oraz negacji. Kolejna porcja ważnych tautologii dotyczy własności implikacji i równoważności.

	Nazwa	Tautologia
1.	przechodniość implikacji	((p -> g) A (g ->■ r)) -*(p-łr)
2.	eliminacja implikacji	(p -> «) <-> (--p v g)
3.	eliminacje równoważności	(p +> g) o ((p -> g) A (g -> p))
		(p«!)«((pAg)v(^A -g))

Każda tautologia generuje nieskończenie wiele innych tautologii. Wynika to następującego twierdzenia:

Twierdzenie 1.1 (O podstawianiu) Załóżmy, że p(po, • • • ,Pn) jest tautologią oraz że ipo, .. .tp_n są dowolnymi zdaniami. Wtedy zdanie p(tpo,... ,ip_n) jest również tautologią.

Dowód tego twierdzenia pozostawiamy czytelnikowi.

Definicja 1.7 Mówimy, że zdania p, ip są równoważne, co zapisujemy p = tp, jeśli

\=(v++ V>)-

Zauważmy, że p = ip wtedy i tylko wtedy, gdy dla dowolnej waluacji 7r zachodzi równość 7r(p) = 7r(V0- W dalszych rozważaniach będziemy posługiwali się następującymi własnościami pojęcia równoważności zdań:

1.    <p=ip,

2.    jeśli p = -ip, to ip = p

3.    jeśli p = ip oraz 'ifj = rj, to <p = 77

4. p = T wtedy i tylko wtedy, gdy |= p,

5. p = _L wtedy i tylko wtedy, gdy |= ->p.

Pokażemy teraz, że zdania sprzeczne, jako zdania zawsze fałszywe, implikują dowolne inne zdania:

Twierdzenie 1.2 Załóżmy, że p jest zdaniem sprzecznym. Wtedy dla dowolnego zdania ip zdanie p —>■ jest tautologią.

Dowód. Niech 7r będzie dowolną waluacją. Wtedy

□

it{p —» ip) = (tt(p) =>- 7r(V’)) = (0 =>■ 7r(ip)) = 1