04 1 Klasyczna logika zadań

1. KLASYCZNA LOGIKA ZDAŃ

1.0. ZAŁOŻENIA

KLASYCZNEGO

RACHUNKU

ZDAŃ

Rozważymy teraz problem rachunku dla logiki zdań

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 ﬁkcyjny. 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

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.

1. KLASYCZNA LOGIKA ZDAŃ

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 deﬁnicję 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ądź zdaniami tworzy zdanie.

PRZYKŁ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

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.

PRZYKŁ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

języka klasycznej logiki zdań jest zbiorem następują-

cych przedmiotów (symboli):

(I)

, p

, . . .

(II)

(III)

⇒

∨

∧

⇔

(IV)

)

, (

Zbiór wszystkich skończonych ciągów elementów

∗

. Ele-

menty

∗

to słowa nad alfabetem

, p

, . . .

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ą

Łacińskie nego znaczy: przeczę.

1. KLASYCZNA LOGIKA ZDAŃ

Spójniki:

⇒

∨

∧

⇔

są dwuargumentowe. Nazywamy je, odpo-

wiednio: implikacją

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. Deﬁnicja 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

będą dowolnymi skończonymi ciągami symboli alfa-

betu języka logiki zdań, czyli

są elementami

∗

(

β ∈ 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 symboli

spełniającymi warunki

(II) i (III).

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.

Pojęcia użyte w deﬁnicji zdania: ciągu, skończonego ciągu, najmniejszego

zbioru należą do teorii mnogości, tam też podane są ich deﬁnicje.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

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

∗

PRZYKŁADY

Zdaniami są:

¬p

(

∨ p

)

(

¬(p

∧ p

)

∨ p

)

Zdaniami nie są:

(

)

¬(p

)

¬(p

)

∨ (p

)

¬(p

)

∨ (p

)

(

∨ p

)

∧

(

∨ p

)

∧ (p

∨ p

)

∧ . . .

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.

PRZYKŁADY

Ciąg

((

⇒ p

)

∧ p

)

⇔ ((p

∨ (p

⇒ ¬p

)))

1. KLASYCZNA LOGIKA ZDAŃ

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

((

∨ (p

⇒ ¬p

)))

nawias lewy i nawias prawy występują po trzy razy, zaś spójniki dwu-
argumentowe występują tylko dwa razy.

Zdaniem jest

(((

⇒ p

)

∧ p

)

⇔ (p

∨ (p

⇒ ¬p

)))

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ób

Tak jest w wypadku

wyżej opisanego języka logiki zdań.

PRZYKŁADY

Niech wyrażeniem poprawnie zbudowanym będzie każdy skoń-

czony ciąg symboli:

∇

♦

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 formalnym

Dział syntaktyki zajmujący się problemem konstrukcji wyrażeń to tektonika.

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

Wyrażenia poprawnie zbudowane – w wypadku języka rachunku

zdań – zdania, są przedmiotami abstrakcyjnymi. Reprezentantem wy-
rażenia poprawnie zbudowanego jest konkretny napis (lub dźwięk).
Dwa napisy (dźwięki) mogą być reprezentantami tego samego wyraże-
nia. Istnienie wyrażenia nie jest uwarunkowane aktualnym istnieniem
konkretnych napisów (dźwięków), ani naszymi możliwościami zapisu.
Pozwala to mówić zarówno o wyrażeniach, których zapis przekracza
ﬁzyczne 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 deﬁnicji zda-

nia. Za zbędne uważamy nawiasy zewnętrzne, czyli zamiast:

(

α)

pi-

szemy:

. Jeżeli spójnik dwuargumentowy

wiąże mocniej niż spój-

nik dwuargumentowy

, to zamiast

(

αs

β)s

piszemy

αs

βs

; po-

dobnie, zamiast

αs

(

βs

γ)

piszemy

αs

βs

. 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

wiążą z jednakową mocą, to zamiast

αs

(

βs

γ)

możemy pisać

αs

βs

. 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 deﬁnicji 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.

1. KLASYCZNA LOGIKA ZDAŃ

„

¬α

” 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

. 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 supozycjach

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.

Szerzej na ten temat zob. Trzęsicki [2000], s. 46–47.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

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-
ﬁczne 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 łukasiewiczowska

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 Łukasiewicz

Okazuje się, że w wypadku, gdy wszyst-

kie spójniki są preﬁksami (czyli gdy pisane są przed swoimi argumen-
tami) lub gdy wszystkie spójniki są suﬁksami (czyli gdy pisane są
po swoich argumentach) możliwe jest wyeliminowanie nawiasów. W
wypadku wyżej opisanego języka preﬁksem jest spójnik negacji, zaś:

∨

∧

⇒

⇔

są inﬁksami (czyli spójniki te pisane są między swoimi

argumentami)

Notacja ta w literaturze anglojęzycznej zwykle określana jest jako polska.

Ł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
konﬂiktu pomiędzy uznaniem, że twórcą symboliki beznawiasowej, zwanej także
polską, jest Łukasiewicz i tym, że pomysł pisania spójników przed argumentami
pochodzi od Chwistka.

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-

1. KLASYCZNA LOGIKA ZDAŃ

SŁOWNIK

(I)

, p

, . . .

litery zdaniowe

(II)

spójnik jednoargumentowy

(III)

C, A, K, E

spójniki dwuargumentowe

DEFINICJA ZDANIA (WYRAŻENIA POPRAWNIE ZBUDOWA-

NEGO LOGIKI ZDAŃ)

Niech

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ą preﬁksami.

Zdaniu:

(

∨ p

)

∧ p

odpowiada zdanie w notacji Łukasiewicza:

a zdaniu:

∨ (p

∧ p

)

– A

Daje się wskazać prostą metodę, która pozwala stwierdzić, czy

dany skończony ciąg symboli jest zdaniem w notacji Łukasiewicza.
Niech

będzie dowolnym skończonym ciągiem elementów słownika.

KRYTERIUM Ł

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

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

(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

mniejsza od liczby

występujących w tym odcinku symboli liter zdaniowych.

Kryterium Ł daje podstawę dla prostego rachunku pozwalającego

obliczyć, czy dany napis

jest zdaniem w notacji Łukasiewicza.

Symbolowi N przyporządkowujemy liczbę

, symbolom C, A, K,

E liczbę

(

−1)

, zaś symbolom liter zdaniowych liczbę

(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

-ty symbol napisu.

jest zdaniem w notacji Ł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

2. początkowym wyrazem ciągu jest liczba

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

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ż

jest tak, że jeżeli pod ich pierwszymi wy-

razami jest pod pisane

, to ciągi te są zdaniami. Niech

jest ciągiem

o długości większej niż

. Jeżeli jest to ciąg mający więcej niż jeden

1. KLASYCZNA LOGIKA ZDAŃ

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ć

. Zgodnie z założeniem jest to zdanie.

Pisząc

przed zdaniem uzyskujemy zdanie. Niech teraz pierwszym

wyrazem będzie któryś ze spójników dwuargumentowych. Zatem pod
przedostatnim wyrazem musi być podpisane

. We fragmencie ciągu

liczbowego poprzedzającym

musi wystąpić

. 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

, które są

zdaniami. Ciąg

jest więc również zdaniem.

PRZYKŁAD

Napis:

CCC

CCCN

tuv

jest zdaniem. Mamy bowiem:

CCC

CCCN

tuv

1 2 3 4 3 4 3 2 3 4 5 5 4 5 4 4 3 4 5 4 5 4 3 4 5 4 3 4 3 2 1 2 1

Na podstawie kryterium Ł można skonstruować reguły „mecha-

nicznego” przekładu zdań w notacji Ł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:

⇒

∨

∧

Zdanie to może być jedynym aksjomatem systemu aksjomatycznego ra-

chunku zdań z regułą odrywania (jeżeli

αβ

, to

) oraz reguła podstawiania

[jeżeli

, to

α(p

/β

), gdzie

α(p

/β)

jest zdaniem uzyskanym ze zdania

przez

jednoczesne wpisanie zdania

w miejsce każdego wystąpienia litery zdaniowej

i ∈ N

.]. O systemach aksjomatycznych będzie mowa w dalszej części książki.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

⇔

bierzemy odcinek napisu

począwszy od drugiego symbolu

taki, że ilość symboli C, A, K, E jest w tym odcinku dokładnie
o

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.

PRZYKŁAD

Przetłumaczmy zdanie

CCC

CCCN

tuv

(

CCCN

tuv ⇒

wv)

((

qp ⇒

CCCN

tuv) ⇒ (w ⇒ v))

(((

p ⇒

qp) ⇒ (

CCN

tu ⇒ v)) ⇒ (w ⇒

v))

(((

p ⇒ (q ⇒ p)) ⇒ ((

t ⇒

tu) ⇒ v)) ⇒

(

w ⇒ v))

(((

p ⇒ (q ⇒ p)) ⇒ (((

r ⇒

t) ⇒ (

su ⇒

tu)) ⇒

v)) ⇒ (w ⇒ v))

(((

p ⇒ (q ⇒ p)) ⇒ (((¬ r ⇒ (s ⇒ ¬ t)) ⇒ ((r ⇒

su) ⇒ (

ts ⇒

tu))) ⇒ v)) ⇒ (w ⇒ v))

(((

p ⇒ (q ⇒ p)) ⇒ (((¬ r ⇒ (s ⇒ ¬ t)) ⇒ ((r ⇒ (s ⇒ u)) ⇒ ((t ⇒

s) ⇒ (t ⇒ u)))) ⇒ v)) ⇒ (w ⇒ v))

1.1.3.3. Indukcyjny charakter deﬁnicji zdania

Deﬁnicja zdania jest deﬁnicją indukcyjną. Najogólniej rzecz bio-

rąc ten sposób deﬁniowania polega na wskazaniu pewnej klasy
(zbioru) przedmiotów (prostych). Może to być klasa skończona, np.

1. KLASYCZNA LOGIKA ZDAŃ

jednoelementowa, której jedynym elementem jest „

”; a może to być

również jakaś klasa nieskończona, np. jak ma to miejsce w wypadku
deﬁnicji 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 deﬁniowanej 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 deﬁniują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.

Deﬁnicje indukcyjne pozwalają na drodze wnioskowania, okre-

ślanego jako wnioskowanie przez indukcję (matematyczną), dowodzić
własności obiektów spełniających warunki deﬁnicji. Liczby naturalne
możemy pojąć jako elementy zbioru wszystkich obiektów:

|||

. . .

Na to, aby dowieść, że każda liczba naturalna ma jakąś własność

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ść

wystarczy pokazać, że

(I) każdej literze zdaniowej przysługuje własność

; oraz

(II) jeżeli

mają własność

, to

¬α

α ⇒ β

α ∨ β

α ∧ β

α ⇔ β

mają własność

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

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 deﬁniujemy indukcyjnie ze względu na jego budowę następu-
jąco. Niech

będą zdaniami

(I)

dł

(

α)

jeżeli

jest literą zdaniową,

(II)

dł

(

¬α)

1 +

dł

(

α)

(III)

dł

(

αsβ)

1 +

dł

(

α) +

dł

(

β)

gdzie

jest spójnikiem

dwuargumentowym.

1.1.4. Model i prawdziwość

W modelu każde zdanie proste powinno być bądź prawdziwe,

bądź 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

zbioru

liter zdaniowych. Jeżeli litera zdaniowa

należy do pod-

zbioru

, to będziemy przez to rozumieć, że

jest praw-

dziwe w modelu

. Gdy

nie należy do

, to będziemy przez to

rozumieć, że

jest fałszywe w modelu

. 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

używać będziemy specjalnego oznaczenia:

M |= α

(DEF.

M |= α

) Niech

będzie podzbiorem zbioru

liter zdaniowych

(

M ⊆ S)

jest prawdziwe (spełnione) w modelu

(

M |= α

) wtedy

i tylko wtedy, gdy:

Symbol „

” w sensie, w jakim tu jest użyty, po raz pierwszy pojawia się w:

S. C. Kleene [1956].

A ⊆ B

(

jest podzbiorem

) wtedy i tylko wtedy, gdy każdy element

jest elementem

. W szczególności każdy zbiór jest swoim podzbiorem.

1. KLASYCZNA LOGIKA ZDAŃ

(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 |= β

M |= γ

;

(VI) jeżeli

jest zdaniem

β ⇔ γ

, to

M |= α

wtedy i tylko wtedy, gdy

(

M |= β

wtedy i tylko wtedy

M |= γ

Użytych w deﬁnicji 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 deﬁniowniu zwany bezpośrednim błędnym kołem, idem per

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

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

. . .

”, „

. . .

”, „

. . .

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, ﬁlozof 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.

1. KLASYCZNA LOGIKA ZDAŃ

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 potraﬁlibyś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śnie

Zauważmy

również, że w wypadku, gdy mamy zdania, o których wiemy, że oba
są fałszywe, to raczej powiemy:

Por. Tarski [1994], s. 27.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

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,

, są prawdziwe. Ta-

kie same warunki prawdziwości formułowali logicy średniowieczni.

1. KLASYCZNA LOGIKA ZDAŃ

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

. . .

”

Sam termin „równo-

ważność”, inaczej niż jest to w wypadku pozostałych nazw spójników
zdaniowych, ma inne specyﬁczne znaczenia

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-

W sprawie rozumienia spójników zdaniowych zob. Tarski [1994], s. 20–33.

Szerzej na ten temat przy okazji omawiania relacji równoważności.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

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 znaleźć 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

liter zda-

niowych, w którym znajdują się wszystkie litery występujące w tym
zdaniu.

Niech

, p

, . . . , p

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:

. To, czym

są te symbole nie jest ważne. Zakładamy o nich jedynie, że są różne.

(DEF. wartości logicznej)

to wartości logiczne

(DEF. interpretacji) Niech

, v

, . . . , v

będzie ciągiem symboli

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

, v

, . . . , v

określamy (rekursywnie) następująco:

(I) jeżeli

jest literą zdaniową

, to wartością logiczną zdania

jest

;

„

” jest literą z angielskiego słowa „false” (fałsz), a „

” – „true” (prawda).

1. KLASYCZNA LOGIKA ZDAŃ

(II) wartości logiczne zdań złożonych obliczamy zaś zgodnie z poniżej

podanymi tabelkami wartości logicznych:

¬β

β γ

β ∨ γ β ∧ γ β ⇒ γ β ⇔ γ

PRZYKŁAD

Zdanie:

∨ (p

∧ ¬ p

)

dla interpretacji:

f, t, t, t

przyjmuje wartość

Zauważmy, że jedyna istotna różnica formalna pomiędzy określe-

niem prawdziwości zdań w modelu a deﬁnicją wartości zdania polega
na tym, że modeli jest nieskończenie wiele (dokładnie tyle, ile jest
podzbiorów zbioru liter zdaniowych, czyli

2N =

)

zaś ilość in-

terpretacji jest skończona. Interpretacji o długości

jest tyle, ile jest

wyrazowych ciągów liter

, czyli

(DEF. tautologii) Zdanie

jest tautologią

co oznaczamy:

wtedy i tylko wtedy, gdy

dla dowolnej interpretacji

, v

, . . . , v

przyjmuje wartość

(DEF. kontrtautologii) Zdanie

jest kontrtautologią wtedy i tylko

wtedy, gdy

dla dowolnej interpretacji przyjmuje wartość

Użyte tu oznaczenia są objaśnione w części poświęconej teorii mnogości.

Greckie

τα`υτoλoγ´ια

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].

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

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ć odpowiedź na pytanie, czy zdanie to jest,
czy też nie jest tautologią.

DOWÓD

Niech

będzie zbudowane z

różnych liter zdaniowych (litery te

mogą występować wielokrotnie). Zgodnie z deﬁnicją 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

różnych liter zdaniowych i mamy dokładnie dwie wartości logiczne,
zatem takich interpretacji jest

Problem, jaka wartość logiczna przysługuje zdaniu

dla danej

interpretacji jest rozstrzygalny. Wartość logiczną zdania

dla zada-

nej interpretacji ustalamy w

krokach, gdzie

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-
szemy niżej jako metodę wprost.

Do wskazania końca dowodu używany będzie kwadracik. P. Halmos w au-

tobiograﬁ pisze, że jego nieśmiertelnymi zasługami są pomysły skrótu i symbolu
typograﬁcznego. Wymyślił „iﬀ” 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.

1. KLASYCZNA LOGIKA ZDAŃ

(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

wyprzedza

i+1

wyprzedza

;

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

PRZYKŁAD

Zdanie:

[

p ∧ (p ⇒ q)] ⇒ q

jest tautologią.

Musimy rozważyć cztery wypadki:

{t, t}

{t, f}

{f, t}

{f, f}

[

p ∧ ( p ⇒ q ) ] ⇒ q
t

II.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

[

p ∧ ( p ⇒ q ) ] ⇒ q

III.

[

p ∧ ( p ⇒ q ) ] ⇒ q

IV.

[

p ∧ ( p ⇒ q ) ] ⇒ q

Zauważmy, że nie jest konieczne wypisywanie liter

w róż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-
wprost

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

Metodę sprawdzania wprost oraz metodę niewprost określa się jako metodę

zero-jedynkową a to dlatego, że zamiast liter „t” i „f” zwykle stosowano „

” i „

”.

Metoda ta jest dziełem E. Schr¨

odera. J. Łukasiewicz w [1951], s. 82 twierdzi, że

metoda ta była wynaleziona przez Ch. S. Peirce’a około 1885 r.

1. KLASYCZNA LOGIKA ZDAŃ

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

polega na tym, że jako założenie bierze

się zaprzeczenie

, czyli dołącza się je do przesłanek

jest dowie-

dzione, jeżeli z tego założenia, czyli z zaprzeczenia

oraz przesłanek

udaje się wywnioskować zdania, które nie mogą być współpraw-

dziwe. Takimi zdaniami są np. zdania, z których jedno jest negacją
drugiego

(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ę

;

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

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

lub

2.2. wyczerpane zostaną wszystkie możliwości i pod każdą literą

znajduje się jedna z liter

lub

;

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

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

PRZYKŁAD

Zdanie:

(

p ⇒ q) ⇒ ( ¬ p ⇒ ¬ q)

nie jest tautologią.

(

p ⇒ q ) ⇒ ( ¬ p ⇒ ¬ q )

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 tautologii

[(

¬p ⇒ q) ∧ (¬p ⇒ ¬q)] ⇒ p

Sprawdzenie metodą niewprost:

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ń.

1. KLASYCZNA LOGIKA ZDAŃ

[ (

¬ p ⇒ q ) ∧ ( ¬ p ⇒ ¬ q ) ] ⇒ p

f t

t f
f

Zdanie:

[(

¬p ⇒ q) ∧ (¬p ⇒ ¬q)] ⇒ p

jest tautologią.

(

p ⇔ q) ⇔ [(p ⇒ q) ∧ (q ⇒ p)]

Sprawdzenie metodą wprost:

(

p ⇔ q ) ⇔ [ ( p ⇒ q ) ∧ ( q ⇒ p ) ]
t

(

p ⇔ q ) ⇔ [ ( p ⇒ q ) ∧ ( q ⇒ p ) ]
t

(

p ⇔ q ) ⇔ [ ( p ⇒ q ) ∧ ( q ⇒ p ) ]
f

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

(

p ⇔ q ) ⇔ [ ( p ⇒ q ) ∧ ( q ⇒ p ) ]
f

Zdanie:

(

p ⇔ q) ⇔ [(p ⇒ q) ∧ (q ⇒ p)]

jest tautologią.

(

p ⇒ q) ⇒ (¬q ⇒ ¬p)

Sprawdzenie metodą niewprost:

(

p ⇒ q ) ⇒ ( ¬ q ⇒ ¬ p )

t t f

Zdanie

(

p ⇒ q) ⇒ (¬q ⇒ ¬p)

jest tautologią.

(

¬q ⇒ ¬p) ⇒ (p ⇒ q)

Sprawdzenie metodą niewprost:

(

¬ q ⇒ ¬ p ) ⇒ ( p ⇒ q )

f t

t f
f

1. KLASYCZNA LOGIKA ZDAŃ

Zdanie:

(

¬q ⇒ ¬p) ⇒ (p ⇒ q)

jest tautologią.

¬(p ⇒ q) ⇒ (p ∧ ¬q)

Sprawdzenie metodą niewprost:

¬ ( p ⇒ q ) ⇒ ( p ∧ ¬ q )

t f

t f t

Zdanie:

¬(p ⇒ q) ⇒ (p ∧ ¬q)

jest tautologią.

(

p ∧ ¬q) ⇒ ¬(p ⇒ q)

Sprawdzenie metodą niewprost:

(

p ∧ ¬ q ) ⇒ ¬ ( p ⇒ q )

t t 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

(

p ⇔ q) ⇔ [(p ⇒ q) ∧ (¬p ⇒ ¬q)]

(

p ⇔ q) ⇔ [(¬q ⇒ ¬p) ∧ (¬p ⇒ ¬q)]

¬(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.

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

łatwo opisać za

pomocą prostych reguł. Np. dla spójnika negacji byłyby to następu-
jące reguły:

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.

1. KLASYCZNA LOGIKA ZDAŃ

W kolumnie I znajduje się schemat konstrukcji, do której stosu-

jemy regułę, zaś w kolumnie II - wynik zastosowania odpowiedniej
reguły.

. . . ¬ α . . .

Podobne reguły można by podać dla pozostałych spójników.

Litery

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

a może to być zdanie będące jego zdaniem składowym. Zauważmy,
że zamiast pisać litery

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

, a w lewą te, którym ma być przyporządkowana litera

. 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łąź, rozdziela się,
rozgałęzia. Drzewo ma tyle gałęzi, ile ma liści. Odcinek powyżej roz-
gałęzień to pień.

korzeń

pień

liść

(DEF. tablicy semantycznej) Tablica semantyczna to drzewo ze zda-
niami. Zdanie może znajdować się po lewej, bądź po prawej stronie
gałęzi. Zdania znajdujące się na pniu znajdują się na każdej gałęzi.

1. KLASYCZNA LOGIKA ZDAŃ

(DEF. relacji leżenia poniżej) Niech

jest innym (jako napis) napisem

niż

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

zachodzi stosu-

nek leżenia poniżej, czyli bądź

leży poniżej

, bądź

leży poniżej

. O zdaniach tworzących gałąź mówimy, że leżą na tej gałęzi.

(DEF. gałęzi sprzecznej) Gałąź 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łąź 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łąź, 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

Mogą to być napisy równokształtne.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

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ść

lub

. 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
(

) i prawostronne (

). 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.

REGUŁY

¬L

√

¬α

Reguła stosuje się do zdania

¬α

, znajdującego się po lewej stronie

gałęzi. Ta strona reprezentuje wartość

. Jeśli zdanie

¬α

ma wartość

1. KLASYCZNA LOGIKA ZDAŃ

, to jaką wartość ma

? Oczywiście,

ma wartość

. 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ść

. Jeśli zdanie

¬α

wartość

, to jakie jest zdanie

? Oczywiście, zdanie

ma wartość

. 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ść

, a więc zarówno

jak i

mają wartość

. Oba te zdania,

, 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

Reguła ta stosuje się do zdania

α ∧ β

, znajdującego się po pra-

wej stronie gałęzi. Strona ta reprezentuje wartość

. Zdanie

α ∧ β

wartość

, gdy

ma wartość

lub gdy

ma wartość

. 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ść

, zatem wartość

ma zdanie

lub wartość

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ść

, zatem wartość

przysłu-

guje zdaniu

i wartość

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

1. KLASYCZNA LOGIKA ZDAŃ

⇒ L

Reguła ta stosuje się do zdania

α ⇒ β

, znajdującego się po lewej

stronie gałęzi. Zdanie takie ma wartość

, zatem

ma wartość

lub

ma wartość

. 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ść

, zatem

ma wartość

, a

ma wartość

. 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

Reguła ta stosuje się do zdania

α ⇔ β

, znajdującego się po lewej

stronie gałęzi. Zdanie takie ma wartość

, zatem wartość

przysługuje

zarówno zdaniu

jak i zdaniu

lub wartość

mają zdania

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 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ść

, zatem zdaniu

przysługuje

wartość

a zdaniu

przysługuje wartość

lub odwrotnie, zdanie

ma wartość

a zdanie

ma wartość

. 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 – odpowiedź 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

1. KLASYCZNA LOGIKA ZDAŃ

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łęźne stosujemy przed regułami rozgałęźnymi.

Mając dwa zbiory zdań

, możemy pytać, czy istnieje in-

terpretacja taka, że wszystkie zdania z

mają wartość

, a wszyst-

kie zdania z

mają wartość

. Odpowiedź 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ść

, a gdy znajdują się po prawej przypisujemy wartość

Literom zdaniowym, które nie występują na branej pod uwagę gałęzi
przypisujemy dowolną z wartości

. Dla tak określonej interpreta-

cji wszystkie zdania ze zbioru

mają wartość

, a wszystkie zdania

ze zbioru

mają wartość

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ść

a wszystkie i tylko zdania ze zbioru

, zapisane

po prawej stronie pnia przyjmują wartość

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ść

a wszystkie i tylko zdania ze zbioru

, zapisane po prawej

stronie pnia przyjmują wartość

W każdym rozważanym tu wypadku będziemy brali pod uwagę

interpretację

taką, że wszystkim literom zdaniowym znajdującym

się na pewnej otwartej gałęzi – oznaczmy ją

– jeśli znajdują się po

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

stronie lewej przypisujemy wartość

, a gdy znajdują się po prawej

przypisujemy wartość

. Literom zdaniowym, które nie występują na

branej pod uwagę gałęzi przypisujemy dowolną z wartości

Nasze twierdzenie będzie wnioskiem z twierdzenia głoszącego, że

dla interpretacji

wszystkie zdania znajdujące się po lewej stronie

gałęzi

przyjmują wartość

, a wszystkie zdania znajdujące się po

prawej stronie

przyjmują wartość

Nasza teza zachodzi dla wypadku, gdy elementami

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

litery znajdujące się po lewej stronie przyjmują

wartość

, a litery znajdujące się po prawej stronie przyjmują wartość

Niech nasza teza zachodzi dla zdań o długości nie większej niż

Niech elementami

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

przyjmuje ono war-

tość

, zatem zdanie

¬α

przyjmuje wartość

. Podobnie będzie, gdy

¬α

będzie elementem

. Tym razem

przyjmie wartość

, a więc

¬α

przyjmie wartość

. Jeżeli elementem

będzie zdanie

α ⇒ β

to otwarta będzie gałąź, po prawej stronie której znajduje się

lub

otwarta będzie gałąź, po lewej stronie której znajduje się

. Zgodnie

z założeniem

dla interpretacji

przyjmuje wartość

lub

dla tej

interpretacji przyjmuje wartość

. Zatem dla interpretacji

zdanie

α ⇒ β

przyjmuje wartość

. 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

zdanie

przyjmuje

wartość

, a zdanie

przyjmuje wartość

. Zdanie

α ⇒ β

dla inter-

pretacji

przyjmuje wartość

. Podobnie pokazuje się zachodzenie

naszej tezy dla pozostałych spójników.

Teraz pokażemy, że zachodzi teza: jeżeli istnieje interpretacja –

oznaczmy ją

– taka, że wszystkie zdania ze zbioru

, zapisane po

lewej stronie pnia przyjmują dla tej interpretacji wartość

a wszystkie

zdania ze zbioru

, zapisane po prawej stronie pnia przyjmują wartość

, to tablica semantyczna jest otwarta.

1. KLASYCZNA LOGIKA ZDAŃ

Dla dowodu pokażemy, że istnieje otwarta gałąź – oznaczmy ją

– taka, że dla interpretacji

wszystkie zdania znajdujące się po

jej lewej stronie przyjmują wartość

, a wszystkie zdania znajdujące

się po jej prawej stronie przyjmują wartość

Sytuacja jest prosta w wypadku, gdy elementami

są wy-

łącznie litery zdaniowe. Załóżmy, że teza zachodzi dla zdań o długości
nie większej niż

. 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ś

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ż

. Dla tych zbiorów, zgodnie z założeniem,

zachodzi teza dowodzonego twierdzenia, czyli istnieje taka otwarta
gałąź, ż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ść

, a wszyst-

kie zdania z

wartość

, to dla tej interpretacji również zdania z

’

przyjmują wartość

a zdania z

’ przyjmują wartość

. Zgodnie z

założeniem dla zbiorów

’ i

’ istnieje otwarta gałąź a z tego wynika,

że również taka gałąź istnieje dla

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ść

, a wszystkie zdania z

mają

wartość

jest wówczas pytaniem o to, czy możliwa jest interpretacja

taka, że zdanie z

ma wartość

. 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ść

, a zdania z

mają wartość

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

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łąź 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ść

, gdy litera

ta znajduje się po lewej stronie, a wartość

, 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ę

lub

PYTANIE:

Czy tautologią jest zdanie

((

p ∧ (q ∨ r)) ⇒ ((p ∧ q) ∨ (p ∧ r)))

TABLICA SEMANTYCZNA

1. KLASYCZNA LOGIKA ZDAŃ

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ść

w wypadku, gdy zdaniom

(

p ⇔ ¬(q ⇔ r))

przysługuje wartość

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

ODPOWIEDŹ:

Wykluczona jest interpretacja taka, żeby zdaniom

(

p ⇔ ¬(q ⇔

r))

przysługiwała wartość

a zdaniu

¬(p ⇔ q)

przysługiwała

wartość

(lub, równoważnie, zdanie

(((

p ⇔ ¬(q ⇔ r)) ∧ r) ⇒ ¬(p ⇔ q))

jest tautologią).

PYTANIE:

Czy tautologią jest zdanie

((

p ⇒ q) ⇒ (¬p ⇒ ¬q))?

TABLICA SEMANTYCZNA

ODPOWIEDŹ:

1. KLASYCZNA LOGIKA ZDAŃ

Zdanie

((

p ⇒ q) ⇒ (¬p ⇒ ¬q))

nie jest tautologią.

Zdanie

((

p ⇒ q) ⇒ (¬p ⇒ ¬q))

przyjmuje wartość

dla interpre-

tacji takiej, że

przyjmuje wartość

wartość

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
(

−43

s.), to wykonanie

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

, ż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

taka, że dla

da-

nych algorytm wymaga wykonania co najwyżej

operacji. O takich

algorytmach mówi się, że działają w czasie wielomianowym. Jak na
razie nie udało się znaleźć takiego algorytmu dla rozstrzygania, czy
dane zdanie jest tautologią.

1.1.8. Elektronowa interpretacja spójników zdaniowych

Rachunek zdań znalazł interesujące zastosowanie techniczne w

maszynach matematycznych. Wartości logiczne zdań złożonych w za-

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

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.

Weźmy układ, który ma wejścia

. . .

oraz jedno wyjście.

Układ taki można graﬁcznie 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 ﬁzyczne. Mogą nimi
być np. pary: impuls, brak impulsu; napięcie

, napięcie

(

= v

Stany te można oznaczać:

. 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-

1. KLASYCZNA LOGIKA ZDAŃ

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ść

wtedy i tylko wtedy, gdy obu jego zdaniom-ar-

gumentom przysługuje wartość

)

albo dysjunkcji Sheﬀera (zdaniu

złożonemu przysługuje wartość

wtedy i tylko wtedy, gdy obu jego

zdaniom-argumentom przysługuje wartość

Z teorii sieci logicznych wywodzi się teoria sieci neuronowych

znajdujących zastosowanie, np. w biologii.

Por. rozdz. „Spójniki prawdziwościowe”.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

1.1.9. Tautologia a zdanie logicznie prawdziwe

TWIERDZENIE 2. (O PEŁ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:

, p

, . . . , p

(A)

Pokażemy, że jeżeli

nie jest prawdziwe w jakimś modelu, to

istnieje interpretacja taka, że

dla tej interpretacji przyjmuje wartość

Weźmy dowolny model

. Niech

, v

, . . . , v

będzie inter-

pretacją taką, że

wtedy i tylko wtedy, gdy

jest elementem

(

∈ M

), czyli

wtedy i tylko wtedy, gdy

nie jest ele-

mentem

(

∈ M

Pokażemy, że

M |= α

wtedy i tylko wtedy,

gdy

dla interpretacji

, v

, . . . , v

przyjmuje wartość

Dowodzić będziemy przez indukcję ze względu na długość zdania.

W wypadku, gdy

jest literą zdaniową, to zgodnie z określeniem

interpretacji

, v

, . . . , v

stwierdzamy, że

M |= α

wtedy i tylko

wtedy, gdy

przyjmuje wartość

ZAŁOŻENIE INDUKCYJNE: Niech

M |= β

wtedy i tylko wtedy,

gdy

dla interpretacji

, v

, . . . , v

przyjmuje wartość

oraz

1. KLASYCZNA LOGIKA ZDAŃ

M |= γ

wtedy i tylko wtedy, gdy

dla interpretacji

, v

, . . . , v

przyjmuje wartość

) Niech

będzie zdaniem:

¬β

1) Niech

M |= α

. Z deﬁnicji

dostajemy, że nie zachodzi

M |= β

Z założenia indukcyjnego otrzymujemy, że zdanie

dla interpretacji

, v

, . . . , v

przyjmuje wartość

, a zatem zdanie

(

¬β

) dla tej

interpretacji przyjmuje wartość

2) Niech

dla interpretacji

, v

, . . . , v

przyjmuje wartość

. A więc

przyjmuje wartość

. Z założenia indukcyjnego wynika

więc, iż nie zachodzi

M |= β

, a zatem zachodzi

M |= α

(

¬β

⇒

) Niech

będzie zdaniem:

β ⇒ γ

⇒

1) Niech nie zachodzi

M |= α

. Z deﬁnicji

wynika, że zachodzi

M |= β

oraz że nie zachodzi

M |= γ

. Korzystając z założenia induk-

cyjnego dostajemy, że

dla interpretacji

, v

, . . . , v

przyjmuje

wartość

zaś

dla tej interpretacji przyjmuje wartość

. Z tego więc

dostajemy, że dla interpretacji

, v

, . . . , v

zdanie

(

β ⇒ γ

)

przyjmuje wartość

⇒

2) Niech

dla interpretacji

, v

, . . . , v

przyjmuje war-

tość

. Pokażemy, że nie zachodzi

M |= α

. Mamy bowiem, że

dla

tej interpretacji przyjmuje wartość

zaś

przyjmuje wartość

. Ko-

rzystając z założenia indukcyjnego dostajemy, że zachodzi

M |= β

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

, v

, . . . , v

zdanie

β ⇔ γ

przyjmuje wartość

. 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

, v

, . . . , v

zdanie

β ⇔ γ

przyjmuje wartość

Teraz dowodzimy, że

(A)

jeżeli

, to

|= α

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

Załóżmy więc, że

. Gdyby nie zachodziło

|= α

, to istniałby model

taki, że

nie byłoby w nim prawdziwe. Zgodnie z powyższym

dla interpretacji

, v

, . . . , v

zdanie

przyjmowałoby wartość

, 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ść

, to

istnieje model taki, że

nie jest w tym modelu prawdziwe.

Niech

, v

, . . . , v

będzie dowolną interpretacją. Niech

bę-

dzie modelem takim, że

∈ M

wtedy i tylko wtedy, gdy

Twierdzimy, iż

dla interpretacji

, v

, . . . , v

przyjmuje wartość

wtedy i tylko wtedy, gdy

|= α

Fakt ten może być dowiedziony przez indukcję w analogiczny

sposób jak dowodziliśmy, że

M |= α

wtedy i tylko wtedy,

gdy

dla interpretacji

, v

, . . . , v

przyjmuje wartość

Zauważmy jednak, że

wtedy i tylko wtedy, gdy

. Fakt

ten jest więc oczywistym wnioskiem z powyższego.

Załóżmy, że

|= α

. Gdyby istniała interpretacja

taka, że

dla tej

interpretacji nie przyjmowałoby wartości

, to

nie byłoby prawdziwe

w modelu

, a to przeczyłoby założeniu. Zatem

dla wszystkich

interpretacji przyjmuje wartość

, 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.

1. KLASYCZNA LOGIKA ZDAŃ

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ń

, 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ójnikiem

Spójniki:

⇒

∨

∧

⇔

są spójnikami prawdziwościowymi.

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 deﬁniowana jest następująco:

α ≺ β =

¬M(α ∧ ¬β)

gdzie

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

(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

ekstensjonalnie różnych

-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. Weźmy dla przykładu spójnik
dwuargumentowy

↓

taki, że zdanie złożone zbudowane za pomocą

tego spójnika ma wartość

wtedy i tylko wtedy, gdy obu zdaniom-

-argumentom przysługuje wartość

(DEF.

↓

) Spójnik

↓

jest charakteryzowany przez następującą tabelkę

wartości logicznych:

β γ

β ↓ γ

f f

Na odczytanie spójnika

↓

, określanego jako binegacja, jednoczesne

zaprzeczenie lub funktor Łukasiewicza, znajdujemy wyrażenie „ani

1. KLASYCZNA LOGIKA ZDAŃ

. . .

, 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”

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

”. Ł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ś

-argumentowego spójnika prawdziwościowego

przez inne spójniki polega więc na tym, żeby znaleźć zdanie zbudo-
wane za pomocą tych innych spójników i (niekoniecznie wszystkich i
niekoniecznie tylko) zdań-argumentów spójnika

takie, aby dla każ-

dej interpretacji wartości logiczne tego zdania i zdania zbudowanego
za pomocą spójnika

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

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,

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

że zdania

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

α/β/ ⇔ α/γ/

ZAŁOŻENIE INDUKCYJNE: Niech dla

, jeżeli

β ⇔ γ

, to

/β/ ⇔ α

/γ/

. Ponadto

⇔ α

, co jest oczywiste.

(

) Jeżeli

jest zdaniem

¬α

β ⇔ γ

, to na podstawie założenia

indukcyjnego mamy, że dla dowolnej interpretacji wartość logiczna

/β/

jest taka sama, jak wartość logiczna

/γ/

. Zatem dla dowolnej

interpretacji wartość logiczna

¬α

/β/

jest taka sama, jak

¬α

/γ/

, czyli

α/β/ ⇔ α/γ/

Dla wszystkich spójników dwuargumentowych postępujemy po-

dobnie. Rozważmy więc tylko wypadek alternatywy.

(

∨

) Jeżeli

jest zdaniem

∨α

β ⇔ γ

, to na podstawie założenia

indukcyjnego dla dowolnej interpretacji wartość logiczna

/β/

jest

taka sama, jak wartość logiczna

/γ/

. Zatem dla dowolnej interpre-

tacji wartość logiczna

/β/ ∨ α

jest taka sama, jak wartość logiczna

/γ/ ∨ α

, czyli

α/β/ ⇔ α/γ/

Podobnie postępujemy, gdy

jest zdaniem

∨ α

TWIERDZENIE 4 (O FUNKCJONALNEJ PEŁ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

-argumentowy spójnik prawdziwościowy

Niech spójnik ten będzie charakteryzowany przez następującą tabelkę
wartości logicznych:

1. KLASYCZNA LOGIKA ZDAŃ

. . .

s(α

, α

, . . . , α

)

. . .

. . . v

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:

¬, ∨

∧

Rozważmy wpierw wypadek, gdy

jest zdaniem, w którym wy-

stępuje tylko spójnik

(wszystkie argumenty spójnika

są literami

zdaniowymi).

W wypadku, gdy wszystkie wartości

, . . . , v

, jakie przyj-

muje

są równe

, to jako

bierzemy koniunkcję wszystkich wystę-

pujących w

liter zdaniowych i ich negacji. Zdanie to dla dowolnej

interpretacji przyjmuje wartość

. Jest zatem równoważne zdaniu

Niech teraz dla jakiegoś układu wartości

, v

, . . . , v

zdanie

przyjmuje wartość

. Dla każdego układu wartości

, v

, . . . , v

(

j =

, . . . , 2

)

, dla którego

przyjmuje wartość

bierzemy koniunkcję liter

zdaniowych

, gdy

przyjmuje wartość

¬p

, gdy

przyjmuje war-

tość

. Koniunkcja ta przyjmuje wartość

wtedy i tylko wtedy, gdy

litera zdaniowa

przyjmuje wartość

(

i = 1, . . . , n; j = 1, . . . , 2

)

Alternatywa wszystkich takich koniunkcji jest równoważna zdaniu

ZAŁOŻENIE INDUKCYJNE: Niech

, . . . β

będą zdaniami takimi,

że istnieją równoważne im zdania, odpowiednio,

, . . . , β

zbudo-

wane tylko za pomocą spójników:

¬, ∨, ∧

. Niech

będzie zdaniem

s(β

, . . . , β

)

. Postępujemy podobnie jak w wypadku, gdy argumen-

tami

były litery zdaniowe. Tym razem jednak zamiast liter zdanio-

wych bierzemy zdania

, . . . , β

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

Każdy ze zbiorów spójników

{¬, ∨}

{¬, ∧}

{¬, ⇒}

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

∨

∧

oraz

⇒

⇔

(a także,

oczywiście, liter zdaniowych) dla interpretacji takiej, że wszystkie li-
tery zdaniowe przyjmują wartość

przyjmuje wartość

Niech

będzie dowolnym zdaniem, w którym występują jedynie

spójniki:

∨

∧

⇒

⇔

1. Jeżeli

jest literą zdaniową, to

ma wartość

2. Niech

przysługuje wartość

. Gdy

jest zdaniem postaci

β∨γ

, wówczas

przysługuje wartość

. Podobnie, gdy

ma postać

β ∧ γ

β ⇒ γ

lub

β ⇔ γ

. Stwierdzamy więc, że dla zdania

¬p

nie

istnieje zdanie jemu logicznie równoważne zbudowane wyłącznie

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óźniej opublikowanej, Post [1921].

1. KLASYCZNA LOGIKA ZDAŃ

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ść

tyle samo razy, ile

razy przyjmuje wartość

albo przyjmuje te wartości parzystą liczbę

razy

Faktu tego dowodzimy przez indukcję po długości zdania.

Litery zdaniowe przyjmują wartość

tyle samo razy, ile razy

przyjmują wartość

. Niech

spełniają założenia. Wypadek zda-

nia

¬α

jest prosty. Jeżeli

przyjmuje wartość

tyle samo razy, ile

razy przyjmuje wartość

, to tak samo jest w wypadku

¬α

. Jeżeli

przyjmuje wartość

parzystą liczbę razy, to z faktu, że liczba wszyst-

kich interpretacji jest parzysta wynika, że

również parzystą liczbę

razy przyjmuje wartość

, zatem tak samo jest w wypadku

¬α

Gdy

przyjmuje wartość

tyle samo razy, ile razy przyjmuje

wartość

i podobnie jest dla

, to – ponieważ wszystkich interpretacji

jest parzysta liczba – zdanie

α ⇔ β

przyjmuje wartości

parzystą

liczbę razy. Gdy dla zdania

α ⇔ β

istnieje więcej niż dwie (różne)

interpretacje, to dla tych interpretacji zarówno

jak i

przyjmują

wartość

lub

parzystą liczbę razy. Z tego wynika, że również

α ⇔ β

przyjmuje wartość

lub

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ść

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ściowych

Pokazano również, że taką samą własność

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.

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

ma także spójnik zwany kreską Sheﬀera, oznaczany

, a odczytywany

„albo nie

. . .

albo nie

. . .

”

Spójnik ten jest charakteryzowany na-

stępującą tabelką:

β γ

β | γ

f f

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ściowych

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.

PRZYKŁAD

Zdaniem o postaci normalnej dysjunkcyjnej jest:

(

p ∧ r) ∨ (p ∧ q ∧ ¬r)

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

∨

został podany w 1912 r.

przez H. M. Sheﬀera (1883–1964), który nie znał prac Peirce’a. Zob. Sheﬀer [1913].

Twierdzenie to udowodnił E. Żyliński [1925].

1. KLASYCZNA LOGIKA ZDAŃ

(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.

PRZYKŁ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 znaleźć. Dla każdej gałęzi bierzemy koniunkcję,

1.2. WYNIKANIE SYNTAKTYCZNE

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 znaleźć. 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

oraz

¬p

, 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

oraz

¬p

, 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. Zdeﬁniujemy 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-

1. KLASYCZNA LOGIKA ZDAŃ

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)

Podstawową regułą syntaktyczną

(operacją na napisach) będzie reguła odrywania (MP, modus ponens):

ze zdań

α ⇒ β

wyprowadzalne jest zdanie

Zdanie

daje się wyprowadzić ze zdań

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ń

, α

, . . . , α

, że

α = α

oraz dla każdego

≤ i ≤ n

, spełniony jest jeden z warunków:

(I)

jest tautologią,

(II)

należy do

(III) istnieją

j, k < i

takie, że

daje się za pomocą reguły odrywania

wyprowadzić ze zdań

Ciąg

, α

, . . . , α

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

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

(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.

PRZYKŁAD

Pokażemy że zdanie

a < c

ma dowód ze zbioru

{a < b ∧ b < c ⇒

a < c, a < b, b < c}

; czyli że

{a < b ∧ b < c ⇒ a < c, a < b, b < c} a < c

a < b ⇒ (b < c ⇒ ((a < b ∧ b < c ⇒ a < c) ⇒ a < c))

tautologia

a < b

założenie

b < c ⇒ ((a < b ∧ b < c ⇒ a < c) ⇒ a < c)

(MP 1, 2)

b < c

założenie

(

a < b ∧ b < c ⇒ a < c) ⇒ (a < c)

(MP 3, 4)

a < b ∧ b < c ⇒ a < c

założenie

a < c

(MP 5, 6)

LEMAT 1.

Jeżeli

α ⇒ β

są tautologiami, to

jest tautologią.

DOWÓD

Niech w ciągu

, p

, . . . , p

znajdują się wszystkie litery zdaniowe,

z których jest zbudowane zdanie

α ⇒ β

i niech

nie będzie tautolo-

gią. Istnieje zatem taka interpretacja

, v

, . . . , v

, że zdanie

dla tej

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.

1. KLASYCZNA LOGIKA ZDAŃ

interpretacji przyjmuje wartość

. Ponieważ z założenia

α ⇒ β

jest

tautologią, więc

dla tej interpretacji musi przyjmować wartość

, 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

, α

, . . . , α

będzie pewnym dowodem

. Przez indukcję po długości tego dowodu

pokażemy, że

jest tautologią.

Ponieważ

jest puste, więc zgodnie z deﬁnicją dowodu

może

być tylko tautologią.

ZAŁOŻENIE INDUKCYJNE: Niech dla

i ≤ k

będzie tautologią.

Pokażemy, że

k+1

jest tautologią. Zgodnie z deﬁnicją 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

, . . . , α

. 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

(DEF.

Cn(Σ)

) Niech

Cn(Σ)

będzie zbiorem wszystkich zdań, które

mają dowód ze zbioru

, czyli

Cn(Σ) = {α : Σ α}.

Cn(Σ)

mówimy,

że jest zbiorem konsekwencji

TWIERDZENIE 6.

⊆ Cn(Σ)

2. jeżeli

⊆ Γ

, to

Cn(Σ) ⊆ Cn(Γ)

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

, α

, . . . , α

będzie dowodem

zbioru

. Ciąg ten jest również dowodem

ze zbioru

3. Niech

α ∈ Cn[Cn(Σ)].

Niech

, α

, . . . , α

będzie dowodem

ze zbioru

Cn(Σ).

Na drodze wnioskowania przez indukcję po

długości dowodu pokażemy, że dla każdego

i, 0 ≤ i ≤ n

dowód ze zbioru

; czyli że jest elementem zbioru

Cn(Σ).

może być tylko tautologią lub elementem

Cn(Σ).

Jeżeli

jest

tautologią, to ma dowód z

. Jeżeli

jest elementem

Cn(Σ)

, to –

na podstawie deﬁnicji

–

ma również dowód z

. Zatem

dowód z

, czyli

∈ Cn(Σ).

ZAŁOŻENIE INDUKCYJNE: Niech dla

(

≤ k < n

ma dowód z

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

. Pozostaje więc rozważyć wypadek, gdy

k+1

jest otrzy-

mane za pomocą MP ze zdań

mających dowód z

Cn(Σ)

. Z

– 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].

1. KLASYCZNA LOGIKA ZDAŃ

założenia indukcyjnego zdania te mają dowód z

. Niech

, β

, . . . , β

będzie dowodem ze zbioru

zdania

, zaś

, γ

, . . . , γ

niech będzie

dowodem ze zbioru

zdania

. Ciąg

, β

, . . . , β

, γ

, . . . , γ

, α

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

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

, p

, . . . , p

znajdują się wszystkie litery zdaniowe,

z których jest zbudowane zdanie

β ⇒ α

. Gdyby

β ⇒ α

nie było tau-

tologią, to istniałaby interpretacja

, v

, . . . , v

taka, że dla tej inter-

pretacji zdanie

β ⇒ α

przyjmowałoby wartość

. Byłoby to jednak

możliwe tylko wówczas, gdyby

dla tej interpretacji przyjmowało

wartość

, a to jest wykluczone, z założenia bowiem

jest tautolo-

gią.

TWIERDZENIE 7 (O DEDUKCJI)

∪ {α} β

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

wtedy i tylko wtedy, gdy

α ⇒ β

DOWÓD

Udowodnimy dwie tezy, które łącznie składają się na twierdzenie

o dedukcji, a mianowicie:

jeżeli

α ⇒ β

, to

∪ {α} β

jeżeli

∪ {α} β

, to

α ⇒ β

Dowód faktu A jest krótki. Niech

, α

, . . . , α

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:

, α

, . . . , α

, α

. Ponieważ

daje się za pomocą

MP wyprowadzić z

α ⇒ β

) i

, zatem do ciągu dowodowego

, α

, . . . , α

, α

możemy również dołączyć

. Ciąg:

, α

, . . . , α

, α, β

jest dowodem ze zbioru

∪ {α}

zdania

Dowód faktu B jest bardziej złożony. Niech

∪ {α} β

, czyli

niech istnieje dowód

ze zbioru

∪ {α}

. Niech

, α

, . . . , α

będzie

tym dowodem. Przez indukcję po długości tego dowodu pokażemy, że
dla każdego

i, 0 ≤ i ≤ n

α ⇒ α

. W szczególności dla

i = n

będzie:

α ⇒ β

Pokażmy to wpierw dla

i = 0

może być tautologią bądź może być założeniem.

Gdy

jest tautologią, to – na podstawie wyżej udowodnionego

lematu –

α ⇒ α

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-
dyﬁkacje twierdzenia o dedukcji jak np. dla implikacji zstępujących, zob. Surma
[1968]. Odpowiedniki twierdzenia o dedukcji wskazano dla wielu nieklasycznych
systemów logiki.

1. KLASYCZNA LOGIKA ZDAŃ

Jeżeli

jest założeniem, to jest to bądź zdanie

, bądź jakiś

element zbioru

Jeżeli

jest zdaniem

, to zdanie

α ⇒ α

ma dowód z

, jest

bowiem tautologią.

Niech

∈ Σ

. Ciąg:

⇒ (α ⇒ α

)

tautologia

założenie

α ⇒ α

(MP; 1,2)

jest dowodem zdania

α ⇒ α

ze zbioru

ZAŁOŻENIE INDUKCYJNE: Niech dla

i ≤ k < n

zachodzi:

α ⇒

Pokażemy, że dla

i = k + 1

zachodzi

α ⇒ α

k+1

Zgodnie z deﬁnicją dowodu,

k+1

może być bądź tautologią, bądź

założeniem, bądź 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

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

oraz

⇒ α

k+1

. Zgodnie z zało-

żeniem indukcyjnym zdania

α ⇒ α

α ⇒ (α

⇒ α

k+1

)

mają dowód

ze zbioru

. Niech ciąg:

, β

, . . . , β

α ⇒ α

)

będzie dowodem ze zbioru

zdania

α ⇒ α

a ciąg:

, γ

, . . . , γ

α ⇒ (α

⇒ α

k+1

)]

będzie dowodem ze zbioru

zdania

α ⇒ (α

⇒ α

k+1

)

Ciąg:

, β

, . . . , β

, γ

, . . . , γ

przedłużony o następujące trzy zdania:

(l+u+3).

[

α ⇒ (α

⇒ α

k+1

)]

⇒

1.2. WYNIKANIE SYNTAKTYCZNE

[(

α ⇒ α

)

⇒ (α ⇒ α

k+1

)]

tautologia

(l+u+4).

(

α ⇒ α

)

⇒ (α ⇒ α

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ń.

Deﬁnicja zbioru sprzecznego jest równoważna określeniu zbioru

sprzecznego jako takiego zbioru, którego zbiór konsekwencji jest
równy zbiorowi

wszystkich zdań, czyli

jest sprzecznym zbiorem

zdań wtedy i tylko wtedy, gdy

(

)

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

1. KLASYCZNA LOGIKA ZDAŃ

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

mówi się, że są przeciwne (wykluczają się) wtedy i

tylko wtedy, gdy tautologią jest zdanie:

¬(α ∧ β)

(DEF. pary zdań podprzeciwnych) Zdania

są podprzeciwne (do-

pełniają się) wtedy i tylko wtedy, gdy tautologią jest zdanie:

(

α ∨ β)

PRZYKŁADY

Wykluczają się zdania:

¬p ∧ q

Dopełniają się zdania:

¬p ∨ q

(DEF. pary zdań sprzecznych) O zdaniach

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

(

α ∨ β)

PRZYKŁ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

(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

wykluczają się, a

więc że tautologią jest zdanie

(

α ∧ β

). Pokażemy, że dla dowolnego

istnieje dowód ze zbioru

{α, β}.

(

α ∧ β) ⇒ γ

tautologia

α ⇒ [β ⇒ (α ∧ β)]

tautologia

założenie

β ⇒ (α ∧ β)

(MP;2,3)

założenie

(

α ∧ β)

(MP; 4,5)

(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

wykluczają się. W

przeciwnym wypadku istniałaby bowiem taka interpretacja, że zdania

miałyby dla tej interpretacji wartość

. Zdanie

(

α ∧ β

) miałoby

więc wartość

, a co za tym idzie wartość

przysługiwałaby zdaniu

α ⇒

[

β ⇒ ¬

(

α ∧ β

)].

Z powyższego faktu mamy

WNIOSEK

1. KLASYCZNA LOGIKA ZDAŃ

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

dowód z

Cn(Σ)

– czyli

α ∈ Cn[Cn(Σ)]

– to

α ∈ Cn(Σ)

, a więc

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

¬ α

lub

α ∧ ¬ α

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

2. gdy dla pewnego

dowód z

α ∧ ¬α

, 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:

, β

, . . . , β

α)

będzie dowodem ze zbioru

zdania

, a ciąg:

, γ

, . . . , γ

¬α)

dowodem ze zbioru

zdania

¬ α

. Niech

będzie dowolnym zdaniem.

Ciąg:

, β

, . . . , β

, γ

, . . . , γ

, α ⇒ (¬α ⇒ β), ¬α ⇒ β, β

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:

, β

, . . . , β

jest dowodem

α ∧ ¬α

, to ponieważ zdanie

α ∧ ¬α ⇒ β

jest tautologią,

więc ciąg:

, β

, . . . , β

, α ∧ ¬α ⇒ β, β

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

1. KLASYCZNA LOGIKA ZDAŃ

, β

, . . . , β

¬α ⇒ α)

będzie dowodem

¬ α ⇒ α

ze zbioru

. Zdanie:

(

¬α ⇒ α) ⇒ α

jest tautologią. Zatem ciąg:

, β

, . . . , β

, (¬α ⇒ α) ⇒ α, α

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)

Każdy niesprzeczny zbiór zdań może być rozszerzony do maksy-
malnego niesprzecznego zbioru zdań.

DOWÓD

Autorem tego twierdzenia jest Adolf Lindenbaum (1904–1941). W tej sprawie

zob. Tarski [1956], s. 98.

1.2. WYNIKANIE SYNTAKTYCZNE

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:

¬, ∨, ∧, ⇒, ⇔, (, ), p

, p

, . . .

Niech

, α

, . . .

będzie ciągiem wszystkich zdań języka rachunku zdań.

Niech

będzie dowolnym niesprzecznym zbiorem zdań. Two-

rzymy ciąg zbiorów zdań:

, Σ

, . . .

taki, że

(I)

= Σ

(II)

i+1






jeżeli

∪ {α

}

jest sprzeczne,

∪ {α

jeżeli

∪ {α

}

jest niesprzeczne

Twierdzimy, że zbiór

Γ =

∞

i=0

, czyli zbiór będący sumą teorio-

-mnogościową wszystkich i tylko zbiorów z ciągu:

, Σ

, . . . ,

jest

maksymalnym niesprzecznym nadzbiorem

W dowodzie, że

jest maksymalnym niesprzecznym nadzbiorem

zbioru

wykorzystamy fakt, że

⊆ Σ

⊆ . . . ⊆ Γ

, oraz że

wszystkie

≤ 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:

, β

, . . . , β

będzie dowodem ze zbioru

zdania

α ∧ ¬α

Nadzbiorem zbioru

jest każdy zbiór

taki, że

⊆ Γ

1. KLASYCZNA LOGIKA ZDAŃ

Ponieważ ciąg ten ma skończoną ilość wyrazów, więc istnieje

takie,

że wszystkie zdania z ciągu:

, β

, . . . , β

, które są elementami

, są

też elementami

; a więc ciąg ten byłby dowodem z

zdania

α ∧ ¬ α

Na podstawie twierdzenia 9, zbiór

byłby więc zbiorem sprzecz-

nym, a to nie jest prawdą.

Zbiór

jest maksymalny. Gdyby bowiem dla jakiegoś

zbiór

∪{α

}

nie był sprzeczny, to jest jasne, że nie byłby również sprzeczny

zbiór

∪{α

}

. A więc

należałoby do

m+1

i – z określenia zbioru

–

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

;

(V)

α ⇔ β

należy do

wtedy i tylko wtedy, gdy (

należy do

wtedy i tylko wtedy, gdy

należy do

DOWÓD

(I1) Gdyby

¬α

należały do

, to – na podstawie twierdzenia 9 –

byłoby sprzeczne, a to jest wbrew założeniu. Zatem jeżeli

należy

, 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

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

, α

, . . . , α

α ⇒ ¬α)

będzie dowodem ze zbioru

zdania

α ⇒ ¬ α

. Ponieważ zdanie (

α ⇒

¬ α

)

⇒ ¬ α

jest tautologią, więc ciąg:

, α

, . . . , α

, (α ⇒ ¬α) ⇒ ¬α, ¬α

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

¬α

nie należy do

Na podstawie (I) mamy, że

należy do

. Ponieważ

daje się za

pomocą reguły odrywania wyprowadzić z

α ⇒ β

, a

jest zbiorem

maksymalnym, więc

należy do

Teraz rozważmy wypadek, że

α ⇒ β

należy do

nie należy do

. Na podstawie (I) do

należy

¬β

. Korzystając z

[(

α ⇒ β)∧¬β] ⇒ ¬α

(modus tollens) stwierdzamy, że dowód z

¬α

. Z maksymalności

mamy więc, że

¬α

należy do

(II2) Dla dowodu tezy, że jeżeli

¬α

lub

należy do

, to

α ⇒ β

należy

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.

Wyszukiwarka

Podobne podstrony:
07 2 Klasyczna logika predykatów cd
04 Krótka Logika Portalu Ea, 2str(1)
11 04 14 Logika
logika rozw zadan v2
zestawy zadań, rrz 04 22
Logika rozwiazania zadan id 272023
Logika, KLASYCZNY RACHUNEK ZDAŃ
Rozwiązania do zadań z wykładów, Prawo UŁ, rok I 2011, Logika dla prawników
logika wyklad 04
Logika NSA 04 2014
logika 25.04, Prawo UMK, 1. rok, Logika
Logika prawnicza Ćwiczenia 1 04 2014r
W9 - Klasyczny rachunek logiczny, szkoła, logika
zestawy zadań rrz-03-04
zestawy zadań rrz-04-22
Wstęp do logiki klasycznej, Filozofia, @Filozofia, PhilloZ, Logika
Z Ćwiczenia 06.04.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika

więcej podobnych podstron