Konstrukcja i dyskusja systemu

Reguły postępowania podzielimy na 5 grup i grupy te oznaczać będziemy cyframi I - V.


  ⎧p, q, r, s, t,... są literami logicznymi;
I⎨jeśli E jest literą logiczną, E jest sądem;
  ⎩ jeśli E jest sądem, jeśli F jest sądem, | EF jest sądem.

Skrót Sąd
F FF
EF EF
EF ⎪∼EF
EF ∼⎪EF
EF ∧⊃EFFE

II jeśli E jest sądem, ⊃EE jest twierdzeniem.

Przy sformułowaniu dalszych reguł postępowania używać będziemy bardzo wygodnego sposobu pisania: "X, Y; Z" zamiast: "jeśli X jest twierdzeniem, jeśli Y jest twierdzeniem, Z jest twierdzeniem". Podobnie schemat: X, Y; A, B oznaczać będzie układ 2 reguł postępowania : 1) jeśli X jest twierdzeniem, jeśli Y jest twierdzeniem, A jest twierdzeniem; 2) jeśli X jest twierdzeniem, jeśli Y jest twierdzeniem, B jest twierdzeniem.

Analogiczne znaczenie nadawać będziemy schematom: X, Y, A, B, C; X, Y, Z; A, B, C; itd. Przy użyciu naszej symboliki reguły III, IV, V otrzymają kształt:

III ⊃EG, ⊃FF; ⊃∧EFG, ⊃∧FEG.



    ⎧⊃EF, ⊃EG, ⊃∼⎪EG
    ⎪⊃EF, ⊃EG, ⊃⎪EG
IV⎨
    ⎪⊃EF, ⊃EG, ⊃⎪EG
    ⎩⊃EF, ⊃EG, ⊃⎪EG

   ⎧⊃∧EFG, ⊃∧EFG, ⊃EG,
V⎨
   ⎩⊃EF, E; F.

Przechodzimy teraz do dyskusji przyjętych reguł postępowania- I-V z punktu widzenia ich znaczenia dla całości rachunku zdań.

Otóż reguły I łącznie z przyjętymi skrótami pozwalają natychmiast wnioskować:



   ⎧jeśli F jest sądem, ∼ F jest sądem;
   ⎪jeśli E jest sądem, jeśli F jest sądem,⊃ EF jest sądem;
I'⎨ jeśli E jest sądem, jeśli F jest sądem, ∨EF jest sądem;
   ⎪jeśli E jest sądem, jeśli F jest sądem, ∧ EF jest sądem;
   ⎩jeśli E jest sądem, jeśli F jest sądem, ≡ EF jest sądem.

Stosując I' otrzymujemy łatwo:
p jest sądem,
q jest sądem,
pq jest sądem,
pq jest sądem,
∧ ∼pq jest sądem,
∧ ∼ pq jest sądem itd.
Reguła II stanowi znaną zasadę identyczności. Przy jej pomocy otrzymujemy łatwo twierdzenia kształtu:

pp, ⊃ ∼pp, ⊃qq, ⊃rr, ⊃ ∼rr,

Dla wyjaśnienia dalszych reguł postępowania naszego systemu musimy wprowadzić dwa nowe pojęcia.

a) Iloczyn logiczny dowolnej liczby czynników nazwiemy iloczynem elementarnym, jeśli:
1) każdy jego czynnik jest literą logiczną lub jej zaprzeczeniem,
2) żadna litera nie występuje w nim więcej niż raz,
3) wszystkie znaki ∧ znajdują się w nim na początku.

Przykłady iloczynów elementarnych:

p, q, r, ∼p, ∼q, ∼r, ∧pq, ∧pq, ∧∼pq, ∧ ∼pq ∧∧pqr, ∧∧pqr, ∧∧pqr, ∧∧pqr,

b) Niech będzie dany dowolny sąd P. Powiemy, że iloczyn elementarny ⎪ jest iloczynem właściwym sądu P jeśli każda litera logiczna zachodząca w ⎪, zachodzi także w P i na odwrót. Sąd zawierający n liter logicznych posiada zawsze 2n istotnie różnych iloczynów właściwych, jeżeli nie uważamy za różne iloczynów różniących się jedynie porządkiem czynników, np. :

∧ ∧ pqr, ∧ ∧ ∼qrp, ∧ ∧ ∼rpq,...

