Ÿ

2

.

Ra

h

unek

zda«

Zdania

w

logi e

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

A

F

unktory

zdaniot

w

ór ze

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

B

F

orm

uªy

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

C

W

arto±¢

form

uªy

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

D

W

arto±¢

form

uªy



algorytm

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

F

T

autologie

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

H

F

orm

uªy

ró

wno

w

a»ne

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

I

Meto

da

rezolu ji

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

J

Reguªy

do

w

o

dzenia

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

L

‚

wi zenia

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

M

Zadania

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2

O

Zdania

w

logi e

☛

Zdanie

oraz

warto±¢

lo

gi zna

zdania

to

p

o

j ia

pierw

otne

logiki;

logik

a

klasy zna

k

orzysta

z

dw

ó

h

w

arto± i

logi zn

y

h:

pr

awdy

i

faªszu

,

ozna zan

y

h

sym

b

olami

1

i

0

.

☛

W

ystpuj¡ e

dalej

zmienne

zdanio

w

e

b

dziem

y

ozna zali

literami

p

,

q

i

r

,

a

i

h

w

arto± i

logi zne

o

dp

o

wiednio

sym

b

olami

w(p)

,

w(q)

i

w(r)

.

☛

P

o

dsta

w

o

wym

zastoso

w

aniem

ra

h

unku

zda«

jest

badanie

formalnej

struktury

t

y

h

zda«

z

jzyk

a

na-

turalnego,

o

który

h

mo»na

p

o

wiedzie¢,

»e

s¡

pra

wdziw

e

lub

faªszyw

e.



Zmienne

zdanio

w

e

reprezen

tuj¡

te

sp

o±ró

d

zda«

jzyk

a

naturalnego,

które

s¡

pra

wdziw

e

lub

faªszyw

e

i

nie

s¡

zdaniami

zªo»on

ymi

(nie

za

wiera

j¡

sp

ó

jnik

ó

w

logi zn

y

h).



Odp

o

wiednikiem

zda«

zªo»on

y

h

s¡

omó

wione

dalej

form

uªy

logi zne.

Ÿ

2

.

Ra

h

unek

zda«

2

A

F

unktory

zdaniot

w

ór ze

☛

F

unktory

zdaniotwór

ze

,

nazyw

ane

tak»e

sp

ójnikami

lo

gi znymi

,

s¡

wyk

orzyst

yw

ane

w

jzyku

natural-

n

ym

do

t

w

orzenia

zda«

zªo»on

y

h;

w

logi e

sªu»¡

one

do

t

w

orzenia

form

uª.

☛

Istnieje

wiele

funktoró

w;

do

na

jw

a»niejszy

h

nale»¡:



ne

ga ja

;

¬p

zytam

y:

niepra

wda,

»e

p

;



koniunk ja

;

p ∧ q

zytam

y:

p

i

q

;



alternatywa

;

p ∨ q

zytam

y:

p

lub

q

;



implika ja

;

p ⇒ q

zytam

y:

je»eli

p

,

to

q

;



r

ównowa»no±¢

;

p ⇔ q

zytam

y:

p

wtedy

i

t

ylk

o

wtedy

,

gdy

q

.

☛

Nega ja

jest

funktorem

jednoargumen

to

wym;

k

oniunk

ja,

alternat

yw

a,

implik

a ja

i

ró

wno

w

a»no±¢

s¡

dwuargumen

to

w

e.

Ÿ

2

.

Ra

h

unek

zda«

2

B

F

orm

uªy

☛

F

ormuªami

r

a hunku

zda«

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

zmienn¡

zdanio

w

¡,

to

p

jest

(

atomow¡

)

form

uª¡

ra

h

unku

zda«.

(2)

Je»eli

ϕ

jest

form

uª¡

ra

h

unku

zda«,

to

(ϕ)

i

¬ϕ

s¡

form

uªami

ra

h

unku

zda«.

(3)

Je»eli

ϕ

i

ψ

s¡

form

uªami

ra

h

unku

zda«,

to

(ϕ ∧ ψ)

,

(ϕ ∨ ψ)

,

(ϕ ⇒ ψ)

i

(ϕ ⇔ ψ)

s¡

form

uªami

ra

h

unku

zda«.

☛

T

am,

gdzie

nie

b

dzie

to

pro

w

adzi¢

do

niep

orozumie«,

b

dziem

y

w

form

uªa

