1. KLASYCZNA LOGIKA ZDAC

1.0. ZAA
OŻENIA KLASYCZNEGO RACHUNKU
ZDAC

Rozważymy teraz problem rachunku dla logiki zdań20 . Logika
zdań jest logiką języka, którego najprostsze, wewnętrznie nieanali-
zowalne elementy to zdania i w którym z tych zdań  określanych
jako proste lub atomowe  i ze specjalnych wyrażeń zwanych spój-
nikami oraz znaków interpunkcyjnych, którymi są nawiasy, konstru-
owane są wszystkie pozostałe wyrażenia poprawnie zbudowane tego
języka  zdania złożone. W języku zdaniowym wszystkie elementy
znaczeniowe wiążące te zdania ze sobą są więc wyrażalne przez spój-
niki zdaniowe. Takim językiem nie jest ani język naturalny, ani żaden
z języków różnych systemów wiedzy. W takim sensie język logiki zdań
jest fikcyjny. Zasady logiki zdań stosują się jednak do wszystkich ję-
zyków o tyle, o ile abstrahujemy od wewnętrznej złożoności ich zdań
prostych. Rozważanie logiki zdań jest użyteczne zarówno teoretycznie
jak i dydaktycznie. Rachunek dla logiki zdań jest bowiem fragmen-
tem bogatszego rachunku dla logiki języka, w którym wyróżnia się
elementy składowe zdań  będzie to rachunek predykatów. Klasyczna
20
Rachunek zdań jest powszechnie uważany za polską specjalność. J. Woleński
[1985] podaje następującą anegdotę. Gdy A. Tarski spotkał się po raz pierwszy z
E. Postem (było to zapewne w roku 1939 lub 1940) sugerował mu, że jest jedynym
logikiem, który uzyskał ważne wyniki w rachunku zdań, a nie ma nic wspólnego
z Polską. Na to Post miał rzec:  O nie, urodziłem się w Białymstoku, a to jest
miasto we wschodniej Polsce. (zob. s. 84) W życiorysie E. Posta podaje się, że
urodził się w Augustowie.
22 1. KLASYCZNA LOGIKA ZDAC

logika zdań to logika języka, którego wszystkie spójniki są prawdzi-
wościowe i ponad to przyjmuje się dwie wartości logiczne: prawdę i
fałsz.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAW-
DZIWE
Określimy teraz czysto formalnie język rachunku zdań. Podamy
więc alfabet tego języka i reguły konstrukcji wyrażeń poprawnie zbu-
dowanych: zdań.
Zdania budujemy, aby mówić o pewnej rzeczywistości, o jakimś
świecie. W logice matematycznej takim �światem jest abstrakcyjny
konstrukt: model. Będzie on tak zbudowany, aby ujmował interesu-
jące nas aspekty odnoszenia zdań do świata. Ściśle określony �świat,
model, umożliwi definicję prawdziwości zdania (w modelu). Pojęcie
prawdziwości zdania jest pojęciem semantycznym. Naszym celem jest
wskazanie czysto syntaktycznych własności owych zdań, a więc tych
własności ich kształtu, budowy, które są charakterystyczne dla zdań
prawdziwych we wszystkich modelach. Wyróżnimy pewną klasę zdań,
które będziemy określali jako tautologie. Pojęcie tautologii będzie
więc pojęciem syntaktycznym. Ustalimy związek pomiędzy byciem
tautologią a byciem zdaniem prawdziwym we wszystkich modelach.
1.1.1. Pojęcie spójnika
W każdym języku istnieją różne sposoby tworzenia zdań ze zdań.
Służyć temu celowi mogą różne wyrażenia (w gramatyce nazywane
spójnikami i partykułami), zestawienie zdań (połączenie zdań skła-
dowych wraz z użyciem  w języku mówionym  stosownej intonacji
 a w języku pisanym  odpowiedniej interpunkcji).
Spójnik to każde i tylko takie wyrażenie, które łącznie ze zdaniem
bądz
zdaniami tworzy zdanie.
PRZYKA
ADY
Spójnikami są np.:  nieprawda, że. . .  ,  konieczne jest, że . . . 
oraz  . . . lub . . .  i  . . . oraz . . .  . Spójnikiem nie jest:  . . . jest .
�
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 23
Zdania, z których dany spójnik tworzy zdanie to argumenty tego
spójnika. Spójniki dzieli się ze względu na ilość ich argumentów. Wy-
różniamy więc spójniki jednoargumentowe, dwuargumentowe itd.
Zdania, które otrzymujemy w wyniku dopisania zdania lub zdań
do spójnika to zdania złożone. Zdania proste to zdania, które nie są
złożone, czyli w których nie występują spójniki.
PRZYKA
ADY
Zdaniami prostymi są:
2+2=4.
Trójkąt ma trzy boki.
Zdaniami złożonymi są:
Nieprawda, że 2+2=4.
Jeżeli czworokąt ma cztery boki równe, to ma dwa kąty równe.
�
1.1.2. Alfabet języka klasycznej logiki zdań
Alfabet A języka klasycznej logiki zdań jest zbiorem następują-
cych przedmiotów (symboli):
(I) p0, p1, . . .,
(II) Ź,
(III) �!, (", '", �!,
(IV) ), (.
Zbiór wszystkich skończonych ciągów elementów A to A". Ele-
menty A" to słowa nad alfabetem A.
p0, p1, . . . to litery zdaniowe. Intuicyjnie reprezentują one zdania
proste, czyli zdania, w których nie występują spójniki. Stąd też nazy-
wane są atomami. Dopuszczamy by zdań tych było tyle, ile jest liczb
naturalnych, czyli przeliczalnie nieskończenie wiele. W teoretycznych
rozważaniach przyjmujemy, że litery zdaniowe są niezłożonymi zna-
kami. Zwykle jako liter zdaniowych używać będziemy liter: p, q, r, . . ..
Ź jest spójnikiem jednoargumentowym. Nazywamy go negacją21 .
21
A
acińskie nego znaczy: przeczę.
24 1. KLASYCZNA LOGIKA ZDAC

Spójniki: �!, (", '", �! są dwuargumentowe. Nazywamy je, odpo-
wiednio: implikacją22 ,alternatywą, koniunkcją i równoważnością. W
wypadku implikacji jej pierwszy argument nazywamy poprzednikiem
a drugi następnikiem.
Nawiasy: )  nawias prawy, (  nawias lewy, pełnią funkcję znaków
interpunkcyjnych. Znaki te w naszym języku logiki zdań są niezbędne
dla jednoznacznego zapisu wyrażeń tego języka. Zwykle dla wygody 
w tym celu, aby napis był bardziej czytelny  stosuje się też nawiasy
innych kształtów: ], [; }, {.
1.1.3. Definicja zdania (wyrażenia poprawnie zbudowa-
nego logiki zdań)
1.1.3.1. Zdanie w notacji standardowej
Z elementów powyżej opisanego słownika (alfabetu) budujemy
zdania. Zdania są jedynymi poprawnie zbudowanymi wyrażeniami
języka logiki zdań.
DEFINICJA ZDANIA
Niech ą i � będą dowolnymi skończonymi ciągami symboli alfa-
betu języka logiki zdań, czyli ą i � są elementami A" (ą, � "A").
(I) litery zdaniowe są zdaniami;
(II) jeżeli ą jest zdaniem, to Źą jest zdaniem;
(III) jeżeli ą, � są zdaniami, to (ą �! �), (ą (" �), (ą '" �), (ą �! �) są
zdaniami;
(IV) nie ma innych zdań oprócz liter zdaniowych oraz tych wyrażeń,
które są skończonymi ciągami symboli23 spełniającymi warunki
(II) i (III).
22
Spójnik ten określany jest również jako implikacja materialna dla odróż-
nienia od implikacji formalnej. Termin  implikacja formalna używany jest na
oznaczenie implikacji, której warunkiem koniecznym poprawności i sensowności
jest zachodzenie związku formalnego między poprzednikiem a następnikiem.
23
Pojęcia użyte w definicji zdania: ciągu, skończonego ciągu, najmniejszego
zbioru należą do teorii mnogości, tam też podane są ich definicje.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 25
Warunek (IV) można zastąpić warunkiem równoważnym:
(IV) zbiór zdań jest najmniejszym zbiorem skończonych ciągów
symboli spełniających warunki (I)  (III).
Zbiór wyrażeń poprawnie zbudowanych, w tym wypadku zdań,
jest podzbiorem A".
PRZYKA
ADY
Zdaniami są: p0, p4, p5, Źp0, (p5 (" p0), (Ź(p0 '" p5) (" p0).
Zdaniami nie są: (p0), Ź(p0)Ź(p5) (" (p0), Ź(p0p5) (" (p0), (p0 (" p1) '"
(p0 (" p1) '" (p0 (" p1) '" . . ..
�
Skończony ciąg ą elementów słownika jest zdaniem wtedy i tylko
wtedy, gdy łącznie spełnione są następujące warunki:
1. Pierwszym wyrazem ciągu ą jest litera zdaniowa, albo spójnik
negacji albo nawias lewy.
2. Po literze zdaniowej albo nie następuje nawias prawy, albo na-
stępuje nawias prawy albo następuje spójnik dwuargumentowy.
3. Po nawiasie lewym następuje litera zdaniowa, albo spójnik nega-
cji albo nawias lewy.
4. W ą występuje tyle samo spójników dwuargumentowych, co na-
wiasów lewych i co nawiasów prawych.
5. W każdym miejscu w ą, w którym znajduje się nawias lewy za-
czyna się odcinek ciągu taki, że liczba wystąpień nawiasów lewych
jest równa liczbie wystąpień nawiasów prawych, a w najkrótszym
tego rodzaju odcinku liczby te są równe liczbie wystąpień spój-
ników dwuargumentowych.
Podana charakterystyka daje podstawę dla automatyzacji spraw-
dzania, czy dany ciąg ą jest zdaniem.
PRZYKA
ADY
Ciąg
((p0 �! p1) '" p2) �! ((p3 (" (p1 �!Źp2)))
26 1. KLASYCZNA LOGIKA ZDAC

nie spełnia warunku 5. Zauważmy bowiem, że w odcinku zaczynają-
cym się lewym nawiasem występującym bezpośrednio po równoważ-
ności, dla którego zachodzą założenia warunku 5, czyli
((p3 (" (p1 �!Źp2)))
nawias lewy i nawias prawy występują po trzy razy, zaś spójniki dwu-
argumentowe występują tylko dwa razy.
Zdaniem jest
(((p0 �! p1) '" p2) �! (p3 (" (p1 �!Źp2))).
�
Język rachunku zdań jest przykładem języka formalnego. Zbiór
wszystkich wyrażeń poprawnie zbudowanych języka formalnego zo-
staje ustalony decyzją twórcy tego języka. Zazwyczaj podaje się:
(I) zbiór symboli (alfabet, słownik)
(II) zbiór reguł konstrukcji.
Znajomość interpretacji, czyli przyporządkowania znaczeń wyra-
żeniom, jest zbyteczna dla określenia zbioru wyrażeń poprawnie zbu-
dowanych. Język formalny, taki jak język rachunku zdań, mogłaby w
pełni przyswoić sobie maszyna, np. komputer.
Język formalny jest zwykle tak opisany, że dane wyrażenie po-
prawnie zbudowane tego języka może być zbudowane, w sensie pro-
cesu konstrukcji, w jeden i tylko jeden sposób24 . Tak jest w wypadku
wyżej opisanego języka logiki zdań.
PRZYKA
ADY
Niech wyrażeniem poprawnie zbudowanym będzie każdy skoń-
czony ciąg symboli: ", f& rozpoczynający się od symbolu: ". Taki
język jest językiem formalnym.
Niech wyrażeniem poprawnie zbudowanym będzie każdy sen-
sowny ciąg elementów słownika języka polskiego. W tym wypadku o
poprawności budowy przesądzają reguły semantyczne. Tak określony
język nie jest więc językiem formalnym25 .
�
24
Dział syntaktyki zajmujący się problemem konstrukcji wyrażeń to tektonika.
25
Gdyby udało się sformalizować język polski, to istniałaby możliwość kompu-
terowego sprawdzania poprawności wyrażeń.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 27
Wyrażenia poprawnie zbudowane  w wypadku języka rachunku
zdań  zdania, są przedmiotami abstrakcyjnymi. Reprezentantem wy-
rażenia poprawnie zbudowanego jest konkretny napis (lub dz
więk).
Dwa napisy (dz
więki) mogą być reprezentantami tego samego wyraże-
nia. Istnienie wyrażenia nie jest uwarunkowane aktualnym istnieniem
konkretnych napisów (dz
więków), ani naszymi możliwościami zapisu.
Pozwala to mówić zarówno o wyrażeniach, których zapis przekracza
fizyczne możliwości człowieka jak i o językach mających nieskończe-
nie wiele wyrażeń. Mówimy tu o możliwości w takim samym sensie,
jak w arytmetyce liczb naturalnych, gdzie dysponujemy dziesięcioma
cyframi, gdy mówimy, że za ich pomocą, tworząc skończone ciągi mo-
żemy zapisać nazwę dowolnej liczby naturalnej.
Pisać będziemy mniej nawiasów niż wynikałoby to z definicji zda-
nia. Za zbędne uważamy nawiasy zewnętrzne, czyli zamiast: (ą) pi-
szemy: ą. Jeżeli spójnik dwuargumentowy s1 wiąże mocniej niż spój-
nik dwuargumentowy s2, to zamiast (ąs1�)s2ł piszemy ąs1�s2ł; po-
dobnie, zamiast ąs2(�s1ł) piszemy ąs2�s1ł. Przyjmujemy, że spośród
spójników dwuargumentowych najmocniej wiąże koniunkcja, następ-
nie alternatywa a po niej implikacja i równoważność.
Jeżeli spójniki s1 i s2 wiążą z jednakową mocą, to zamiast
ąs1(�s2ł) możemy pisać ąs1�s2ł. Jest to tak zwana zasada wiąza-
nia na lewo. Zwykle dla większej czytelności pozostawiamy więcej
nawiasów niż to wynikałoby z zasad opuszczania nawiasów. Ponadto,
można używać nawiasy innych kształtów: {, }; [, ]. Gdy wyrażenie
ą chcemy ująć w nawias, to piszemy: [ą], jeśli w ą występują: (, ).
Piszemy zaś {ą}, gdy w ą występują: [, ]. Nasze zasady używania i
opuszczania nawiasów nie różnią się w jakiś istotny sposób od zasad
znanych z arytmetyki szkolnej.
Na użytek definicji zdania przyjęliśmy umowę, że litery greckie
 ą ,  � , . . ., ewentualnie z indeksami, oznaczają dowolny ciąg sym-
boli. Teraz odstępujemy od tej umowy. Liter greckich  ą ,  � , . . .
będziemy używać  jeżeli nie powiemy inaczej  tylko na oznaczenie
zdań.
Zauważmy, że litery  ą ,  � , . . . nie są zdaniami, lecz nazwami
zdań. Podobnie jest w wypadku konstrukcji z tych liter i spójników.
28 1. KLASYCZNA LOGIKA ZDAC

 Źą jest nazwą zdania, które powstaje ze zdania ą poprzez napisa-
nie przed nim spójnika negacji.  ąs� jest nazwą zdania złożonego ze
zdania ą jako lewego argumentu i zdania � jako prawego argumentu
spójnika s. Wyrażenia  ą i  Źą należą do języka, którym mówimy,
a nie do języka, o którym mówimy, czyli należą do metajęzyka. Wyra-
żenia te nie są zdaniami metajęzyka. Są w nim nazwami zdań języka,
o którym mówimy (w metajęzyku).
Nazw języka naturalnego używamy na kilka sposóbów, w róż-
nych supozycjach26 . Na przykład nazwy  człowiek możemy użyć
do wskazania jakiegoś jednego określonego człowieka, gdy mówimy
 pod drzewem stał człowiek . Podobnie liter  ą ,  � , . . . możemy
użyć np. do wskazania zdań, o których była wcześniej mowa, wówczas
oznaczają one te właśnie zdania, odpowiednio,  ą ,  � , . . ..
Nazwy generalne mogą być użyte do wskazania każdego przed-
miotu, posiadającego cechy, które określa treść danej nazwy. Na przy-
kład nazwy  człowiek możemy użyć do wskazania człowieka i tylko
człowieka, np. gdy mówimy  człowiek ma prawa, które przysługują
mu z natury . Treść nazw  ą ,  � , . . . wyczerpuje się w tym, że mogą
być one użyte do wskazania zdań i tylko zdań (jeśli nie powiemy ina-
czej). Możemy ich użyć na oznaczenie dowolnych zdań. Na przykład
gdy mówimy:
w zdaniu
ą �! ą
poprzednik jest równokształtny z następnikiem,
to mamy na uwadze dowolne zdanie ą.
Tak użyte litery  ą ,  � , . . . są zmiennymi, których zakresem
zmienności jest zbiór zdań. Mówimy, że są to zmienne metaprzedmio-
towe.
Wyrażenia zbudowane wyłącznie z liter  ą ,  � , . . . oraz spójni-
ków i nawiasów mogą oznaczać każde zdanie, które można otrzymać
przez wpisanie w miejsce poszczególnych liter  ą ,  � , . . . jakichś
zdań. O wyrażeniach takich mówimy, że są to schematy zdaniowe.
26
Szerzej na ten temat zob. Trzęsicki [2000], s. 46 47.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 29
Język, którym mówi się o logice nie różni się istotnie od języka
naturalnego, w naszym wypadku polskiego. W zasadzie różnica ta
sprowadza się do tego, że jest tu wiele słów  są to terminy specy-
ficzne logiki  których na co dzień nie używamy. Język logiki jest
językiem uniwersalnym, w tym sensie, że nie zależy od języka naro-
dowego, którym się mówi o logice. Podobnie jak język arytmetyki jest
wspólny wszystkim, którzy mówią o arytmetyce, choć każdy mówi o
niej jakimś językiem narodowym.
(DEF. spójnika głównego) Spójnikami głównymi w zdaniach: Ź ą, ą
�! �, ą (" �, ą '" �, ą �! � są spójniki, odpowiednio: negacji, impli-
kacji, alternatywy, koniunkcji i równoważności. Zdania te skrótowo
określamy jako, odpowiednio: negację, implikację, alternatywę, ko-
niunkcję i równoważność.
1.1.3.2. Notacja łukasiewiczowska27
Z semiotycznego i informatycznego punktu widzenia  ze względu
na ekonomię środków wyrazu  interesujące jest pytanie o możliwość
języka bez znaków interpunkcyjnych, nawiasów. Otóż taką notację
wynalazł Jan A
ukasiewicz28 . Okazuje się, że w wypadku, gdy wszyst-
kie spójniki są prefiksami (czyli gdy pisane są przed swoimi argumen-
tami) lub gdy wszystkie spójniki są sufiksami (czyli gdy pisane są
po swoich argumentach) możliwe jest wyeliminowanie nawiasów. W
wypadku wyżej opisanego języka prefiksem jest spójnik negacji, zaś:
(", '", �!, �! są infiksami (czyli spójniki te pisane są między swoimi
argumentami)29 .
27
Notacja ta w literaturze anglojęzycznej zwykle określana jest jako polska.
28
A
ukasiewicz ([1931], s. 165) podaje, że zasady symboliki beznawiasowej opra-
cował w 1924 r. O pisaniu spójników przed argumentami mówił na początku lat
dwudziestych Chwistek. Jak pisze Woleński ([1985], s. 93) symbolika beznawia-
sowa to coś więcej niż samo pisanie spójników przed argumentami, stąd nie ma
konfliktu pomiędzy uznaniem, że twórcą symboliki beznawiasowej, zwanej także
polską, jest A
ukasiewicz i tym, że pomysł pisania spójników przed argumentami
pochodzi od Chwistka.
29
Przy okazji zauważmy również możliwość zastosowania znaków interpunk-
cyjnych o innym niż nawiasy kształcie i innych zasadach stosowania. W takiej
roli używa się na przykład kropek. Zob. Quine [1940]. Dominacja notacji nawia-
30 1. KLASYCZNA LOGIKA ZDAC

SA
OWNIK
(I) p0, p1, . . . litery zdaniowe
(II) N spójnik jednoargumentowy
(III) C, A, K, E spójniki dwuargumentowe
DEFINICJA ZDANIA (WYRAŻENIA POPRAWNIE ZBUDOWA-
NEGO LOGIKI ZDAC
)
Niech ą i � będą dowolnymi ciągami symboli.
(I) litery zdaniowe są zdaniami;
(II) jeżeli ą jest zdaniem, to Ną jest zdaniem;
(III) jeżeli ą, � są zdaniami, to Cą�, Aą�, Ką�, Eą� są zdaniami.
(IV) nie ma innych zdań oprócz liter zdaniowych oraz tych wyrażeń,
które można w skończonej ilości kroków skonstruować wedle
punktów (II) i (III).
Litery: N, C, A, K, E są spójnikami, odpowiednio: negacji,
implikacji, alternatywy, koniunkcji i równoważności. Wszystkie one
są prefiksami.
Zdaniu: (p0 (" p1) '" p0 odpowiada zdanie w notacji A
ukasiewicza:
KAp0p1p0 a zdaniu: p0 (" (p1 '" p0)  Ap0Kp1p0.
Daje się wskazać prostą metodę, która pozwala stwierdzić, czy
dany skończony ciąg symboli jest zdaniem w notacji A
ukasiewicza.
Niech ą będzie dowolnym skończonym ciągiem elementów słownika.
KRYTERIUM A

ą jest zdaniem wtedy i tylko wtedy, gdy spełnione są łącznie
wszystkie poniższe warunki:
(I) ostatnią literą ciągu jest litera zdaniowa,
(II) ilość symboli spójników C, A, K, E (nie liczymy symbolu N)
w ciągu ą jest o 1 mniejsza od liczby występujących symboli
liter zdaniowych,
sowej być może związana jest z przyzwyczajeniami, jakich nabywamy na lekcjach
matematyki w szkołach.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 31
(III) w każdym odcinku zaczynającym się od jednego z symboli C,
A, K, E (nie bierzemy pod uwagę symbolu N) ich ilość, li-
cząc do końca napisu, jest o co najmniej 1 mniejsza od liczby
występujących w tym odcinku symboli liter zdaniowych.
Kryterium A
daje podstawę dla prostego rachunku pozwalającego
obliczyć, czy dany napis ą jest zdaniem w notacji A
ukasiewicza.
Symbolowi N przyporządkowujemy liczbę 0, symbolomC, A, K,
E liczbę (-1), zaś symbolom liter zdaniowych liczbę 1.
(I) pod ostatnim symbolem skończonego ciągu ą piszemy liczbę
przyporządkowaną temu symbolowi,
(II) pod (k +1)-szym symbolem  licząc od końca napisu  podpi-
sujemy liczbę uzyskaną przez dodanie liczby przyporządkowanej
temu symbolowi do liczby podpisanej pod k-ty symbol napisu.
ą jest zdaniem w notacji A
ukasiewicza wtedy i tylko wtedy, gdy
w ciągu liczbowym utworzonym zgodnie z podanymi regułami
1. w żadnym miejscu nie pojawia się liczba mniejsza lub równa 0,
2. początkowym wyrazem ciągu jest liczba 1.
Pokażmy wpierw, że gdy ą jest zdaniem, to pod początkowym
symbolem ą podpisane jest 1. Zauważmy, że w wypadku, gdy ą zbu-
dowane jest tylko z jednej litery zdaniowej, to pod początkowym (i
jedynym) symbolem piszemy 1. Niech � i ł będą zdaniami i niech
pod początkowymi symbolami będzie podpisane 1. Pod początko-
wym symbolem N� będzie podpisane 1. Pod początkowym symbo-
lem ciągu ą� będzie podpisane 2. Zatem pisząc przed tym ciągiem
któryś ze spójników dwuargumentowych uzyskamy ciąg, pod którego
początkowym symbolem będzie podpisane 1.
Pokażemy teraz, że jeżeli pod początkowym symbolem ą jest pod-
pisane 1, to ą jest zdaniem. Jeżeli ą jest ciągiem jednowyrazowym,
to tym wyrazem może być tylko litera zdaniowa. Litera zdaniowa jest
zaś zdaniem. Załóżmy, że w wypadku wszystkich ciągów o długości
równej lub mniejszej niż k jest tak, że jeżeli pod ich pierwszymi wy-
razami jest pod pisane 1, to ciągi te są zdaniami. Niech ą jest ciągiem
o długości większej niż k. Jeżeli jest to ciąg mający więcej niż jeden
32 1. KLASYCZNA LOGIKA ZDAC

wyraz, to jego pierwszym wyrazem nie może być litera zdaniowa, bo-
wiem wówczas pod pierwszym wyrazem mogłaby być podpisana tylko
liczba większa niż 1. Jeżeli pierwszym wyrazem jest N, to pod przed-
ostatnim wyrazem musi być 1. Zgodnie z założeniem jest to zdanie.
Pisząc N przed zdaniem uzyskujemy zdanie. Niech teraz pierwszym
wyrazem będzie któryś ze spójników dwuargumentowych. Zatem pod
przedostatnim wyrazem musi być podpisane 2. We fragmencie ciągu
liczbowego poprzedzającym 2 musi wystąpić 1. Bierzemy fragment �
ciągu począwszy od wyrazu, pod którym jest podpisana pierwsza 1
poprzedzająca nasze 2 a skończywszy na ostatnim wyrazie ą. Zgod-
nie z założeniem � jest zdaniem. Fragment ł ciągu ą, pod którego
pierwszym wyrazem jest podpisane 2 do ostatniego wyrazu poprze-
dzającego 1 jest również zdaniem, bowiem przeprowadzając dla niego
opisaną wyżej procedurę pod jego pierwszym wyrazem uzyskamy 1.
Nasz spójnik dwuargumentowy łączy więc dwa ciągi ł i �, które są
zdaniami. Ciąg ą jest więc również zdaniem.
PRZYKA
AD
Napis:
CCCpCqpCCCNrCsNtCCrCsuCCtsCtuvCwv
jest zdaniem. Mamy bowiem:
CCCpCqpCCCNrCsNtCCrCsuCCtsCtuvCwv30
1 2 343432 3 4 5 54 54434 545434543432121
�
Na podstawie kryterium A
można skonstruować reguły  mecha-
nicznego przekładu zdań w notacji A
ukasiewicza na zdania w zwykłej
notacji. Mianowicie,
(I) gdy pierwszym symbolem napisu ą jest N, czyli gdy napis ma
postać N�, to piszemy: Ź �;
(II) gdy pierwszym symbolem napisu jest jeden z symboli C, A,
K, E, to jako lewy argument symbolu, odpowiednio: �!, (", '",
30
Zdanie to może być jedynym aksjomatem systemu aksjomatycznego ra-
chunku zdań z regułą odrywania (jeżeli ą i Cą�, to �) oraz reguła podstawiania
[jeżeli ą, to ą(pi/�), gdzie ą(pi/�) jest zdaniem uzyskanym ze zdania ą przez
jednoczesne wpisanie zdania � w miejsce każdego wystąpienia litery zdaniowej
pi, i " N.]. O systemach aksjomatycznych będzie mowa w dalszej części książki.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 33
�! bierzemy odcinek napisu ą począwszy od drugiego symbolu
taki, że ilość symboli C, A, K, E jest w tym odcinku dokładnie
o 1 mniejsza od liczby symboli liter zdaniowych; a jako prawy
argument bierzemy pozostały odcinek ciągu ą; uzyskany napis
umieszczamy w nawiasach;
(III) z odcinkami uzyskanego napisu zawierającymi tylko symbole
N, C, A, K, E (i symbole liter zdaniowych) postępujemy we-
dług reguł (I) i (II). Każdy najdłuższy taki napis zastępujemy
przez napis uzyskany przez zastosowanie tych reguł. Postępo-
wanie to kontynuujemy tak długo, aż dostaniemy napis nie za-
wierający symboli N, C, A, K, E.
PRZYKA
AD
Przetłumaczmy zdanie
CCCpCqpCCCNrCsNtCCrCsuCCtsCtuvCwv
1. (CCpCqpCCCNrCsNtCCrCsuCCtsCtuv �! Cwv)
2. ((CpCqp �! CCCNrCsNtCCrCsuCCtsCtuv) �! (w �! v))
3. (((p �! Cqp) �! (CCNrCsNtCCrCsuCCtsCtu �! v)) �! (w �!
v))
4. (((p �! (q �! p)) �! ((CNrCsNt �! CCrCsuCCtsCtu) �! v)) �!
(w �! v))
5. (((p �! (q �! p)) �! (((Nr �! CsNt) �! (CrCsu �! CCtsCtu)) �!
v)) �! (w �! v))
6. (((p �! (q �! p)) �! (((Ź r �! (s �!Ź t)) �! ((r �! Csu) �! (Cts �!
Ctu))) �! v)) �! (w �! v))
7. (((p �! (q �! p)) �! (((Ź r �! (s �!Ź t)) �! ((r �! (s �! u)) �! ((t �!
s) �! (t �! u)))) �! v)) �! (w �! v))
�
1.1.3.3. Indukcyjny charakter definicji zdania
Definicja zdania jest definicją indukcyjną. Najogólniej rzecz bio-
rąc ten sposób definiowania polega na wskazaniu pewnej klasy
(zbioru) przedmiotów (prostych). Może to być klasa skończona, np.
34 1. KLASYCZNA LOGIKA ZDAC

jednoelementowa, której jedynym elementem jest  | ; a może to być
również jakaś klasa nieskończona, np. jak ma to miejsce w wypadku
definicji zdania. Ponadto podane są reguły budowy obiektów złożo-
nych oraz może być wyróżniona pewna klasa przedmiotów, które jedy-
nie służą do �budowy obiektów złożonych. Przedmioty te same nie
należą do definiowanej klasy obiektów. W wypadku języka rachunku
zdań są nimi spójniki i nawiasy. Reguły budowy obiektów złożonych
są pewnego rodzaju przepisami określającymi, jaki dokładnie jeden
obiekt powstanie, gdy do budowy zostaną użyte określone obiekty.
Np. mając obiekt  | oraz operację konkatenacji, czyli operację do-
pisywania symbolu  | po prawej stronie danego obiektu, możemy
skonstruować obiekty: |, ||, |||, . . . . Czysto formalnie reguły konstruk-
cji obiektów złożonych można opisać  jak to uczyniliśmy definiując
zdanie  jako uporządkowane pary, których pierwszym członem są
pewne ciągi przedmiotów zaś drugim jakiś jeden obiekt. Istotnym
warunkiem jest to, żeby danemu ciągowi obiektów jako pierwszemu
elementowi pary przyporządkowany był co najwyżej jeden obiekt jako
drugi element pary.
Definicje indukcyjne pozwalają na drodze wnioskowania, okre-
ślanego jako wnioskowanie przez indukcję (matematyczną), dowodzić
własności obiektów spełniających warunki definicji. Liczby naturalne
możemy pojąć jako elementy zbioru wszystkich obiektów: |, ||, |||, . . ..
Na to, aby dowieść, że każda liczba naturalna ma jakąś własność W
wystarczy pokazać  jest to znany ze szkoły średniej schemat wnio-
skowania  że
(I) własność ta przysługuje obiektowi: |;
oraz
(II) jeżeli przysługuje obiektowi ą, to przysługuje obiektowi: ą|.
Podobnie, aby dowieść, że każde zdanie ma jakąś własność W
wystarczy pokazać, że
(I) każdej literze zdaniowej przysługuje własność W ; oraz
(II) jeżeli ą i � mają własność W , to Źą, ą �! �, ą (" �, ą '" �, ą �! �
mają własność W .
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 35
Mówimy tu o wnioskowaniu przez indukcję ze względu na dłu-
gość zdania. Wszelkich własności zdań będziemy dowodzić na drodze
wnioskowania indukcyjnego.
(DEF. dł(ą)) Długość zdania ą oznaczać będziemy dł(ą). Długość
zdania definiujemy indukcyjnie ze względu na jego budowę następu-
jąco. Niech ą i � będą zdaniami
(I) dł(ą) = 1, jeżeli ą jest literą zdaniową,
(II) dł(Źą) = 1+dł(ą),
(III) dł(ąs�) = 1+dł(ą) +dł(�), gdzie s jest spójnikiem
dwuargumentowym.
1.1.4. Model i prawdziwość
W modelu każde zdanie proste powinno być bądz
prawdziwe,
bądz
fałszywe. Interpretacja (określenie znaczeń zdań w modelu) po-
lega na przyporządkowaniu poszczególnym zdaniom prostym znacze-
nia jednego z terminów:  prawda ,  fałsz . Pomijając nieistotne de-
tale możemy model po prostu utożsamić z jakimś podzbiorem M
zbioru S liter zdaniowych. Jeżeli litera zdaniowa pn należy do pod-
zbioru M zbioru S, to będziemy przez to rozumieć, że pn jest praw-
dziwe w modelu M. Gdy pn nie należy do M, to będziemy przez to
rozumieć, że pn jest fałszywe w modelu M. Prawdziwość i fałszywość
zdań złożonych określa się zaś ze względu na prawdziwość i fałszywość
zdań składowych.
Zamiast mówić, że zdanie jest prawdziwe w modelu będziemy
też mówić, że jest spełnione w modelu. Do zapisania, że zdanie ą jest
prawdziwe w modelu M używać będziemy specjalnego oznaczenia:
M|= ą31 .
(DEF. M|= ą) NiechM będzie podzbiorem zbioru S liter zdaniowych
(Mą"S).32 ą jest prawdziwe (spełnione) w modelu M (M|= ą) wtedy
i tylko wtedy, gdy:
31
Symbol  |= w sensie, w jakim tu jest użyty, po raz pierwszy pojawia się w:
S. C. Kleene [1956].
32
A ą" B (A jest podzbiorem B) wtedy i tylko wtedy, gdy każdy element A
jest elementem B. W szczególności każdy zbiór jest swoim podzbiorem.
36 1. KLASYCZNA LOGIKA ZDAC

(I) jeżeli ą jest literą zdaniową, to
M|= ą
wtedy i tylko wtedy, gdy
ą " M;
(II) jeżeli ą jest zdaniem Ź �, to
M|= ą
wtedy i tylko wtedy, gdy
nie jest tak, że M|= �;
(III) jeżeli ą jest zdaniem � �! ł, to
M|= ą
wtedy i tylko wtedy, gdy
nie jest tak, że M|= � lub jest tak, że M|= ł;
(IV) jeżeli ą jest zdaniem � (" ł, to
M|= ą
wtedy i tylko wtedy, gdy
M|= � lub M|= ł;
(V) jeżeli ą jest zdaniem � '" ł, to
M|= ą
wtedy i tylko wtedy, gdy
M|= � i M|= ł;
(VI) jeżeli ą jest zdaniem � �! ł, to
M|= ą
wtedy i tylko wtedy, gdy
(M|= � wtedy i tylko wtedy M|= ł).
Użytych w definicji spójników fraz języka naturalnego:  nie jest
tak, że ,  lub ,  i ,  wtedy i tylko wtedy, gdy nie możemy zastąpić
symbolami: Ź, �!, (", '", �!. Gdybyśmy tak postąpili, to popełnilibyśmy
błąd w definiowniu zwany bezpośrednim błędnym kołem, idem per
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 37
idem. Powyższych warunków nie możemy więc zapisać �krócej np.
zamiast (VI) pisząc
jeżeli ą jest zdaniem � �! ł, to M|= ą �! (M|= � �!M|= ł).
Spójniki: Ź, �!, (", '", �! w języku polskim będą odczytywane za
pomocą wyrażeń, odpowiednio:  nieprawda, że . . .  ,  jeżeli . . . , to
. . .  ,  . . . lub . . .  ,  . . . i . . .  ,  . . . wtedy i tylko wtedy, gdy . . .  .
W języku polskim np. zdanie  Jan jest studentem zaprzeczamy
raczej mówiąc  Jan nie jest studentem niż mówiąc  Nieprawda, że
Jan jest studentem . Zaprzeczenia raczej nie stawiamy na początku
zdania, lecz poprzedzamy nim orzeczenie. Stoicy zwracali uwagę, że
zaprzeczenie zdania tworzy się przez umieszczenie przed tym zda-
niem znaku negacji zdaniowej. Odróżniali oni zaprzeczenie zdania od
poprzedzenia znakiem negacji pewnych części zdania.
Rozumienie zdania ą �! � budziło już spory w starożytności i
średniowieczu. Filon Megarejczyk (ok. 300 r. przed Chr.) pierwszy
określił je jako zdanie, które jest fałszywe tylko wtedy, gdy poprzed-
nik (ą) jest prawdziwy a następnik (�) jest fałszywy, i które jest
prawdziwe we wszystkich pozostałych trzech wypadkach. Tak rozu-
mianą implikację określa się jako implikację materialną. Różnił się
tu od swojego mistrza, Diodorosa Kronosa, który jako warunek ko-
nieczny poprawności i prawdziwości implikacji postrzegał istnienie
związków formalnych między poprzednikiem a następnikiem impli-
kacji (implikacja formalna). Diodoros zapoczątkował tym spory na
temat rozumienia implikacji. W szkole megarejsko-stoickiej podano
jeszcze inne rozumienia, między innymi  jest to antyczna postać
implikacji ścisłej  jako zdania, które jest prawdziwe, gdy negacja
jego następnika jest niezgodna z poprzednikiem. O żywości tych spo-
rów świadczy epigramat Kalimacha, bibliotekarza w Aleksandrii w
II w. przed Chr.:  Kraczą już kruki na dachach, które implikacje
są trafne . Pierwszej próby systematycznego opracowania implikacji
formalnej dokonał, tworząc systemy implikacji ścisłej, filozof i logik
amerykański C. I. Lewis [1932].
W języku potocznym spójnikiem implikacji łączymy zdania po-
zostające ze sobą w jakiegoś rodzaju związku. Można wskazać przy-
najmniej cztery rodzaje związków.
38 1. KLASYCZNA LOGIKA ZDAC

W zdaniu  jeżeli na ciało działa niezrównoważona siła, to ciało
porusza się ruchem jednostajnie przyśpieszonym pomiędzy tym, na
co wskazuje poprzednik (na ciało działa niezrównoważona siła), a
tym, na co wskazuje następnik (ciało porusza się ruchem jednostajnie
przyśpieszonym), istnieje związek przyczynowo-skutkowy.
W zdaniu  jeżeli dzisiaj jest poniedziałek, to jutro będzie wtorek
pomiędzy tym, na co wskazuje poprzednik (dzisiaj jest poniedziałek),
a tym, na co wskazuje następnik (jutro będzie poniedziałek) istnieje
związek strukturalny. Taka jest struktura czasu.
W zdaniu  jeżeli kierujesz samochodem, to powinieneś posiadać
prawo jazdy pomiędzy tym, na co wskazuje poprzednik (kierujesz
samochodem), a tym, na co wskazuje następnik (powinieneś posia-
dać prawo jazdy) istnieje związek tetyczny, czyli związek powstały z
ustanowienia.
W zdaniu  jeżeli 2 +2 = 4, to 2 +2 = 4 pomiędzy tym, na co
wskazuje poprzednik (2 +2 = 4), a tym, na co wskazuje następnik
(2+2=4) istnieje związek wynikania (logicznego).
Podane przez nas reguły konstrukcji implikacji nie wykluczają
połączenia tym spójnikiem jakichkolwiek zdań, a więc nawet ta-
kich, w wypadku których nie potrafilibyśmy wskazać jakiegoś rodzaju
związku. Ponadto, reguły rozumienia implikacji są takie, że takiemu
zdaniu możemy przypisać wartość logiczną. Możliwa jest więc kon-
strukcja zdania  jeżeli Białystok jest miastem wojewódzkim, to War-
szawa jest stolicą Polski . Zdanie to jest ponadto prawdziwe. Otóż
zwykły użytkownik języka skłonny byłby kwestionować te ustalenia z
powodu niedostrzegania związku między tym, że Białystok jest mia-
stem wojewódzkim, a tym, że Warszawa jest stolicą Polski. Warto
jednak zauważyć, że fakt, iż nie dostrzega się związku nie oznacza, że
związku nie ma. Czasem jednak łączymy zdania, o których wiemy, że
nie ma między nimi żadnego związku treściowego, np. mówiąc: jeśli
rozwiążesz to zadanie, to mi kaktus na dłoni wyrośnie33 . Zauważmy
również, że w wypadku, gdy mamy zdania, o których wiemy, że oba
są fałszywe, to raczej powiemy:
33
Por. Tarski [1994], s. 27.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 39
gdyby . . . , to . . .
niż
jeśli . . . , to . . . .
Stoicy zdanie ą("� skłonni byli rozumieć w sensie alternatywy wy-
kluczającej (rozłącznej), czyli takie zdanie byłoby prawdziwe wtedy
i tylko wtedy, gdy dokładnie jeden z jego członów, ą albo �, byłby
prawdziwy. Piotr Hiszpan (XIII w.) stwierdza, że dla prawdziwości
alternatywy potrzeba, by jeden z członów był prawdziwy, a dla fał-
szywości, by fałszywe były oba człony. Zdecydowanym zwolennikiem
takiego rozumienia alternatywy (niewykluczającej, nierozłącznej) był
Burleigh (XIV w.), który zwraca uwagę na to, że zdanie takie wynika
z każdego ze swych członów; z tego więc wynika, że jeśli oba człony
są prawdziwe, to alternatywa jest prawdziwa. Tu podany warunek
prawdziwości zdania o postaci alternatywy rozstrzyga na rzecz nie-
wykluczającego rozumienia alternatywy. Nie znaczy to  jak będzie
można łatwo zauważyć przy okazji dyskusji nad spójnikami  żeby nie
było możliwe rozważanie logiki ze spójnikiem alternatywy rozłącznej.
W języku potocznym słówko  lub rozumiemy raczej w sensie al-
ternatywy nierozłącznej. Jednak dyskusje wykazują, że w wypadku,
gdy słowem  lub połączymy zdania, z których o przynajmniej jed-
nym z góry wiadomo, że jest prawdziwe, to skłonni jesteśmy kwe-
stionować prawdziwość zdania złożonego. Jest tak w wypadku zdań:
 Warszawa jest stolicą Polski lub Białystok jest stolicą Polski ,  1
+ 1 = 2 lub 2 + 2 = 4 . Jak się wydaje jest to jednak raczej wyni-
kiem tego, że zdania, o którym wiemy, że jest prawdziwe nie zwykli-
śmy łączyć z jakimś zdaniem (być może również prawdziwym) sło-
wem  lub , niż skutkiem rozłącznego rozumienia tego słowa. Podob-
nie jak w wypadku innych spójników dwuargumentowych, w szcze-
gólności implikacji, nie ograniczamy też możliwości łączenia słowem
 lub zdań ze względu na związki treściowe między nimi. Podobnie
jak w wypadku implikacji należy zauważyć, że fakt niedostrzegania
związku, nie oznacza braku tego związku.
Już stoicy określali koniunkcję jako zdanie prawdziwe wtedy i
tylko wtedy, gdy oba argumenty spójnika, ą i �, są prawdziwe. Ta-
kie same warunki prawdziwości formułowali logicy średniowieczni.
40 1. KLASYCZNA LOGIKA ZDAC

Słówko  i jest jednym z wielu możliwych słów języka polskiego uży-
wanych do wypowiedzenia koniunkcji. Ze względów stylistycznych
stosujemy je zamiennie ze słowem  oraz . W niektórych kontekstach
do tego celu musimy użyć słówka  a . Na przykład nie powiemy  Jan
czyta gazetę i Zosia gotuje obiad , lecz powiemy  Jan czyta gazetę, a
Zosia gotuje obiad . Również w wypadku koniunkcji nie nakładamy
żadnych ograniczeń na zdania, które łączymy tym spójnikiem.
Równoważność wypowiadamy za pomocą frazy  wtedy i tylko
wtedy, gdy . Problemy związane z użyciem tej frazy są analogiczne
do tych, jakie mamy z frazą  jeśli . . . , to . . .  34 . Sam termin  równo-
ważność , inaczej niż jest to w wypadku pozostałych nazw spójników
zdaniowych, ma inne specyficzne znaczenia35 .
Symbole: Ź, �!, (", '", �! są symbolami języka logiki zdań, a więc
należą do języka, o którym mówimy. Z punktu widzenia języka, któ-
rym mówimy są one pewnego rodzaju przedmiotami, o których się
mówi. Symbole te nie należą do języka, którym pisany jest ten tekst.
Symboli tych i wyrażeń z nich zbudowanych używamy wyłącznie jako
�cytatów, jako �przytoczeń symboli i wyrażeń języka, o którym
mówimy. Symboli tych nie możemy użyć jako wygodnych skrótów
dla spójników języka, którym mówimy. Nie możemy więc zastąpić, np.
 jeżeli. . . , to. . .  i  wtedy i tylko wtedy, gdy przez, odpowiednio: �!,
�!. W naszym tekście o języku rachunku zdań symbole i wyrażenia
tego języka występują w supozycji materialnej, czyli na oznaczenie
samych siebie. Jeżeli istnieje taka potrzeba, to użycie wyrażenia w
supozycji materialnej jest zwykle zaznaczane za pomocą cudzysłowu.
(DEF. prawdziwości zdania) Zdanie ą jest (logicznie) prawdziwe
wtedy i tylko wtedy, gdy ą jest prawdziwe we wszystkich modelach;
czyli gdy:
dla każdego Mą"S, M|= ą.
Tam, gdzie będzie istniała obawa nieporozumień, że  prawdziwe
(bez odnoszenia do jakiegoś modelu) będzie brane w znaczeniu  praw-
34
W sprawie rozumienia spójników zdaniowych zob. Tarski [1994], s. 20 33.
35
Szerzej na ten temat przy okazji omawiania relacji równoważności.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 41
dziwe w świecie realnym , zamiast o prawdziwości zdania będziemy
mogli mówić o jego logicznej prawdziwości.
1.1.5. Tautologia
Pojęcie zdania logicznie prawdziwego jest pojęciem semantycz-
nym. Przedmiotem semantyki są relacje między znakiem a rzeczy-
wistością (do której ten znak odnosi). Zależy nam na syntaktycznym
scharakteryzowaniu pojęcia zdania logicznie prawdziwego. Przedmio-
tem syntaktyki są relacje między znakami. Chcemy więc znalez
ć takie
własności zdań jako wyrażeń, które dałyby się opisać w kategoriach
relacji między znakami bez odwoływania się do relacji między zna-
kami a rzeczywistością i które wyróżniałyby zdania logicznie praw-
dziwe.
Zdanie jest skończonym ciągiem symboli, a więc w jego skład
wchodzi skończona ilość liter zdaniowych. Dla każdego zdania można
zatem wskazać taki początkowy skończony odcinek ciągu S liter zda-
niowych, w którym znajdują się wszystkie litery występujące w tym
zdaniu.
Niech p0, p1, . . . , pn będzie ciągiem liter zdaniowych, wśród któ-
rych znajdują się wszystkie litery zdaniowe występujące w ą. Każdej
literze zdaniowej przyporządkowujemy jeden z symboli: f, t. To, czym
są te symbole nie jest ważne. Zakładamy o nich jedynie, że są różne.
(DEF. wartości logicznej) f i t to wartości logiczne36 .
(DEF. interpretacji) Niech v0, v1, . . . , vn będzie ciągiem symboli f i t.
Ciąg ten to interpretacja.
W ramach logiki zdań interpretacja liter zdaniowych wyczerpuje
się więc w określeniu ich wartości logicznej.
(DEF. wartości logicznej zdania) Wartość logiczną zdania ą dla in-
terpretacji v0, v1, . . . , vn określamy (rekursywnie) następująco:
(I) jeżeli ą jest literą zdaniową pm, to wartością logiczną zdania ą
jest vm;
36
 f jest literą z angielskiego słowa  false (fałsz), a  t   true (prawda).
42 1. KLASYCZNA LOGIKA ZDAC

(II) wartości logiczne zdań złożonych obliczamy zaś zgodnie z poniżej
podanymi tabelkami wartości logicznych:
� Ź� � ł � (" ł � '" ł � �! ł � �! ł
t f t t t t t t
f t t f t f f f
f t t f t f
f f f f t t
PRZYKA
AD
Zdanie:
p1 (" (p0 '" Ź p2)
dla interpretacji:
f, t, t, t
przyjmuje wartość t.
�
Zauważmy, że jedyna istotna różnica formalna pomiędzy określe-
niem prawdziwości zdań w modelu a definicją wartości zdania polega
na tym, że modeli jest nieskończenie wiele (dokładnie tyle, ile jest
podzbiorów zbioru liter zdaniowych, czyli 2N, 2N = c37 ) zaś ilość in-
terpretacji jest skończona. Interpretacji o długości n jest tyle, ile jest
n wyrazowych ciągów liter t i f, czyli 2n.
(DEF. tautologii) Zdanie ą jest tautologią38 , co oznaczamy: ą39 ,
wtedy i tylko wtedy, gdy ą dla dowolnej interpretacji v0, v1, . . . , vn
przyjmuje wartość t.
(DEF. kontrtautologii) Zdanie ą jest kontrtautologią wtedy i tylko
wtedy, gdy ą dla dowolnej interpretacji przyjmuje wartość f.
37
Użyte tu oznaczenia są objaśnione w części poświęconej teorii mnogości.
38
Greckie �ą`�ooł� znaczy tyle, co  powtarzanie tego, co już zostało po-
� ąą
wiedziane . Termin  tautologia w znaczeniu  zdanie prawdziwe w każdym mo-
delu (a więc w znaczeniu innym niż tu przyjęte) został wprowadzony do logiki
przez Wittgensteina [1921].
39
Symbol   pojawia się u G. Fregego [1879]. Jego użycie, takie jak współ-
cześnie, ma miejsce w: S. C. Kleene [1934], J. B. Rosser [1935].
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 43
Pytanie, czy zdanie jest tautologią jest rozstrzygalne.
TWIERDZENIE 1.
Problem, czy zdanie jest tautologią, jest rozstrzygalny, czyli w
wypadku dowolnego zdania klasycznej logiki zdań można w skoń-
czonej ilości kroków dać odpowiedz
na pytanie, czy zdanie to jest,
czy też nie jest tautologią.
DOWÓD
Niech ą będzie zbudowane z n różnych liter zdaniowych (litery te
mogą występować wielokrotnie). Zgodnie z definicją tautologii należy
wziąć taki początkowy fragment ciągu liter zdaniowych, w którym
mieszczą się wszystkie litery zdaniowe występujące w ą. Zauważmy
jednak, że dla interpretacji nie różniących się na miejscach, odpowia-
dających literom zdaniowym występującym w ą, wartości logiczne ą
też się nie różnią. Pod uwagę wystarczy zatem wziąć te i tylko te
interpretacje, które różnią się na miejscach odpowiadających literom
zdaniowym występującym w ą. Ponieważ wą występuje dokładnie n
różnych liter zdaniowych i mamy dokładnie dwie wartości logiczne,
zatem takich interpretacji jest 2n.
Problem, jaka wartość logiczna przysługuje zdaniu ą dla danej
interpretacji jest rozstrzygalny. Wartość logiczną zdania ą dla zada-
nej interpretacji ustalamy w m krokach, gdzie m jest liczbą spójników
występujących w zdaniu ą. Ilość spójników określamy tak, że każde
wystąpienie spójnika (każdy symbol) liczymy osobno. W celu okre-
ślenia wartości logicznej zdania dla danej interpretacji korzystamy
z tabelek wartości logicznych. Szczegóły takiego postępowania opi-
40
szemy niżej jako metodę wprost.
40
Do wskazania końca dowodu używany będzie kwadracik. P. Halmos w au-
tobiografi pisze, że jego nieśmiertelnymi zasługami są pomysły skrótu i symbolu
typograficznego. Wymyślił  iff jako skrót dla  if and only if , ale nie jest pewny,
czy rzeczywiście był pierwszy. Z całą pewnością zaś jego pomysłem jest używanie
kwadraciku do wskazywania końca, zwykle końca dowodu. Zauważa, że obok czę-
sto używanej nazwy  tombstone jeden z życzliwych autorów określił ten znak
jako  halmos . Zob. P. R. Halmos [1985], s. 403.
44 1. KLASYCZNA LOGIKA ZDAC

(DEF. metody wprost) W celu znalezienia metodą sprawdzania
wprost odpowiedzi na pytanie, czy zdanie jest tautologią:
1. określamy wszystkie możliwe układy wartości logicznych zdań
prostych, z których zbudowane jest dane zdanie; porządkujemy je
np. alfabetycznie według zasady pi wyprzedza pi+1 a t wyprzedza
f;
2. rozpatrujemy kolejne układy wartości pod każdą literą zdaniową
podpisując wartość logiczną, jaka przysługuje mu dla rozpatry-
wanego układu;
3. tam, gdzie pod argumentami jakiegoś spójnika znajdują się pod-
pisane wartości logiczne, określamy zgodnie z tabelkami wartość
logiczną zdania zbudowanego za pomocą tego spójnika i wartość
tą podpisujemy pod tym spójnikiem; postępowanie to kontynu-
ujemy tak długo, aż zostanie podpisana wartość logiczna pod
spójnikiem głównym rozpatrywanego zdania;
4. zdanie jest tautologią wtedy i tylko wtedy, gdy dla każdego
układu wartości  określonego zgodnie z pkt. 1  pod spójnikiem
głównym tego zdania znajduje się litera t.
PRZYKA
AD
Zdanie:
[p '" (p �! q)] �! q
jest tautologią.
Musimy rozważyć cztery wypadki: {t, t}, {t, f}, {f, t}, {f, f}.
I.
[ p '" ( p �! q ) ] �! q
t t t t
t
t
t
II.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 45
[ p '" ( p �! q ) ] �! q
t t f f
f
f
t
III.
[ p '" ( p �! q ) ] �! q
f f t t
t
f
t
IV.
[ p '" ( p �! q ) ] �! q
f f f f
t
f
t
�
Zauważmy, że nie jest konieczne wypisywanie liter t i f wróżnych
wierszach. Metodę można stosować pisząc je na jednej lini.
Opisany sposób znajdowania metodą sprawdzania wprost od-
powiedzi na pytanie, czy zdanie jest tautologią, jest uciążliwy. W
praktyce zwykle korzystniej jest stosować metodę sprawdzania nie-
wprost41 . Metoda niewprost, podobnie jak metoda wprost, ma cha-
rakter czysto �mechaniczny, tzn. stosując ją do dowolnego zdania
postępujemy krok po kroku zgodnie z podanymi regułami. Nie są to
41
Metodę sprawdzania wprost oraz metodę niewprost określa się jako metodę
zero-jedynkową a to dlatego, że zamiast liter  t i  f zwykle stosowano  1 i  0 .
Metoda ta jest dziełem E. Schr�dera. J. A
ukasiewicz w [1951], s. 82 twierdzi, że
metoda ta była wynaleziona przez Ch. S. Peirce a około 1885 r.
46 1. KLASYCZNA LOGIKA ZDAC

jedyne metody tego rodzaju. Taki sam charakter ma opisana tu me-
toda tablic semantycznych. Ponadto zauważmy, że zawsze możemy
zastosować szczególną procedurę, na jaką zezwala budowa zdania, o
które pytamy się czy jest tautologią.
Najogólniej rzecz biorąc, metoda dowodzenia niewprost jakiejś
tezy � z jakichś przesłanek P polega na tym, że jako założenie bierze
się zaprzeczenie �, czyli dołącza się je do przesłanek P . � jest dowie-
dzione, jeżeli z tego założenia, czyli z zaprzeczenia � oraz przesłanek
P udaje się wywnioskować zdania, które nie mogą być współpraw-
dziwe. Takimi zdaniami są np. zdania, z których jedno jest negacją
drugiego42 .
(DEF. metody niewprost) W celu sprawdzenia metodą niewprost, czy
zdanie jest tautologią postępujemy następująco:
1. pod spójnikiem głównym danego zdania piszemy literę f;
2. jeżeli pod spójnikiem napisana jest jakaś litera, to rozważamy tyle
wypadków (przez powtórzenie danego  rysunku ), ile zgodnie z
tabelkami wartości logicznych jest możliwych sposobów podpi-
sania liter t i f pod argumenty tego spójnika; każdy taki wy-
padek rozważamy oddzielnie; gdy podpisujemy wartość logiczną
pod jakąś literą zdaniową, to wartość tę podpisujemy pod każde
wystąpienie tej litery zdaniowej;
opisaną procedurę przeprowadzamy dla każdego wypadku z
osobna aż do momentu, gdy
2.1. pod jakimś spójnikiem lub literą zdaniową pojawią się litery
t i f,
lub
2.2. wyczerpane zostaną wszystkie możliwości i pod każdą literą
znajduje się jedna z liter t lub f;
42
Ten sposób dowodzenia u Arystotelesa nazywa się ąĄął�ł� (odprowadze-
nie, sprawdzenie), stąd określenie: dowód apagogiczny. Scholastycy zaś stosowali
określenie reductio ad impossibile (sprowadzenie do niemożliwości), reductio ad
absurdum (sprowadzenie do niedorzeczności); jak również: reductio indirecta, re-
ductio contradictionem.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 47
3. zdanie jest tautologią wtedy i tylko wtedy, gdy w każdym wy-
padku otrzymanym zgodnie z pkt. 2 stwierdzamy, że pod jakimś
spójnikiem lub jakąś literą zdaniową podpisane zostały obie litery
t i f.
PRZYKA
AD
Zdanie:
(p �! q) �! ( Ź p �!Ź q)
nie jest tautologią.
( p �! q ) �! ( Ź p �!Ź q )
f
tf
t f
f t
f t
t
�
Inne przykłady zastosowania metody niewprost znajdujemy po-
niżej.
1.1.6. Wybrane tautologie klasycznej logiki zdań
Nim udowodnimy twierdzenie ustalające związek między poję-
ciem tautologii a pojęciem zdania logicznie prawdziwego, rozważmy
przykłady tautologii43 .
1. [(Źp �! q) '" (Źp �!Źq)] �! p
Sprawdzenie metodą niewprost:
43
Prawa logiki są powszechne, znaczy to m.in., że korzystamy z nich w naszych
rozumowaniach o logice. Przykładowe tautologie są podstawą zasad rozumowania
stosowanych w dowodach tu formułowanych twierdzeń.
48 1. KLASYCZNA LOGIKA ZDAC

[ ( Ź p �! q ) '" ( Ź p �!Ź q ) ] �! p
f
tf
tt f
f t f t
t t t t t
t t t t
t t f
f
Zdanie:
[(Źp �! q) '" (Źp �!Źq)] �! p
jest tautologią.
2. (p �! q) �! [(p �! q) '" (q �! p)]
Sprawdzenie metodą wprost:
( p �! q ) �! [ ( p �! q ) '" ( q �! p ) ]
t t t t t t
tt t
tt
t
( p �! q ) �! [ ( p �! q ) '" ( q �! p ) ]
t f t f f t
ff t
ff
t
( p �! q ) �! [ ( p �! q ) '" ( q �! p ) ]
f t f t t f
ft f
ff
t
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 49
( p �! q ) �! [ ( p �! q ) '" ( q �! p ) ]
f f f f f f
tt t
tt
t
Zdanie:
(p �! q) �! [(p �! q) '" (q �! p)]
jest tautologią.
3. (p �! q) �! (Źq �!Źp)
Sprawdzenie metodą niewprost:
( p �! q ) �! ( Ź q �!Ź p )
f
tf
tt f
tf t
t t f
f
Zdanie
(p �! q) �! (Źq �!Źp)
jest tautologią.
4. (Źq �!Źp) �! (p �! q)
Sprawdzenie metodą niewprost:
( Ź q �!Ź p ) �! ( p �! q )
f
tf
tt f
f t t
t t f
f
50 1. KLASYCZNA LOGIKA ZDAC

Zdanie:
(Źq �!Źp) �! (p �! q)
jest tautologią.
5. Ź(p �! q) �! (p '"Źq)
Sprawdzenie metodą niewprost:
Ź ( p �! q ) �! ( p '" Ź q )
f
tf
ff
t f f
t f f
t f t
t
Zdanie:
Ź(p �! q) �! (p '"Źq)
jest tautologią.
6. (p '"Źq) �!Ź(p �! q)
Sprawdzenie metodą niewprost:
( p '" Ź q ) �!Ź ( p �! q )
f
tf
t t t
t f t
t t f
f
Zdanie:
(p '"Źq) �!Ź(p �! q)
jest tautologią.
Na podstawie powyższych tautologii można zauważyć, że tauto-
logiami są również:
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 51
7. (p �! q) �! [(p �! q) '" (Źp �!Źq)]
8. (p �! q) �! [(Źq �!Źp) '" (Źp �!Źq)]
9. Ź(p �! q) �! (p '"Źq)
Tautologią jest także
10. (p �! q) �! [Ź(p '"Źq) '"Ź(Źp '" q)]
Tautologią zaś nie jest:
11. (p �! q) �! [(p �! q) '" (Źq �!Źp)].
1.1.7. Tablice semantyczne
Metoda zero-jedynkowa wprost pozwala w wypadku do-
wolnego zdania rozstrzygnąć, czy jest ono tautologią, czy też
nie jest. Jest to jednak metoda, która wymaga wykonania
bardzo wielu operacji.44 Zrozumiałe jest więc poszukiwanie bar-
dziej efektywnych sposobów znajdowania odpowiedzi na pytanie, czy
zdanie jest tautologią. Jednym z nich jest metoda tablic semantycz-
nych. Metodę tablic semantycznych stworzył w latach 1954-55 Beth.
Stąd używa się też terminu  tablice semantyczne Betha . Istnieje
wiele ujęć tej metody. Wyróżnia ją nie tylko sprawność, lecz również
uniwersalność. Metoda ta, w odróżnieniu od metody zero-jedynko-
wej, ma zastosowanie  oczywiście, po stosownym uzupełnieniu  w
rachunku predykatów. Oprócz logiki klasycznej wykorzystywana jest
także w innych logikach, jak np. logiki modalne i logika intuicjoni-
styczna.
Stosowany wyżej sposób podpisywania liter t i f łatwo opisać za
pomocą prostych reguł. Np. dla spójnika negacji byłyby to następu-
jące reguły:
44
Na przykład, gdy w zdaniu jest dokładnie sześć (różnych) liter zdaniowych,
mamy 64 układy wartości. Jeżeli jest ich dziesięć, to takich układów jest już
1024. Angielski logik Charles Lutwidge Dodgson (1832 1898), bardziej znany pod
swym literackim pseudonimem Lewis Carroll jako autor np.  Alicji w krainie
czarów , wymyślił problem żaby. Dla rozwiązania tej zagadki należy rozważyć
zdanie z osiemnastoma (różnymi) literami zdaniowymi. Gdyby chcieć metodą
zero-jedynkową szukać odpowiedzi na pytanie, czy zdanie to jest tautologią, trzeba
wziąć pod uwagę 262 144 układy wartości.
52 1. KLASYCZNA LOGIKA ZDAC

W kolumnie I znajduje się schemat konstrukcji, do której stosu-
jemy regułę, zaś w kolumnie II - wynik zastosowania odpowiedniej
reguły.
III
1. . . . Ź ą . . . . . . Ź ą . . .
..
..
..
tt
f
2. . . . Ź ą . . . . . . Ź ą . . .
..
..
..
ff
t
3. . . . Ź ą . . . . . . Ź ą . . .
..
..
..
tt
f
4. . . . Ź ą . . . . . . Ź ą . . .
..
..
..
ff
t
Podobne reguły można by podać dla pozostałych spójników.
Litery t i f wskazują wartość logiczną, którą przybiera określone
zdanie. Może to być zdanie, o które pytamy się, czy jest tautologią,
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 53
a może to być zdanie będące jego zdaniem składowym. Zauważmy,
że zamiast pisać litery t i f moglibyśmy pisać zdania, które mają
przybierać odpowiednią wartość logiczną wpisując je w tablice, po-
wiedzmy, w prawą część te, którym ma być przyporządkowana litera
f, a w lewą te, którym ma być przyporządkowana litera t. W wypadku
stosowania metody niewprost możliwe jest dalsze usprawnienie. Do
tablic wpisujemy zdania składowe rozważanego zdania. Na tej idei
oparta jest metoda tablic semantycznych sprawdzania tautologiczno-
ści zdań.
Podane zostaną reguły budowy pewnych konstrukcji, które są ry-
sunkiem schematycznym drzewa postawionego pniem do góry. Kon-
strukcje te będziemy nazywali tablicami semantycznymi. Górę drzewa
tworzy jego korzeń. Na dole są liście. Odcinki łączące korzeń z liśćmi
to gałęzie. Drzewo, które ma więcej niż jedną gałąz
, rozdziela się,
rozgałęzia. Drzewo ma tyle gałęzi, ile ma liści. Odcinek powyżej roz-
gałęzień to pień.
korzeń
pień
liść
liść liść
(DEF. tablicy semantycznej) Tablica semantyczna to drzewo ze zda-
niami. Zdanie może znajdować się po lewej, bądz
po prawej stronie
gałęzi. Zdania znajdujące się na pniu znajdują się na każdej gałęzi.
54 1. KLASYCZNA LOGIKA ZDAC

(DEF. relacji leżenia poniżej) Niech ą jest innym (jako napis) napisem
niż �45 . Zdanie ą leży poniżej zdania � wtedy i tylko wtedy, gdy od
zdania � można  przejść do zdania ą poruszając się wyłącznie w dół
odcinkami.
Stosunek leżenia poniżej jest więc tego rodzaju, że jeżeli ą leży
poniżej �, a � leży poniżej ł, to ą leży poniżej ł (czyli, stosunek ten
jest przechodni).
(DEF. gałęzi) Gałęzią nazywamy każdą taką największą klasę zdań
(jako napisów) ze zbioru zdań użytych w konstrukcji drzewa, że po-
między dowolnymi dwoma elementami tej klasy ą i � zachodzi stosu-
nek leżenia poniżej, czyli bądz
ą leży poniżej �, bądz
� leży poniżej
ą. O zdaniach tworzących gałąz
mówimy, że leżą na tej gałęzi.
(DEF. gałęzi sprzecznej) Gałąz
jest sprzeczna (zamknięta) wtedy i
tylko wtedy, gdy dla pewnego zdania ą po obu stronach, prawej i
lewej, odcinków wskazujących stosunek leżenia poniżej na danej gałęzi
są napisy równokształtne z ą.
Fakt, że gałąz
jest sprzeczna zaznaczamy pisząc kreskę poziomą
na końcu tej gałęzi (na poziomie najniżej leżącego zdania).
(DEF. gałęzi otwartej) Gałąz
, która nie jest zamknięta jest otwarta.
(DEF. tablicy zamkniętej) Tablica jest zamknięta wtedy i tylko wtedy,
gdy zamknięte są wszystkie gałęzie tworzące tę tablicę.
(DEF. tablicy otwartej) Tablica, które nie jest zamknięta jest otwarta.
Będziemy mieli dwa rodzaje reguł. Takie, które wymagają tylko
dopisania jednego odcinka pod każdą gałęzia, na której znajduje się
badane zdanie; oraz takie, które wymagają dopisania dwóch odcinków
pod każdą gałęzią, na której znajduje się badane zdanie. Te ostatnie
reguły powodują rozgałęzienie.
W wypadku metody zero-jedynkowej wprost postępujemy  z
dołu do góry  przypisujemy wartości literom zdaniowym, a następ-
nie obliczamy wartość logiczną zdania. Metoda tablic semantycznych
45
Mogą to być napisy równokształtne.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 55
oparta jest na strategii  z góry do dołu  rozpoczynamy od wartości
logicznej zdania, dochodząc do wartości logicznych liter zdaniowych.
Reguły tworzenia tablic semantycznych są regułami analitycznymi
 zdaniu złożonemu przyporządkowują jego części składowe. Zaczy-
namy zawsze od spójnika głównego. Zdanie składowe może mieć war-
tość t lub f. W zależności od tego piszemy je po, odpowiednio, le-
wej lub prawej stronie odcinka. Dla każdego spójnika potrzebujemy
dwóch reguł: jedna mówi jak postępować ze zdaniem znajdującym
się po lewej, a druga jak postępować ze zdaniem znajdującym się po
prawej stronie gałęzi. Będziemy więc odróżniali reguły lewostronne
(L) i prawostronne (P ). Będziemy mieli następujące reguły: ŹL, ŹP ,
'"L, '"P , ("L, ("P , �! L, �! P , �! L, �! P . Fakt zastosowania reguły
"
do danego zdania zaznaczać będziemy pisząc przy tym zdaniu .
"
Zdań oznaczonych nie bierze się pod uwagę w dalszej konstrukcji
drzewa: informacja w nich zawarta została wykorzystana do rozbu-
"
dowy drzewa. Zdania oznaczone to zdania martwe, zdania nieozna-
kowane tak to zdania żywe.
(DEF. tablicy zakończonej) Tablica jest zakończona wtedy i tylko
wtedy, gdy jest (a) zamknięta lub (b) jedynymi żywymi zdaniami na
niej są litery zdaniowe.
Konstrukcję tablicy prowadzimy tak długo aż otrzymamy tablicę
zamkniętą lub, gdy jedynymi żywymi zdaniami będą litery zdaniowe.
W wypadku logiki zdań tablica zawsze będzie miała skończoną
ilość elementów. Ponadto będzie binarna, tzn. rozgałęzienie dokonuje
się na dokładnie dwie gałęzie.
REGUA
Y
"
ŹL Źą
�
�
�
ą
Reguła stosuje się do zdania Źą, znajdującego się po lewej stronie
gałęzi. Ta strona reprezentuje wartość t. Jeśli zdanie Źą ma wartość
56 1. KLASYCZNA LOGIKA ZDAC

t, to jaką wartość ma ą? Oczywiście, ą ma wartość f. Zatem piszemy
ą po prawej stronie na końcu każdej już istniejącej otwartej gałęzi,
znajdującej się poniżej Źą (jako napisu).
"
ŹP Źą
�
�
�
ą
Reguła ta stosuje się do zdania Źą, znajdującego się po prawej
stronie gałęzi. Strona ta reprezentuje wartość f. Jeśli zdanie Źą ma
wartość f, to jakie jest zdanie ą? Oczywiście, zdanie ą ma wartość
t. Zatem piszemy ą po lewej stronie na końcu każdej już istniejącej
otwartej gałęzi, znajdującej się poniżej Źą (jako napisu).
"
'"L ą '" �
�
�
�
ą
�
Reguła ta stosuje się do zdania ą '" �, znajdującego się po lewej
stronie gałęzi. Zdanie ą '" � ma wartość t, a więc zarówno ą jak i �
mają wartość t. Oba te zdania, ą i �, piszemy więc jedno pod dru-
gim na przedłużeniu drzewa po lewej stronie każdej otwartej gałęzi,
znajdującej się poniżej ą '" � (jako napisu).
'"P
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 57
Reguła ta stosuje się do zdania ą '" �, znajdującego się po pra-
wej stronie gałęzi. Strona ta reprezentuje wartość f. Zdanie ą '" � ma
wartość f, gdy ą ma wartość f lub gdy � ma wartość f. W celu zapi-
sania tego faktu do każdej już istniejącej otwartej gałęzi, znajdującej
się poniżej zdania ą '" � (jako napisu) dopisujemy dwie gałęzie. Po
prawej stronie na końcu jednej piszemy ą a na końcu drugiej �.
("L
Reguła ta stosuje się do zdania ą (" �, znajdującego się po lewej
stronie gałęzi. Zdanie takie ma wartość t, zatem wartość t ma zdanie
ą lub wartość t przysługuje zdaniu �. W celu zapisania tego faktu
do każdej już istniejącej otwartej gałęzi, znajdującej się poniżej ą (" �
(jako napisu) dopisujemy dwie gałęzie. Po lewej stronie na końcu
jednej piszemy ą a na końcu drugiej �.
("P
Reguła ta stosuje się do zdanie ą (" �, znajdującego się po prawej
stronie gałęzi. Zdanie takie ma wartość f, zatem wartość f przysłu-
guje zdaniu ą i wartość f przysługuje zdaniu �. Zatem po prawej
stronie na końcu każdej już istniejącej otwartej gałęzi, znajdującej
się poniżej ą (" � (jako napisu) piszemy jedno pod drugim ą i �.
58 1. KLASYCZNA LOGIKA ZDAC

�! L
Reguła ta stosuje się do zdania ą �! �, znajdującego się po lewej
stronie gałęzi. Zdanie takie ma wartość t, zatemą ma wartość f lub
� ma wartość t. Nasze drzewo będzie się więc rozgałęziać. Do każdej
już istniejącej otwartej gałęzi, znajdującej się poniżej ą �! � (jako
napisu) dopisujemy dwie gałęzie. Na końcu po prawej stronie jednej
z nich piszemy ą a po lewej stronie drugiej piszemy �.
�! P
Reguła ta stosuje się do zdanie ą �! �, znajdującego się po prawej
stronie gałęzi. Zdanie takie ma wartość f, zatemą ma wartość t, a
� ma wartość f. Na każdej otwartej gałęzi, znajdującej się poniżej
ą �! � (jako napisu) piszemy po lewej stronie ą, a po prawej �.
�! L
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 59
Reguła ta stosuje się do zdania ą �! �, znajdującego się po lewej
stronie gałęzi. Zdanie takie ma wartość t, zatem wartość t przysługuje
zarówno zdaniu ą jak i zdaniu � lub wartość f mają zdania ą i �.
Drzewo będzie się więc rozgałęziać. Do każdej już istniejącej otwartej
gałęzi, znajdującej się poniżej ą �! � (jako napisu) dopisujemy dwie
gałęzie. Po lewej stronie jednej z nich piszemy jedno pod drugim ą i
� i tak samo po prawej stronie drugiej z nich.
�! P
Reguła ta stosuje się do zdania ą �! �, znajdującego się po prawej
stronie gałęzi. Zdanie takie ma wartość f, zatem zdaniu ą przysługuje
wartość t a zdaniu � przysługuje wartość f lub odwrotnie, zdanie
ą ma wartość f a zdanie � ma wartość t. Drzewo będzie się więc
rozgałęziać. Do każdej już istniejącej otwartej gałęzi, znajdującej się
poniżej ą �! � (jako napisu) dopisujemy dwie gałęzie. W wypadku
jednej z nich piszemy po lewej stronie ą a po prawej �, a w wypadku
drugiej z nich odwrotnie, piszemy po prawej ą a po lewej �.
Podane reguły są tego rodzaju, że stosują się do dwóch dowolnych
skończonych zbiorów zdań: jednego zapisanego po lewej, a drugiego
zapisanego po prawej stronie pnia. Konstrukcję uzyskaną dla danych
zbiorów zdań nazywamy tablicą semantyczną lub drzewem analitycz-
nym tych zbiorów.
Reguły odnoszące do poszczególnych spójników mogą być stoso-
wane w dowolnej kolejności. Z formalnego punktu widzenia kolejność
nie ma znaczenia, czyli  inaczej mówiąc  odpowiedz
na pytanie, czy
dla danych zbiorów zdań  jednego zapisanego po lewej a drugiego
zapisanego po prawej stronie pnia  drzewo jest zamknięte nie zależy
60 1. KLASYCZNA LOGIKA ZDAC

od tego, w jakiej kolejności stosujemy poszczególne reguły. Od ich ko-
lejności zależy jednak kształt drzewa, w szczególności jedne drzewa
mogą być większe (w sensie ilości gałęzi) od innych. Zależy nam na
możliwie najmniejszym drzewie. Uzyskaniu takiego drzewa sprzyja
stosowanie reguły o charakterze pragmatycznym, a mianowicie:
reguły nierozgałęz
ne stosujemy przed regułami rozgałęz
nymi.
Mając dwa zbiory zdań � i Ł, możemy pytać, czy istnieje in-
terpretacja taka, że wszystkie zdania z � mają wartość t, a wszyst-
kie zdania z Ł mają wartość f. Odpowiedz
na to pytanie uzyskamy
konstruując tablicę semantyczną. Na początku konstrukcji po lewej
stronie piszemy wszystkie zdania z �, a po prawej stronie wszystkie
zdania z Ł. Jeżeli uzyskamy tablicę zamkniętą, to taka możliwość
jest wykluczona. Jeżeli zaś tablica będzie otwarta, to taka możliwość
istnieje. Interpretację, dla której to zachodzi określamy biorąc pod
uwagę jedną z otwartych gałęzi. Wszystkim literom zdaniowym znaj-
dującym się na tej gałęzi, jeśli znajdują się po stronie lewej przypisu-
jemy wartość t, a gdy znajdują się po prawej przypisujemy wartość f.
Literom zdaniowym, które nie występują na branej pod uwagę gałęzi
przypisujemy dowolną z wartości t i f. Dla tak określonej interpreta-
cji wszystkie zdania ze zbioru � mają wartość t, a wszystkie zdania
ze zbioru Ł mają wartość f.
Pokażemy, że tablica semantyczna nie jest zamknięta wtedy i
tylko wtedy, gdy istnieje interpretacja taka, że wszystkie i tylko zda-
nia ze zbioru �, zapisane po lewej stronie pnia przyjmują dla tej in-
terpretacji wartość t a wszystkie i tylko zdania ze zbioru Ł, zapisane
po prawej stronie pnia przyjmują wartość f.
Wpierw dowiedziemy tezy: jeżeli tablica semantyczna jest otwar-
ta, to istnieje interpretacja taka, że wszystkie i tylko zdania ze zbioru
�, zapisane po lewej stronie pnia przyjmują dla tej interpretacji war-
tość t a wszystkie i tylko zdania ze zbioru Ł, zapisane po prawej
stronie pnia przyjmują wartość f.
W każdym rozważanym tu wypadku będziemy brali pod uwagę
interpretację I taką, że wszystkim literom zdaniowym znajdującym
się na pewnej otwartej gałęzi  oznaczmy ją GI  jeśli znajdują się po
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 61
stronie lewej przypisujemy wartość t, a gdy znajdują się po prawej
przypisujemy wartość f. Literom zdaniowym, które nie występują na
branej pod uwagę gałęzi przypisujemy dowolną z wartości t i f.
Nasze twierdzenie będzie wnioskiem z twierdzenia głoszącego, że
dla interpretacji I wszystkie zdania znajdujące się po lewej stronie
gałęzi GI przyjmują wartość t, a wszystkie zdania znajdujące się po
prawej stronie GI przyjmują wartość f.
Nasza teza zachodzi dla wypadku, gdy elementami � i Ł są tylko
litery zdaniowe. Z założenia tablica jest otwarta, a więc żadna z liter
zdaniowych nie występuje zarówno po prawej jak i po lewej stronie.
Dla interpretacji I litery znajdujące się po lewej stronie przyjmują
wartość t, a litery znajdujące się po prawej stronie przyjmują wartość
f.
Niech nasza teza zachodzi dla zdań o długości nie większej niż k.
Niech elementami � i Ł będą teraz zdania o długości (k +1). Jeżeli
elementem � będzie zdanie Źą, to zdanie ą znajdzie się po prawej
stronie. Zgodnie z założeniem dla interpretacji I przyjmuje ono war-
tość f, zatem zdanie Źą przyjmuje wartość t. Podobnie będzie, gdy
Źą będzie elementem Ł. Tym razem ą przyjmie wartość t, a więc
Źą przyjmie wartość f. Jeżeli elementem � będzie zdanie ą �! �,
to otwarta będzie gałąz
, po prawej stronie której znajduje się ą lub
otwarta będzie gałąz
, po lewej stronie której znajduje się �. Zgodnie
z założeniem ą dla interpretacji I przyjmuje wartość f lub � dla tej
interpretacji przyjmuje wartość t. Zatem dla interpretacji I zdanie
ą �! � przyjmuje wartość t. Niech teraz zdanie ą �! � będzie elemen-
tem Ł. Zdanie ą znajdzie się po lewej, a zdanie � po prawej stronie
gałęzi. Zgodnie z założeniem dla interpretacji I zdanie ą przyjmuje
wartość t, a zdanie � przyjmuje wartość f. Zdanie ą �! � dla inter-
pretacji I przyjmuje wartość f. Podobnie pokazuje się zachodzenie
naszej tezy dla pozostałych spójników.
Teraz pokażemy, że zachodzi teza: jeżeli istnieje interpretacja 
oznaczmy ją I  taka, że wszystkie zdania ze zbioru �, zapisane po
lewej stronie pnia przyjmują dla tej interpretacji wartość t awszystkie
zdania ze zbioru Ł, zapisane po prawej stronie pnia przyjmują wartość
f, to tablica semantyczna jest otwarta.
62 1. KLASYCZNA LOGIKA ZDAC

Dla dowodu pokażemy, że istnieje otwarta gałąz
 oznaczmy ją
GI  taka, że dla interpretacji I wszystkie zdania znajdujące się po
jej lewej stronie przyjmują wartość t, a wszystkie zdania znajdujące
się po jej prawej stronie przyjmują wartość f.
Sytuacja jest prosta w wypadku, gdy elementami � i Ł są wy-
łącznie litery zdaniowe. Załóżmy, że teza zachodzi dla zdań o długości
nie większej niż k. Pokażemy, że zachodzi dla zdań o długości (k +1).
Jeżeli zdanie Źą należy do zbioru �, to ą piszemy po stronie prawej.
Jeżeli zaś Źą należy do Ł, to ą piszemy po stronie lewej. Jeżeli ą �! �
należy do �, to ą piszemy po stronie prawej jednej gałęzi, zaś � po
stronie lewej drugiej gałęzi. Odpowiednio postępujemy z pozostałymi
spójnikami. Uzyskujemy dwa zbiory zdań � i Ł , których elementami
są zdania nie dłuższe niż k. Dla tych zbiorów, zgodnie z założeniem,
zachodzi teza dowodzonego twierdzenia, czyli istnieje taka otwarta
gałąz
, że wszystkie zdania przyjmują wartość odpowiadającą stronie,
na której się znajdują. Jeżeli istniała interpretacja taka, że dla tej
interpretacji wszystkie zdania z � przyjmowały wartość t, a wszyst-
kie zdania z Ł wartość f, to dla tej interpretacji również zdania z �
przyjmują wartość t a zdania z Ł przyjmują wartość f. Zgodnie z
założeniem dla zbiorów � i Ł istnieje otwarta gałąz
a z tego wynika,
że również taka gałąz
istnieje dla � i Ł.
W szczególnym wypadku może być tak, że zbiór � jest pusty, a
zbiór Ł ma dokładnie jeden element. Pytanie o to, czy może być tak,
że wszystkie zdania z � mają wartość t, a wszystkie zdania z Ł mają
wartość f jest wówczas pytaniem o to, czy możliwa jest interpretacja
taka, że zdanie z Ł ma wartość f. Pytanie to jest więc pytaniem o to,
czy ten jedyny element Ł jest tautologią.
Zdanie ą jest tautologią wtedy i tylko wtedy, gdy zamknięta jest
tablica semantyczna ze zdaniem ą jako zdaniem początkowym
znajdującym się po prawej stronie pnia.
W wypadku, gdy zbiór � jest jednoelementowy, a zbiór Ł jest
pusty pytanie o możliwość interpretacji takiej, że wszystkie zdania z
� mają wartość t, a zdania z Ł mają wartość f jest pytaniem o to,
czy zdanie będące jedynym elementem � jest kontrtautologią.
Zdanie ą jest kontrtautologią wtedy i tylko wtedy, gdy zamknięta
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 63
jest tablica semantyczna ze zdaniem ą jako zdaniem początko-
wym znajdującym się po lewej stronie pnia.
Zauważmy, że podane reguły analizy zdań są tego rodzaju, że
w wyniku ich zastosowania uzyskujemy zdanie lub zdania prostsze
niż zdanie, do którego reguły są stosowane, a ponadto zdanie, do
którego zastosowano odpowiednią regułę staje się martwe, czyli nie
może być przedmiotem ponownego zastosowania któreś z reguł. Pro-
ces budowy tablicy semantycznej zawsze więc będzie mógł być za-
kończony. W szczególności, w wyniku stosowania reguł otrzymamy
litery zdaniowe. Oznacza to nic innego, jak tylko to, że rozstrzygalny
jest problem, czy mając skończony zbiór zdań języka rachunku zdań
możliwa jest taka interpretacja żeby każde z tych zdań miało wska-
zaną dla niego wartość logiczną. Jeżeli zostaną wyczerpane wszystkie
możliwości stosowania podanych reguł i tablica jest zamknięta to taka
możliwość jest wykluczona. Jeżeli zaś tablica pozostaje nie zamknięta
(gdy chociaż jedna gałąz
nie jest zamknięta), to wówczas możliwe jest
jednoczesne przysługiwanie wskazanych wartości wszystkim zdaniom
zbioru zdań będącego przedmiotem analizy. Ażeby wskazać interpre-
tację, dla której to ma miejsce, wystarczy wziąć pod uwagę jedną z nie
zamkniętych gałęzi i literze zdaniowej przypisać wartość t, gdy litera
ta znajduje się po lewej stronie, a wartość f, gdy litera ta znajduje się
po prawej stronie gałęzi. W wypadku liter zdaniowych występujących
w zdaniu, a nie występujących na rozważanej gałęzi, wystarczy wziąć
dowolną literę t lub f.
PYTANIE:
Czy tautologią jest zdanie
((p '" (q (" r)) �! ((p '" q) (" (p '" r)))?
TABLICA SEMANTYCZNA
64 1. KLASYCZNA LOGIKA ZDAC

Zdanie
((p '" (q (" r)) �! ((p '" q) (" (p '" r)))
jest tautologią.
PYTANIE:
Czy możliwa jest taka interpretacja, by zdaniu Ź(p �! q) przysłu-
giwała wartość f w wypadku, gdy zdaniom (p �!Ź(q �! r)) i r
przysługuje wartość t?
Problem ten można w sposób równoważny sformułować następu-
jąco:
Czy tautologią jest zdanie
(((p �!Ź(q �! r)) '" r) �!Ź(p �! q))?
Z tego zdania po zastosowaniu właściwych reguł otrzymalibyśmy
zdania, od których rozpoczynamy konstrukcję.
TABLICA SEMANTYCZNA
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 65
ODPOWIEDy
:
Wykluczona jest interpretacja taka, żeby zdaniom (p �!Ź(q �!
r)) i r przysługiwała wartość t a zdaniu Ź(p �! q) przysługiwała
wartość f (lub, równoważnie, zdanie
(((p �!Ź(q �! r)) '" r) �!Ź(p �! q))
jest tautologią).
PYTANIE:
Czy tautologią jest zdanie
((p �! q) �! (Źp �!Źq))?
TABLICA SEMANTYCZNA
ODPOWIEDy
:
66 1. KLASYCZNA LOGIKA ZDAC

Zdanie
((p �! q) �! (Źp �!Źq))
nie jest tautologią.
Zdanie ((p �! q) �! (Źp �!Źq)) przyjmuje wartość f dla interpre-
tacji takiej, że p przyjmuje wartość f a q wartość t.
�
Metoda tablic semantycznych zwykle jest sprawniejsza niż me-
toda zero-jedynkowa wprost. Tak, czy owak liczba operacji rośnie
wykładniczo w zależności od długości zdania. Choć więc problem, czy
zdanie jest tautologią jest rozstrzygalny, to jednak nie jest on prak-
tycznie rozstrzygalny w tym sensie, że oczekiwanie na wynik traci
sens w perspektywie nie tylko życia człowieka. Metoda zero-jedyn-
kowa jest algorytmem, działającym w czasie wykładniczym. Oznacza
to np., że gdyby wykonanie jednej operacji trwało jeden chronom
(10-43 s.), to wykonanie 2n operacji dla n = 200 przekracza czas życia
człowieka, a dla n = 500 przekracza wiek wszechświata. Podziele-
nie zadania i wykonywanie go przez wiele komputerów też sprawy nie
rozwiązuje. Zawsze można wskazać takie n, żeby mimo wykorzystania
wszystkich istniejących maszyn czas wykonania zadania przekraczał
z góry zadaną granicę. Tradycyjnie problem obliczeniowy uważa się
za praktycznie rozwiązywalny, gdy istnieje stała k taka, że dla n da-
nych algorytm wymaga wykonania co najwyżej nk operacji. O takich
algorytmach mówi się, że działają w czasie wielomianowym. Jak na
razie nie udało się znalez
ć takiego algorytmu dla rozstrzygania, czy
dane zdanie jest tautologią.
1.1.8. Elektronowa interpretacja spójników zdaniowych46
Rachunek zdań znalazł interesujące zastosowanie techniczne w
maszynach matematycznych. Wartości logiczne zdań złożonych w za-
46
W akademickim podręczniku logiki o takiej interpretacji pisał H. Greniew-
ski [1955]. Warto tu wspomnieć, że H. Greniewski jeszcze jako doktor stanął na
czele Grupy Aparatów Matematycznych w Instytucie Matematyki w Warszawie.
Pierwszym znaczącym osiągnięciem tej grupy była budowa maszyny ARR w 1954.
Był to pierwszy polski komputer użytkowy (a nie tylko eksperymentalny).
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 67
leżności od spójnika i wartości logicznych zadań-argumentów można
interpretować jako opis działania pewnych układów elektronowych.
Wez
my układ, który ma wejścia p1, p2, . . . , pn oraz jedno wyjście.
Układ taki można graficznie przedstawić następująco:
Przyjmuje się, że każde z wejść może znajdować się w jednym
z dwóch stanów. Są to dwa rozróżnialne stany fizyczne. Mogą nimi
być np. pary: impuls, brak impulsu; napięcie v1, napięcie v2 (v1 = v2).

Stany te można oznaczać: 0, 1. Ponadto zakłada się, że układy te
działają bezczasowo, tzn. że stan wyjścia nie zależy od czasu prze-
twarzania danych na wejściu, a jedynie od stanów wejść. Takie układy
to sieci logiczne.
Związki między wartościami logicznymi zdań-argumentów a war-
tością logiczną zdania złożonego opisywane są przez tablicę. Sieć lo-
giczna realizuje tablicę, jeśli mając na wejściu wartości przyporząd-
kowane zdaniom-argumentom, na wyjściu ma stan odpowiadający
wartości logicznej zdania złożonego.
Układami (sieciami) podstawowymi są sieci realizujące tablice ne-
gacji, alternatywy i koniunkcji.
Zasadniczym problemem teorii sieci logicznych jest określenie za-
sad budowy sieci złożonych z układów podstawowych, realizującej do-
wolną zadaną tablicę. Jest to tzw. problem syntezy sieci logicznych.
Sprowadza się on do podania odpowiadającego danej tablicy zdania
rachunku zdań zbudowanego za pomocą spójników negacji, alterna-
68 1. KLASYCZNA LOGIKA ZDAC

tywy i koniunkcji. Dla takiego zdania konstruuje się sieci z układów
podstawowych, np. dla zdania
(p ("Źq) '" (Źp (" q)
możemy mieć następującą sieć:
Okazuje się, że jest nieskończenie wiele sieci zbudowanych z ukła-
dów podstawowych, które realizują daną tablicę. W związku z tym
kolejnym ważnym problemem jest znalezienie takiego rozwiązania,
które spełnia pewne dodatkowe warunki. Głównie chodzi o warunek
minimalizacji elementów podstawowych. Taka jest istota tzw. pro-
blemu minimalizacji sieci. Problem ten nie jest w ogólności rozwią-
zany.
Prostym problemem związanym z sieciami logicznymi jest okre-
ślenie zdania dla zadanej sieci. Innym problemem jest budowa sieci,
której elementy podstawowe oparte są na binegacji (zdaniu złożonemu
przysługuje wartość t wtedy i tylko wtedy, gdy obu jego zdaniom-ar-
gumentom przysługuje wartość f47 )albo dysjunkcji Sheffera (zdaniu
złożonemu przysługuje wartość f wtedy i tylko wtedy, gdy obu jego
zdaniom-argumentom przysługuje wartość t48 ).
Z teorii sieci logicznych wywodzi się teoria sieci neuronowych
znajdujących zastosowanie, np. w biologii.
47
Por. rozdz.  Spójniki prawdziwościowe .
48
Por. rozdz.  Spójniki prawdziwościowe .
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 69
1.1.9. Tautologia a zdanie logicznie prawdziwe
TWIERDZENIE 2. (O PEA
NOŚCI).
ą wtedy i tylko wtedy, gdy |= ą,
czyli
ą jest tautologią
wtedy i tylko wtedy, gdy
ą jest logicznie prawdziwe.
DOWÓD
Wpierw udowodnijmy, że
(A) jeżeli ą, to |= ą,
a następnie, że
(B) jeżeli |= ą, to ą.
Niech ą będzie zdaniem, którego wszystkie litery zdaniowe znaj-
dują się wśród (n +1) liter: p0, p1, . . . , pn.
(A) Pokażemy, że jeżeli ą nie jest prawdziwe w jakimś modelu, to
istnieje interpretacja taka, że ą dla tej interpretacji przyjmuje wartość
f.
Wez
my dowolny model M. Niech vM0, vM1, . . . , vMn będzie inter-
pretacją taką, że vMm = t wtedy i tylko wtedy, gdy pm jest elementem
M (pm "M), czyli vMm = f wtedy i tylko wtedy, gdy pm nie jest ele-
mentem M (pm "M).

Pokażemy, że
M|= ą wtedy i tylko wtedy,
gdy ą dla interpretacji vM0, vM1, . . . , vMn przyjmuje wartość t.
Dowodzić będziemy przez indukcję ze względu na długość zdania.
W wypadku, gdy ą jest literą zdaniową, to zgodnie z określeniem
interpretacji vM0, vM1, . . . , vMn stwierdzamy, że M|= ą wtedy i tylko
wtedy, gdy ą przyjmuje wartość t.
ZAA
OŻENIE INDUKCYJNE: Niech M|= � wtedy i tylko wtedy,
gdy � dla interpretacji vM0, vM1, . . . , vMn przyjmuje wartość t oraz
70 1. KLASYCZNA LOGIKA ZDAC

M|= ł wtedy i tylko wtedy, gdy ł dla interpretacji vM0, vM1, . . . , vMn
przyjmuje wartość t.
(AŹ) Niech ą będzie zdaniem: Ź�.
(AŹ1) Niech M|= ą. Z definicji |= dostajemy, że nie zachodzi M|= �.
Z założenia indukcyjnego otrzymujemy, że zdanie � dla interpretacji
vM0, vM1, . . . , vMn przyjmuje wartość f, a zatem zdanie ą (Ź�) dla tej
interpretacji przyjmuje wartość t.
(AŹ2) Niech ą dla interpretacji vM0, vM1, . . . , vMn przyjmuje wartość
t. A więc � przyjmuje wartość f. Z założenia indukcyjnego wynika
więc, iż nie zachodzi M|= �, a zatem zachodzi M|= ą (Ź�).
(A�!) Niech ą będzie zdaniem: � �! ł.
(A�!1) Niech nie zachodzi M|= ą. Z definicji |= wynika, że zachodzi
M|= � oraz że nie zachodzi M|= ł. Korzystając z założenia induk-
cyjnego dostajemy, że � dla interpretacji vM0, vM1, . . . , vMn przyjmuje
wartość t zaś ł dla tej interpretacji przyjmuje wartość f. Z tego więc
dostajemy, że dla interpretacji vM0, vM1, . . . , vMn zdanie ą (� �! ł)
przyjmuje wartość f.
(A�!2) Niech ą dla interpretacji vM0, vM1, . . . , vMn przyjmuje war-
tość f. Pokażemy, że nie zachodzi M|= ą. Mamy bowiem, że � dla
tej interpretacji przyjmuje wartość t zaś ł przyjmuje wartość f. Ko-
rzystając z założenia indukcyjnego dostajemy, że zachodzi M|= � a
nie zachodzi M|= ł, a więc nie zachodzi również M|= ą (� �! ł).
W wypadku koniunkcji postępujemy podobnie jak w wypadku
negacji, zaś w wypadku alternatywny podobnie jak w wypadku im-
plikacji. Z równoważnością możemy postępować jak z negacją, czyli
zakładać, że M|= � �! ł a następnie zakładać, że dla interpretacji
vM0, vM1, . . . , vMn zdanie � �! ł przyjmuje wartość t. Możemy rów-
nież postępować jak w wypadku implikacji, czyli zakładając wpierw,
że nie zachodzi M|= � �! ł a następnie zakładając, że dla interpre-
tacji vM0, vM1, . . . , vMn zdanie � �! ł przyjmuje wartość f.
Teraz dowodzimy, że
(A) jeżeli ą, to |= ą,
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 71
Załóżmy więc, że ą. Gdyby nie zachodziło |= ą, to istniałby model
M taki, że ą nie byłoby w nim prawdziwe. Zgodnie z powyższym
dla interpretacji vM0, vM1, . . . , vMn zdanie ą przyjmowałoby wartość
f, a to przeczyłoby założeniu. Zatem ą jest prawdziwe we wszystkich
modelach, czyli |= ą.
Aby dowieść, że
(B) jeżeli |= ą, to ą
pokażemy, że jeżeli ą dla jakiejś interpretacji przyjmuje wartość f, to
istnieje model taki, że ą nie jest w tym modelu prawdziwe.
Niech v0, v1, . . . , vn będzie dowolną interpretacją. Niech Mv bę-
dzie modelem takim, że pm " Mv wtedy i tylko wtedy, gdy vm = t.
Twierdzimy, iż
ą dla interpretacji v0, v1, . . . , vn przyjmuje wartość t
wtedy i tylko wtedy, gdy Mv |= ą.
Fakt ten może być dowiedziony przez indukcję w analogiczny
sposób jak dowodziliśmy, że
M|= ą wtedy i tylko wtedy,
gdy ą dla interpretacji vM0, vM1, . . . , vMn przyjmuje wartość t.
Zauważmy jednak, że vMm = t wtedy i tylko wtedy, gdy vm = t. Fakt
ten jest więc oczywistym wnioskiem z powyższego.
Załóżmy, że |= ą. Gdyby istniała interpretacja v taka, że ą dla tej
interpretacji nie przyjmowałoby wartości t, toą nie byłoby prawdziwe
w modelu Mv, a to przeczyłoby założeniu. Zatem ą dla wszystkich
interpretacji przyjmuje wartość t, czyli ą.
Dowiedzione twierdzenie pozwala zastąpić semantyczne poję-
cie logicznej prawdziwości syntaktycznym pojęciem tautologiczności.
Twierdzenie to umożliwia nam opuszczenie dowodu, że zdanie jest lo-
gicznie prawdziwe jeżeli wiadomo, że jest ono tautologią. Jest to wy-
padek analogiczny do rachunków arytmetycznych, gdy opuszczamy
dowód, że np. liczba wyrachowana w pisemnym dodawaniu jest sumą
liczb, których nazwy zapisane w języku systemu dziesiętnego były
obiektami pisemnego dodawania. Po prostu wystarczyło raz dowieść,
że reguły rachowania zawsze prowadzą do (rzeczywistej) sumy.
72 1. KLASYCZNA LOGIKA ZDAC

Ponieważ rozstrzygalny jest problem, czy zdanie jest tautologią,
więc na podstawie twierdzenia o pełności jest jasne, że również roz-
strzygalny jest problem, czy zdanie jest logicznie prawdziwe.
1.1.10. Spójniki prawdziwościowe
(DEF. spójnika prawdziwościowego) Spójnik prawdziwościowy to
spójnik taki, że wartość logiczna zdania złożonego zbudowanego za
pomocą tego spójnika jest wyznaczona przez wartości logiczne zdań-
-argumentów tego spójnika.
Na to, aby określić wartość logiczną zdania  nieprawda, że ą
wystarczy znać wartość logiczną zdania ą. Fraza  nieprawda, że . . . 
jest spójnikiem prawdziwościowym.
Przykładem dwuargumentowego spójnika, który nie jest prawdzi-
wościowy może być spójnik  z tego, że . . . wynika, że . . .  . Wartość
logiczna zdania  z tego, że ą wynika, że � jest określona w wypadku,
gdy ą jest prawdziwe a � jest fałszywe; zdanie to wówczas jest fał-
szywe. W pozostałych możliwych wypadkach układów wartości zdań
ą i �, wartość logiczna zdania złożonego nie jest określona przez war-
tości logiczne zdań-argumentów. Spójnik implikacji jest prawdziwo-
ściowy, nie należy go więc mylić z omówionym spójnikiem49 .
Spójniki: Ź, �!, (", '", �! są spójnikami prawdziwościowymi.
49
W fundamentalnym dla współczesnej logiki dziele B. Russella i A. N. Whi-
teheada Principia Mathematica, którego pierwszy tom ukazał się w 1910 r. wy-
rażenie  ą �! � jest odczytywane jako  z ą wynika � . Oczywiście prowadzi to
do paradoksów, tautologią jest bowiem zdanie: (ą �! �) (" (� �! ą)  znaczyłoby
to, że dla dowolnych dwóch zdań choć jedno z nich musiałoby wynikać z drugiego.
Jako reakcja przeciw tej interpretacji powstają systemy implikacji ścisłej Lewisa
(1918). Implikacja ścisła definiowana jest następująco:
ą z" � =df ŹM(ą '"Ź�),
gdzie M znaczy:  jest możliwe, że .
Spójnik implikacji ścisłej miałby wiernie odwzorowywać stosunek wynikania 
zdanie złożone zbudowane za pomocą tego spójnika miałoby być prawdziwe wtedy
i tylko wtedy, gdy między poprzednikiem a następnikiem tej implikacji zacho-
dziłby stosunek wynikania. Systemy implikacji ścisłej dały początek próbom bu-
dowy systemów ze szczególnie rozumianym spójnikiem implikacji.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 73
(DEF. równości spójników) Dwa spójniki są (ekstensjonalnie) równe,
wtedy i tylko wtedy, gdy zawsze dla tych samych zdań-argumentów
wartość logiczna zdań złożonych zbudowanych za pomocą tych spój-
ników jest taka sama.
Można obliczyć, że są dokładnie cztery (teoretycznie możliwe)
ekstensjonalnie różne jednoargumentowe spójniki prawdziwościowe.
Takich spójników dwuargumentowych jest szesnaście. Ogólnie, jest
n
22 ekstensjonalnie różnych n-argumentowych spójników prawdziwo-
ściowych (n =1, 2, 3, . . .).
Spośród teoretycznie możliwych spójników prawdziwościowych
wzięliśmy pod uwagę tylko pięć. Decyzja na taki wybór podyktowana
jest tym, że spójniki te:
(1) wystarczają do wypowiedzenia wszystkich teoretycznie możli-
wych spójników prawdziwościowych;
(2) umożliwiają zręczne stylistycznie formułowanie zdań, które bu-
dujemy w języku ze spójnikami prawdziwościowymi, jak np. ma
to miejsce w języku matematyki klasycznej. Okazuje się bowiem,
że na to, by zachodziło (1), można by wziąć jeszcze mniej spój-
ników.
Wyjaśnijmy intuicyjnie, co to znaczy, że jakiś spójnik można wy-
razić za pomocą innych spójników. Wez
my dla przykładu spójnik
dwuargumentowy �! taki, że zdanie złożone zbudowane za pomocą
tego spójnika ma wartość t wtedy i tylko wtedy, gdy obu zdaniom-
-argumentom przysługuje wartość f.
(DEF. �!) Spójnik �! jest charakteryzowany przez następującą tabelkę
wartości logicznych:
� ł � �! ł
t t f
t f f
f t f
f f t
Na odczytanie spójnika �!, określanegojakobinegacja, jednoczesne
zaprzeczenie lub funktor A
ukasiewicza, znajdujemy wyrażenie  ani
74 1. KLASYCZNA LOGIKA ZDAC

. . . , ani . . .  . Takie bowiem znaczenie musimy przypisać temu wy-
rażeniu choćby w takich zwrotach języka polskiego jak:  ani słychu,
ani widu o nim ,  ani mnie to grzeje, ani ziębi . Kierując się wyłącz-
nie intuicją znaczeń wyrażeń języka polskiego zauważmy, iż zamiast
powiedzieć, np.  ani Jan zdolny, ani pracowity 50 możemy z zachowa-
niem myśli zawartej w tym zdaniu powiedzieć  Jan nie jest zdolny i
nie jest pracowity . Różnica pomiędzy obu zdaniami jest tylko różnicą
stylu. Rekonstruując i uogólniając przykład stwierdzamy, że zdanie
 ani ą, ani � jest równoważne zdaniu  nieprawda, że ą i nie prawda,
że � . A
atwo również obliczyć, że spójnik �! przyporządkowuje zda-
niu złożonemu ą �! � taką samą wartość logiczną, jaka przysługuje
zgodnie z tabelkami dla negacji i koniunkcji zdaniu Źą '"Ź�. Problem
wyrażenia jakiegoś n-argumentowego spójnika prawdziwościowego s
przez inne spójniki polega więc na tym, żeby znalez
ć zdanie zbudo-
wane za pomocą tych innych spójników i (niekoniecznie wszystkich i
niekoniecznie tylko) zdań-argumentów spójnika s takie, aby dla każ-
dej interpretacji wartości logiczne tego zdania i zdania zbudowanego
za pomocą spójnika s były takie same.
1.1.11. Funkcjonalna pełność
Nim pokażemy, że wszystkie teoretycznie możliwe spójniki praw-
dziwościowe dadzą się wyrazić za pomocą tylko trzech spójników:
negacji, alternatywy i koniunkcji, podajmy twierdzenie, z którego bę-
dziemy korzystać w dowodzie tego faktu.
Niech ą/�/ oznacza, że � jest odcinkiem ciągu symboli ą.
TWIERDZENIE 3 (O ZAST
POWANIU).
Niech ą i � będą zdaniami i niech ą/�/.
Jeżeli � �! ł, to ą/�/ �! ą/ł/.
Twierdzenie to głosi, że jeżeli w zdaniu ą zastąpimy, będący zda-
niem, występujący w nim ciąg symboli � ciągiem symboli ł takim,
50
Zgodnie z frazeologią języka polskiego powiemy:  Ani Jan nie jest zdolny, ani
nie jest pracowity . Podobnie jest w wypadku innych spójników języka rachunku
zdań  w zależności od kontekstu mogą być wyrażane inaczej niż to ustaliliśmy
jako sposób ich odczytywania.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 75
że zdania � i ł są równoważne ( � �! ł), to otrzymamy zdanie ą/ł/
równoważne zdaniu ą ( ą/�/ �! ą/ł/).
DOWÓD
Dowodzić będziemy przez indukcję po konstrukcji zdania ą.
Niech ą będzie zdaniem �. Po zastąpieniu � przez ł otrzymamy
zdanie ł. Ponieważ z założenia � �! ł, więc ą/�/ �! ą/ł/.
ZAA
OŻENIE INDUKCYJNE: Niech dla ą1, jeżeli � �! ł, to
ą1/�/ �! ą1/ł/. Ponadto ą2 �! ą2, co jest oczywiste.
(Ź) Jeżeli ą jest zdaniem Źą1 a � �! ł, to na podstawie założenia
indukcyjnego mamy, że dla dowolnej interpretacji wartość logiczna
ą1/�/ jest taka sama, jak wartość logiczna ą1/ł/. Zatem dla dowolnej
interpretacji wartość logiczna Źą1/�/ jest taka sama, jak Źą1/ł/, czyli
ą/�/ �! ą/ł/.
Dla wszystkich spójników dwuargumentowych postępujemy po-
dobnie. Rozważmy więc tylko wypadek alternatywy.
((") Jeżeli ą jest zdaniem ą1 ("ą2 a � �! ł, to na podstawie założenia
indukcyjnego dla dowolnej interpretacji wartość logiczna ą1/�/ jest
taka sama, jak wartość logiczna ą1/ł/. Zatem dla dowolnej interpre-
tacji wartość logiczna ą1/�/ (" ą2 jest taka sama, jak wartość logiczna
ą1/ł/ (" ą2, czyli ą/�/ �! ą/ł/.
Podobnie postępujemy, gdy ą jest zdaniem ą2 (" ą1.
TWIERDZENIE 4 (O FUNKCJONALNEJ PEA
NOŚCI).
Zbiór spójników {Ź, (", '"} jest funkcjonalnie pełny, czyli dla do-
wolnego zdania ą, w którym występują tylko spójniki prawdziwo-
ściowe istnieje jemu logicznie równoważne zdanie � ( ą �! �), w
którym występują tylko spójniki: Ź, (", '".
DOWÓD
Niech dany będzie n-argumentowy spójnik prawdziwościowy s.
Niech spójnik ten będzie charakteryzowany przez następującą tabelkę
wartości logicznych:
76 1. KLASYCZNA LOGIKA ZDAC

ą1 ą2 . . . ąn s(ą1, ą2, . . . , ąn)
1 1 1
v1 v2 . . . vn v1
. . . . . . . . . . . . . . .
j j
j
v1 v2 . . . vn vj
. . . . . . . . . . . . . . .
2n 2n 2n
n
v1 v2 . . . vn v2
Dowodzić będziemy przez indukcję po długości zdania ą. Budo-
wać będziemy takie zdanie ą równoważne zdaniu ą, w którym wy-
stępują tylko spójniki: Ź, (" i '".
Rozważmy wpierw wypadek, gdy ą jest zdaniem, w którym wy-
stępuje tylko spójnik s (wszystkie argumenty spójnika s są literami
zdaniowymi).
n
W wypadku, gdy wszystkie wartości v1, . . . , vj, . . . , v2 , jakie przyj-
muje ą są równe f, to jako ą bierzemy koniunkcję wszystkich wystę-
pujących w ą liter zdaniowych i ich negacji. Zdanie to dla dowolnej
interpretacji przyjmuje wartość f. Jest zatem równoważne zdaniu ą.
j j
j
Niech teraz dla jakiegoś układu wartości v1, v2, . . . , vn zdanie ą
j j
j
przyjmuje wartość t. Dla każdego układu wartości v1, v2, . . . , vn (j =
1, . . . , 2n), dla którego ą przyjmuje wartość t bierzemy koniunkcję liter
j j
zdaniowych pi, gdyvi przyjmuje wartość t i Źpi, gdyvi przyjmuje war-
tość f. Koniunkcja ta przyjmuje wartość t wtedy i tylko wtedy, gdy
j
litera zdaniowa pi przyjmuje wartość vi , (i = 1, . . . , n; j = 1, . . . , 2n).
Alternatywa wszystkich takich koniunkcji jest równoważna zdaniu ą.
ZAA
OŻENIE INDUKCYJNE: Niech �1, . . . �n będą zdaniami takimi,

że istnieją równoważne im zdania, odpowiednio, �i, . . . , �n zbudo-
wane tylko za pomocą spójników: Ź, (", '". Niech ą będzie zdaniem
s(�1, . . . , �n). Postępujemy podobnie jak w wypadku, gdy argumen-
tami s były litery zdaniowe. Tym razem jednak zamiast liter zdanio-

wych bierzemy zdania �1, . . . , �n i ich negacje. Korzystając z założenia
indukcyjnego i tw. 3 stwierdzamy, że uzyskane konstrukcje są równo-
ważne zdaniu ą.
Można pokazać, że
WNIOSEK
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 77
Każdy ze zbiorów spójników {Ź, ("}51, {Ź, '"}, {Ź, �!} jest funkcjo-
nalnie pełny.
W dowodzie wystarczy skorzystać z równoważności:
(ą '" �) �!Ź(Źą ("Ź�)
(ą (" �) �!Ź(Źą '"Ź�)
(ą �! �) �! (Źą (" �)
(ą (" �) �! (Źą �! �)
(ą �! �) �!Ź(ą '"Ź�)
(ą '" �) �!Ź(ą �!Ź�).
Żaden inny dwuelementowy zbiór zawierający tylko spójniki: Ź,
(", '", �!, �! nie jest funkcjonalnie pełny. W tym celu wystarczy po-
kazać, że
TWIERDZENIE 5.
Zbiory: {(", '", �!, �!}, {Ź, �!} nie są funkcjonalnie pełne.
DOWÓD
Aby pokazać, że zbiór {(", '", �!, �!} nie jest funkcjonalnie pełny
przez indukcję po długości zdania dowodzimy, że każde zdanie zbu-
dowane wyłącznie za pomocą spójników (" i '" oraz �! i �! (a także,
oczywiście, liter zdaniowych) dla interpretacji takiej, że wszystkie li-
tery zdaniowe przyjmują wartość t przyjmuje wartość t.
Niech ą będzie dowolnym zdaniem, w którym występują jedynie
spójniki: (", '", �!, �!.
1. Jeżeli ą jest literą zdaniową, to ą ma wartość t.
2. Niech � i ł przysługuje wartość t. Gdy ą jest zdaniem postaci
�("ł, wówczas ą przysługuje wartość t. Podobnie, gdy ą ma postać
� '" ł, � �! ł lub � �! ł. Stwierdzamy więc, że dla zdania Źp nie
istnieje zdanie jemu logicznie równoważne zbudowane wyłącznie
51
Twierdzenie o funkcjonalnej pełności zbioru spójników {Ź, ("}  przyjętych
jako pierwotne w Principia Mathematica Russella i Whiteheada  podał E. Post
w swojej dysertacji doktorskiej obronionej na Columbia University w 1920 r. i
póz
niej opublikowanej, Post [1921].
78 1. KLASYCZNA LOGIKA ZDAC

za pomocą spójników alternatywy i koniunkcji oraz implikacji i
równoważności.
Aby dowieść, że zbiór {Ź, �!} nie jest funkcjonalnie pełny, wystar-
czy pokazać, że każde zdanie ą zbudowane przy użyciu tylko spójni-
ków negacji i równoważności przyjmuje wartość t tyle samo razy, ile
razy przyjmuje wartość f albo przyjmuje te wartości parzystą liczbę
razy52 . Faktu tego dowodzimy przez indukcję po długości zdania.
Litery zdaniowe przyjmują wartość t tyle samo razy, ile razy
przyjmują wartość f. Niech ą i � spełniają założenia. Wypadek zda-
nia Źą jest prosty. Jeżeli ą przyjmuje wartość t tyle samo razy, ile
razy przyjmuje wartość f, to tak samo jest w wypadku Źą. Jeżeli ą
przyjmuje wartość t parzystą liczbę razy, to z faktu, że liczba wszyst-
kich interpretacji jest parzysta wynika, że ą również parzystą liczbę
razy przyjmuje wartość f, zatem tak samo jest w wypadku Źą.
Gdy ą przyjmuje wartość t tyle samo razy, ile razy przyjmuje
wartość f i podobnie jest dla �, to  ponieważ wszystkich interpretacji
jest parzysta liczba  zdanie ą �! � przyjmuje wartości t i f parzystą
liczbę razy. Gdy dla zdania ą �! � istnieje więcej niż dwie (różne)
interpretacje, to dla tych interpretacji zarówno ą jak i � przyjmują
wartość t( lub f) parzystą liczbę razy. Z tego wynika, że również ą �! �
przyjmuje wartość t( lub f) parzystą liczbę razy.
Zbiór {Ź, �!} nie jest funkcjonalnie pełny, bowiem za pomocą
spójników z tego zbioru nie skonstruujemy np. zdania, które przy-
biera wartość t trzykrotnie, jak jest to w wypadku zdania p �! q.
Okazuje się, że sam spójnik �! (ani . . . , ani . . . ) wystarcza dla
konstrukcji zdań logicznie równoważnych zdaniom zbudowanym za
pomocą jakichkolwiek (nawet tylko dających się pomyśleć) spójni-
ków prawdziwościowych53 . Pokazano również, że taką samą własność
52
Wypadek, gdy nie przyjmuje jednej z wartości  inaczej mówiąc  gdy przyj-
muje ją 0 razy traktujemy jako wypadek wystąpienia tej wartości parzystą liczbę
razy.
53
Ch. S. Peirce w nie opublikowanym artykule z ok. 1880 r. (A Boolean Algebra
with One Constant, Collected Papers, IV, żż12 20, s. 13 18) określił język z jedną
tylko stałą, którą możemy uznać za dwuargumentowy spójnik  ani . . . , ani . . .  .
Peirce nie podał jednak ścisłego dowodu, że zbiór{�!} jest funkcjonalnie pełny.
1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE 79
ma także spójnik zwany kreską Sheffera, oznaczany |, a odczytywany
 albo nie . . . albo nie . . .  54 . Spójnik ten jest charakteryzowany na-
stępującą tabelką:
� ł � | ł
t t f
t f t
f t t
f f t
Dla ciekawości dodajmy, że oprócz  ani . . . , ani . . .  i  albo nie
. . . albo nie . . .  żaden inny co najwyżej dwuargumentowy spójnik
sam jeden nie wystarcza dla wypowiedzenia wszystkich pozostałych
spójników prawdziwościowych55 .
1.1.12. Postacie normalne
Zdania o postaci opisanej w dowodzie twierdzenia o funkcjonalnej
pełności mają szczególną budowę. Taką budowę mają zdania o postaci
normalnej dysjunkcyjnej (alternatywnej).
(DEF. postaci normalnej dysjunkcyjnej) Zdanie ą ma postać nor-
malną dysjunkcyjną (alternatywną) wtedy i tylko wtedy, gdy ą jest
koniunkcją zdań, z których każde jest literą zdaniową lub literą zda-
niową poprzedzoną spójnikiem negacji, albo ą jest alternatywą takich
koniunkcji.
PRZYKA
AD
Zdaniem o postaci normalnej dysjunkcyjnej jest:
(p '" r) (" (p '" q '"Źr).
�
54
Ch. S. Peirce w nie opublikowanym artykule z 1902 r. (Collected Papers, IV,
ż265, s. 216) pokazał, że wszystko, co można wypowiedzieć za pomocą spójnika
 ani . . . , ani . . .  można wyrazić używając tylko  albo nie . . . albo nie . . .  .
Dowód, że zarówno spójnik �! jak i spójnik | same wystarczają dla wypowiedzenia
wszystkich zdań zbudowanych za pomocą spójników Ź i (" został podany w 1912 r.
przez H. M. Sheffera (1883 1964), który nie znał prac Peirce a. Zob. Sheffer [1913].
55
Twierdzenie to udowodnił E. Żyliński [1925].
80 1. KLASYCZNA LOGIKA ZDAC

(DEF. postaci normalnej koniunkcyjnej) Zdanie ą ma postać nor-
malną koniunkcyjną wtedy i tylko wtedy, gdy ą jest alternatywą zdań,
z których każde jest literą zdaniową lub literą zdaniową poprzedzoną
znakiem negacji, albo ą jest koniunkcją takich alternatyw.
PRZYKA
AD
Zdaniem o postaci normalnej koniunkcyjnej jest:
(p ("Źp (" q) '" (p ("Źq).
�
Z dowodu twierdzenia o funkcjonalnej pełności wynika, że każde
zdanie klasycznej logiki zdań daje się przedstawić w postaci normalnej
dysjunkcyjnej.
Dla każdego zdania sformułowanego w języku klasycznej logiki
zdań można skonstruować jemu logicznie równoważne zdanie o po-
staci alternatywnej normalnej oraz jemu logicznie równoważne zdanie
o postaci koniunkcyjnej normalnej. Konstrukcja takich zdań może być
przeprowadzana przez zastępowanie zdań składowych, z których jest
zbudowane dane zdanie ą w kolejnych krokach według podanych wzo-
rów (zdanie po lewej stronie znaku równości zastępowane jest przez
zdanie po jego prawej stronie)
Krok 1. ą �! � = (ą �! �) '" (� �! ą)
ą �! � = Źą (" �
Krok 2. ŹŹą = ą
Ź(ą (" �) = Źą '"Ź�
Ź(ą '" �) = Źą ("Ź�
Krok 3. ą (" (� '" ł) = (ą (" �) '" (ą (" ł)
Krok 3 . ą '" (� (" ł) = (ą '" �) (" (ą '" ł)
Krok 3 stosujemy w wypadku konstrukcji zdania o postaci nor-
malnej koniunkcyjnej, zaś Krok 3  w przypadku konstrukcji zdania
o postaci normalnej dysjunkcyjnej.
Do konstrukcji postaci normalnych można wykorzystać drzewa
analityczne.
W wypadku postaci normalnej dysjunkcyjnej konstruujemy drze-
wo zapisując po lewej stronie zdanie, którego normalną postać dys-
junkcyjną chcemy znalez
ć. Dla każdej gałęzi bierzemy koniunkcję,
1.2. WYNIKANIE SYNTAKTYCZNE 81
której wszystkimi i tylko członami są litery zdaniowe znajdujące się
po lewej stronie i negacje liter zdaniowych znajdujących się po prawej
stronie tej gałęzi. Alternatywa takich koniunkcji, dających się skon-
struować dla wszystkich i tylko gałęzi takiego drzewa analitycznego,
jest zdaniem o normalnej postaci dysjunkcyjnej równoważnym zdaniu
ą.
W wypadku postaci normalnej koniunkcyjnej konstruujemy drze-
wo zapisując po prawej stronie zdanie, którego normalną postać ko-
niunkcyjną chcemy znalez
ć. Dla każdej gałęzi bierzemy alternatywę,
której wszystkimi i tylko członami są litery zdaniowe znajdujące się
po prawej stronie i negacje liter zdaniowych znajdujących się po lewej
stronie tej gałęzi. Koniunkcja takich alternatyw, dających się skon-
struować dla wszystkich i tylko gałęzi takiego drzewa analitycznego,
jest zdaniem o normalnej postaci koniunkcyjnej równoważnym zdaniu
ą.
Dla danego zdania ą może być więcej niż jedno jemu równoważne
zdanie o postaci normalnej dysjunkcyjnej i więcej niż jedno jemu rów-
noważne zdanie o postaci normalnej koniunkcyjnej.
Zdanie o postaci normalnej koniunkcyjnej jest tautologią wtedy i
tylko wtedy, gdy na każdą alternatywę zdań będącą członem koniunk-
cji składa się jakaś litera zdaniowa pi oraz Źpi, a więc gdy wszystkie
człony koniunkcji są tautologiami.
Zauważmy, że zdanie o postaci normalnej dysjunkcyjnej jest
kontrtautologią wtedy i tylko wtedy, gdy alternatywę tworzą koniunk-
cje takie, że w każdej z nich występuje jakaś litera zdaniowa pi oraz
Źpi, a więc gdy wszystkie człony alternatywy są kontrtautologiami.
1.2. WYNIKANIE SYNTAKTYCZNE
Celem naszym jest skonstruowanie rachunku takiego, żeby sto-
sunek wynikania ze względu na reguły tego rachunku  będzie to
wynikanie syntaktyczne  wiernie odwzorowywał rzeczywisty, czyli
semantyczny stosunek wynikania. Zdefiniujemy teraz wynikanie syn-
taktyczne i udowodnimy kilka twierdzeń, które będą potrzebne w do-
wodzie uogólnionego twierdzenia o pełności, z którego prostym wnio-
82 1. KLASYCZNA LOGIKA ZDAC

skiem jest teza, że stosunek wynikania syntaktycznego pokrywa się
ze stosunkiem wynikania semantycznego.
1.2.1. Dowód w rachunku zdań
(DEF. reguły odrywania MP)56 Podstawową regułą syntaktyczną
(operacją na napisach) będzie reguła odrywania (MP, modus ponens):
ze zdań ą i ą �! � wyprowadzalne jest zdanie �.
Zdanie ą daje się wyprowadzić ze zdań � i ł za pomocą reguły
odrywania, gdy ł jest zdaniem � �! ą.
(DEF. dowodu) Niech Ł będzie dowolnym (skończonym lub nieskoń-
czonym) zbiorem zdań. ą wynika syntaktycznie (daje się wyprowadzić
z, ma dowód z, jest konsekwencją) Ł, co oznaczamy: Ł ą, wtedy i
tylko wtedy, gdy istnieje taki skończony ciąg zdań ą0, ą1, . . . , ąn , że
ą = ąn oraz dla każdego i, 0 d" i d" n, spełniony jest jeden z warunków:
(I) ąi jest tautologią,
(II) ąi należy do Ł,
(III) istnieją j, k < i takie, że ąi daje się za pomocą reguły odrywania
wyprowadzić ze zdań ąj i ąk.
Ciąg ą0, ą1, . . . , ąn nazywamy dowodem z Ł zdania ą.
Ilość zdań-wyrazów ciągu dowodowego nazywamy długością do-
wodu. Zdania ze zbioru Ł nazywamy założeniami (dowodu z Ł).
Dowody zapisujemy w postaci kolumny wierszy dowodowych, na
które składać się będą:
(I) kolejny numer zdania,
(II) zdanie
oraz
56
Sformułowanie reguły odrywania znajduje się w logice stoików  systemie
logicznym, który powstał w III w. p.n.e. w Grecji. Zaliczona została do sylogi-
zmów hipotetycznych niedowodliwych. W średniowieczu nadano jej nazwę: modus
ponendo ponens albo krótko: modus ponens.
1.2. WYNIKANIE SYNTAKTYCZNE 83
(III) wskazanie racji, dla których to zdanie można dołączyć do do-
wodu.
(1) Będziemy pisali  tautologia , jeżeli dołączone zdanie jest
tautologią.
(2)  Założenie piszemy w wypadku, gdy zdanie to należy
do zbioru Ł.
(3) Jeżeli zdanie będzie uzyskane w wyniku użycia reguły
odrywania, będziemy pisali  MP oraz numery wierszy
dowodowych, w których znajdują się zdania, do których
reguła ta została zastosowana.
PRZYKA
AD
Pokażemy że zdanie a a {a 1. a 2. a 3. b 4. b 5. (a 6. a 7. a �
LEMAT 1.
Jeżeli ą i ą �! � są tautologiami, to � jest tautologią.
DOWÓD
Niech w ciągu p0, p1, . . . , pn znajdują się wszystkie litery zdaniowe,
z których jest zbudowane zdanie ą �! � i niech � nie będzie tautolo-
gią. Istnieje zatem taka interpretacja v0, v1, . . . , vn, że zdanie � dla tej
57
Poszczególne wyrażenia języka teorii mniejszości: a < b, b < c, a < c od-
powiadają literom zdaniowym, czyli są przez nas traktowane jako wewnętrznie
niezłożone.
84 1. KLASYCZNA LOGIKA ZDAC

interpretacji przyjmuje wartość f. Ponieważ z założenia ą �! � jest
tautologią, więc ą dla tej interpretacji musi przyjmować wartość f, a
to przeczy założeniu, że ą jest tautologią.
LEMAT 2.
ą ma dowód z pustego zbioru zdań wtedy i tylko wtedy, gdy ą
jest tautologią.
DOWÓD
Jeżeli ą jest tautologią, to ciąg, którego jedynym wyrazem jest ą
jest dowodem ą.
Niech ą ma dowód z pustego zbioru zdań. Niech ą0, ą1, . . . , ąn
będzie pewnym dowodem ą. Przez indukcję po długości tego dowodu
pokażemy, że ą jest tautologią.
Ponieważ Ł jest puste, więc zgodnie z definicją dowodu ą0 może
być tylko tautologią.
ZAA
OŻENIE INDUKCYJNE: Niech dla i d" k, ąi będzie tautologią.
Pokażemy, że ąk+1 jest tautologią. Zgodnie z definicją dowodu
ąk+1 może być tautologią lub być otrzymane przez zastosowanie
reguły odrywania do wyrazów poprzedzających ąk+1 w ciągu ą0,
ą1, . . . , ąn. Jeżeli jednak stosujemy regułę odrywania do zdań, które
są tautologiami, to w wyniku otrzymujemy tautologię. W każdym
wypadku ąk+1 jest więc tautologią.
WNIOSEK
ą jest tautologią wtedy i tylko wtedy, gdy ą ma dowód z dowol-
nego zbioru zdań.
UWAGA
W wypadku gdy Ł jest pustym zbiorem zdań (Ł = ") zamiast
" ą
będziemy pisali
ą.
1.2.2. Operacja konsekwencji
1.2. WYNIKANIE SYNTAKTYCZNE 85
(DEF. Cn(Ł)) Niech Cn(Ł)58 będzie zbiorem wszystkich zdań, które
mają dowód ze zbioru Ł, czyli Cn(Ł) = {ą : Ł ą}. O Cn(Ł) mówimy,
że jest zbiorem konsekwencji Ł.
TWIERDZENIE 6.
1. Ł ą" Cn(Ł)
2. jeżeli Ł ą" �, to Cn(Ł) ą" Cn(�)
3. Cn[Cn(Ł)] ą" Cn(Ł).
DOWÓD
1. Niech ą będzie elementem Ł (ą " Ł). Ciąg, którego jedynym
wyrazem jest zdanie ą jest dowodem zdania ą ze zbioru Ł.
2. Niech ą " Cn(Ł). Niech ą0, ą1, . . . , ąn będzie dowodem ą ze
zbioru Ł. Ciąg ten jest również dowodem ą ze zbioru �.
3. Niech ą " Cn[Cn(Ł)]. Niech ą0, ą1, . . . , ąn będzie dowodem ą
ze zbioru Cn(Ł). Na drodze wnioskowania przez indukcję po
długości dowodu pokażemy, że dla każdego i, 0 d" i d" n, ąi ma
dowód ze zbioru Ł; czyli że jest elementem zbioru Cn(Ł).
ą0 może być tylko tautologią lub elementem Cn(Ł). Jeżeli ą0 jest
tautologią, to ma dowód z Ł. Jeżeli ą0 jest elementem Cn(Ł), to 
na podstawie definicji Cn  ą0 ma również dowód z Ł. Zatemą0 ma
dowód z Ł, czyli ą0 " Cn(Ł).
ZAA
OŻENIE INDUKCYJNE: Niech dla i (d" k Ł.
ąk+1 może być tautologią, elementem zbioru Cn(Ł) lub może być
otrzymane przez zastosowanie reguły odrywania do zdań mających
dowód z Cn(Ł). W pierwszych dwóch wypadkach jest tak samo, jak w
wypadku ą0. Pozostaje więc rozważyć wypadek, gdy ąk+1 jest otrzy-
mane za pomocą MP ze zdań ąl, ąm mających dowód z Cn(Ł). Z
58
Cn  są początkowymi literami łacińskiego słowa consequor  iść za kimś,
następować. Pojęcie konsekwencji jest jednym z najbardziej podstawowych pojęć
logiki. Zostało wprowadzone przez Tarskiego w latach 1929 1935. Badania nad
nim rozwijają prace Tarskiego: [1930], [1930a].
86 1. KLASYCZNA LOGIKA ZDAC

założenia indukcyjnego zdania te mają dowód z Ł. Niech �0, �1, . . . , �t
będzie dowodem ze zbioru Ł zdania ąl, zaś ł0, ł1, . . . , łr niech będzie
dowodem ze zbioru Ł zdania ąm. Ciąg �0, �1, . . . , �t, ł0, ł1, . . . , łr, ąk+1
jest dowodem ze zbioru Ł zdania ąk+1, czyli ąk+1 " Cn(Ł).
1.2.3. Twierdzenie o dedukcji
Intuicyjnie utożsamiane są stwierdzenia:
Zdanie � jest wnioskiem ze zdania ą
i
Twierdzeniem jest, że jeżeli ą, to �.
Mając do udowodnienia zdanie  jeżeli ą, to � bierzemy zdanie ą jako
przesłankę, a następnie wyprowadzamy � jako wniosek z ą. Mając zaś
udowodnione, że � jest wnioskiem z ą przyjmujemy jako udowodnione
zdanie:  jeżeli ą, to � .
Nim przystąpimy do twierdzenia o dedukcji udowodnijmy prosty
fakt, z którego będziemy korzystać w dowodzie.
LEMAT 3.
Jeżeli ą jest tautologią, to � �! ą jest tautologią.
DOWÓD
Niech w ciągu p0, p1, . . . , pn znajdują się wszystkie litery zdaniowe,
z których jest zbudowane zdanie � �! ą. Gdyby � �! ą nie było tau-
tologią, to istniałaby interpretacja v0, v1, . . . , vn taka, że dla tej inter-
pretacji zdanie � �! ą przyjmowałoby wartość f. Byłoby to jednak
możliwe tylko wówczas, gdyby ą dla tej interpretacji przyjmowało
wartość f, a to jest wykluczone, z założenia bowiem ą jest tautolo-
gią.
TWIERDZENIE 7 (O DEDUKCJI)59 .
Ł *"{ą} �
59
Sformułowanie twierdzenia o dedukcji jako postulatu wnioskowania deduk-
cyjnego znajduje się już w  Die Wissenschaftslehre Bernarda Bolzano [1836].
Ponownie w ujęciu intuicyjnym pojawia się w: Herbrand [1928], a z dowodem
1.2. WYNIKANIE SYNTAKTYCZNE 87
wtedy i tylko wtedy, gdy
Ł ą �! �.
DOWÓD
Udowodnimy dwie tezy, które łącznie składają się na twierdzenie
o dedukcji, a mianowicie:
A. jeżeli Ł ą �! �, to Ł *"{ą} �
B. jeżeli Ł *"{ą} �, to Ł ą �! �.
Dowód faktu A jest krótki. Niech ą0, ą1, . . . , ąn będzie dowodem
ze zbioru Ł zdania ą �! �. W wypadku, gdy zbiorem założeń jest zbiór
zdań Ł*"{ą}, zdanie ą jest założeniem, więc może być dołączone do do-
wodu. Mamy zatem: ą0, ą1, . . . , ąn, ą. Ponieważ � daje się za pomocą
MP wyprowadzić z ąn(= ą �! �) i ą, zatem do ciągu dowodowego
ą0, ą1, . . . , ąn, ą możemy również dołączyć �. Ciąg: ą0, ą1, . . . , ąn, ą, �
jest dowodem ze zbioru Ł *"{ą} zdania �.
Dowód faktu B jest bardziej złożony. Niech Ł *"{ą} �, czyli
niech istnieje dowód � ze zbioru Ł *"{ą}. Niech ą0, ą1, . . . , ąn będzie
tym dowodem. Przez indukcję po długości tego dowodu pokażemy, że
dla każdego i, 0 d" i d" n, Ł ą �! ąn. W szczególności dla i = n będzie:
Ł ą �! �.
Pokażmy to wpierw dla i =0.
ą0 może być tautologią bądz
może być założeniem.
Gdy ą0 jest tautologią, to  na podstawie wyżej udowodnionego
lematu  ą �! ą0 jest tautologią, a więc ma dowód z dowolnego zbioru
zdań, w szczególności z Ł.
w: Herbrand [1930]. Twierdzenie o dedukcji jako zasada odnosząca się do sys-
temów dedukcyjnych znajduje się u Tarskiego [1930]. Tarski ([1956], przypis na
s. 32) pisze, że znał ją i stosował od 1921 r., a samo twierdzenie sformułował w
związku z dyskusją nad książką Ajdukiewicza [1921]. Nazwa  twierdzenie o de-
dukcji jest autorstwa Dawida Hilberta, który użył jej w napisanych wspólnie z
Paulem Bernaysem  Grundlagen der Mathematik [1934]. Znane są liczne mo-
dyfikacje twierdzenia o dedukcji jak np. dla implikacji zstępujących, zob. Surma
[1968]. Odpowiedniki twierdzenia o dedukcji wskazano dla wielu nieklasycznych
systemów logiki.
88 1. KLASYCZNA LOGIKA ZDAC

Jeżeli ą0 jest założeniem, to jest to bądz
zdanie ą, bądz
jakiś
element zbioru Ł.
Jeżeli ą0 jest zdaniem ą, to zdanie ą �! ą ma dowód z Ł, jest
bowiem tautologią.
Niech ą0 " Ł. Ciąg:
1. ą0 �! (ą �! ą0) tautologia
2. ą0 założenie
3. ą �! ą0 (MP; 1,2)
jest dowodem zdania ą �! ą0 ze zbioru Ł.
ZAA
OŻENIE INDUKCYJNE: Niech dla i d" k ąi.
Pokażemy, że dla i = k +1 zachodzi
Ł ą �! ąk+1.
Zgodnie z definicją dowodu, ąk+1 może być bądz
tautologią, bądz

założeniem, bądz
może być uzyskane przez zastosowanie reguły od-
rywania.
Jeżeli ąk+1 jest tautologią lub założeniem, to postępujemy tak
samo jak w wypadku ą0.
Rozważmy więc tylko wypadek, gdy ąk+1 uzyskane jest przez za-
stosowanie reguły odrywania. Niech więc w ciągu dowodowym ąk+1
będzie poprzedzane przez zdania ąm oraz ąm �! ąk+1. Zgodnie z zało-
żeniem indukcyjnym zdania ą �! ąm i ą �! (ąm �! ąk+1) mają dowód
ze zbioru Ł. Niech ciąg:
�0, �1, . . . , �l(= ą �! ąm)
będzie dowodem ze zbioru Ł zdania ą �! ąm a ciąg:
ł0, ł1, . . . , łu[= ą �! (ąm �! ąk+1)]
będzie dowodem ze zbioru Ł zdania ą �! (ąm �! ąk+1).
Ciąg:
�0, �1, . . . , �l, ł0, ł1, . . . , łu,
przedłużony o następujące trzy zdania:
(l+u+3). [ą �! (ąm �! ąk+1)] �!
1.2. WYNIKANIE SYNTAKTYCZNE 89
[(ą �! ąm) �! (ą �! ąk+1)] tautologia
(l+u+4). (ą �! ąm) �! (ą �! ąk+1) (MP; l+u+3, l+u+2)
(l+u+5). ą �! ąk+1 (MP; l+u+4, l + 1)
jest dowodem ze zbioru Ł zdania ą �! ąk+1.
1.2.4. Sprzeczne i niesprzeczne zbiory zdań
(DEF. syntaktycznie sprzecznego zbioru zdań) Ł jest (syntaktycznie)
sprzecznym zbiorem zdań wtedy i tylko wtedy, gdy dla dowolnego ą:
Ł ą.
W przeciwnym wypadku, a więc gdy
(DEF. syntaktycznie niesprzecznego zbioru zdań) dla pewnego ą nie
jest tak, że Ł ą mówimy, że Ł jest (syntaktycznie) niesprzecznym
zbiorem zdań.
Definicja zbioru sprzecznego jest równoważna określeniu zbioru
sprzecznego jako takiego zbioru, którego zbiór konsekwencji jest
równy zbiorowi L wszystkich zdań, czyli Ł jest sprzecznym zbiorem
zdań wtedy i tylko wtedy, gdy Cn(Ł) = L.
Intuicyjne pojęcie semantycznie niesprzecznego zbioru zdań jest
takie, że za niesprzeczny (semantycznie) uważamy każdy zbiór zdań
prawdziwych w jakiejś dziedzinie przedmiotowej, a także uznajemy
istnienie jakiejś  rzeczywistości , w której prawdziwe są wszystkie
zdania z jakiegoś zbioru zdań, za warunek konieczny niesprzeczności
(semantycznej) tego zbioru. A zatem w terminologii logicznej ozna-
czałoby to, że
(DEF. semantycznie niesprzecznego zbioru zdań) Zbiór zdań jest se-
mantycznie niesprzeczny wtedy i tylko wtedy, gdy ma model.
W wypadku, gdy istnieje równoważność wynikania syntaktycz-
nego i semantycznego, pojęcia niesprzeczności syntaktycznej i seman-
tycznej są też równoważne. W zastosowaniach logiki nie będzie więc
potrzebne ich odróżnianie. Okaże się, że twierdzenie głoszące, że wy-
nikanie syntaktyczne pokrywa się z wynikaniem semantycznym będzie
90 1. KLASYCZNA LOGIKA ZDAC

prostą konsekwencją twierdzenia głoszącego, że zbiór zdań jest (syn-
taktycznie) niesprzeczny wtedy i tylko wtedy, gdy ma model, czyli
gdy jest semantycznie niesprzeczny.
(DEF. pary zdań przeciwnych) W tradycyjnej terminologii o dwóch
zdaniach ą i � mówi się, że są przeciwne (wykluczają się) wtedy i
tylko wtedy, gdy tautologią jest zdanie:
Ź(ą '" �).
(DEF. pary zdań podprzeciwnych) Zdania ą i � są podprzeciwne (do-
pełniają się) wtedy i tylko wtedy, gdy tautologią jest zdanie:
(ą (" �).
PRZYKA
ADY
Wykluczają się zdania: p i Źp '" q.
Dopełniają się zdania: p i Źp (" q.
�
(DEF. pary zdań sprzecznych) O zdaniach ą i � mówi się, że two-
rzą parę zdań sprzecznych wtedy i tylko wtedy, gdy się wykluczają i
dopełniają; czyli, gdy tautologiami są zdania
Ź(ą '" �)
oraz
(ą (" �).
PRZYKA
AD
Sprzeczne są zdania
2+2=4,
Ź (2+2=4).
�
Udowodnimy teraz pewną własność zdań wykluczających się.
LEMAT 4.
Dwa zdania tworzą sprzeczny zbiór zdań (w przyjętym tu rozu-
mieniu) wtedy i tylko wtedy, gdy zdania te wykluczają się.
DOWÓD
Na dowodzone twierdzenie składają się dwie tezy:
1.2. WYNIKANIE SYNTAKTYCZNE 91
(A) Jeżeli zdania się wykluczają, to tworzą sprzeczny zbiór zdań
oraz
(B) Jeżeli dwa zdania tworzą sprzeczny zbiór zdań, to zdania te
wykluczają się.
Rozpocznijmy od (A). Załóżmy, że zdania ą i � wykluczają się, a
więc że tautologią jest zdanie Ź (ą '" �). Pokażemy, że dla dowolnego
ł istnieje dowód ze zbioru {ą, �}.
1. (ą '" �) �! ł tautologia
2. ą �! [� �! (ą '" �)] tautologia
3. ą założenie
4. � �! (ą '" �) (MP;2,3)
5. � założenie
6. (ą '" �) (MP; 4,5)
7. ł (MP; 1,6)
W dowodzie (B) będziemy korzystali z twierdzenia o dedukcji.
Niech {ą, �} będzie sprzecznym zbiorem zdań. Zatem ze zbioru tego
ma dowód dowolne zdanie, w szczególności zdanie Ź(ą '" �), czyli:
{ą, �} Ź(ą '" �).
Ponieważ {ą, �} = "*"{ą}*"{�}, więc
"*"{ą}*"{�} Ź(ą '" �).
Korzystając dwukrotnie z twierdzenia o dedukcji otrzymujemy
" ą �! [� �!Ź(ą '" �)].
Zdanie
ą �! [� �!Ź(ą '" �)],
jako mające dowód z pustego zbioru zdań winno więc być tautologią,
a tak może być tylko w wypadku, gdy zdania ą i � wykluczają się. W
przeciwnym wypadku istniałaby bowiem taka interpretacja, że zdania
ą i � miałyby dla tej interpretacji wartość t. Zdanie Ź (ą '" �) miałoby
więc wartość f, a co za tym idzie wartość f przysługiwałaby zdaniu
ą �! [� �!Ź (ą '" �)].
Z powyższego faktu mamy
WNIOSEK
92 1. KLASYCZNA LOGIKA ZDAC

jeżeli elementami Ł są dwa zdania, które się wykluczają, to Ł jest
sprzecznym zbiorem zdań.
TWIERDZENIE 8.
Ł jest niesprzecznym zbiorem zdań wtedy i tylko wtedy, gdy Cn(Ł)
jest zbiorem niesprzecznym.
DOWÓD
Gdy Ł jest sprzeczne, to Cn(Ł) jest sprzeczne. Wynika to z twier-
dzenia o własnościach operacji konsekwencji (tw. 6, I). Ponieważ
Ł ą" Cn(Ł), więc każdy dowód z Ł jest zarazem dowodem z Cn(Ł).
Aby pokazać, że jeżeli Cn(Ł) jest sprzeczne, to Ł jest sprzeczne
wystarczy skorzystać z tw. 6.3. Bowiem dla każdego ą: jeżeli ą ma
dowód z Cn(Ł)  czyli ą " Cn[Cn(Ł)]  to ą " Cn(Ł), a więc ą ma
dowód z Ł.
Prostą konsekwencją powyższego twierdzenia i twierdzenia 6 jest
następujący
WNIOSEK
Jeżeli Ł jest niesprzecznym zbiorem zdań, to każdy jego podzbiór
jest niesprzecznym zbiorem zdań.
TWIERDZENIE 9.
Zbiór zdań Ł jest sprzeczny wtedy i tylko wtedy, gdy dla pewnego
ą:
1. Ł ą, Ł Ź ą
lub
2. Ł ą '" Ź ą.
DOWÓD
Oczywiście, gdy Ł jest sprzeczne, to z Ł mają dowody dowolne
zdania, a w szczególności ą, Źą oraz ą '"Źą. Pokazać więc trzeba, że
1. jeżeli dla pewnego ą dowody z Ł mają zarówno ą jako i Źą, to Ł
jest sprzeczne,
a także
1.2. WYNIKANIE SYNTAKTYCZNE 93
2. gdy dla pewnego ą dowód z Ł ma ą '"Źą, to Ł jest sprzeczne.
Dla dowodu (1) wystarczy pokazać, że jeżeli dla pewnego ą do-
wody z Ł mają zarówno ą jak i Źą, to dla dowolnego zdania � istnieje
jego dowód z Ł. Niech ciąg:
�0, �1, . . . , �n(= ą)
będzie dowodem ze zbioru Ł zdania ą, a ciąg:
ł0, ł1, . . . , łm(= Źą)
dowodem ze zbioru Ł zdania Ź ą. Niech � będzie dowolnym zdaniem.
Ciąg:
�0, �1, . . . , �n, ł0, ł1, . . . , łm, ą �! (Źą �! �), Źą �! �, �
jest dowodem ze zbioru Ł zdania �. Zdanie ą �! (Źą �! �) jest tauto-
logią, a kolejne zdania ciągu uzyskujemy stosując regułę odrywania.
Podobnie, gdy ą '"Źą jest konsekwencją Ł, to Ł jest sprzeczne.
Zauważmy bowiem, że gdy ciąg:
�0, �1, . . . , �n
jest dowodem ą '"Źą, to ponieważ zdanie ą '"Źą �! � jest tautologią,
więc ciąg:
�0, �1, . . . , �n, ą'"Źą �! �, �
jest dowodem �.
TWIERDZENIE 10.
Jeżeli Ł jest niesprzecznym zbiorem zdań i ą nie ma dowodu z Ł,
to zbiór Ł *"{Źą} jest niesprzecznym zbiorem zdań.
DOWÓD
Niech Ł będzie niesprzecznym zbiorem zdań i niech nie będzie
prawdą, że Ł ą. Gdyby zbiór Ł *"{Źą} był zbiorem sprzecznym, to
dowód z niego miałoby dowolne zdanie, w szczególności ą. Więc:
Ł *"{Źą} ą.
Na podstawie twierdzenia o dedukcji mamy, że
Ł Źą �! ą.
Niech
94 1. KLASYCZNA LOGIKA ZDAC

�0, �1, . . . , �n(= Źą �! ą)
będzie dowodem Ź ą �! ą ze zbioru Ł. Zdanie:
(Źą �! ą) �! ą
jest tautologią. Zatem ciąg:
�0, �1, . . . , �n, (Źą �! ą) �! ą, ą
byłby dowodem zdania ą ze zbioru Ł, a to przeczyłoby założeniu.
1.2.5. Maksymalne niesprzeczne zbiory zdań
(DEF. maksymalnego niesprzecznego zbioru zdań) Zbiór Ł jest mak-
symalnym niesprzecznym wtedy i tylko wtedy, gdy Ł jest zbiorem
niesprzecznym oraz kiedy jedynym niesprzecznym zbiorem zawiera-
jącym Ł jest Ł, czyli gdy sprzeczny jest każdy zbiór powstały ze
zbioru Ł przez dołączenie jakichś zdań nie należących do Ł.
TWIERDZENIE 11.
Jeżeli Ł jest zbiorem maksymalnym niesprzecznym oraz Ł ą, to
ą " Ł.
DOWÓD
Na podstawie twierdzenia 8 jeżeli Ł jest niesprzeczne, to Cn(Ł)
jest niesprzeczne. Z tego, że Ł ą mamy, iż Ł *"{ą} jest podzbiorem
Cn(Ł). Zatem  na podstawie wniosku z twierdzenia 8  Ł *"{ą} jest
niesprzeczne jako podzbiór zbioru niesprzecznego. Z maksymalności
Ł wynika więc, że ą " Ł.
TWIERDZENIE 12 (LEMAT LINDENBAUMA)60
Każdy niesprzeczny zbiór zdań może być rozszerzony do maksy-
malnego niesprzecznego zbioru zdań.
DOWÓD
60
Autorem tego twierdzenia jest Adolf Lindenbaum (1904 1941). W tej sprawie
zob. Tarski [1956], s. 98.
1.2. WYNIKANIE SYNTAKTYCZNE 95
Wszystkie zdania można ustawić w ciąg porządkując je np. tak,
jak porządkuje się wyrazy w słowniku. Wystarczy tylko ustalić kolej-
ność znaków naszego alfabetu  słownika. Mógłby to być np. nastę-
pujący porządek:
Ź, (", '", �!, �!, (, ), p0, p1, p2, . . ..
Niech
ą0, ą1, ą2, . . .
będzie ciągiem wszystkich zdań języka rachunku zdań.
Niech Ł będzie dowolnym niesprzecznym zbiorem zdań. Two-
rzymy ciąg zbiorów zdań:
Ł0, Ł1, Ł2, . . .
taki, że
(I) Ł0 =Ł,
(II)
ńł
�ł Łi, jeżeli Łi *"{ąi} jest sprzeczne,
Łi+1 =
ół
Łi *"{ąi}, jeżeli Łi *"{ąi} jest niesprzeczne
"

Twierdzimy, że zbiór �= Łi, czyli zbiór będący sumą teorio-
i=0
-mnogościową wszystkich i tylko zbiorów z ciągu: Ł0, Ł1, Ł2, . . . , jest
maksymalnym niesprzecznym nadzbiorem Ł61 .
W dowodzie, że � jest maksymalnym niesprzecznym nadzbiorem
zbioru Ł wykorzystamy fakt, że Ł0 ą" Ł1 ą" Ł2 ą" . . . ą" �, oraz że
wszystkie Łi, 0 d" i, są niesprzecznymi zbiorami zdań.
Załóżmy, że � jest zbiorem sprzecznym. Wówczas ze zbioru �
dowód ma dowolne zdanie, w szczególności istnieje dowód dla zdania
ą '"Źą.
Niech ciąg: �0, �1, . . . , �n będzie dowodem ze zbioru � zdania
ą '"Źą.
61
Nadzbiorem zbioru Ł jest każdy zbiór � taki, że Ł ą" �.
96 1. KLASYCZNA LOGIKA ZDAC

Ponieważ ciąg ten ma skończoną ilość wyrazów, więc istnieje m takie,
że wszystkie zdania z ciągu: �0, �1, . . . , �n, które są elementami �, są
też elementami Łm; a więc ciąg ten byłby dowodem z Łm zdania
ą '" Ź ą.
Na podstawie twierdzenia 9, zbiór Łm byłby więc zbiorem sprzecz-
nym, a to nie jest prawdą.
Zbiór � jest maksymalny. Gdyby bowiem dla jakiegoś ąm zbiór
�*"{ąm} nie był sprzeczny, to jest jasne, że nie byłby również sprzeczny
zbiór Łm*"{ąm}. Awięc ąm należałoby do Łm+1 i  z określenia zbioru
�  ąm należałoby również do zbioru �.
Zauważmy, że dla danego Ł może być więcej niż jeden maksy-
malny niesprzeczny nadzbiór. Konstrukcja takiego nadzbioru zależy
bowiem nie tylko od Ł, ale także od sposobu uporządkowania zdań.
TWIERDZENIE 13.
Niech Ł będzie zbiorem maksymalnym niesprzecznym. Dla każ-
dego ą:
(I) ą należy do Ł wtedy i tylko wtedy, gdy Źą nie należy do Ł;
(II) ą �! � należy do Ł wtedy i tylko wtedy, gdy Źą należy do
Ł lub � należy do Ł;
(III) ą (" � należy do Ł wtedy i tylko wtedy, gdy ą należy do Ł
lub � należy do Ł;
(IV) ą '" � należy do Ł wtedy i tylko wtedy, gdy ą należy do Ł i
� należy do Ł;
(V) ą �! � należy do Ł wtedy i tylko wtedy, gdy (ą należy do Ł
wtedy i tylko wtedy, gdy � należy do Ł).
DOWÓD
(I1) Gdyby ą i Źą należały do Ł, to  na podstawie twierdzenia 9 
Ł byłoby sprzeczne, a to jest wbrew założeniu. Zatem jeżeli ą należy
do Ł, to Źą nie należy do Ł.
(I2) Dla dowodu tezy, że jeżeli Źą nie należy do Ł, to ą należy do
Ł załóżmy, że zarówno ą jak i Źą nie należą do Ł. Ponieważ Ł jest
1.2. WYNIKANIE SYNTAKTYCZNE 97
zbiorem maksymalnym, więc zbiór Ł *"{ą} byłby sprzeczny. Z tego
zbioru, w szczególności, miałoby dowód zdanie Źą, czyli Ł*"{ą} Źą.
Na podstawie twierdzenia o dedukcji stwierdzamy zaś, że Ł ą �!Źą.
Niech
ą0, ą1, . . . , ąn(= ą �!Źą)
będzie dowodem ze zbioru Ł zdania ą �!Ź ą. Ponieważ zdanie (ą �!
Ź ą) �!Ź ą jest tautologią, więc ciąg:
ą0, ą1, . . . , ąn, (ą �!Źą) �!Źą, Źą
jest dowodem zdania Ź ą ze zbioru Ł. Z maksymalności Ł i twierdze-
nia 11 mamy więc, że Źą należy do Ł, a to przeczy założeniu. Zatem
jeżeli Źą nie należy do Ł, to ą należy do Ł.
(II1) Dla dowodu tezy, że jeżeli ą �! � należy do Ł, to Źą lub �
należy do Ł załóżmy, że ą �! � należy do Ł a Źą nie należy do Ł.
Na podstawie (I) mamy, że ą należy do Ł. Ponieważ � daje się za
pomocą reguły odrywania wyprowadzić z ą �! � i ą, a Ł jest zbiorem
maksymalnym, więc � należy do Ł.
Teraz rozważmy wypadek, że ą �! � należy do Ł a � nie należy do
Ł. Napodstawie (I) doŁ należy Ź�. Korzystając z [(ą �! �)'"Ź�] �!Źą
(modus tollens) stwierdzamy, że dowód z Ł ma Źą. Z maksymalności
Ł mamy więc, że Źą należy do Ł.
(II2) Dla dowodu tezy, że jeżeli Źą lub � należy do Ł, to ą �! � należy
do Ł załóżmy, iż Źą należy do Ł lub � należy do Ł.
Gdy Źą należy do Ł, to ponieważ zdanie Źą �! (ą �! �) jest
tautologią, więc ą �! � jako mające dowód z Ł należy do Ł jako
zbioru maksymalnego.
Gdy � należy do Ł, to korzystając z faktu, że � �! (ą �! �) jest
tautologią stwierdzamy, iż ą �! � daje się wyprowadzić z Ł, a zatem
z maksymalności Ł, ą �! � należy do Ł.
Wypadków (III)  (V) dowodzi się równie krótko.