W zastosowaniach praktycznych wypisujemy litery logiczne w pewnym ustalonym porządku i stosujemy ten sam porządek przy budowie iloczynów właściwych danego sądu. Tak np. iloczynami właściwymi sądu ≡∨ pqr∨ ∨ pqr są iloczyny:

∧∧pqr, ∧∧pqr, ∧∧pqr, ∧∧pqr, ∧∧∼pqr, ∧∧∼pqr, ∧∧∼pqr,∧∧∼pqr

Iloczyny powyższe są ścisłym odpowiednikiem różnych "sposobów tabliczkowania" danego sądu. W ten sposób 8 kombinacjom znaków +, -, które nadajemy literom p,q,r odpowiadają iloczyny właściwe według tabelki:

p q r iloczyn właściwy
+ + + ∧∧pqr
+ + - ∧∧pqr
+ - + ∧∧pqr
+ - - ∧∧pqr
- + + ∧∧∼pqr
- + - ∧∧∼pqr
- - + ∧∧∼pqr
- - - ∧∧∼pqr

Zauważmy teraz, że warunkiem koniecznym i dostatecznym na to, aby dany sąd P był twierdzeniem rachunku zdań jest, aby zachodziło twierdzenie ⊃ ⎪P, gdzie I oznacza dowolny iloczyn właściwy sądu P. Jeżeli sąd Q tej własności nie spełnia, to znajdziemy zawsze iloczyn właściwy I sądu Q, dla którego zachodzić będzie twierdzenie ⊃ IQ. Otóż reguły III i IV pozwalają nam rozstrzygnąć, czy przy danym P oraz I zachodzi ⊃ IP, czy też ⊃ IP. W końcu przy pomocy reguł V potrafimy udowodnić P, jeśli tylko stwierdzimy poprzednio ⊃ IP dla każdego iloczynu właściwego sądu P.

Przechodzimy do szczegółowej dyskusji naszych reguł. Rozpoczynamy od twierdzeń kształtu ⊃IA, gdzie I oznacza dowolny iloczyn elementarny, A zaś jeden z jego czynników. Metoda uzyskiwania takich twierdzeń jest najzupełniej elementarna i opiera się na stosowaniu reguł III Dlatego też ograniczę się tutaj do podania jednego przykładu: ⊃ ∧ ∧pqrq.

Stosując I i II dowodzimy najpierw twierdzeń:

pp, ⊃ ∼qq, ⊃ ∼rr,

i na mocy reguł III uzyskujemy kolejno ⊃∧pqq, ⊃ ∧ ∧pqrq.

Tą samą drogą otrzymamy ⊃ ∧ ∧pqrp, ⊃ ∧ ∧pqrr. Niech teraz P oznacza dowolny sąd, a I jego iloczyn właściwy. Zobaczymy, że reguły IV pozwolą nam zawsze udowodnić jeden i tylko jeden z dwóch sądów: ⊃ IP, ⊃ I∼P. Ponieważ w zastosowaniach praktycznych sąd P zawiera zwykle różne funktory logiczne, których definicje podaliśmy w tabeli skrótów, wyprowadzamy najpierw przy pomocy reguł IV kilka pomocniczych reguł postępowania :



     ⎧⊃EF; ⊃E∼∼F.
     ⎪⊃EF,⊃EG;⊃EFG, ⊃EFG, ⊃EFG, ⊃EFG.
IV'⎨ ⊃EF,⊃EG;⊃E∼⊃FG, ⊃EFG, ⊃E∼∧FG, ⊃E∼≡FG.
     ⎪⊃EF,⊃EG;⊃EFG, ⊃EFG, ⊃E∼∧FG, ⊃E∼≡FG.
     ⎩⊃EF,⊃EG;⊃EFG, ⊃E∼∨FG, ⊃E∼∧FG, ⊃EFG.

Dowody powyższych reguł są zupełnie elementarne. Dla przykładu jeden z nich przeprowadzimy dokładnie: ⊃EF, ⊃EG; ⊃EFG.

Reguła ta po usunięciu skrótu ∨FG przybiera kształt:
EF, ⊃E∼G ⊃E⎪ ⎪FFGG.

Przypuszczamy, że zachodzą twierdzenia ⊃EF, ⊃EG i podstawiamy w IV F za F, F G. Otrzymamy
EF, ⊃EF, ⊃∼ ⎪FF

Mamy zatem twierdzenia: ⊃E∼ ⎪FF, ⊃EGG

Podstawiając w IV ⎪FF za F,⎪GG za G, otrzymamy ⊃E∼ ⎪FF, ⊃EGG, ⊃E⎪⎪FFGG. a więc zachodzi ⊃E⎪⎪FFGG. czyli ⊃EFG.