h

opusz za¢

na

wiasy;

dot

y zy

to

w

sz zególno± i

wyra»e«

p

osta i

p ∧ q

,

p ∨ q

,

p ⇒ q

i

p ⇔ q

.

☛

Po

dformuªami

form

uªy

ϕ

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)

ϕ

jest

p

o

dform

uª¡

ϕ

.

(2)

Je»eli

ψ

jest

p

o

dform

uª¡

ϕ

,

a

φ

jest

p

o

dform

uª¡

ψ

,

to

φ

jest

p

o

dform

uª¡

ϕ

.

(3)

Je»eli

ϕ

jest

ró

wne

(ψ)

lub

¬ψ

,

to

ψ

jest

p

o

dform

uª¡

ϕ

.

(4)

Je»eli

ϕ

jest

ró

wne

(ψ ∧ φ)

,

(ψ ∨ φ)

,

(ψ ⇒ φ)

lub

(ψ ⇔ φ)

,

to

ψ

i

φ

s¡

p

o

dform

uªami

ϕ

.

☛

W

ystpuj¡ e

dalej

form

uªy

b

dziem

y

ozna zali

sym

b

olami

ϕ

,

ψ

i

φ

.

Li zb



znak

ó

w,

z

który

h

form

uªa

si

skªada,

nazyw

a¢

b

dziem

y

jej

dªugo± i¡

;

dªugo±¢

form

uªy

ϕ

ozna za¢

b

dziem

y

sym

b

olem

d(ϕ)

.

Ÿ

2

.

Ra

h

unek

zda«

2

C

W

arto±¢

form

uªy

☛

Ka»dej

form

ule

mo»na

przyp

orz¡dk

o

w

a¢

w

arto±¢

logi zn¡;

jest

ona

zale»na

zaró

wno

o

d

struktury

samej

form

uªy

,

jak

i

w

arto± i

logi zn

y

h

wystpuj¡ y

h

w

niej

zmienn

y

h.

☛

W

arto±¢

logi zn¡

form

uªy

ϕ

ozna za¢

b

dziem

y

sym

b

olem

w(ϕ)

;

zasady

obli zania

w(ϕ)

okre±la

j¡

p

oni»sze

tab

ele.

w(ϕ)

w((ϕ))

0

0

1

1

w(ϕ) w(ψ)

w((ϕ ∧ ψ))

0

0

0

0

1

0

1

0

0

1

1

1

w(ϕ) w(ψ)

w((ϕ ⇒ ψ))

0

0

1

0

1

1

1

0

0

1

1

1

w(ϕ)

w(¬ϕ)

0

1

1

0

w(ϕ) w(ψ)

w((ϕ ∨ ψ))

0

0

0

0

1

1

1

0

1

1

1

1

w(ϕ) w(ψ)

w((ϕ ⇔ ψ))

0

0

1

0

1

0

1

0

0

1

1

1

Ÿ

2

.

Ra

h

unek

zda«

2

D

W

arto±¢

form

uªy

(2)

☛

W

arto±¢

form

uªy

obli za

si

k

orzysta

j¡

z

tzw.

tab

elek

zer

oje

dynkowy h

.

Dziaªanie

tej

meto

dy

zade-

monstrujem

y

na

przykªadzie

form

uªy

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

.

☛

Ab

y

obli zy¢

w

arto±¢

form

uªy

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

t

w

orzym

y

tab

elk

,

której

pierwsze

dwie

k

olumn

y

wyp

eªniam

y

wszystkimi

mo»liwymi

w

arto± iami

zda«

p

i

q

.

☛

P

ozostaªe

k

olumn

y

wyp

eªniam

y

w

arto± iami

logi zn

ymi

form

uª

¬q

,

p ⇒ (¬q)

,

p ⇒ q

i

(p ⇒ q) ⇒

(p ⇒ (¬q))

,

obli zon

ymi

na

p

o

dsta

wie

w

arto± i

zna

jduj¡ y

h

si

w

pierwszy

h

dw

ó

h

k

olumna

h.

☛

W

arto± i

form

uª

¬q

,

p ⇒ (¬q)

i

p ⇒ q

umiesz zono

w

tab

el e

t

ylk

o

p

o

to,

b

y

upro± i¢

obli zenie

w

arto± i

form

uªy

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

.

p q

¬q p ⇒ (¬q) p ⇒ q

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

0

0

1

