Wstęp

2

1. Wynikanie semantyczne

3

2. Reguły inferencyjne i pojęcie dowodu formalnego

5

3. System dedukcji naturalnej

9

4. Dowody przez dodatkowe założenie

16

5. Formy zdaniowe

17

6. Kwantyfikatory

19

Bibliografia

21

Wynikanie logiczne

i elementy rachunku kwantyfikatorów

2

Wstęp

W niniejszej części materiałów przedstawimy ciąg dalszy rozważań dotyczących
rachunku zdań. Zdefiniowane zostanie — a także scharakteryzowane
odpowiednimi twierdzeniami — pojęcie wynikania semantycznego. Na tej bazie
wprowadzimy analogiczne pojęcie, jakim jest wynikanie syntaktyczne. Zdefiniujemy
zatem pojęcie dowodu formalnego wprost i nie wprost. Wprowadzimy pewien
układ reguł dedukcji naturalnej zupełny wobec prezentowanego w poprzednim
module semantycznego ujęcia rachunku zdań. Zdefiniowane zostanie też pojęcie
formy zdaniowej i wprowadzone kwantyfikatory. Omówimy pojęcia zmiennej
wolnej i zmiennej związanej. Zaprezentujemy przykładowe prawa rachunku
kwantyfikatorów.

3

1. Wynikanie semantyczne

Powiemy, że

formuła

α

wynika

semantycznie ze zbioru formuł

X, co będziemy oznaczać

X ׀= α, jeżeli formuła α jest prawdziwa dla wszystkich wartościowań dających
wartość 1 dla wszystkich formuł ze zbioru X.

Przykład 1

Rozważmy formułę p ⇒ q oraz zbiór formuł X = {p, q}. Rozważmy wszystkie
wartościowania v, w których są prawdziwe wszystkie formuły (zmienne) ze zbioru
X. Mamy wartościowanie v(p) = 1 oraz v(q) = 1. Ale wtedy mamy również
w(p ⇒ q) = 1. Zatem zdanie p ⇒ q wynika ze zbioru X = {p, q} ({p, q} ׀= p ⇒ q).

Przykład 2

Rozważmy formułę ¬(¬p ∧ q) oraz zbiór formuł X = {p, ¬q}. Rozważmy
wszystkie wartościowania v, w których są prawdziwe wszystkie zdania ze zbioru
X. Mamy wartościowanie v(p) = 1 oraz v(q) = 0. Dla tego wartościowania
jest: w(¬(¬p ∧ q)) = 1. Zatem formuła ¬(¬p ∧ q) wynika ze zbioru
X = {p, ¬q} ({p, ¬q} ׀= ¬(¬p ∧ q)).

Z definicji wynikania można wyprowadzić warunek na fakt, że dane zdanie nie
wynika z odpowiedniego zbioru zdań.

Powiemy, że

formuła

α

nie wynika

semantycznie ze zbioru formuł

X (X ׀≠ α), jeżeli dla

pewnego wartościowania v wszystkie zdania ze zbioru X

są prawdziwe, zaś zdanie

α jest fałszywe (w(α) = 0).

Przykład 3

Rozważmy formułę ¬p ∧ q oraz zbiór formuł X = {p, q}. Rozważmy wszystkie
wartościowania v, w których są prawdziwe wszystkie zdania ze zbioru X.
Mamy wartościowanie v(p) = 1 oraz v(q) = 1. Dla tego wartościowania jest:
w(¬p ∧ q) = 0. Zatem formuła ¬p ∧ q nie wynika ze zbioru X = {p, q} ({p, q} ׀≠ ¬p ∧ q).

Zachodzą następujące twierdzenia:

Twierdzenie 1

Formuła α jest tautologią wtedy i tylko wtedy, gdy wynika semantycznie ze zbioru
pustego. Symbolicznie ∅ ׀= α lub krócej ׀= α (bez wypisywania zbioru przed
symbolem wynikania).

Twierdzenie 2

Formuła

α

wynika

semantycznie

ze

skończonego

zbioru

formuł

X = {α

1

, α

2

, ..., α

n

} (X ׀= α) wtedy i tylko wtedy, gdy implikacja (α

1

∧ α

2

∧ ... ∧ α

n

) ⇒ α

jest tautologią.

4

Dowód

Załóżmy, że formuła α wynika semantycznie ze skończonego zbioru formuł
X = {α

1

, α

2

, ..., α

n

}. Wtedy dla dowolnego wartościowania, dla którego formuły

α

1

, α

2

, ..., α

n

przyjmują wartość 1, również formuła α przyjmuje wartość 1.

Rozważmy implikację (α

1

∧ α

2

∧ ... ∧ α

n

) ⇒ α. Wszystkie wartościowania możemy

podzielić na dwie grupy: takie, dla których wartość koniunkcji α

1

∧ α

2

∧ ... ∧ α

n

wynosi 0 oraz takie, dla których wartość tej koniunkcji jest równa 1. W pierwszym
przypadku mamy fałszywy poprzednik rozpatrywanej implikacji, jest ona
zatem prawdziwa. W drugim przypadku zauważmy, że jeżeli wartość koniunkcji

α

1

∧ α

2

∧ ... ∧ α

n

jest równa 1, to każda z formuł α

1

, α

2

, ..., α

n

musi również

przyjmować wartość 1. Możemy wtedy skorzystać z założenia, że również formuła

α (następnik rozpatrywanej implikacji) ma wartość 1, zatem implikacja jest
także prawdziwa. Widzimy, że dla dowolnych wartościowań wartość implikacji
(α

1

∧ α

2

∧ ... ∧ α

n

)

⇒ α jest równa 1. Zatem jest ona tautologią.

Załóżmy teraz, że implikacja (α

1

∧ α

2

∧ ... ∧ α

n

) ⇒ α jest tautologią. Rozważmy

wszystkie wartościowania, dla których formuły ze zbioru X = {α

1

, α

2

, ..., α

n

} mają

wartość 1. Oczywiście, dla tych wartościowań formuła α nie może mieć wartości
0, gdyż byłoby to sprzeczne z tautologicznością implikacji (α

1

∧ α

2

∧ ... ∧ α

n

) ⇒ α.

Zatem formuła α musi mieć wartość 1. Oznacza to oczywiście, że formuła α wynika
semantycznie ze skończonego zbioru formuł X = {α

1

, α

2

, ..., α

n

} (X ׀= α).

5

2. Reguły inferencyjne

i pojęcie dowodu formalnego

