SYSTEM ZALOZENIOWY RACHUNKU ZDAN - jest to kolejna, po matrycowej, metoda przeprowadzania rachunku zdan, polegajaca na dowodzeniu tautologicznosci schematu, wylacznie poprzez ustalone reguly (dyrektywy) dowodzenia (wnioskowania). Tych reguł jest ich co prawda mnostwo, aczkolwiek podam Ci je w na tyle przystepny sposob, ze po niewielkim uplywie czasu zapewne beda one Twoje: 1. REGULA ODRYWANIA - jesli do dowodu naleza dwie rzeczy : pierwsza - implikacja i druga - jej poprzednik, wystepujacy samodzielnie, to wolno nam oderwac ten poprzednik z implikacji, pozostawiajac jedynie sam nastepnik . UWAGA ! Nastepnik to nasza prawa koperta (nastepuje po lewej), poprzednik to nasza lewa koperta (poprzedza prawa). Nazwy te wystepuja tylko i wylacznie, jesli glownym spojnikiem jest implikacja.   PAMIETAJ ! Przyklad zastosowania RO (reguly odrywania):  A teraz to samo na literach : p   q (w lewej kopercie mamy “p”, w prawej zas “q”) p (samodzielny poprzednik tej implikacji - “p”) q (zastosowana RO, dzieki niej otrzymano “q”) [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]} (inna implikacja) [r   ~ (q   ~ p)] (samodzielny poprzednik innej implikacji) {~ p   [r   ~ (q V p)]} (efekt zastosowania RO) I W GORE I ------------------------------------------------------------------------------------------------------------ 2. REGULA DOLACZANIA KONIUNKCJI - gdy do dowodu naleza dwie rozne rzeczy, mozna tworzyc z nich koniunkcje.  Przyklad zastosowania DK (reguly dolaczania koniunkcji):  To samo na literach : p (pierwsza rzecz) q (druga rzecz) p   q DK [r   ~ (q   ~ p)] (pierwsza rzecz) {~ p   [r   ~ (q V p)]} (druga rzecz) [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]} DK I W GORE I ------------------------------------------------------------------------------------------------------------ 3. REGULA OPUSZCZANIA KONIUNKCJI - jesli do dowodu nalezy koniunkcja, to mozemy rozszczepic ja na dwa oddzielne skladniki.  Przyklad zastosowania OK (reguly opuszczania koniunkcji): Teraz na literach : p   q (koniunkcja) p OK q OK [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]} (koniunkcja) [r   ~ (q  ~ p)] OK {~ p   [r   ~ (q V p)]} OK UWAGA ! Czasem pojawia sie w zadaniach koniunkcja skladajaca sie z wiecej niz dwoch czesci, np. p   q   r . Regula opuszczania takiej koniunkcji jest analogiczna do sposobu postepowania z koniunkcja dwuskladnikowa i otrzymuje sie w ten sposob : p , q , r . PAMIETAJ ! I W GORE I ------------------------------------------------------------------------------------------------------------ 4. REGULA DOLACZANIA ALTERNATYWY - do dowodu wolno dolaczyc alternatywe, o ile ktorys z jej czlonow juz nalezal do tego dowodu. Przyklad zastosowania DA (reguly dolaczania alternatywy):  Teraz na literach : p (rzecz nalezaca juz do dowodu) p V q DA [r   ~ (q   ~ p)] (rzecz nalezaca juz do dowodu)  [r   ~ (q   ~ p)] V {~ p   [r   ~ (q V p)]} DA I W GORE I ------------------------------------------------------------------------------------------------------------ 5. REGULA OPUSZCZANIA ALTERNATYWY - jesli do dowodu naleza dwie rzeczy : pierwsza - alternatywa i druga - negacja jednego z jej czlonow, to mozemy w nast. wierszu wpisac drugi jej czlon. 6 mozliwych przykladow zastosowania OA (reguly opuszczenia alternatywy) :  Wariant I Teraz na literach : p V q (alternatywa) ~ p (negacja pierwszego jej czlonu) q OA [r   ~ (q   ~ p)] V {~ p   [r   ~ (q V p)]} (alternatywa)  ~ [r   ~ (q   ~ p)] (negacja pierwszego jej czlonu) {~ p   [r   ~ (q V p)]} OA Wariant II Teraz na literach : p V q (alternatywa) ~ q (negacja drugiego jej czlonu) p OA [r   ~ (q   ~ p)] V {~ p   [r   ~ (q V p)]} (alternatywa) ~{~ p   [r   ~ (q V p)]} (negacja drugiego jej czlonu) [r   ~ (q   ~ p)] OA Wariant III Teraz na literach : (~ p ) V q (alternatywa) p (przeciwienstwo pierwszego jej czlonu) q OA ~ [r   ~ (q   ~ p)] V {~ p   [r   ~ (q V p)]}  [r   ~ (q  ~ p)] {~ p   [r   ~ (q V p)]} OA Wariant IV Teraz na literach : p V (~ q) (alternatywa) q (przeciwienstwo drugiego jej czlonu) p OA [r   ~ (q   ~ p)] V ~ {~ p   [r   ~ (q V p)]}  {~ p   [r   ~ (q V p)]} [r   ~ (q   ~ p)] OA  Wariant V Teraz na literach : (~ p ) V ( ~q ) (alternatywa) p (przeciwienstwo pierwszego jej czlonu) ~q OA ~ [r   ~ (q   ~ p)] V ~ {~ p   [r   ~ (q V p)]}  [r   ~ (q  ~ p)] ~ {~ p   [r   ~ (q V p)]} OA Wariant VI Teraz na literach : (~ p ) V ( ~q ) (alternatywa) q (przeciwienstwo pierwszego jej czlonu) ~p OA ~ [r   ~ (q   ~ p)] V ~ {~ p   [r   ~ (q V p)]}  {~ p   [r   ~ (q V p)]}  ~ [r   ~ (q   ~ p)] OA  I W GORE I ------------------------------------------------------------------------------------------------------------ 6. REGULA DOLACZANIA ROWNOWAZNOSCI - do dowodu mozemy dolaczyc rownowaznosc, jesli naleza do dwie implikacje, rozniace sie od siebie tylko tym, ze ich czesci skladowe sa zamienione miejscami.  Przyklad zastosowania DR (reguly dolaczania rownowaznosci) :  Dla wprawy przesledzmy przebieg tego dzialania na literach : p   q (pierwsza implikacja) q   p (druga implikacja) p   q DR [r   ~ (q  ~ p)]   {~ p   [r   ~ (q V p)]}  {~ p   [r   ~ (q V p)]}   [r   ~ (q   ~ p)] [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]} DR  I W GORE I ------------------------------------------------------------------------------------------------------------ 7. REGULA OPUSZCZANIA ROWNOWAZNOSCI - (odwrotnosc reguly DR), jesli do dowodu nalezy rownowaznosc, to mozna ja rozlozyc na dwie implikacje.  Przyklad zastosowania OR (reguly opuszczania rownowaznosci) : I przebieg tego dzialania na literach : p   q (rownowaznosc) p   q OR (pierwsza implikacja) q   p OR (druga implikacja) [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]}  [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]} OR  {~ p   [r   ~ (q V p)]}   [r   ~ (q   ~ p)] OR I W GORE I ------------------------------------------------------------------------------------------------------------ 8. REGULA OPUSZCZANIA NEGACJI - jesli w dowodzie mamy podwojna negacje pewnego elementu tego dowodu, wolno nam w kolejnym wierszu wpisac ten element juz bez obu znakow negacji (nie zmieni to jego wartosci logicznej). Przyklad zastosowania ON (reguly opuszczania negacji):  Na literach wyglada to tak : ~ ~ p p ON ~ ~ [r   ~ (q   ~ p)] [r   ~ (q   ~ p)] ON I W GORE I ------------------------------------------------------------------------------------------------------------ 9. REGULA DODAWANIA NEGACJI - jesli w dowodzie mamy pewien element, wolno nam w kolejnym wierszu wpisac ten element z podwojnym znakiem negacji. Przyklad zastosowania DN (reguly dolaczania negacji) :    Na literach wyglada to tak : p ~ ~ p DN [r   ~ (q   ~ p)] ~ ~ [r   ~ (q   ~ p)] DN I W GORE I ------------------------------------------------------------------------------------------------------------ 10. REGULA MODUS TOLLENS - jesli do dowodu naleza dwie rzeczy : pierwsza - implikacja i druga - negacja jej nastepnika, wystepujaca samodzielnie, to wolno nam oderwac ten zanegowany nastepnik z implikacji, pozostawiajac jedynie sama negacje poprzednika. Dwa mozliwe przyklady zastosowania MT (reguly modus tollens):  WARIANT I Na literach : p   q (implikacja) ~ q (negacja nastepnika) ~ p MT [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]} ~ {~ p   [r   ~ (q V p)]}  ~ [r   ~ (q   ~ p)] MT WARIANT II  Na literach : p   (~ q) (implikacja) q (negacja nastepnika) ~ p MT [r   ~ (q   ~ p)]   {~ p   [r   ~ (q V p)]} {~ p   [r   ~ (q V p)]}  ~ [r   ~ (q   ~ p)] MT I W GORE I ------------------------------------------------------------------------------------------------------------ 11. REGULA NEGOWANIA KONIUNKCJI - zanegowana koniunkcja dwoch elementow, wystepujaca w dowodzie, moze zostac zastapiona alternatywa negacji obu tych elementow.  Przyklad zastosowania NK (reguly negowania koniunkcji):  Literki w akcji : ~ ( p   q ) (zanegowana koniunkcja)  ~ p V ~ q NK ~ {[r   ~ (q   ~ p)]   [r   ~ (q V p)]} { ~ [r   ~ (q   ~ p)]} V { ~ [r   ~ (q V p)]} NK I W GORE I ------------------------------------------------------------------------------------------------------------ 12. REGULA NEGOWANIA ALTERNATYWY - zanegowana alternatywa dwoch elementow, wystepujaca w dowodzie, moze zostac zastapiona koniunkcja negacji obu tych elementow.  Przyklad zastosowania NA (reguly negowania alternatywy):  Literki w akcji : ~ ( p V q ) (zanegowana alternatywa)  ~ p   ~ q NA ~ {[r   ~ (q   ~ p)] V [r ~ (q V p)]} { ~ [r   ~ (q   ~ p)]}   { ~ [r   ~ (q V p)]} NA I W GORE I ------------------------------------------------------------------------------------------------------------ 13. REGULA NEGOWANIA IMPLIKACJI - zanegowana implikacja dwoch elementow, wystepujaca w dowodzie, moze byc zastapiona koniunkcja niezmienionego pierwszego i negacji drugiego elementu.  Przyklad zastosowania NI (reguly negowania implikacji):  Literki w akcji : ~ ( p   q ) (zanegowana implikacja)  p   ( ~ q ) NI ~ {[r   ~ (q   ~ p)]   [r   ~ (q V p)]} [r   ~ (q   ~ p)]   { ~ [r   ~ (q V p)]} NI I W GORE I ------------------------------------------------------------------------------------------------------------ 14. REGULA NEGOWANIA ROWNOWAZNOSCI - zanegowana rownowaznosc dwoch elementow nalezaca do dowodu zostaje zastapiona : w pierwszym przypadku rownowaznoscia zanegowanego pierwszego elementu i niezmienionego drugiego elementu lub tez w drugim wariancie rownowaznoscia niezmienionego pierwszego elementu i negacji drugiego . Przyklad zastosowania NR (reguly negowania rownowaznosci): WARIANT I No i na literach to wyglada tak : ~ ( p   q ) (zanegowana rownowaznosc)  ~ p   q NR ~ {[r   ~ (q   ~ p)]   [r   ~ (q V p)]} ~ [r   ~ (q   ~ p)]   [r   ~ (q V p)] NR WARIANT II Na literach to tak : ~ ( p   q ) (zanegowana rownowaznosc)  p   ~ q NR ~ {[r   ~ (q   ~ p)]   [r   ~ (q V p)]} [r   ~ (q   ~ p)]   ~ [r   ~ (q V p)] NR I W GORE I

