Ÿ

3

.

Ra

h

unek

predyk

ató

w

Predyk

at

y

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3

A

K

w

an

t

yk

atory

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3

B

F

orm

uªy

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3

C

Pra

w

a

ra

h

unku

predyk

ató

w

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3

D

‚

wi zenia

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3

F

Zadania

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3

G

Predyk

at

y

☛

Pr

e

dykat

jest

p

o

j iem

pierw

otn

ym

logiki;

k

a»dy

predyk

at

p

osiada

ustalon¡

li zb



argumen

tó

w,

zw

an¡

jego

ar

gumentowo± i¡

oraz

ustalone

zakresy

zmienno± i

argumen

tó

w.

☛

Predyk

at

y

nazyw

ane

s¡

niekiedy

funk jami

zdaniowymi

,

b

o

sta

j¡

si

zdaniami,

gdy

za

i

h

argumen

t

y

p

o

dsta

wim

y

w

arto± i

wzite

z

o

dp

o

wiedni

h

zakresó

w

zmienno± i.

☛

W

szystkie

zdania

s¡

predyk

atami



predyk

at

0

-argumen

to

wy

i

zdanie

to

synonim

y

.

W

ystpuj¡ e

dalej

predyk

at

y

b

d¡

ozna zane

literami

P

i

Q

.

☛

Zmienne

zdanio

w

e

s¡

jednoargumen

to

wymi

predyk

atami.

Przykªadem

predyk

atu

dwuargumen

to

w

ego

jest

rela ja

ró

wno± i

x = y

.

☛

Predyk

at

y

reprezen

tuj¡

te

sp

o±ró

d

zda«

jzyk

a

naturalnego,

które

za

wiera

j¡

zmienne

i

które

sta

j¡

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

.

Ra

h

unek

predyk

ató

w

3

A

K

w

an

t

yk

atory

☛

K

wantykatory

s¡

wyk

orzyst

yw

ane

w

jzyku

naturaln

ym

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¡

dw

a

kw

an

t

yk

atory:



o

gólny

(

uniwersalny

);

∀

x

P(x)

zytam

y:

dla

k

a»dego

x

za

ho

dzi

P(x)

;



sz ze

góªowy

(

e

gzysten jalny

);

∃

x

P(x)

zytam

y:

istnieje

takie

x

,

»e

P(x)

.

☛

Je»eli

zmienna

x

ma

sk

o« zon

y

zakres

zmienno± i

X = {x

1

, x

2

, . . . , x

n

}

,

to

zdanie

∀

x

P(x)

(

∃

x

P(x)

)

jest

ró

wno

w

a»ne

zdaniu

P(x

1

) ∧ P(x

2

) ∧ . . . ∧ P(x

n

)

(

P(x

1

) ∨ P(x

2

) ∨ . . . ∨ P(x

n

)

).

☛

Ab

y

skró

i¢

zapis

niektóry

h

form

uª

ra

h

unku

predyk

ató

w,

b

dziem

y

k

orzysta¢

z

kilku

skróto

wy

h

zapisó

w.

Przyjm

ujem

y

w

sz zególno± i,

»e:



∃

!

x

P(x) ⇔ (∃

x

P(x)) ∧ (∀

x

∀

y

((P(x) ∧ P(y)) ⇒ (x = y)))

;



∃

Q(x)

P(x) ⇔ ∃

x

(Q(x) ∧ P(x))

i

∀

Q(x)

P(x) ⇔ ∀

x

(Q(x) ⇒ P(x))

.

☛

Napis

∃

!

x

P(x)

zytam

y:

istnieje

dokªadnie

jedno

x

takie,

»e

P(x)

;

∃

Q(x)

P(x)

(

∀

Q(x)

P(x)

)

zytam

y:

istnieje

takie

x

,

»e

Q(x)

i

P(x)

(dla

k

a»dego

x

,

o

ile

Q(x)

,

to

P(x)

).

Ÿ

3

.

Ra

h

unek

predyk

ató

w

3

B

F

orm

uªy

☛

F

ormuªami

r

a hunku

pr

e

dykatów

nazyw

a¢

b

dziem

y

te

i

t

ylk

o

te

napisy

,

które

mo»na

zbudo

w

a¢

wskutek

zastoso

w

ania

sk

o« zon¡

li zb



razy

p

oni»szy

h

reguª.

(1)

Je»eli

P

jest

n

-argumen

to

wym

predyk

atem,

a

x

1

,

x

2

,

.

.

.

,

x

n

s¡

zmienn

ymi

lub

staªymi,

to

P(x

1

, x

2

, . . . ,

x

n

)

jest

(

atomow¡

)

form

uª¡

ra

h

unku

predyk

ató

w.

(2)

Je»eli

ϕ

jest

form

uª¡

ra

h

unku

predyk

ató

w,

a

x

jest

zmienn¡,

to

(ϕ)

,

¬ϕ

,

∀

x

ϕ

i

∃

x

ϕ

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.

☛

F

orm

uªy

ra

h

unku

zda«

s¡

ró

wno

ze±nie

form

uªami

ra

h

unku

predyk

ató

w,

wi

oba

t

yp

y

form

uª

b

d¡

ozna zane

t

ymi

sam

ymi

sym

b

olami,

tzn.

ϕ

,

ψ

i

φ

.

☛

Zmienna

x

jest

zmienn¡

woln¡

form

uªy

ϕ

wtedy

i

t

ylk

o

wtedy

,

gdy

istnieje

takie

miejs e,

w

którym

x

wystpuje

w

ϕ

,

a

które

nie

nale»y

do

»adnej

p

o

dform

uªy

form

uªy

ϕ

p

osta i

∃

x

ψ

lub

∀