1

1

1

0

1

0

1

1

1

1

0

1

1

0

1

1

1

0

0

1

0

Ÿ

2

.

Ra

h

unek

zda«

2

E

W

arto±¢

form

uªy



algorytm

☛

Algorytm

wyzna zania

w

arto± i

form

uªy

jest

dwuetap

o

wy

.

W

pierwszym

etapie

(kroki

1



3

)

zapisujem

y

form

uª

w

tzw.

o

dwr

otnej

nota ji

p

olskiej

,

która

jest

wygo

dniejsza

w

obli zenia

h

o

d

trady yjnej

nota ji.

W

drugim

etapie

(kroki

4



5

)

wyzna zam

y

jej

w

arto±¢.

(1)

W

yzna z

p

oziom

zagnie»d»enia

znak

ó

w,

z

który

h

zbudo

w

ana

jest

form

uªa.

Zwiksz

p

oziom

zagnie»-

d»enia

nega ji

oraz

wyra»e«

p

osta i

¬p

o

1

.

(2)

Usu«

z

form

uªy

wszystkie

na

wiasy

.

Przegl¡da

j

p

o

wstaªy

napis

o

d

lew

ej

do

pra

w

ej,

wyk

on

uj¡

przy

k

a»dym

znaku

p

oni»sze

zynno± i:

(2a)

dop

óki

na

sz zy ie

stosu

s¡

funktory

o

p

oziomie

zagnie»d»enia

wikszym

ni»

p

oziom

bie»¡ ego

znaku,

zdejm

uj

je

ze

stosu

i

umiesz za

j

w

napisie

b

ezp

o±rednio

przed

nim;

(2b)

je»eli

bie»¡ y

znak

jest

funktorem,

to

usu«

go

z

napisu

i

o

dªó»

na

stos.

(3)

Opró»nij

stos,

umiesz za

j¡

jego

za

w

arto±¢

na

k

o« u

napisu.

(4)

Przegl¡da

j

otrzyman

y

napis

o

d

lew

ej

do

pra

w

ej,

wyk

on

uj¡

przy

k

a»dym

znaku

p

oni»sze

zynno± i:

(4a)

je»eli

bie»¡ y

znak

jest

funktorem,

to

zdejmij

ze

stosu

t

yle

elemen

tó

w,

ile

wynosi

jego

argumen-

to

w

o±¢,

obli z

na

ni

h

w

arto±¢

funktora

i

wynik

umie±¢

na

stosie;

(4b)

je»eli

bie»¡ y

znak

jest

nazw

¡

zmiennej,

to

umie±¢

jej

w

arto±¢

na

stosie.

(5)

Zdejmij

ze

stosu

wynik.

Ÿ

2

.

Ra

h

unek

zda«

2

F

W

arto±¢

form

uªy



algorytm

(2)

☛

Ab

y

zademonstro

w

a¢

dziaªanie

tego

algorytm

u,

obli zym

y

w

arto±¢

form

uªy

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

dla

zmienn

y

h

p

i

q

,

który

h

w

arto± i¡

jest

faªsz.

☛

Obli zenie

p

oziomó

w

zagnie»d»enia

da

nastpuj¡ y

wynik

(indeks

doln

y

znaku

to

jego

p

oziom

zagnie»-

d»enia):

(

0

p

1

⇒

1

q

1

)

0

⇒

0

(

0

p

1

⇒

1

(

1

¬

3

q

3

)

1

)

0

.

☛

P

o

usuni iu

na

wiasó

w

otrzymam

y

napis

p

1

⇒

1

q

1

⇒

0

p

1

⇒

1

¬

3

q

3

.

W

yk

onanie

krok

ó

w

2a



2b

da

nastpuj¡ y

rezultat:

Bie»¡ y

znak

Stos

Napis

Bie»¡ y

znak

Stos

Napis

p

1

p

1

⇒

1

q

1

⇒

0

p

1

⇒

1

¬

3

q

3

p

1

⇒

0

p

1

q

1

⇒

1

p

1

⇒

1

¬

3

q

3

⇒

1

⇒

1

p

1

q

1

⇒

0

p

1

⇒

1

¬

3

q

3

⇒

1

⇒

1

⇒

0

p

1

q

1

⇒

1

p

1

¬

3

q

3

q

1

⇒

1

p

1

q

1

⇒

0

p

1

⇒

1

¬

3

q

