3
.
Ra
h
unek
predyk
ató
w
3
Predyk
at
y
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A
3
K
w
an
t
yk
atory
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B
3
F
orm
uªy
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C
3
Pra
w
a
ra
h
unku
predyk
ató
w
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
D
3
wi zenia
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
F
3
Zadania
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
G
Predyk
at
y
☛ Predykat jest poj iem pierwotnym logiki; ka»dy predykat posiada ustalon¡ li zb argumentów, zwan¡
jego
ar
gumentowo± i¡
oraz
ustalone
zakresy
zmienno± i
argumen
tó
w.
☛ Predykaty nazywane s¡ niekiedy funk jami zdaniowymi , bo staj¡ si zdaniami, gdy za i h argumenty
p
o
dsta
wim
y
w
arto± i
wzite
z
o
dp
o
wiedni
h
zakresó
w
zmienno± i.
☛
0
W
szystkie
zdania
s¡
predyk
atami
predyk
at
-argumen
to
wy
i
zdanie
to
synonim
y
.
W
ystpuj¡ e
dalej
P
Q
predyk
at
y
b
d¡
ozna zane
literami
i
.
☛ Zmienne zdaniowe s¡ jednoargumentowymi predykatami. Przykªadem predykatu dwuargumentowego x = y
jest
rela ja
ró
wno± i
.
☛ Predykaty reprezentuj¡ te spo±ród zda« jzyka naturalnego, które zawieraj¡ zmienne i które staj¡ si
pra
wdziw
e
lub
faªszyw
e,
gdy
za
te
zmienne
p
o
dsta
wim
y
w
arto± i
z
i
h
zakresu.
3
3
.
Ra
h
unek
predyk
ató
w
A
K
w
an
t
yk
atory
☛ Kwantykatory s¡ wykorzystywane w jzyku naturalnym i w logi e do wyra»ania wªasno± i wszystki h
lub
niektóry
h
obiektó
w
z
zakresu
zmienno± i
zmienn
y
h,
który
h
dot
y z¡.
☛ Istniej¡ dwa kwantykatory:
∀xP(x)
x
P(x)
o
gólny
(uniwersalny
);
zytam
y:
dla
k
a»dego
za
ho
dzi
;
∃xP(x)
x
P(x)
sz ze
góªowy
(e
gzysten jalny
);
zytam
y:
istnieje
takie
,
»e
.
☛
x
X = {x
∀
∃
1, x2, . . . , xn}
xP(x)
xP(x)
Je»eli
zmienna
ma
sk
o« zon
y
zakres
zmienno± i
,
to
zdanie
(
)
jest
P(x1) ∧ P(x2) ∧ . . . ∧ P(xn) P(x1) ∨ P(x2) ∨ . . . ∨ P(xn) ró
wno
w
a»ne
zdaniu
(
).
☛ Aby skró i¢ zapis niektóry h formuª ra hunku predykatów, bdziemy korzysta¢ z kilku skrótowy h
zapisó
w.
Przyjm
ujem
y
w
sz zególno± i,
»e:
∃!
∀
xP(x) ⇔ (∃xP(x)) ∧ (∀x y((P(x) ∧ P(y)) ⇒ (x = y)))
;
∃
∀
Q(x)P(x) ⇔ ∃x(Q(x) ∧ P(x)) Q(x)P(x) ⇔ ∀x(Q(x) ⇒ P(x))
i
.
☛
∃!
∃
∀
xP(x)
x
P(x)
Q(x)P(x)
Q(x)P(x)
Napis
zytam
y:
istnieje
dokªadnie
jedno
takie,
»e
;
(
)
zytam
y:
x
Q(x)
P(x)
x
Q(x)
P(x)
istnieje
takie
,
»e
i
(dla
k
a»dego
,
o
ile
,
to
).
3
3
.
Ra
h
unek
predyk
ató
w
B
F
orm
uªy
☛ Formuªami ra hunku predykatów nazywa¢ bdziemy te i tylko te napisy, które mo»na zbudowa¢ wskutek zastoso
w
ania
sk
o« zon¡
li zb
razy
p
oni»szy
h
reguª.
(1)
P
n
x1 x2
xn
P(x1, x2, . . . , Je»eli
jest
-argumen
to
wym
predyk
atem,
a
,
,
.
.
.
,
s¡
zmienn
ymi
lub
staªymi,
to
xn) jest (atomow¡) formuª¡ ra hunku predykatów.
(2)
ϕ
x
(ϕ) ¬ϕ ∀
∃
xϕ
xϕ
Je»eli
jest
form
uª¡
ra
h
unku
predyk
ató
w,
a
jest
zmienn¡,
to
,
,
i
s¡
form
uªami
ra
h
unku
predyk
ató
w.
(3)
ϕ
ψ
(ϕ ∧ ψ) (ϕ ∨ ψ) (ϕ ⇒ ψ) (ϕ ⇔ ψ)
Je»eli
i
s¡
form
uªami
ra
h
unku
predyk
ató
w,
to
,
,
i
s¡
form
uªami
ra
h
unku
predyk
ató
w.
☛ Formuªy ra hunku zda« s¡ równo ze±nie formuªami ra hunku predykatów, wi oba typy formuª bd¡
ϕ ψ
φ
ozna zane
t
ymi
sam
ymi
sym
b
olami,
tzn.
,
i
.
☛
x
ϕ
x
Zmienna
jest
zmienn¡
woln¡
form
uªy
wtedy
i
t
ylk
o
wtedy
,
gdy
istnieje
takie
miejs e,
w
którym
ϕ
ϕ
∃
∀
xψ
xψ
wystpuje
w
,
a
które
nie
nale»y
do
»adnej
p
o
dform
uªy
form
uªy
p
osta i
lub
.
☛
ϕ
Zmienne,
które
wystpuj¡
w
form
ule
,
a
nie
s¡
w
olne,
to
zmienne
zwi¡zane
.
Domkni
iem
form
uªy
ϕ
∀
∀
x
x . . . ∀x ϕ
x1 x2
xn
ϕ
nazyw
a¢
b
dziem
y
zdanie
1
2
n
,
gdzie
,
,
.
.
.
,
to
wszystkie
zmienne
w
olne
form
uªy
.
☛
ϕ
x1
Napis
p
o
wstaªy
z
p
oprzez
zamian
wszystki
h
wyst¡
pie«
zmiennej
w
olnej
na
(zmienn¡,
staª¡
lub
y1 x2
y2
xn
yn
ϕ(x1 := y1, x2 := y2, . . . , xn := yn) form
uª)
,
na
,
.
.
.
,
na
ozna za¢
b
dziem
y
sym
b
olem
.
3
3
.
Ra
h
unek
predyk
ató
w
C
Pra
w
a
ra
h
unku
predyk
ató
w
☛
ϕ
F
orm
uªa
jest
pr
awem
r
a hunku
pr
e
dykatów
wtedy
i
t
ylk
o
wtedy
,
gdy
domkni ie
k
a»dej
z
form
uª,
ϕ
które
p
o
wsta
j¡
z
p
oprzez
zast¡
pienie
wystpuj¡ y
h
w
niej
predyk
ató
w
inn
ymi
predyk
atami
o
tej
samej
argumen
to
w
o± i
jest
zdaniem
pra
wdziwym.
☛
ϕ
ψ
Istnieje
wiele
pra
w
ra
h
unku
predyk
ató
w;
oto
niektóre
z
ni
h
(
i
to
do
w
olne
form
uªy;
zakªadam
y
,
x
ψ
»e
nie
jest
zmienn¡
w
oln¡
w
):
(∀xϕ) ⇒ ϕ ϕ ⇒ (∃xϕ)
i
;
(¬∀xϕ) ⇔ (∃x¬ϕ) (¬∃xϕ) ⇔ (∀x¬ϕ)
i
(pra
w
a
de
Morgana);
∀
∀
x(ϕ ∧ ψ) ⇔ (∀xϕ ∧ ψ) x(ϕ ∨ ψ) ⇔ (∀xϕ ∨ ψ)
i
;
∃
∃
x(ϕ ∧ ψ) ⇔ (∃xϕ ∧ ψ) x(ϕ ∨ ψ) ⇔ (∃xϕ ∨ ψ)
i
;
∀
∀
x(ϕ ⇒ ψ) ⇔ (∃xϕ ⇒ ψ) x(ψ ⇒ ϕ) ⇔ (ψ ⇒ ∀xϕ)
i
;
∃
∃
x(ϕ ⇒ ψ) ⇔ (∀xϕ ⇒ ψ) x(ψ ⇒ ϕ) ⇔ (ψ ⇒ ∃xϕ)
i
;
∀
∃
xϕ ⇔ ∀yϕ(x := y)
xϕ ⇔ ∃yϕ(x := y)
y
ϕ
i
(o
ile
nie
wystpuje
w
);
∀ ∀
∀
∃ ∃
∃
∃ ∀
∃
x yϕ ⇔ ∀y xϕ
x yϕ ⇔ ∃y xϕ
x yϕ ⇒ ∀y xϕ
,
i
.
☛ Nie istnieje algorytm, który potraªby odpowiedzie¢ na pytanie, zy dana formuªa jest prawem ra hunku
predyk
ató
w.
Istnieje
za
to
algorytm,
który
dla
form
uª
b
d¡ y
h
pra
w
ami
ra
h
unku
predyk
ató
w
zwra a
o
dp
o
wied¹
tak,
a
dla
p
ozostaªy
h
nie
k
o« zy
si.
3
3
.
Ra
h
unek
predyk
ató
w
D
Pra
w
a
ra
h
unku
predyk
ató
w
(2)
☛
1
T
o,
zy
dana
form
uªa
nie
za
wiera
j¡ a
predyk
ató
w
o
argumen
to
w
o± i
wikszej
ni»
jest
pra
w
em
ra-
h
unku
predyk
ató
w,
mo»na
spra
wdzi¢
k
orzysta
j¡
ze
zmo
dykowany h
tab
elek
zer
oje
dynkowy h
.
☛
(P(x) ⇔ Q(x)) ∨ ∃yQ(y) Dziaªanie
tej
meto
dy
zademonstrujem
y
na
przykªadzie
form
uªy
,
która
p
o
∀x((P(x) ⇔ Q(x)) ∨ ∃yQ(y)) domkni iu
sta
je
si
zdaniem
.
☛ Tworzymy tabelk, której pierwsze ztery kolumny wypeªniamy wszystkimi mo»liwymi warto± iami
∃
∃
∃
∃
x(P(x) ∧ Q(x))
x(P(x) ∧ ¬Q(x))
x(¬P(x) ∧ Q(x))
x(¬P(x) ∧ ¬Q(x))
zda«
,
,
i
.
☛
∃
∃
yQ(y)
x((P(x) ∧ ¬Q(x)) ∨ (¬P(x) ∧
P
ozostaªe
k
olumn
y
wyp
eªniam
y
w
arto± iami
logi zn
ymi
zda«
,
Q(x)))
∀x((P(x) ⇔ Q(x)) ∨ ∃yQ(y)) i
.
☛
∃
∃
yQ(y)
x((P(x) ∧ ¬Q(x)) ∨ (¬P(x) ∧ Q(x))) W
arto± i
zda«
i
umiesz zono
w
tab
el e
t
ylk
o
p
o
to,
b
y
∀x((P(x) ⇔ Q(x)) ∨ ∃yQ(y)) upro± i¢
obli zenie
w
arto± i
zdania
.
Q(y))
∃ (P(x) ∧ Q(x))
(P(x) ∧ ¬Q(x))
(¬P(x) ∧ Q(x))
(¬P(x) ∧ ¬Q(x))
Q(y)
((P(x) ∧ ¬Q(x))
((P(x) ⇔ Q(x))
x
∃x
∃x
∃x
∃y
∃x
∨(¬P(x) ∧ Q(x)))
∀x
∨∃y
0
0
0
1
0
0
1
.
.
.
1
1
1
1
1
1
1
3
3
.
Ra
h
unek
predyk
ató
w
E