Temat13.pdf

13. DOWODZENIE V:

DOWODZENIE TAUTOLOGII

13.1. Cele i wprowadzenie

umięjętność dowodzenia tautologii

13.2. Tautologie i zdania logicznie prawdziwe

Temat 5 rozpoczęliśmy intuicyjnym rozróżnieniem zdań przygodnie prawdziwych od zdań logicznie

prawdziwych, tzn. prawdziwych ze względu na swą strukturę logiczną. Wskazaliśmy wówczas na

istnienie tautologii, tzn. schematów zdań logicznie prawdziwych i stosowaliśmy metodę

zerojedynkową, aby wykazać tautologiczność takich schematów.

W systemie dedukcji naturalnej SD możemy dowodzić zarówno tautologiczności schematów

zdaniowych, jak i logicznej prawdziwości zdań. W obydwu przypadkach dowód taki przybiera

charakterystyczną postać wyprowadzenia danego schematu zdaniowego lub zdania bez założeń

pierwotnych.

Schemat zdaniowy S jest tautologią (w systemie SD) zawsze i tylko wtedy, gdy istnieje

w systemie SD dowód, że S na podstawie pustego zbioru założeń pierwotnych, czyli gdy

∅ ⊢ S .

Zdanie p jest logicznie prawdziwe (w systemie SD) zawsze i tylko wtedy, gdy istnieje w

systemie SD dowód, że p na podstawie pustego zbioru założeń pierwotnych, czyli gdy

∅ ⊢ p .

13.3. Dowodzenie tautologii

Dowód 1: Dowiedź, że ~( p ∧ ~ p ) jest tautologią

Spróbujmy dowieść, że ~( p ∧ ~ p ) jest tautologią. Podejdziemy do dowodu dokładnie tak, jak do tej

pory, z wyjątkiem tego, że nie możemy wpisać żadnych założeń pierwotnych, gdyż ich nie ma.

Tautologię ~( p ∧ ~ p ) natomiast wpisać musimy na dole linii dowodowej. Musimy skonstruować

dowód stanowiący jej uzasadnienie. Przygotowujemy zatem nasz dowód:

1. ~( p ∧ ~ p )

Mimo porażającej oczy pustki, nasze postępowanie niczym się nie będzie różnić od dotychczasowego.

Dowody tautologii i prawd logicznych zawsze będą wymagały zastosowania reguł konstrukcyjnych. W

naszym wypadku narzuca się zastosowanie reguły ~Wpr. Musimy zatem skonstruować subderywację o

ściśle określonym założeniu dodatkowym:

13-1

Samouczek logiki zdań (wersja wstępna)

Wszelkie prawa zastrzeżone

Uwagi proszę kierować na adres:

Katarzyna.Paprzycka@swps.edu.pl

1. p ∧ ~ p Zał. (~Wpr)

3. ~W ∧Elim 1

5. ~S ∧Elim 1

6. ~( p ∧ ~ p )

~Wpr 2–4, 2–5

Założenie to jest pierwszym wierszem przeprowadzanego dowodu. Teraz naszym zadaniem jest

znalezienie zdań bezpośrednio sprzecznych, co w powyższym wypadku jest trywialne:

1. p ∧ ~ p

Zał. (~Wpr)

2. p

∧Elim 1

3. ~ p

∧Elim 1

4. ~( p ∧ ~ p )

~Wpr 1–2, 1–3

Dowód 2 – dla przerażonych dowodzeniem tautologii

Zdarza się niekiedy studentom przyzwyczajonym do dowodzenia, że pewne zdanie wynika logicznie z

innych, iż trudno im przezwyciężyć porażenie spowodowane wspomnianą już pustką wśród założeń

pierwotnych. Na takie kłopoty sugeruję przeprowadzenie następującego dowodu:

1. q ∧ s

Zał.

1. p → ( p ∨ r )

Ponieważ mamy wyprowadzić implikację, musimy zastosować regułę →Wpr. Po przygotowaniu

subderywacji:

1. q ∧ s

Zał.

2. p Zał. (→Wpr)

3. ~W ∧Elim 1

5. p ∨ r ∧Elim 1

6. p → ( p ∨ r )

~Wpr 2–4, 2–5

strategia dowodzenia narzuca się sama – aby otrzymać alternatywę p ∨ r mając dany jej pierwszy człon

wystarczy zastosować regułę ∨Wpr.

1. q ∧ s

Zał.

2. p Zał. (→Wpr)

3. p ∨ r ∨Wpr 2

4. p → ( p ∨ r ) →Wpr 2–3

Ten dowód jest bardzo prosty. Należy jednak zwrócić uwagę, że nie korzysta się w ogóle z

przesłanki 1. Istotnie schemat p → ( p ∨ r ) jest tautologią – można go wyprowadzić z pustego zbioru

przesłanek pierwotnych. Przeprowadź ten dowód (por. Rozwiązania ):

1. p → ( p ∨ r )

Katarzyna Paprzycka, Samouczek logiki zdań (wersja wstępna): Temat 13. Dowodzenie VII

13-2

Oczywiście istotne przebiegi obu dowodów są identyczne. W pierwszym wypadku wstawiliśmy

przesłankę „atrapę”, która służyła tylko uśmierzeniu palpitacji serca. Zawsze taką atrapę można sobie

postawić, pod warunkiem, że w przesłance tej nie występują żadne zmienne zdaniowe (ew. zdania)

występujące w tautologii (ew. zdaniu logicznie prawdziwym), którego mamy dowieść.

Ćwiczenie I.

Dowiedź, że następujące schematy zdaniowe są tautologiami:

(a) p → p

(b) ( ( p → q ) ∧ ( q → r ) ) → ( p → r )

prawo sylogizmu hipotetycznego

prawo mnożenia następników

(d) ( ( p → r ) ∧ ( p → ~ r ) ) → ~ p

prawo redukcji do absurdu

(e) ( p ∧ ( q → r ) ) → ( ( p ∧ q ) → r )

(f) ( p ∧ ( q → r ) ) → ( q → ( p ∧ r ) )

(g) ( p → ( q → r ) ) ≡ ( q → ( p → r ) )

(h) ( ( p ∨ q ) ∧ ( ( p → r ) ∧ ( q → s ) ) ) → ( r ∨ s )

prawo dylematu konstrukcyjnego

Dowód 3 – prawo wyłączonego środka

Nie wszystkie dowody tautologii są równie proste – w szczególności jeżeli nie korzysta się z reguł

wtórnych i reguł podstawiania. Jednym z trudniejszych dowodów – w oparciu o wspomniane

ograniczenia – jest dowód prostego wydawałoby się prawa wyłączonego środka (po lewej stronie

umieszczony jest opis strategii; po prawej stronie kolejne etapy konstruowania dowodu – aby lepiej

zrozumieć przebieg dowodu wpisz odpowiednie informacje w zaznaczone pola, a potem sprawdź czy

wpisane zostały poprawnie):

(A) Mamy wyprowadzić p ∨ ~ p . Narzuca się

zastosowanie reguły ∨Wpr, nie mamy jednak

żadnego członu, do którego można byłoby coś

dodać. Nie mamy też możliwości otrzymania

takiego członu. Sytuacja jest beznadziejna, a w

takiej sytuacji Babunia radzi „stosuj regułę

~Elim!”:

~( p ∨ ~ p )

Zał. (~Elim)

p ∨ ~ p

~( p ∨ ~ p )

p ∨ ~ p

(B) Zyskujemy teraz dodatkową informację, ale

musimy dążyć do wyprowadzenia jakiejś (choć

nie wiemy jakiej) sprzeczności. Ponieważ jednak

nie mamy specjalnego wyboru spróbujmy

wyprowadzić zdanie sprzeczne z tym właśnie

założeniem. Naszym celem pośrednim staje się

otrzymanie pary zdań:

p ∨ ~ p

~( p ∨ ~ p )