3

¬

3

¬

3

⇒

1

⇒

0

p

1

q

1

⇒

1

p

1

q

3

⇒

0

⇒

0

p

1

q

1

⇒

1

p

1

⇒

1

¬

3

q

3

q

3

¬

3

⇒

1

⇒

0

p

1

q

1

⇒

1

p

1

q

3

☛

P

o

opró»nieniu

stosu

otrzymam

y

napis

pq ⇒ pq¬ ⇒⇒

,

który

jest

form

uª¡

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

zapisan¡

w

o

dwrotnej

nota ji

p

olskiej.

W

yk

onanie

krok

ó

w

4a



4b

da

nastpuj¡ y

rezulat:

Bie»¡ y

znak:

p

q

⇒

p

q

¬

⇒

⇒

Stos:

0

00

1

01

001

101

11

1

☛

Na

sz zy ie

stosu

zna

jduje

si

jedynk

a,

wi

szuk

an¡

w

arto± i¡

jest

pra

wda.

Ÿ

2

.

Ra

h

unek

zda«

2

G

T

autologie

☛

Ze

wzgldu

na

przyjmo

w

ane

w

arto± i,

form

uªy

ra

h

unku

zda«

mo»na

p

o

dzieli¢

na

trzy

grup

y:



tautolo

gie

,

zyli

form

uªy

,

który

h

w

arto±¢

logi zna

jest

za

wsze

pra

wdziw

a,

niezale»nie

o

d

tego,

jakie

s¡

w

arto± i

zmienn

y

h

w

ni

h

wystpuj¡ y

h;



kontrtautolo

gie

,

zyli

form

uªy

,

który

h

w

arto±¢

logi zna

jest

za

wsze

faªszyw

a,

niezale»nie

o

d

tego,

jakie

s¡

w

arto± i

zmienn

y

h

w

ni

h

wystpuj¡ y

h;



form

uªy

sp

eªnialne

,

zyli

takie,

które

nie

s¡

k

on

trtautologiami.

☛

Ze

wzgldu

na

p

eªnion¡

funk

j,

tautologie

nazyw

ane

s¡

tak»e

pr

awami

r

a hunku

zda«

.

Istnieje

wiele

tautologii;

do

na

jistotniejszy

h

z

ni

h

nale»¡:



(p ∧ q) ⇔ (q ∧ p)

i

(p ∨ q) ⇔ (q ∨ p)

(przemienno±¢

k

oniunk

ji

i

alternat

ywy);



((p ∧ q) ∧ r) ⇔ (p ∧ (q ∧ r))

i

((p ∨ q) ∨ r) ⇔ (p ∨ (q ∨ r))

(ª¡ zno±¢

k

oniunk

ji

i

alternat

ywy);



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

(prze

ho

dnio±¢

implik

a ji);



(p ∧ (q ∨ r)) ⇔ ((p ∧ q) ∨ (p ∧ r))

i

(p ∨ (q ∧ r)) ⇔ ((p ∨ q) ∧ (p ∨ r))

(pra

w

a

rozdzielno± i);



¬

(p ∧ q) ⇔ (¬p ∨ ¬q)

i

¬

(p ∨ q) ⇔ (¬p ∧ ¬q)

(pra

w

a

de

Morgana);



p ∨ ¬p

i

¬

(p ∧ ¬p)

(pra

w

o

wyª¡ zonego

±ro

dk

a

i

pra

w

o

sprze zno± i);



p ⇔ ¬¬p

(pra

w

o

p

o

dw

ó

jnego

prze zenia).

Ÿ

2

.

Ra

h

unek

zda«

2

H

F

orm

uªy

ró

wno

w

a»ne

☛

P

o

wiem

y

,

»e

form

uªy

ϕ

,

ψ

s¡

r

ównowa»ne

(

ϕ

jest

p

osta i¡

form

uªy

ψ

,

ψ

jest

p

osta i¡

form

uªy

ϕ

)

wtedy

i

t

ylk

o

wtedy

,

gdy

i

h

w

arto± i

logi zne

s¡

iden

t

y zne.

☛

Przyjmijm

y

,

»e

w

form

ule

ϕ

wystpuje

m

zmienn

y

h

p

1

,

p

2

,

.

.

.

,

p

m

.



F

orm

uªa

ψ

jest

normaln¡

p

osta i¡

suma yjn¡

form

uªy

ϕ

wtedy

i

t

ylk

o

wtedy

,

gdy

ψ = ψ

1

∨ ψ

2

∨ . . .

∨ ψ

n

,

gdzie

n

jest

p

ewn¡

li zb¡

naturaln¡,

a

ψ

i

= (φ

1

∧ φ

2

∧ . . . ∧ φ

m

)

,

gdzie

φ

i

= p

i

lub

φ

i

= ¬p

i

.



F

orm

uªa

ψ

jest

normaln¡

p

osta i¡

ilo

zynow¡

form

uªy

ϕ

wtedy

i

t

ylk

o

wtedy

,

gdy

ψ = ψ

1

∧ ψ

2

∧ . . .

∧ ψ

n

,

gdzie

n

jest

p

ewn¡

li zb¡

naturaln¡,

a

ψ

i

= (φ

1

∨ φ

2

∨ . . . ∨ φ

m

)

,

gdzie

φ

i

= p

i

lub

φ

i

= ¬p

i

.

☛

Ka»da

form

uªa

nie

b

d¡ a

k

on

trtautologi¡

(tautologi¡)

p

osiada

suma yjn¡

(ilo

zyno

w

¡)

p

osta¢

nor-

maln¡;

suma yjn¡

(ilo

zyno

w

¡)

p

osta i¡

normaln¡

dla

k

on

trtautologii

(tautologii)

jest

z

deni ji

0

(

1

).

☛

Ka»da

form

uªa

ϕ

p

osiada

p

osta¢

ψ

,

która

jest

zbudo

w

ana

wyª¡ znie

ze

zmienn

y

h,

na

wiasó

w

i



funktoró

w

nega ji

i

implik

a ji;



funktoró

w

nega ji

i

k

oniunk

ji;



funktoró

w

nega ji

i

alternat

ywy

.

☛

Istniej¡

funktory

f

takie,

»e

k

a»da

form

uªa

logi zna

ϕ

p

osiada

p

osta¢

ψ

,

która

jest

zbudo

w

ana

wyª¡ znie

ze

zmienn

y

h,

na

wiasó

w

i

funktora

f

.

F

unktory

¬

,

∧

,

∨

,

⇒

i

⇔

tej

wªasno± i

nie

ma

j¡.

Ÿ

2

.

Ra

h

unek

zda«

2

I

Meto

da

rezolu ji

☛

Badanie

sp

eªnialno± i

form

uª

jest

trudne

obli zenio

w

o.

Jedn

ym

z

algorytmó

w,

które

mo»na

wyk

orzysta¢

do

tego

elu

jest

tzw.

meto

da

r

ezolu ji

.

☛

W

pierwszym

etapie

przeksztaª am

y

badan¡

form

uª

do

p

osta i

b

d¡ ej

k

oniunk

j¡

alternat

yw

liter

a-

ªów

,

tj.

wyra»e«

p

osta i

p

lub

¬p

,

gdzie

p

jest

zmienn¡

zdanio

w

¡.

(1)

Usu«

z

form

uªy

funktory

ró

wno

w

a»no± i

i

implik

a ji,

zamienia

j¡

wszystkie

wyra»enia

p

osta i

ϕ ⇔ ψ

na

(ϕ ∧ ψ) ∨ (¬ϕ ∧ ¬ψ)

i

wszystkie

wyra»enia

p

osta i

ϕ ⇒ ψ

na

(¬ϕ) ∨ ψ

.

(2)

Przenie±

wszystkie

nega je

do

±ro

dk

a

k

orzysta

j¡

z

pra

w

de

Morgana.

Usu«

p

o

dw

ó

jne

prze zenia.

(3)

Zastosuj

pra

w

a

rozdzielno± i

w

elu

usuni ia

k

oniunk

ji

z

wntrza

alternat

yw.

Usu«

zb

dne

na

wiasy

.

☛

Na

p

o

z¡tku

drugiego

etapu

badana

form

uªa

ma

p

osta¢

ϕ

1

∧ ϕ

2

∧ . . . ∧ ϕ

n

,

gdzie

ϕ

1

,

ϕ

2

,

.

.

.

,

ϕ

n

s¡

alternat

yw

ami

p

ewn

y

h

literaªó

w.

(4)

Nie

h

S = {S

1

, S

2

, . . . , S

n

}

,

gdzie

S

i

jest

zbiorem

literaªó

w,

z

który

h