a) DOWOD ZALOZENIOWY “WPROST” I Pierwsze cwiczenie w rozdziale nr 5 I

Budujac zalozeniowy dowod wprost schematu o postaci: W₁ 
 { W₂ 
 [ W₃ 
 ... 
 ( W_n 
 W ) ] } wypisujemy najpierwzalozenia : W₁ , W₂ , W₃ , ... , W_n , potem zas przeksztalcenia dokonywane na podstawie poznanych wczesniej regul dowodzenia w systemie zalozeniowym. Dowod jest zakonczony, gdy ostatecznie otrzymamy to wyrazenie “W”.

Od razu przyklad:

(p 
r) 
[ (r 
q) 
( p 
q ) ] 






Mamy wiec schemat : “(p 
 r) 
 [ (r 
 q) 
 ( p 
 q ) ]”, i naszym zadaniem jest sprawdzenie czy jest on tautologia. Chcac uczynic to wczesniej podstawialismy zmudnie do niego kombinacje zerojedynkowe i oczekiwalismy, ze da nam to za kazdym razem wartosc calego schematu “1”. Tym razem jednak zrobimy to krotka i prosta metoda <<dowodu wprost>> :


- jak wyczytalismy to w powyzszej definicji, musimy zaczac od wypisania zalozen, czego poprawne wykonanie jest polowa naszego sukcesu:

1. p   r 2. r   q 3. p

zal. zal. zal.

Widzisz, ze mamy teraz trzy zalozenia : I - jest nim ZAWSZE wszystko to, co wystepuje przed glowna implikacja calego schematu (wyrazenie : “p  r”, u nas znajdujace sie w lewej kopercie, a w definicji figurujace jako “W1”). II - jest nim ZAWSZE wszystko to, co wystepuje przed glowna implikacja nastepnika calego schematu (wyrazenie : “r   q”, u nas to znaczek poczty lotniczej, znajdujacy sie na prawej kopercie, a w definicji figurujace jako “W2”). III - jest nim ZAWSZE wszystko to, co wystepuje przed ostatnia implikacja, jaka mamy w schemacie (wyrazenie : “p”, u nas to pole adresowe prawej wielkiej koperty , a w definicji figurujace jako “Wn”). - kolejny krok to dokonanie stosownych przeksztalcen na podstawie znanych regul:

4. r 5. q

RO : 1,3  RO : 2,4

UWAGA ! Trzeba koniecznie zapisywac ktore wiersze biora udzial w danej regule i tak np. w naszej RO uzytej w wierszu 4 braly udzial : wiersz 1 i 3 . PAMIETAJ! W wierszu czwartym zastosowalismy znana nam reg. odrywania, uzywajac do tego celu rzeczy z wiersza pierwszego i trzeciego: 1. p   r  ... 3. p 4. r W wierszu piatym zastosowalismy takze RO: 2. r   q  ... 4. r 5. q - tak oto dostalismy, co chcielismy: nasz piaty wiersz jest zgodny z rzecza, ktora mielismy osiagnac, czyli ZAWSZE tym, co znajduje sie po ostatnim znaku implikacji wystepujacym w calym schemacie (wyrazenie : “q”, u nas jest to znaczek przyklejony na prawej wielkiej kopercie, a w definicji figurujace jako “W”). - pozostaje teraz jedynie napisac odpowiedz, ze badany schemat jest tautologia. Zapis calego dzialania wyglada nastepujaco : (p   r)  [(r  q)   (p   q)]