Wszystkie reguły IV' wyprowadzamy w analogiczny sposób.

Metoda dowodu jednego ze sądów ⊃ I P, ⊃ I ∼P jest dla wszelkich P oraz I ta sama i dlatego ograniczymy się znów do pokazania jej na jednym przykładzie. Niech zatem P oznacza sąd ≡∨pqr∨ ∨pqr, a I iloczyn właściwy tego sądu ∧ ∧∼pqr. Na mocy reguł III udowodnimy :⊃ Ip, ⊃ Ip, ⊃ Ir. Podstawiając w IV I za E, q za F, r za G. otrzymamy

Iq,⊃ Ir; ⊃ Iqr, a więc ⊃ Iqr

Podstawiamy teraz w IV' I za E, p za F, ∨qr za G,

Otrzymamy ⊃ ;Ip, ⊃ ⎪∨qr; ⊃ ⎪∨pqr, a więc ⎪∨pqr

W ten sam sposób dowodzimy kolejno: ⊃Ipq, ⊃I∨∨pqr, ⊃ I≡ ∨pqr∨ ∨pqr Stosując to samo postępowanie do każdego iloczynu właściwego sądu P, otrzymamy układ twierdzeń (U):


⊃∧ ∧pqrP (1)
⊃∧ ∧pq;∼rP (2)
⊃∧ ∧p;∼qrP (3)
⊃∧ ∧p;∼q;∼rP (4)
⊃∧ ∧ ;∼pqrP (5)
⊃∧ ∧ ;∼pq;∼rP (6)
⊃∧ ∧ ;∼p;∼qrP (7)
⊃∧ ∧ ;∼p;∼q;∼rP (8)

Z reguł V wyprowadzamy łatwo regułę pomocniczą V': ⊃∼FG, ⊃∼FG; G.

Załóżmy bowiem, że zachodzą twierdzenia: ⊃FG, ⊃∼FG. Na mocy IIl otrzymamy : ⊃∧ ⊃ pp FG, ⊃∧ ⊃pp∼FG, a stąd ze względu na V: ⊃ ⊃ppG i w końcu G, gdyż sąd ⊃pp jest twierdzeniem.

Korzystając z reguł V, V' oraz z twierdzeń (U) udowodnimy teraz, że sąd P jest twierdzeniem.

Podstawiamy w V ∧pq za E, r za F, P za G: ⊃ ∧ ∧pqrP, ⊃ ∧ ∧pqrP, ∧pqP

Na mocy (1) I (2) mamy zatem

pqP (1')

Korzystając z dalszych twierdzeń (3) - (8) dowodzimy kolejno: ⊃p;∼qP (2')

⊃ ;∼pqP (3')

⊃ ;∼p;∼qP (4')

To samo rozumowanie pozwala nam

pP (na postawie(1'), (2')),

⊃∼pP (na postawie(3'), (4')).

Jeśli skorzystamy teraz reguły V' otrzymamy twierdzenie P czyli ≡ ∨pqr∨ ∨pqr

Konstrukcja ogólnej metody rozstrzygania dowolnych sądów naszego systemu jest zarazem dowodem jego zupełności. Widzimy, że dowód taki jest zupełnie elementarny i nie jest nam wcale potrzebna redukcja danego sądu do postaci kanonicznej Hilberta. Dowód nasz streszczamy w kilku zdaniach.

Niech dany będzie dowolny sąd P naszego systemu zawierający n liter logicznych. Tworzymy iloczyny właściwe I1, I2... I2n tego sądu. Zachodzą teraz dwie możliwości.

Stosując reguły I - IV udowodnimy twierdzenia ⊃ Ik P dla k = 1, 2,... 2n i na mocy reguł V uzyskamy twierdzenie P. Dla jednego z iloczynów właściwych otrzymamy twierdzenie ⊃ IiP, a wówczas sąd P jest fałszywy przy "sposobie tabliczkowania" odpowiadającym iloczynowi Ii .

Dowód niesprzeczności naszego systemu uzyskujemy metodą Hilberta. Kształt naszych reguł pozwala bowiem stwierdzić, że wszystkie nasze reguły postępowania nie wyprowadzają nas z klasy sądów prawdziwych w sensie tabliczki Sheffera. Z drugiej strony sąd kształtu ∧PP me czyni zadość powyższemu warunkowi, nie może być zatem twierdzeniem naszego systemu.