zbudo

w

ane

jest

ϕ

i

.

(5)

Dop

óki

istniej¡

zmienna

p

oraz

elemen

t

y

s

1

, s

2

∈ S

takie,

»e

p ∈ s

1

,

¬p ∈ s

2

i

(s

1

\ {p}) ∪ (s

2

\ {¬p}) /

∈ S

wyk

on

uj

S = S ∪ {(s

1

\ {p}) ∪ (s

2

\ {¬p})}

.

(6)

Badana

form

uªa

jest

sp

eªnialna

wtedy

i

t

ylk

o

wtedy

,

gdy

∅ /

∈ S

.

Ÿ

2

.

Ra

h

unek

zda«

2

J

Meto

da

rezolu ji

(2)

☛

Ab

y

zademonstro

w

a¢

dziaªanie

meto

dy

rezolu ji,

ustalim

y

przy

jej

p

omo

y

zy

form

uªa

(p ⇒ q) ⇒

(p ⇒ (¬q))

jest

sp

eªnialna.

Przeksztaª enia

wyk

on

yw

ane

w

krok

a

h

1



3

dadz¡

nastpuj¡ y

efekt:

P

osta¢

form

uªy

W

yk

onana

op

era ja

¬

(¬p ∨ q) ∨ (¬p ∨ ¬q)

p

o

usuni iu

implik

a ji

¬

(¬p ∨ q) ∨ (¬p ∨ ¬q)

p

o

usuni iu

ró

wno

w

a»no± i

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

p

o

zastoso

w

aniu

pra

w

de

Morgana

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

p

o

usuni iu

p

o

dw

ó

jn

y

h

prze ze«

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

p

o

zastoso

w

aniu

pra

w

rozdzielno± i

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

p

o

usuni iu

zb

dn

y

h

na

wiasó

w

☛

Otrzyman

y

na

tej

p

o

dsta

wie

w

kroku

zw

art

ym

zbiór

S

ma

p

osta¢

{{p, ¬p, ¬q}, {¬q, ¬p}}

.

Krok

pi¡t

y

go

nie

zmieni.

☛

P

oniew

a»

∅ /

∈ S

,

wi

badana

form

uªa

jest

sp

eªnialna.

Ÿ

2

.

Ra

h

unek

zda«

2

K

Reguªy

do

w

o

dzenia

☛

Nie

h

ϕ

1

,

ϕ

2

,

.

.

.

,

ϕ

n

oraz

ψ

b

d¡

form

uªami.



Napis

ϕ

1

,ϕ

2

,...,ϕ

n

ψ

jest

s hematem

wnioskowania

wtedy

i

t

ylk

o

wtedy

,

gdy

form

uªa

(ϕ

1

∧ϕ

2

∧. . .∧ϕ

n

) ⇒

ψ

jest

tautologi¡.



Je»eli

napis

ϕ

1

,ϕ

2

,...,ϕ

n

ψ

jest

s

hematem

wniosk

o

w

ania,

to

form

uªy

ϕ

1

,

ϕ

2

,

.

.

.

,

ϕ

n

s¡

jego

przesªankami

,

a

form

uªa

ψ

wnioskiem

.

☛

Z

u

w

agi

na

p

eªnion¡

funk

j,

s

hemat

y

wniosk

o

w

ania

nazyw

ane

s¡

tak»e

r

e

guªami

dowo

dzenia

.

Istnieje

wiele

reguª

do

w

o

dzenia;

do

na

jw

a»niejszy

h

nale»¡:

S

hemat

Nazw

a

p⇔q

(p⋆r)⇔(q⋆r)

reguªa

zastp

o

w

ania

zdaniem

ró

wno

w

a»n

ym

p,p⇒q

q

reguªa

o

dryw

ania

p⇒q,q⇒r

p⇒r

reguªa

sylogizm

u

w

arunk

o

w

ego

p⇒q

¬q⇒¬p

reguªa

k

on

trap

ozy ji

p⇒q,p⇒r

p⇒(q∧r)

reguªa

do

w

o

dzenia

z

k

oniunk

j¡

q⇒p,r⇒p

(q∨r)⇒p

reguªa

do

w

o

dzenia

z

alternat

yw

¡

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

p

,

¬p⇒(q∧¬q)

p

reguªy

do

w

o

dzenia

nie

wprost

Ÿ

2

.

Ra

h

unek

zda«

2

L