x

ψ

.

☛

Zmienne,

które

wystpuj¡

w

form

ule

ϕ

,

a

nie

s¡

w

olne,

to

zmienne

zwi¡zane

.

Domkni

iem

form

uªy

ϕ

nazyw

a¢

b

dziem

y

zdanie

∀

x

1

∀

x

2

. . . ∀

x

n

ϕ

,

gdzie

x

1

,

x

2

,

.

.

.

,

x

n

to

wszystkie

zmienne

w

olne

form

uªy

ϕ

.

☛

Napis

p

o

wstaªy

z

ϕ

p

oprzez

zamian

wszystki

h

wyst¡

pie«

zmiennej

w

olnej

x

1

na

(zmienn¡,

staª¡

lub

form

uª)

y

1

,

x

2

na

y

2

,

.

.

.

,

x

n

na

y

n

ozna za¢

b

dziem

y

sym

b

olem

ϕ(x

1

:= y

1

, x

2

:= y

2

, . . . , x

n

:= y

n

)

.

Ÿ

3

.

Ra

h

unek

predyk

ató

w

3

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

,

»e

x

nie

jest

zmienn¡

w

oln¡

w

ψ

):



(∀

x

ϕ) ⇒ ϕ

i

ϕ ⇒ (∃

x

ϕ)

;



(¬∀

x

ϕ) ⇔ (∃

x

¬ϕ)

i

(¬∃

x

ϕ) ⇔ (∀

x

¬ϕ)

(pra

w

a

de

Morgana);



∀

x

(ϕ ∧ ψ) ⇔ (∀

x

ϕ ∧ ψ)

i

∀

x

(ϕ ∨ ψ) ⇔ (∀

x

ϕ ∨ ψ)

;



∃

x

(ϕ ∧ ψ) ⇔ (∃

x

ϕ ∧ ψ)

i

∃

x

(ϕ ∨ ψ) ⇔ (∃

x

ϕ ∨ ψ)

;



∀

x

(ϕ ⇒ ψ) ⇔ (∃

x

ϕ ⇒ ψ)

i

∀

x

(ψ ⇒ ϕ) ⇔ (ψ ⇒ ∀

x

ϕ)

;



∃

x

(ϕ ⇒ ψ) ⇔ (∀

x

ϕ ⇒ ψ)

i

∃

x

(ψ ⇒ ϕ) ⇔ (ψ ⇒ ∃

x

ϕ)

;



∀

x

ϕ ⇔ ∀

y

ϕ(x := y)

i

∃

x

ϕ ⇔ ∃

y

ϕ(x := y)

(o

ile

y

nie

wystpuje

w

ϕ

);



∀

x

∀

y

ϕ ⇔ ∀

y

∀

x

ϕ

,

∃

x

∃

y

ϕ ⇔ ∃

y

∃

x

ϕ

i

∃

x

∀

y

ϕ ⇒ ∀

y

∃

x

ϕ

.

☛

Nie

istnieje

algorytm,

który

p

otraªb

y

o

dp

o

wiedzie¢

na

p

ytanie,

zy

dana

form

uªa

jest

pra

w

em

ra

h

unku

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

.

Ra

h

unek

predyk

ató

w

3

D

Pra

w

a

ra

h

unku

predyk

ató

w

(2)

☛

T

o,

zy

dana

form

uªa

nie

za

wiera

j¡ a

predyk

ató

w

o

argumen

to

w

o± i

wikszej

ni»

1

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

.

☛

Dziaªanie

tej

meto

dy

zademonstrujem

y

na

przykªadzie

form

uªy

(P(x) ⇔ Q(x)) ∨ ∃

y

Q(y)

,

która

p

o

domkni iu

sta

je

si

zdaniem

∀

x

((P(x) ⇔ Q(x)) ∨ ∃

y

Q(y))

.

☛

T

w

orzym

y

tab

elk

,

której

pierwsze

ztery

k

olumn

y

wyp

eªniam

y

wszystkimi

mo»liwymi

w

arto± iami

zda«

∃

x

(P(x) ∧ Q(x))

,

∃

x

(P(x) ∧ ¬Q(x))

,

∃

x

(¬P(x) ∧ Q(x))

i

∃

x

(¬P(x) ∧ ¬Q(x))

.

☛

P

ozostaªe

k

olumn

y

wyp

eªniam

y

w

arto± iami

logi zn

ymi

zda«

∃

y

Q(y)

,

∃

x

((P(x) ∧ ¬Q(x)) ∨ (¬P(x) ∧

Q(x)))

i

∀

x

((P(x) ⇔ Q(x)) ∨ ∃

y

Q(y))

.

☛

W

arto± i

zda«

∃

y

Q(y)

i

∃

x

((P(x) ∧ ¬Q(x)) ∨ (¬P(x) ∧ Q(x)))

umiesz zono

w

tab

el e

t

ylk

o

p

o

to,

b

y

upro± i¢

obli zenie

w

arto± i

zdania

∀

x

((P(x) ⇔ Q(x)) ∨ ∃

y

Q(y))

.

∃

x

(P(x

) ∧ Q

(x))

∃

x

(P(x

) ∧ ¬

Q(x

))

∃

x

(¬P(

x) ∧

Q(x

))

∃

x

(¬P(

x) ∧

¬Q(

x))

∃

y

Q(y

)

∃

x

((P(x

) ∧ ¬

Q(x

))

∨(¬

P(x)

∧ Q

(x)))

∀

x

((P(x

) ⇔

Q(x

))

∨∃

y

Q(y

))

0

0

0

1

0

0

1

.

.

.

1

1

1

1

1

1

1

Ÿ

3

.

Ra

h

unek

predyk

ató

w

3

E