W dotychczasowych rozważaniach przedstawiliśmy tzw. semantyczne ujęcie
rachunku zdań. Oznacza to, że odwoływaliśmy się do pojęcia wartości logicznych,
wartościowania zmiennych i wartości formuł dla danych wartościowań zmiennych.
Przedstawimy teraz tak zwane syntaktyczne ujęcie omawianego rachunku
logicznego. W ujęciu tym nie odwołujemy się do pojęć semantycznych (wartości
logicznych itp.), ale wykonujemy wnioskowanie, wyprowadzając (dedukując) jedne
formuły z innych.

Odpowiednikiem omawianego wyżej pojęcia wynikania semantycznego jest tutaj
pojęcie wynikania syntaktycznego związane ściśle z pojęciami reguł inferencyjnych
oraz dowodu formalnego.

Reguły inferencyjne

to schematy pozwalające wyprowadzać (dedukować) formuły

z innych formuł. Schematy te przedstawiać będziemy w następującej postaci:

, gdzie formuły α

1

, α

2

, ..., α

n

będziemy nazywać

przesłankami

, zaś

formułę β —

wnioskiem

. Ogólnie reguła o schemacie:

pozwala z for-

muł (przesłanek) α

1

, α

2

, ..., α

n

wyprowadzić (wydedukować) formułę β (wniosek).

Dla uproszczenia zapisu będziemy czasem stosować następującą notację

dla symetrycznych par reguł postaci:

oraz .

Przykład 4

Jako przykład przedstawimy reguły

E

liminacji

K

oniunkcji (

EK

) o schematach:

oraz

. Reguły te pozwalają z dowolnej koniunkcji α ∧ β (zauważmy, że α

oraz β mogą być dowolnymi formułami) wyprowadzać czynniki tej koniunkcji.

I tak — jeżeli rozważymy formułę (¬r ∨ p) ∧ ¬(¬p ∨ q ⇒ s) — to na mocy reguł

EK

możemy z tej formuły wyprowadzić oba jej czynniki: ¬r ∨ p oraz ¬(¬p ∨ q ⇒ s).

Oczywiście, dane reguły nie zawsze możemy stosować do dowolnych formuł.
Powyższych reguł

EK

nie możemy zastosować na przykład do formuły

¬(¬p ∨ q ⇒ s), gdyż ta nie jest koniunkcją.

Przykład 5

Reguły

E

liminacji

A

lternatywy (

EA

) mają następujące schematy:

,

.

6

Reguły te pozwalają z alternatywy i negacji jednego z jej składników wyprowadzić
drugi składnik alternatywy. I tak — jeżeli rozważymy formułę (¬p ⇒ q) ∨ (q ⇒ s)
oraz formułę ¬(¬p ⇒ q) — to na mocy jednej z reguł

EA

możemy z tych formuł

wyprowadzić formułę (q ⇒ s). Oczywiście — jak w poprzednim przypadku
— dane reguły nie zawsze możemy stosować do dowolnych formuł.

Przykład 6

Z pewnych względów wzbogacamy język rozważań o stałą logiczną reprezentującą
pojęcie sprzeczności, oznaczaną symbolem

⊥. W dalszych rozważaniach będziemy

korzystać z następującej reguły

D

ołączania

S

przeczności (

DS

):

DS

:

.

Jeżeli w ciągu dowodowym mamy jako przesłanki formułę i jej negację, to możemy
do dowodu dopisać symbol sprzeczności.

Za pomocą pojęcia reguł inferencyjnych możemy już zdefiniować — kluczowe
w ujęciach syntaktycznych — pojęcie dowodu formalnego formuły. Podamy
definicje dwóch różnych typów dowodów, a mianowicie dowodu wprost i dowodu
nie wprost.

Dowodem formalnym wprost formuły

α na gruncie reguł ze zbioru ℜ oraz formuł

ze zbioru X nazywamy skończony ciąg formuł ϕ

1

, ϕ

2

, ..., ϕ

n

o następujących

własnościach:
1. Ostatnia formuła ciągu dowodowego jest formułą dowodzoną (ϕ

n

= α).

2. Każda formuła ciągu dowodowego jest albo elementem zbioru X, albo wnioskiem

z wcześniej wyprowadzonych formuł dowodu w myśl pewnej reguły ze zbioru ℜ.

Przykład 7

Weźmy zbiór reguł

ℜ = {

,

,

,

} oraz

jednoelementowy zbiór formuł X = {(¬p ∨ q) ∧ ¬q}.

Rozważmy następujący ciąg formuł:
1. ϕ

1

= (¬p ∨ q) ∧ ¬q.

2. ϕ

2

= ¬p ∨ q.

3. ϕ

3

= ¬q.

4. ϕ

4

= ¬p.

Zauważmy, że każda formuła powyższego ciągu jest albo elementem zbioru X, albo
wnioskiem z wcześniejszych formuł ciągu w myśl pewnej reguły ze zbioru ℜ.

I tak kolejno: formuła ϕ

1

jest elementem zbioru X, formuły ϕ

2

i ϕ

3

są wnioskami

z formuły ϕ

1

w myśl reguł

EK

, formuła ϕ

4

jest wnioskiem z formuł ϕ

2

i ϕ

3

w myśl

jednej z reguł

EA

.

Możemy zatem stwierdzić, że ciąg formuł ϕ

1

, ϕ

2

, ϕ

3

, ϕ

4

jest dowodem wprost

formuły ¬p (ϕ

4

) na gruncie zbiorów ℜ oraz X.

Dowodem formalnym nie wprost formuły

α na gruncie reguł ze zbioru ℜ oraz formuł ze zbioru

X nazywamy skończony ciąg formuł ϕ

1

, ϕ

2

, ..., ϕ

n

o następujących własnościach:

7

1. Ostatnia formuła ciągu dowodowego jest symbolem sprzeczności (ϕ

n

= ⊥).

2. Każda formuła ciągu dowodowego jest albo elementem zbioru X, albo negacją

formuły α, albo wnioskiem z wcześniej wyprowadzonych formuł dowodu w myśl
pewnej reguły ze zbioru ℜ.

Przykład 8

Rozważmy zbiór reguł

ℜ = {

,

,

,

,

}

oraz jednoelementowy zbiór formuł X = {(p ∨ q) ∧ ¬q}. Podany niżej dowód jest

dowodem nie wprost dla formuły p.
1. ϕ

1

= (p ∨ q) ∧ ¬q.

2. ϕ

2

= ¬p.

3. ϕ

3

= p ∨ q.

4. ϕ

4

= ¬q.

5. ϕ

5

= p.

6. ϕ

6

= ⊥.