Drugie z tych zdań otrzymujemy przez

powtórzenie. Kłopot tylko z pierwszym.

1. ~( p ∨ ~ p )

Zał. (~Elim)

~( p ∨ ~ p )

p ∨ ~ p

~( p ∨ ~ p )

p ∨ ~ p

Katarzyna Paprzycka, Samouczek logiki zdań (wersja wstępna): Temat 13. Dowodzenie VII

13-3

p ∨ ~ p

schemat p ∨ ~ p . Jest to schemat alternatywy.

Dostępne są dwie strategie: (i) albo korzystamy z

reguły ∨Wpr, (ii) albo korzystamy z reguły

~Elim. Zwróćmy uwagę, że do drugiej strategii

już się uciekliśmy (por. (A)). Gdybyśmy to

uczynili ponownie wówczas bylibyśmy na dobrej

drodze do nieskończonego regresu subderywacji.

Spróbujmy zatem wykorzystać strategię (i) i

zastosować regułę ∨Wpr. Należy też zwrócić

uwagę, że obiekcja podniesiona wobec tej

strategii w punkcie wyjście (A) przestaje

obowiązywać. Teraz już bowiem dysponujemy

czymś, a mianowicie założeniem dodatkowym w

wierszu 1.

1. ~( p ∨ ~ p )

Zał. (~Elim)

~ p

p ∨ ~ p

~( p ∨ ~ p )

p ∨ ~ p

~( p ∨ ~ p )

p ∨ ~ p

(D) Aby zastosować regułę ∨Wpr do

wyprowadzenia p ∨ ~ p , musimy dysponować

jednym z jej członów. W tym momencie możemy

obrać za cel dowolny z nich – wybierzmy ~ p .

Naszym celem jest wyprowadzenie ~ p .

1. ~( p ∨ ~ p )

Zał. (~Elim)

~ p

p ∨ ~ p

~( p ∨ ~ p )

~ p

p ∨ ~ p

~( p ∨ ~ p )

p ∨ ~ p

(E) Aby wyprowadzić p , spróbujemy

zastosować regułę ~Wpr. Konstruujemy więc

subderywację, której założeniem dodatkowym

jest p . Musimy teraz wyprowadzić jakąś

bezpośrednią sprzeczność. Może to być albo:

~ p

albo

p ∨ ~ p

~( p ∨ ~ p )

1. ~( p ∨ ~ p )

Zał. (~Elim)

2. p

Zał. (~Wpr)

p ∨ ~ p

~( p ∨ ~ p )

~ p

~( p ∨ ~ p )

p ∨ ~ p

(F) Chwila refleksji wystarczy aby wybrać tę

drugą ewentualność:

p ∨ ~ p – otrzymamy przez zastosowanie reguły

∨Wpr

~( p ∨ ~ p ) – otrzymamy przez powtórzenie;

1. ~( p ∨ ~ p )

Zał. (~Elim)

2. p Zał. (~Wpr)

3. p ∨ ~ p ∨Wpr 2

4. ~( p ∨ ~ p ) R1

5. p ~Wpr 2–3, 2–4

6. p ∨ ~ p ∨Wpr 5

7. ~( p ∨ ~ p )

Reszta układa się w dowód.

8. p ∨ ~ p

~Elim 1–6, 1–7

Warto zwrócić uwagę, że dowód ten jest trudny, o ile przeprowadza się wyłącznie przy użyciu reguł

pierwotnych. Zastosowanie reguły de Morgana (deM) do schematu w wierszu 1 sprawia, że znacznie

się upraszcza. Por. Dowód 3 w Rozwiązaniach .

Ćwiczenie II.

Spróbuj dowieść (a) bez pomocy reguł podstawiania, (b) z pomocą tych reguł, że następujący

schemat zdaniowy jest tautologią: ( p → q ) ∨ ( q → p )

Katarzyna Paprzycka, Samouczek logiki zdań (wersja wstępna): Temat 13. Dowodzenie VII

13-4

p ∨ ~ p

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: