Podstawy logiki i teorii mnogości Ćwiczenie 3
---------------------------------------------------------------------------------------------------------------------------------------

– 1 –

ĆWICZENIE 3

Klasyczny Rachunek Zdań (KRZ): literał, alternatywa elementarna, koniunkcja
elementarna, formuła w koniunkcyjnej postaci normalnej, formuła w alternatywnej postaci
normalnej, minimalna apn i kpn, siatka karnaugha.

Postacie normalne formuł KRZ

DEF
Formuły p i

p

¬

¬

¬

¬

, gdzie p jest dowolną zmienną zdaniową, nazywamy

literałami

:

p

jest

literałem pozytywnym

, a

p

¬

¬

¬

¬

negatywnym

. Literały

p

i

p

¬

¬

¬

¬

są

przeciwne

(jeden względem

drugiego).

Alternatywa elementarna (klauzula)

jest to alternatywa skończenie wielu literałów, np.

r

q

p

∨∨∨∨

¬

¬

¬

¬

∨∨∨∨

.

Koniunkcja elementarna

jest to koniunkcja skończenie wielu literałów, np.

r

q

p

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

.

Formuła w koniunkcyjnej postaci normalnej

(kpn

)

jest to koniunkcja skończenie wielu

alternatyw elementarnych, np.

((((

)))) ((((

))))

r

p

r

q

p

¬

¬

¬

¬

∨∨∨∨

¬

¬

¬

¬

∧∧∧∧

∨∨∨∨

¬

¬

¬

¬

∨∨∨∨

Formuła w alternatywnej postaci normalnej

(apn)

jest to alternatywa skończenie wielu

koniunkcji elementarnych, np.

((((

)))) ((((

))))

r

p

r

q

p

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

∨∨∨∨

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

TW. Każda formuła KRZ jest logicznie równoważna pewnej formule w kpn i pewnej
formule w apn.


Przypadki szczególne:

(1)

(((( ))))

0

=

==

=

A

w

dla każdego wartościowania w.

Wtedy

A

jest logicznie równoważna formule

p

p

¬

¬

¬

¬

∧∧∧∧

, która jest w apn

(2)

(((( ))))

1

=

==

=

A

w

dla każdego wartościowania w.

Wtedy

A

jest logicznie równoważna formule

p

p

¬

¬

¬

¬

∨∨∨∨

, która jest w kpn

Podstawy logiki i teorii mnogości Ćwiczenie 3
---------------------------------------------------------------------------------------------------------------------------------------

– 2 –

TW. Formuła w kpn jest tautologią KRZ wtedy i tylko wtedy, gdy w każdej składowej
alternatywie elementarnej występuje para przeciwnych literałów.




TW. Formuła w apn nie jest spełnialna wtedy i tylko wtedy, gdy w każdej składowej
koniunkcji elementarnej występuje para przeciwnych literałów.





Sprowadzanie formuł KRZ do apn i kpn metodą przekształceń równoważnych


Podformuły danej formuły zastępujemy formułami równoważnymi w następującej kolejności:


(1) eliminujemy spójniki ↔ i → zastępując odpowiednio:
C

D

↔

przez

(

) (

)

C

D

D

C

→

∧

→

C

D

→

przez

(

)

¬ ∨

C

D

(2) wprowadzamy znak negacji do wnętrza oraz usuwamy
podwójną negację zastępując odpowiednio:

(

)

k

C

C

∧

∧

¬

K

1

przez

(

)

k

C

C

¬

∨

∨

¬

K

1

(

)

k

C

C

∨

∨

¬

K

1

przez

(

)

k

C

C

¬

∧

∧

¬

K

1

¬¬C

przez

C

(3) stosujemy

a) rozdzielczość koniunkcji względem alternatywy (kpn)

zastępując odpowiednio:

(

)

k

C

C

D

∧

∧

∨

K

1

przez

(

)

(

)

k

C

D

C

D

∨

∧

∧

∨

K

1

(

)

D

C

C

k

∨

∧

∧

K

1

przez

(

)

(

)

D

C

D

C

k

∨

∧

∧

∨

K

1

b) rozdzielczość alternatywy względem koniunkcji (apn)

zastępując odpowiednio:

((((

))))

k

C

C

D

∨∨∨∨

∨∨∨∨

∧∧∧∧

K

1

przez

((((

))))

((((

))))

k

C

D

C

D

∧∧∧∧

∨∨∨∨

∨∨∨∨

∧∧∧∧

K

1

((((

))))

D

C

C

k

∧∧∧∧

∨∨∨∨

∨∨∨∨

K

1

przez

((((

))))

((((

))))

D

C

D

C

k

∧∧∧∧

∨∨∨∨

∨∨∨∨

∧∧∧∧

K

1

Podstawy logiki i teorii mnogości Ćwiczenie 3
---------------------------------------------------------------------------------------------------------------------------------------

– 3 –

Sprowadzanie formuł KRZ do apn i kpn metodą tablicową - przykład

r

q

q

p

A

¬

¬

¬

¬

∧

∧

∧

∧

↔

↔

↔

↔

∧

∧

∧

∧

=

=

=

=

p

q

r

q

p

∧∧∧∧

r

¬

¬

¬

¬

r

q

¬

¬

¬

¬

∧∧∧∧

A

apn

kpn

1

1

1

1

0

0

0

r

q

p

¬

¬

¬

¬

∨∨∨∨

¬

¬

¬

¬

∨∨∨∨

¬

¬

¬

¬

1

1

0

1

1

1

1

r

q

p

¬

¬

¬

¬

∧∧∧∧

∧∧∧∧

1

0

1

0

0

0

1

r

q

p

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

1

0

0

0

1

0

1

r

q

p

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

0

1

1

0

0

0

1

r

q

p

∧∧∧∧

∧∧∧∧

¬

¬

¬

¬

0

1

0

0

1

1

0

r

q

p

∨∨∨∨

¬

¬

¬

¬

∨∨∨∨

0

0

1

0

0

0

1

r

q

p

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

0

0

0

0

1

0

1

r

q

p

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

apn: (

r

q

p

¬

¬

¬

¬

∧∧∧∧

∧∧∧∧

)

∨ (

r

q

p

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

)

∨ (

r

q

p

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

)

∨ (

r

q

p

∧∧∧∧

∧∧∧∧

¬

¬

¬

¬

)

∨ (

r

q

p

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

)

∨

(

r

q

p

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

∧∧∧∧

¬

¬

¬

¬

)

kpn: (

r

q

p

¬

¬

¬

¬

∨∨∨∨

¬

¬

¬

¬

∨∨∨∨

¬

¬

¬

¬

)

∧ (

r

q

p

∨∨∨∨

¬

¬

¬

¬

∨∨∨∨

)

Minimalizacja formuł apn i kpn.

DEF.

Minimalną apn

formuły A nazywamy apn mającą najmniejszą liczbę literałów spośród wszystkich apn

tej formuły. Podobnie określamy

minimalną kpn

.

Do upraszczania formuł w postaci apn i kpn stosujemy następujące równoważności logiczne:

(

)

p

p

p

∧

↔

p

p

↔

↔

↔

↔

∧

∧

∧

∧ 1

1

1 ↔

↔

↔

↔

∨

∨

∨

∨

p

(

)

p

p

p

∨

↔

0

0 ↔

↔

↔

↔

∧

∧

∧

∧

p

p

p

↔

↔

↔

↔

∨

∨

∨

∨ 0

((((

))))

p

q

p

p

↔

↔

↔

↔

∧

∧

∧

∧

∨

∨

∨

∨

((((

)))) ((((

))))

p

q

p

q

p

↔

↔

↔

↔

¬

¬

¬

¬

∧

∧

∧

∧

∨

∨

∨

∨

∧

∧

∧

∧

((((

))))

p

q

p

p

↔

↔

↔

↔

∨

∨

∨

∨

∧

∧

∧

∧

((((

)))) ((((

))))

p

q

p

q

p

↔

↔

↔

↔

¬

¬

¬

¬

∨

∨

∨

∨

∧

∧

∧

∧

∨

∨

∨

∨

Podstawy logiki i teorii mnogości Ćwiczenie 3
---------------------------------------------------------------------------------------------------------------------------------------

– 4 –

Minimalizacja apn – siatki Karnaugh’a

1) 2 zmienne

((((

)))) ((((

))))

q

q

p

q

p

↔

↔

↔

↔

∧

∧

∧

∧

¬

¬

¬

¬

∨

∨

∨

∨

∧

∧

∧

∧

q

¬

¬

¬

¬q

p

¬

¬

¬

¬p

Zaznaczamy

n

2 sąsiadujących pól (możliwie najwięcej) i redukujemy tą zmienną, dla której

mamy raz jej negację i raz bez negacji. Reszta bez zmian.

2) 3 zmienne

((((

)))) ((((

)))) ((((

)))) ((((

)))) ((((

))))

r

q

r

p

r

q

p

r

q

p

r

q

p

∧

∧

∧

∧

¬

¬

¬

¬

∨

∨

∨

∨

∧

∧

∧

∧

↔

↔

↔

↔

∧

∧

∧

∧

¬

¬

¬

¬

∧

∧

∧

∧

¬

¬

¬

¬

∨

∨

∨

∨

∧

∧

∧

∧

¬

¬

¬

¬

∧

∧

∧

∧

∨

∨

∨

∨

∧

∧

∧

∧

∧

∧

∧

∧

q

¬

¬

¬

¬q ¬

¬

¬

¬q q

p

¬

¬

¬

¬p

r r

¬

¬

¬

¬r ¬

¬

¬

¬r

p

∧∧∧∧q

p

∧∧∧∧¬

¬

¬

¬q

¬

¬

¬

¬p∧∧∧∧q

¬

¬

¬

¬p∧∧∧∧¬

¬

¬

¬q

X

X

X

Podstawy logiki i teorii mnogości Ćwiczenie 3
---------------------------------------------------------------------------------------------------------------------------------------

– 5 –

3) 4 zmienne

((((

)))) ((((

)))) ((((

))))

q

p

s

r

s

r

q

p

r

q

p

q

p

p

∨

∨

∨

∨

∨

∨

∨

∨

∨

∨

∨

∨

↔

↔

↔

↔

∧

∧

∧

∧

¬

¬

¬

¬

∧

∧

∧

∧

¬

¬

¬

¬

∧

∧

∧

∧

¬

¬

¬

¬

∨

∨

∨

∨

∧

∧

∧

∧

¬

¬

¬

¬

∧

∧

∧

∧

¬

¬

¬

¬

∨

∨

∨

∨

∧

∧

∧

∧

¬

¬

¬

¬

∨

∨

∨

∨

q q q q

p

¬

¬

¬

¬p

¬

¬

¬

¬p

p

r r

¬

¬

¬

¬r ¬

¬

¬

¬r

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

Podstawy logiki i teorii mnogości Ćwiczenie 3
---------------------------------------------------------------------------------------------------------------------------------------

– 6 –

Ćwiczenie 3: wiadomości i umiejętności

1.

Po ćwiczeniu 3 student powinien znać definicje pojęć podanych w nagłówku ćwiczenia

2.

Student powinien posiadać następujące umiejętności:

•

dla danej formuły KRZ wyznaczyć równoważną apn i kpn metodą przekształceń

równoważnych

•

dla danej formuły KRZ wyznaczyć równoważną apn i kpn metodą tablicową

•

dla danej apn (kpn) znaleźć jej postać minimalną za pomocą siatki Karnaugha