Zauważmy, że każda formuła powyższego ciągu jest albo negacją dowodzonej
formuły, albo elementem zbioru X, albo wnioskiem z wcześniejszych formuł ciągu
w myśl pewnej reguły ze zbioru ℜ.

I tak kolejno: formuła ϕ

1

jest elementem zbioru X, formuła ϕ

2

jest negacją

dowodzonej formuły p, formuły ϕ

3

i ϕ

4

są wnioskami z formuły ϕ

1

w myśl reguł

EK

, formuła ϕ

5

jest wnioskiem z formuł ϕ

3

i ϕ

4

w myśl jednej z reguł

EA

. Natomiast

symbol sprzeczności ⊥ (ϕ

6

) jest wnioskiem z formuł ϕ

2

i ϕ

5

w myśl reguły

DS

.

Możemy zatem stwierdzić, że ciąg formuł ϕ

1

, ϕ

2

, ϕ

3

, ϕ

4

, ϕ

5

, ϕ

6

jest dowodem nie

wprost formuły p na gruncie zbiorów ℜ oraz X.

Powiemy, że

formuła

α

wynika syntaktycznie

ze zbioru X na gruncie reguł ze zbioru ℜ

(co będziemy oznaczać X ׀−

ℜ

α), jeżeli formuła α ma dowód (wprost lub nie wprost)

na gruncie reguł ze zbioru ℜ oraz formuł ze zbioru X.

Dla uproszczenia — jeżeli X = {α

1

, α

2

, ..., α

n

}, to będziemy stosować zapis

α

1

, α

2

, ..., α

n

׀−

ℜ

α. Formuły α

1

, α

2

, ..., α

n

nazywamy

przesłankami

lub

założeniami

,

zaś formułę α

wnioskiem

.

Przykład 9

Z

przykładu 7

wynika, że

(¬p ∨ q) ∧ ¬q ׀−

ℜ

¬p. Ale także, jeżeli przyjrzymy się

uważnie temu przykładowi, widać, że prawdą jest również: (¬p ∨ q) ∧ ¬q ׀−

ℜ

¬q oraz

(¬p ∨ q) ∧ ¬q ׀−

ℜ

¬p ∨ q.

Twierdzenie 3

Dla dowolnej formuły α i dowolnego niepustego układu reguł ℜ spełnione jest:

α ׀−

ℜ

α.

8

Dowód

Aby udowodnić powyższe twierdzenie, trzeba wykazać istnienie odpowiedniego
ciągu formuł

α

1

, α

2

, ..., α

n

, spełniającego warunki dla dowodu wprost lub dowodu

nie wprost. W przypadku dowodu wprost mamy następujące warunki:
1. Ostatnia formuła ciągu dowodowego jest formułą dowodzoną (α

n

= α).

2. Każda formuła ciągu dowodowego jest formułą α albo wnioskiem z wcześniej

wyprowadzonych formuł dowodu w myśl pewnej reguły ze zbioru ℜ.

Rozważmy jednoelementowy ciąg formuł:

α

1

= α.

Zauważmy, że tak podany jednoelementowy ciąg spełnia oba warunki wymagane
dla ciągu dowodowego dla danej formuły. Zatem — ponieważ istnieje odpowiedni
dowód wprost — uzyskaliśmy, że α ׀−

ℜ

α.

Twierdzenie 4

Dla dowolnego niepustego zbioru formuł X, dowolnej formuły α ze zbioru X
i dowolnego niepustego układu reguł ℜ spełnione jest:

X ׀−

ℜ

α.

Dowód opiera się na poprzednim twierdzeniu.

Zachodzi również następujące twierdzenie o monotoniczności:

Twierdzenie 5

Dla dowolnych formuł α, β, γ i dowolnego niepustego układu reguł ℜ, jeżeli

α ׀−

ℜ

β oraz β ׀−

ℜ

γ, to spełnione jest również α ׀−

ℜ

γ.

Dowód

Załóżmy, że

α ׀−

ℜ

β oraz β ׀−

ℜ

γ. Istnieją zatem odpowiednie dowody wprost lub

nie wprost dla formuł β oraz γ. W przypadku dowodów wprost istnieje ciąg
dowodowy α

1

, α

2

, ..., α

n

taki, że α

n

= β i każda formuła ciągu jest formułą α lub

wynika z poprzednich formuł ciągu w myśl reguł ze zbioru ℜ, oraz istnieje ciąg
dowodowy β

1

, β

2

, ..., β

m

taki, że β

m

= γ i każda formuła ciągu jest formułą β lub

wynika z poprzednich formuł ciągu w myśl reguł ze zbioru ℜ. Jeżeli rozważymy
ciąg α

1

, α

2

, ..., α

n

, β

1

, β

2

, ..., β

m

, można zauważyć, że spełnia on warunki dla ciągu

dowodowego wprost dla formuły γ na gruncie formuły α oraz układu reguł ℜ.
W innych przypadkach dowód jest analogiczny.

Powyższe twierdzenie można uogólnić w następujący sposób:

Twierdzenie 6

Dla dowolnego zbioru formuł X = {α

1

, α

2

, ..., α

n

} oraz dla dowolnych

formuł β, γ i dowolnego niepustego układu reguł ℜ, jeżeli α

1

, α

2

, ..., α

n

׀−

ℜ

β

oraz α

1

, α

2

, ..., α

n

, β ׀−

ℜ

γ, to spełnione jest również α

1

, α

2

, ..., α

n

׀−

ℜ

γ.

9

Dowód

Załóżmy, że

α

1

, α

2

, ..., α

n

׀−

ℜ

β. Istnieje zatem odpowiedni dowód wprost lub

nie wprost dla formuły β. W przypadku dowodu wprost istnieje ciąg dowodowy

β

1

, β

2

, ..., β

n

taki, że β

n

= β i każda formuła ciągu jest formułą ze zbioru

X = {α

1

, α

2

, ..., α

n

} lub wynika z poprzednich formuł ciągu w myśl reguł ze zbioru

ℜ. Załóżmy także, że α

1

, α

2

, ..., α

n

, β ׀−

ℜ

γ, istnieje zatem odpowiedni dowód

wprost lub nie wprost dla formuły γ. W przypadku dowodu wprost istnieje ciąg
dowodowy γ

1

, γ

2

, ..., γ

n

taki, że γ

n

= γ i każda formuła ciągu jest formułą ze zbioru

{α

1

, α

2

, ..., α

n

, β} lub wynika z poprzednich formuł ciągu w myśl reguł ze zbioru ℜ.

Rozważmy ciąg skonstruowany w sposób następujący: Jeżeli w ciągu dowodowym

γ

1

, γ

2

, ..., γ

n