1. p   r	zal.
2. r   q	zal.
3. p	zal.
4. r	RO : 1,3
5. q Odp. Ten schemat jest tautologia.	RO : 2,4

b) DOWOD ZALOZENIOWY “NIEWPROST”  Budujac zalozeniowy dowod niewprost schematu o postaci: W1  { W2   [ W3   ...  ( Wn   W ) ] } wypisujemy najpierw zalozenia: W1 , W2 , W3 , ... , Wn , nastepnie negacje wyrazenia W, potem zas przeksztalcenia dokonywane na podstawie poznanych wczesniej regul dowodzenia w systemie zalozeniowym. Dowod jest zakonczony, gdy wystapia w nim jakiekolwiek dwa sprzeczne ze soba wyrazenia ( jedno musi byc negacja drugiego ). Maly przykladzik “na goraco”:  (p  r)  [ (r  q)  ( p  q ) ] Oto schemat : “(p   r)   [ (r   q)   ( p   q ) ]”. Teraz sprawdzimy czy jest on tautologia, uzywajac do tego celu jeszcze prostszego sposobu, niz “metoda wprost - <<dowodu niewprost>>: - zaczynamy znow od wypisania zalozen:

1. p   r 2. r   q 3. p

zal. zal. zal.

Sa w tym przypadku trzy zalozenia:  I - jest nim ZAWSZE wszystko to, co wystepuje przed glowna implikacja calego schematu (wyrazenie : “p  r”, u nas znajdujace sie w lewej kopercie, a w definicji figurujace jako “W1”). II - jest nim ZAWSZE wszystko to, co wystepuje przed glowna implikacja nastepnika calego schematu (wyrazenie : “r   q”, u nas to znaczek poczty lotniczej, znajdujacy sie na prawej kopercie, a w definicji figurujace jako “W2”). III - jest nim ZAWSZE wszystko to, co wystepuje przed ostatnia implikacja, jaka mamy w schemacie (wyrazenie : “p”, u nas to pole adresowe prawej wielkiej koperty , a w definicji figurujace jako “Wn”). - teraz musimy dodac tzw. “zalozenie dowodu niewprost”, ktore to ZAWSZE jest NEGACJA tego wyrazenia, ktore znajduje sie po ostatnim znaku implikacji wystepujacym w calym schemacie (wyrazenie : “q”, u nas jest to znaczek przyklejony na prawej wielkiej kopercie, a w definicji figurujace jako “W”). Cala sprawa wyglada tak :

4. ~ q	z.d.n. (UWAGA!“z.d.n.”trzeba tutaj pisac PAMIETAJ!)
- dalszy krok - przeksztalcenia na podstawie regul:
5. r 6. ~ r	RO : 1,3  MT : 2,4
Wiersz nr 6 wzial sie stad:  2. r   q ... 4. ~ q  ... 6. ~ r

- i naszym oczom ukazala sie upragniona sprzecznosc : wyrazenie w wierszu piatym jest sprzeczne z wyrazeniem z wiersza szostego, co pozwala nam udzielic odpowiedzi, iz schemat jest tautologia. UWAGA! Nie musimy wcale szukac negacji wyrazenia, ktore wystepuje po ostatniej implikacji - “znaczka”, by uzyskac sprzecznosc, a tym samym udowodnic tautologicznosc schematu. Wystarczy, jak ma to miejsce w podanym tu przykladzie, ze znajdziemy jakakolwiek sprzecznosc. PAMIETAJ!.  Zapis calego dzialania wyglada nastepujaco: (p   r)   [(r   q)   (p   q)]
1. p   r	zal.
2. r   q	zal.
3. p	zal.
4. ~ q	z.d.n.
5. r	RO : 1,3
6. ~ r Odp. Sprzecznosc:5,6 - schemat jest tautologia.	MT : 2,4
UWAGA ! Dowodzenie tautologicznosci schematu, ktorego glownym spojnikiem nie jest implikacja najlepiej robic metoda “NIEWPROST”. Oto kolejne kroki tej procedury w przypadku takiego rodzaju schematu (glownym spojnikiem jest tu alternatywa): ( p  q ) v ( q  p )  (calosc traktujemy sobie jako swoisty nastepnik nieistniejacej w istocie implikacji) - ZAWSZE zaczynamy wiec od “zalozenia dowodu niewprost” - zanegowania calego schematu (u nas jest to cala koperta), gdyz nigdy nie wypisuje sie zwyklych zalozen (taki panuje tu konwenans):
1. ~ [( p   q ) V ( q   p )]	z.d.n.
- przeksztalcenia, zgodne ze znanymi regulami:
2. ~ ( p   q )   ~ ( q   p )	NA : 1
3.~ ( p   q )	OK : 2
4. ~ ( q   p )	OK : 2
5. p   ~ q	NI : 3
6. q   ~ p	NI : 4
7. p	OK : 5
8. ~ q	OK : 5
9. q	OK : 6
10. ~ p	OK : 6
- pokazala sie "jakakolwiek" sprzecznosc (wiersze: 8,9 , a nawet dodatkowo wiersze : 7,10 , choc wystarczylaby zupelnie jedna, ale “od przybytku sprzecznosci glowa nie boli”), co sklania nas do odpowiedzi, iz badany schemat jest tautologia. PAMIETAJ ! Zapis calego dzialania wyglada nastepujaco : ( p   q ) V ( q   p )

1. ~ [( p   q ) V ( q   p )]	z.d.n.
2. ~ ( p   q )   ~ ( q   p )	NA : 1
3.~ ( p   q )	OK : 2
4. ~ ( q   p )	OK : 2
5. p   ~ q	NI : 3
6. q   ~ p	NI : 4
7. p	OK : 5
8. ~ q	OK : 5
9. q	OK : 6
10. ~ p  Odp. Sprzecznosc: 8,9 - schemat jest tautologia.	OK : 6

---