któraś z formuł jest formułą β, to formułę tę zastępujemy ciągiem

dowodowym β

1

, β

2

, ..., β

n

. Skonstruowany w ten sposób ciąg dowodowy jest ciągiem

dowodowym dla formuły γ na gruncie formuł ze zbioru X = {α

1

, α

2

, ..., α

n

}. Mamy

zatem α

1

, α

2

, ..., α

n

׀−

ℜ

γ. W pozostałych przypadkach dowód jest analogiczny.

10

3. System dedukcji naturalnej

Przedstawimy teraz układ reguł umożliwiających przeprowadzanie dowodów,
nazywany układem dedukcji naturalnej

1

.

Reguły dedukcji naturalnej

Reguły

E

liminacji

K

oniunkcji:

EK

:

α

∧

β

α

,

α

∧

β

β

Jeżeli w ciągu dowodowym mamy jako przesłankę koniunkcję, to możemy do
dowodu dopisać każdy czynnik koniunkcji.

Reguły

E

liminacji

A

lternatywy:

EA

:

α

∨

β,

¬

α

β

,

α

∨

β,

¬

β

α

Jeżeli w ciągu dowodowym mamy jako przesłanki alternatywę i negację jednego
z jej składników, to możemy do dowodu dopisać drugi składnik alternatywy.

Reguła

E

liminacji

I

mplikacji:

EI

:

Jeżeli w ciągu dowodowym mamy jako przesłanki pewną formułę i implikację
o takim samym poprzedniku, to możemy do dowodu dopisać następnik tej
implikacji.

R

eguły

R

ównoważności:

RR :

Jeżeli w ciągu dowodowym mamy jako przesłankę równoważność dwóch formuł,
to możemy dopisać do ciągu dowodowego koniunkcję odpowiednich implikacji.
Zachodzi również reguła odwrotna.

1

Prezentowany układ jest pewnym rozszerzeniem systemu zaproponowanego i przebadane-

go przez polskich logików Ludwika Borkowskiego i Jerzego Słupeckiego.

11

Reguła

D

ołączania

K

oniunkcji:

DK

:

Do ciągu dowodowego zawsze możemy dopisać koniunkcję dowolnych przesłanek
występujących w ciągu dowodowym.

Reguły

D

ołączania

A

lternatywy:

DA

:

Do ciągu dowodowego zawsze możemy dopisać alternatywę którejkolwiek
z przesłanek występujących w ciągu dowodowym z dowolną formułą.

Reguła

D

ołączania

I

mplikacji (z negacji

P

oprzednika):

DIP

:

Jeżeli w ciągu dowodowym mamy jako przesłankę negację pewnej formuły, to
możemy do dowodu dopisać implikację o poprzedniku będącym tą formułą
i dowolnym następniku.

Reguła

D

ołączania

I

mplikacji (z

N

astępnika):

DIN

:

Jeżeli w ciągu dowodowym mamy jako przesłankę pewną formułę, to możemy do
dowodu dopisać implikację o dowolnym poprzedniku i następniku będącym tą
formułą.

Reguły

P

odwójnej

N

egacji:

PN

:

.

Jeżeli w ciągu dowodowym mamy jako przesłankę negację negacji pewnej formuły, to
możemy do dowodu dopisać tę formułę. I odwrotnie — jeżeli w ciągu dowodowym
mamy jako przesłankę pewną formułę, to możemy do dowodu dopisać negację
negacji tej formuły.

12

Reguły

N

egacji

K

oniunkcji:

NK

:

Jeżeli w ciągu dowodowym mamy jako przesłankę negację koniunkcji dwóch
formuł, to możemy do dowodu dopisać alternatywę negacji tych formuł. Jeżeli
w ciągu dowodowym mamy alternatywę negacji dwóch formuł, to możemy dopisać
do dowodu negację ich koniunkcji.

Reguły

N

egacji

A

lternatywy:

NA

:

Jeżeli w ciągu dowodowym mamy jako przesłankę negację alternatywy dwóch
formuł, to możemy do dowodu dopisać koniunkcję negacji tych formuł. Jeżeli
w ciągu dowodowym mamy koniunkcję negacji dwóch formuł, to możemy dopisać
do dowodu negację ich alternatywy.

Reguły

N

egacji

I

mplikacji:

NI

:

Jeżeli w ciągu dowodowym mamy jako przesłankę negację implikacji, to możemy
do dowodu dopisać koniunkcję poprzednika tej implikacji i negacji jej następnika.
Jeżeli w ciągu dowodowym mamy koniunkcję formuły i negacji innej formuły, to
możemy do dowodu dopisać negację implikacji tych formuł.

Reguły

N

egacji

R

ównoważności:

NR

:

Jeżeli w ciągu dowodowym mamy jako przesłankę negację równoważności
dwóch formuł, to możemy dopisać do ciągu dowodowego alternatywę negacji
odpowiednich implikacji. Zachodzi również reguła odwrotna.

Reguła

D

ołączania

S

przeczności:

DS

:

13

Jeżeli w ciągu dowodowym mamy jako przesłanki formułę i jej negację, to możemy
do dowodu dopisać symbol sprzeczności.

Wynikanie syntaktyczne na gruncie powyższego układu reguł będziemy oznaczać
symbolem ׀−

DN

.

Przykład 10

Wykażemy, że:

p ∧ ¬q, p ⇒ s, t ∨ q ׀−

DN

s ∧ t.

Wypisujemy kolejno założenia — (Z):
1. ϕ

1

= p ∧ ¬q (Z).

2. ϕ

2

= p ⇒ s (Z).

3. ϕ

3

= t ∨ q (Z).

Formuły ϕ

4

oraz ϕ

5

wyprowadzamy z formuły ϕ

1

(założenia 1) w myśl reguły

EK

:

4. ϕ

4

= p (1,

EK

).

5. ϕ

5

= ¬q (1,

EK),

Kolejno stosujemy do odpowiednich formuł reguły

EI

,

EA

oraz

DK

:

6. ϕ

6

= s (2, 4

EI

).

7. ϕ

7

= t (3, 5,

EA

).

8. ϕ

8

= s ∧ t (6, 7,

DK

).

Zauważmy, że — podobnie jak w poprzednim przykładzie — każda formuła
powyższego ciągu jest albo elementem zbioru X, albo wnioskiem z wcześniejszych
formuł ciągu w myśl pewnej reguły dedukcji naturalnej. Możemy zatem stwierdzić,
że p ∧ ¬q, p ⇒ s, t ∨ q ׀−

DN

s ∧ t.

Przykład 11

Wykażemy, że:

p ∨ q, ¬(s ⇒ q), s ⇒ t ׀−

DN

s ⇒ (p ∧ t).

Wypisujemy kolejno założenia — (Z):

1. ϕ

1

= p ∨ q (Z).

2. ϕ

2

= ¬(s ⇒ q) (Z).

3. ϕ

3

= s ⇒ t (Z).

Korzystamy z reguły negacji implikacji

NI

:

4. ϕ

4

= s ∧ ¬q (2,

NI).

Formuły

ϕ

5

oraz ϕ

6

wyprowadzamy z formuły ϕ

4

w myśl reguły

EK

:

5. ϕ

5

= s (4,

EK

).

6. ϕ

6

= ¬q (4,

EK).

Kolejno stosujemy do odpowiednich formuł reguły

EA

,

EI

,

DK

oraz

DIN

:

7. ϕ

7

= p (1, 6,

EA

).

8. ϕ

8

= t (3, 5,

EI

).

9. ϕ

9

= p ∧ t (7, 8,

DK

).

10. ϕ

10

= s ⇒ (p ∧ t) (9,

DIN).

Zauważmy, że — podobnie jak w poprzednim przykładzie — każda formuła
powyższego ciągu jest albo elementem zbioru X (założenia), albo wnioskiem
z wcześniejszych formuł ciągu w myśl pewnej reguły dedukcji naturalnej. Możemy
zatem stwierdzić, że p ∨ q, ¬(s ⇒ q), s ⇒ t ׀−

DN

s ⇒ (p ∧ t).

14

Przykład 12

Udowodnimy metodą nie wprost wynikanie:

p ׀−

DN

p ∨ q.

Wypisujemy założenie — (Z):
1.

p (Z),

a następnie dopisujemy negację wniosku (oznaczamy to symbolem ZN):
2. ¬(p ∨ q) (ZN).
Stosując do punktu 2 regułę negacji alternatywy, otrzymujemy:
3. ¬p ∧ ¬q (2,

NA

).

4. ¬p (3,

EK).

5.

⊥ (1, 4,

DS

).

Przykład 13

Udowodnimy również metodą nie wprost dowodzone wyżej wynikanie:

p ∨ q, ¬(s ⇒ q), s ⇒ t ׀−

DN

s ⇒ (p ∧ t).

Wypisujemy kolejno założenia — (Z):

1. p ∨ q (Z).
2. ¬(s ⇒ q) (Z).
3. s ⇒ t (Z),

a następnie dopisujemy negację wniosku (oznaczamy to symbolem ZN).

4. ¬[s ⇒ (p ∧ t)] (ZN).

Kolejno stosując do odpowiednich formuł reguły dedukcji naturalnej, uzyskujemy
następujące formuły:

5. s ∧ ¬(p ∧ t) (4,

NI

),

6. s (5,

EK

),

7. ¬(p ∧ t) (5,

EK

),

8. ¬p ∨ ¬t (7,

NK

),

9. t (3, 6,

EI

),

10. s ∧ ¬q (2,

NI

),

11. ¬q (10,

EK

),

12. p (1, 11,

EA

),

13. ¬¬t (9,

PN

),

14. ¬p (8, 13,

EA

),

15. ⊥ (w punktach 12 i 14), co kończy dowód.
Dla podanego wyżej systemu dedukcji naturalnej zachodzi następujące:

Twierdzenie 7

(mocne twierdzenie o pełności względem semantyki rachunku zdań)

Formuła

α wynika syntaktycznie ze zbioru formuł X na gruncie systemu

DN

(X ׀−

DN

α) wtedy i tylko wtedy, gdy formuła α wynika semantycznie ze zbioru

formuł X (X ׀= α).

Symbolicznie:

X ׀−

DN

α wtedy i tylko wtedy, gdy X ׀= α.

Powróćmy do metody dowodzenia nie wprost. Możliwość dopisania negacji
dowodzonej formuły do przesłanek umożliwia dowodzenie formuł bez przesłanek.
Takie bezprzesłankowe wynikania oznaczać będziemy ׀−

DN

α (bez wypisywania

przesłanek przed znakiem wynikania), a o formułach mających dowody bez
przesłanek będziemy mówić, że

wynikają z systemu

dedukcji naturalnej DN.

15

Przykład 14

Udowodnimy metodą nie wprost poniższe wynikanie:

׀−

DN

¬p ⇒ (p ⇒ q).

Negację dowodzonej formuły umieszczamy w dowodzie jako założenie nie wprost
— (ZN):
1. ¬(¬p ⇒ (p ⇒ q)) (ZN).
Kolejno stosując do odpowiednich formuł reguły dedukcji naturalnej uzyskujemy
następujące formuły:
2. ¬p ∧ ¬(p ⇒ q) (1,

NI

).

3. ¬p (2,

EK

).

4. ¬(p ⇒ q) (2,

EK

).

5. p

∧ ¬q (4,

NI

).

6. p (5,

EK).

7.

⊥ (3, 6

DS).

Dla formuł mających dowody bez przesłanek zachodzi następujące:

Twierdzenie 8

(słabe twierdzenie o pełności względem semantyki rachunku zdań)

Formuła

α wynika syntaktycznie z systemu

DN

(׀−

DN

α) wtedy i tylko wtedy, gdy

formuła α wynika semantycznie ze zbioru pustego (׀= α).

Symbolicznie:

׀−

DN

α wtedy i tylko wtedy, gdy ׀= α.

16

4. Dowody przez dodatkowe założenie

Omówione w poprzednich paragrafach techniki dowodowe można wzbogacić
jeszcze o następującą metodę. Jeżeli dowodzonym wnioskiem jest formuła będąca
implikacją, to poprzednik tej implikacji możemy dołączyć do założeń dowodu.
Wnioskiem pozostaje następnik tej implikacji. Dalsze postępowanie podczas
dowodzenia opiera się na wcześniej omówionych technikach dowodu wprost
i dowodu nie wprost. Wynikania dowodzone za pomocą tej metody będziemy
oznaczać symbolem

׀−

DNZ

.

Przykład 15

Udowodnimy wprowadzoną wyżej metodą następujące wynikanie:

p ⇒ q, q ⇒ r ׀−

DNZ

p ⇒ r.

Wypisujemy kolejno założenia — (Z):
1. p ⇒ q (Z).
2. q ⇒ r (Z),
a następnie dopisujemy poprzednik wniosku (oznaczamy to symbolem ZD):
3. p (ZD).
Kolejno stosując do odpowiednich formuł reguły dedukcji naturalnej, uzyskujemy
następujące formuły:
4. q (1, 3

EI

).

5. r (2, 4

EI

).

Co kończy dowód, mamy zatem p ⇒ q, q ⇒ r ׀−

DNZ

p ⇒ r.

Przykład 16

Udowodnimy wynikanie ׀−

DNZ

(p ⇒ r) ⇒ [(q ⇒ r) ⇒ (p ∧ q ⇒ r)].

Wypisujemy kolejno założenia dodatkowe — (ZD) (po dopisaniu poprzednika
implikacji jako dodatkowego założenia, zauważamy, że następnik jest również
implikacją, zatem można dopisać jako założenie dodatkowe jej poprzednik itp.).
1. p ⇒ r (ZD).
2. q ⇒ r (ZD).
3. p ∧ q (ZD).
Kolejno stosując do odpowiednich formuł reguły dedukcji naturalnej, uzyskujemy
następujące formuły:
4. p (3,

EK

).

5. r (1, 4

EI).

Co kończy dowód, mamy zatem

׀−

DNZ

(p ⇒ r) ⇒ [(q ⇒ r) ⇒ (p ∧ q ⇒ r)].

17

5. Formy zdaniowe

Rachunek zdań jest najprostszym i najbardziej rozpowszechnionym rachunkiem
logicznym. Niestety, z różnych powodów nie wystarcza do opisu rzeczywistości.
Przypomnijmy, że rachunek ten bazuje na pojęciu zdania w sensie logicznym, czyli
wyrażenia, któremu jesteśmy w stanie przyporządkować prawdę lub fałsz.

Oczywiście, jeżeli rozważymy wyrażenie „Janek lubi Zosię”, łatwo można
stwierdzić, że jest to zdanie w sensie logicznym. Jednak już drobna modyfikacja
tego wyrażenia — „Człowiek lubi Zosię” — nastręcza problem, jeżeli chodzi
o zaklasyfikowanie go do zbioru zdań. Nie jesteśmy bowiem w stanie orzec, czy to
wyrażenie jest prawdziwe, czy fałszywe.

Podobnie jest w przypadku znanych nam wyrażeń arytmetycznych: 2 + 3 = 6 jest
zdaniem (fałszywym), zaś wyrażenia x + 3 = 6 nie można nazwać zdaniem.

Zauważmy następujące prawidłowości:

 jeżeli w wyrażeniu „Człowiek lubi Zosię” wyraz „człowiek” zastąpimy imieniem

konkretnej osoby, to uzyskamy zdanie (np. „Janek lubi Zosię”),

 jeżeli w wyrażeniu x + 3 = 6 zastąpimy zmienną x konkretną wartością

dowolnej liczby, to uzyskamy zdanie (np. 2 + 3 = 6).

Forma zdaniowa zmiennej

x to wyrażenie, które zawiera tę zmienną i które staje się

zdaniem po wstawieniu za zmienną pewnych obiektów.

Zakres

danej

formy

to dowolny zbiór takich elementów, które wstawione do formy

w miejsce zmiennej dają wyrażenia sensowne.

Przykład 17

Oczywiście wyrażenie „Człowiek lubi Zosię” jest formą zdaniową zmiennej
„człowiek”. Zakresem tej formy może być dowolny zbiór ludzi.

Przykład 18

Wyrażenia x + 3 = 6, x + 1 = 4 czy x + 3 ≥ 6 są formami zdaniowymi zmiennej
x. Zakresem tej formy może być dowolny zbiór liczbowy.

W dalszych rozważaniach formy zdaniowe zmiennej x będziemy oznaczali
symbolami ϕ(x), ψ(x) itp. Zauważmy również, że jeżeli za zmienną w formie ϕ(x)
podstawimy element zakresu a, to wyrażenie ϕ(a) jest zdaniem w sensie logicznym
i jako takie może przyjmować wartości 0 lub 1.

Przykład 19

Rozważmy formę zdaniową ϕ(x) : (x + 3 = 6) oraz zakres {0, 1, 2, 3, 4, 5}.
Zauważmy, że wyrażenie ϕ(1) : (1 + 3 = 6) jest zdaniem fałszywym, co możemy
zapisać w(ϕ(1)) = 0, zaś wyrażenie ϕ(3) : (3 + 3 = 6) jest zdaniem prawdziwym,
co możemy zapisać w(ϕ(3)) = 1.

Formy zdaniowe możemy łączyć spójnikami logicznymi, budując formy złożone.
Jeżeli ϕ(x) i ψ(x) są formami zdaniowymi, to wyrażenia: ¬ϕ(x), ¬ψ(x), ϕ(x) ∧ ψ(x),

18

ϕ(x) ∨ ψ(x), ϕ(x) ⇒ ψ(x), ϕ(x) ⇔ ψ(x) są również formami zdaniowymi. Formy:

ϕ(x) ∧ ψ(x), ϕ(x) ∨ ψ(x), ϕ(x) ⇒ ψ(x), ϕ(x) ⇔ ψ(x) możemy również oznaczać
odpowiednio w sposób następujący: (ϕ ∧ ψ)(x), (ϕ ∨ ψ)(x), (ϕ ⇒ ψ)(x), (ϕ ⇔ ψ)(x),
akcentując w ten sposób, że zmienne form składowych są takie same.

Niech ϕ(x) będzie formą zdaniową zmiennej x, zaś zbiór X będzie jej zakresem.

Powiemy, że

element

a należący do zbioru X

spełnia formę zdaniową

ϕ(x) wtedy

i tylko wtedy, gdy po wstawieniu w miejsce zmiennej x w formie ϕ(x) elementu
a otrzymamy zdanie prawdziwe — czyli w(ϕ(a)) = 1.

Analogicznie powiemy, że

element

a należący do zbioru X

nie spełnia formy zdaniowej

ϕ(x) wtedy i tylko wtedy, gdy po wstawieniu w miejsce zmiennej x w formie ϕ(x)
elementu a, otrzymamy zdanie fałszywe — czyli w(ϕ(a)) = 0.

W zależności od rozpatrywanego zakresu, formy można podzielić na trzy
kategorie:
1. Formę ϕ(x) nazywamy

spełnialną dla danego zakresu

, jeżeli

istnieje

element zakresu

a spełniający tę formę (w(ϕ(a)) = 1).

2. Formę ϕ(x) nazywamy

prawdziwą dla danego zakresu

, jeżeli

każdy

element tego

zakresu a spełnia tę formę (w(ϕ(a)) = 1).

3. Formę ϕ(x) nazywamy

fałszywą dla danego zakresu

, jeżeli żaden element tego

zakresu a nie spełnia formy (w(ϕ(a)) = 0).

Przykład 20

Rozważmy jako przykład następujące formy ϕ

1

(x) : (x = x), ϕ

2

(x) : (2x = 4) oraz

ϕ

3

(x) : (x > x) w zakresie liczb rzeczywistych R.

Zauważmy, że:

 podstawienie dowolnej liczby rzeczywistej do formy ϕ

1

(x) daje zdanie

prawdziwe,

 istnieje liczba rzeczywista, która po podstawieniu za zmienną x w formie ϕ

2

(x)

daje zdanie prawdziwe, mamy bowiem w(ϕ

2

(2)) = 1,

 żadna liczba rzeczywista podstawiona do formy ϕ

3

(x) nie daje zdania

prawdziwego.

Oczywiście, zgodnie z podanymi wcześniej definicjami można stwierdzić, że

ϕ

1

(x) jest formą prawdziwą, ϕ

2

(x) — spełnialną oraz ϕ

3

(x) — formą fałszywą

w zakresie liczb rzeczywistych R.

Przykład 21

Zauważmy, że pojęcia spełnialności, prawdziwości i fałszywości form zdaniowych
są ściśle związane z rozpatrywanym zakresem. Rozważmy bowiem formę

ϕ(x) : (x ≥ 4) w trzech różnych zakresach, będących przedziałami prostej
rzeczywistej. W przedziale (−∞, 2) forma ϕ(x) jest formą fałszywą, w przedziale
(0, +∞) — spełnialną, zaś w przedziale (4, +∞) — prawdziwą.

19

6. Kwantyfikatory

Rozważaliśmy w poprzednim paragrafie wyrażenia typu „Człowiek lubi Zosię”
lub x + 3 = 6, o których orzekliśmy, że nie są zdaniami w sensie logicznym.
Stwierdziliśmy, że aby nadać tym wyrażeniom sens zdania, należy podstawić
w miejsce zmiennej jakiś obiekt.

Rozważmy teraz następujące modyfikacje tych wyrażeń: „Każdy człowiek lubi
Zosię” oraz „Istnieje liczba x taka, że x + 3 = 6”. Zauważmy, że wyrażenia te są
już zdaniami w sensie logicznym.

Zauważmy, że zwrot „Istnieje takie x, że...” można uważać za równoważny zwrotowi:
„Dla pewnego x jest ...”. Zwrot ten nazywamy

kwantyfikatorem egzystencjalnym

(lub

małym

albo

szczegółowym

) i oznaczamy symbolem ∃

x

.

Zauważmy, że wyrażenie ∃

x

ϕ(x) jest zdaniem w sensie logicznym.

Zwrot „dla każdego” nazywamy

kwantyfikatorem uniwersalnym

(

ogólnym

lub

dużym

)

i oznaczamy symbolem ∀

x

. Zauważmy, że wyrażenie ∀

x

ϕ(x) jest zdaniem w sensie

logicznym.

Zmienna występująca w zasięgu (wyznaczanym zwyczajowo przez odpowiedni
nawias) kwantyfikatora identyczna z kwantyfikowaną kwantyfikatorem zmienną
nazywa się zmienną związaną danym kwantyfikatorem. Natomiast zmienna
występująca w wyrażeniu, która nie jest związana żadnym kwantyfikatorem,
nazywa się zmienną wolną.

Jeżeli w zasięgu kwantyfikatora znajdują się jakieś inne kwantyfikatory, to
kwantyfikator początkowy wiąże tylko te zmienne, które nie są związane żadnym
kwantyfikatorem zawartym w jego zasięgu.

Przykład 22

Rozważmy następujące wyrażenie ∀

x

(2x + y = 5). Zasięgiem kwantyfikatora jest

wyrażenie 2x + y = 5. Zmienna x jest w tym wyrażeniu zmienną związaną, zaś
zmienna y zmienną wolną.

Podamy teraz definicję

formuł (wyrażeń) kwantyfikatorowych

.

Poprawnie zbudowanymi wyrażeniami (formułami) kwantyfikatorowymi
są wszystkie zmienne zdaniowe p, q, ... oraz wszystkie symbole form zdaniowych

ϕ(x), ψ(x), .....

Jeżeli α i β są poprawnie zbudowanymi formułami kwantyfikatorowymi, to ¬α,

¬

β, α ∧ β, α ∨ β, α ⇒ β, α ⇔ β są również poprawnie zbudowanymi formułami

kwantyfikatorowymi.

Jeżeli α jest poprawnie zbudowaną formułą kwantyfikatorową, w której x nie
jest zmienną związaną, to ∀

x

α oraz ∃

x

α są również poprawnie zbudowanymi

wyrażeniami kwantyfikatorowymi.

Poprawnie zbudowane wyrażenie kwantyfikatorowe, w którym nie występują
zmienne wolne, nazywamy

zdaniem rachunku kwantyfikatorów.

20

Wyrażenie matematyczne

jest podstawieniem poprawnie zbudowanego wyrażenia

kwantyfikatorowego wtedy i tylko wtedy, gdy powstaje z niego przez zastąpienie
wszystkich zmiennych zdaniowych p, q, ... zdaniami w sensie logicznym,
a wszystkich wyrażeń typu ϕ(x) — formami zdaniowymi.

Poprawnie zbudowane wyrażenie kwantyfikatorowe jest

prawem rachunku

kwantyfikatorów

(

tautologią kwantyfikatorową

) wtedy i tylko wtedy, gdy każde

poprawne podstawienie tego wyrażenia jest prawdziwym zdaniem matematycznym
lub prawdziwą formą zdaniową.

Twierdzenie 9

Wszystkie prawa rachunku zdań są prawami rachunku kwantyfikatorów.

Twierdzenie 10

Prawami rachunku kwantyfikatorów są następujące wyrażenia (w nawiasach
podajemy pewne ich podstawienia):
(a) ∀

x

ϕ(x) ⇒ ∃

x

ϕ(x)

[∀

x

(x + 1 = 2) ⇒ ∃

x

(x +1 = 2) lub ∀

x

(x

2

≥ 0) ⇒ ∃

x

(x

2

≥ 0)],

(b) ∀

x

ϕ(x) ⇒ ϕ(a)

[∀

x

(x

2

≥ 0) ⇒ (4

2

≥ 0) lub ∀

x

(–x

2

< 0) ⇒ (–3

2

< 0)],

(c) ϕ(a) ⇒ ∃

x

ϕ(x)

[(2 + 1 = 3) ⇒ ∃

x

(x + 1 = 3) lub (1 < 3) ⇒ ∃

x

(x < 3)].

Twierdzenie 11

Jeżeli x nie jest zmienną wolną formy ϕ, to następujące wyrażenia są prawami
rachunku kwantyfikatorów:
(a) ∀

x

(ϕ ∨ ψ(x)) ⇔ (ϕ ∨ ∀

x

ψ(x)),

(b) ∀

x

(ϕ ∧ ψ(x)) ⇔ (ϕ ∧ ∀

x

ψ(x)),

(c) ∀

x

(ϕ ⇒ ψ(x) ⇔ (ϕ ⇒ ∀

x

ψ(x)),

(d) ∃

x

(ϕ ∨ ψ(x)) ⇔ (ϕ ∨ ∃

x

ψ(x)),

(e) ∃

x

(ϕ ∧ ψ(x)) ⇔ (ϕ ∧ ∃

x

ψ(x)),

(f) ∃

x

(ϕ ⇒ ψ(x) ⇔ (ϕ ⇒ ∃

x

ψ(x).

Twierdzenie 12

Prawami rachunku kwantyfikatorów są następujące wyrażenia:
(a) ¬∀

x

ϕ(x) ⇔ ∃

x

¬

ϕ(x) — prawo de Morgana rachunku kwantyfikatorów,

(b) ¬∃

x

ϕ(x) ⇔ ∀

x

¬

ϕ(x) — prawo de Morgana rachunku kwantyfikatorów,

(c) ∀

x

[ϕ(x) ∧ ψ(x)] ⇔ [∀

x

ϕ(x) ∧ ∀

x

ψ(x)] — prawo dystrybucji kwantyfikatora

uniwersalnego względem koniunkcji,

(d) ∃

x

[ϕ(x) ∨ ψ(x)] ⇔ [ ∃

x

ϕ(x) ∨ ∃

x

ψ(x)] — prawo dystrybucji kwantyfikatora

egzystencjalnego względem alternat yw y,

(e) [∀

x

ϕ(x) ∨ ∀

x

ψ(x)] ⇒ ∀

x

[ϕ(x) ∨ ψ(x)] — prawo dystrybucji kwant yfikatora

uniwersalnego względem alternat yw y,

(f) ∃

x

[ϕ(x) ∧ ψ(x)] ⇒ [∃

x

ϕ(x) ∧ ∃

x

ψ(x)]

— prawo dystrybucji kwant yfikatora

egzystencjalnego względem koniunkcji,

(g) ∀

x

[ϕ(x) ⇒ ψ(x)] ⇒ [∀

x

ϕ(x) ⇒ ∀

x

ψ(x)] — prawo dystrybucji kwantyfikatora

uniwersalnego względem implikacji,

21

(h) ∀

x

[ϕ(x) ⇒ ψ(x)] ⇒ [∃

x

ϕ(x) ⇒ ∃

x

ψ(x)] — prawo dystrybucji kwantyfikatora

egzystencjalnego względem implikacji.

Twierdzenie 13

Następujące wyrażenia nie są prawami rachunku kwantyfikatorów:
(a) ∃

x

ϕ(x) ∧ ∃

x

ψ(x) ⇒ ∃

x

[ϕ(x) ∧ ψ(x)],

(b) ∀

x

[ϕ(x) ∨ ψ(x)] ⇒ [∀

x

ϕ(x) ∨ ∀

x

ψ(x)].

Dowód

(a) rozważmy

podstawienie

∃

x

(x = 1) ∧ ∃

x

(x = 2) ⇒ ∃

x

[(x = 1) ∧ (x = 2)]

w zakresie liczb rzeczywistych R. Oczywiście poprzednik tej implikacji jest
prawdziwy (istnieje liczba rzeczywista równa jeden i istnieje liczba rzeczywista
równa 2), ale następnik jest fałszywy (nie istnieje liczba rzeczywista równa
jednocześnie jeden i dwa). Zatem implikacja jest fałszywa. Zgodnie z definicją
wyrażenie nie jest prawem rachunku kwantyfikatorów;

(b) rozważmy

podstawienie

∀

x

[(x ≥ 0) ∨ (x ≤ 0)] ⇒ [∀

x

(x ≥ 0) ∨ ∀

x

(x ≤ 0)]

w zakresie liczb rzeczywistych R. Poprzednik tej implikacji jest prawdziwy
(prawdą jest, że dowolna liczba rzeczywista jest mniejsza lub równa od zera
lub większa lub równa od zera), ale następnik jest fałszywy (nieprawdą jest, że
każda liczba rzeczywista jest nieujemna lub to, że każda liczba rzeczywista jest
niedodatnia). Implikacja jest fałszywa i zgodnie z definicją wyrażenie nie jest
prawem rachunku kwantyfikatorów.

Twierdzenie 14

Prawami rachunku kwantyfikatorów są następujące wyrażenia:
(a) ∀

x

∀

y

ϕ(x, y) ⇔ ∀

y

∀

x

ϕ(x, y),

(b) ∃

x

∃

y

ϕ(x, y) ⇔ ∃

y

∃

x

ϕ(x, y),

(c) ∃

x

∀

y

ϕ(x, y) ⇒ ∀

y

∃

x

ϕ(x, y),

ale nie jest prawem wyrażenie:
(d) ∀

x

∃

y

ϕ(x, y) ⇒ ∃

y

∀

x

ϕ(x, y).

Dowód (d)

Rozważmy podstawienie ∀

x

∃

y

(y < x) ⇒ ∃

y

∀

x

(y < x) w zakresie liczb rzeczywistych

R. Poprzednik implikacji jest prawdziwy: dla dowolnej liczby rzeczywistej istnieje
liczba od niej mniejsza. Następnik jest fałszywy: nie ma bowiem liczby rzeczywistej,
od której byłyby większe wszystkie liczby rzeczywiste.

22

Bibliografia

1.

Gubareni N., 2001: Logika dla studentów, Wydawnictwo Politechniki

Częstochowskiej.

2.

Kuratowski K., 2004: Wstęp do teorii mnogości i topologii, PWN,

Warszawa.

3.

Marek W., Onyszkiewicz J., 2003: Elementy logiki i teorii mnogości

w zadaniach, PWN, Warszawa.

4.

Rasiowa H., 2004: Wstęp do matematyki współczesnej, PWN,

Warszawa.

5.

Słupecki J., Hałkowska K., Piróg-Rzepecka K., 1994: Logika i teoria

mnogości

, Warszawa.

Bibliografia stron WWW

6. Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Witryna internetowa. h�p://www.mimuw.edu.pl/~tiuryn/skrypt-98.ps.gz, stan

z 21.09.2005 (J. Tiuryn, Wstęp do teorii mnogości i logiki).