Politechnika Rzeszowska

Katedra Informatyki i Automatyki

Krzysztof Wiktorowicz

Logika i teoria mnogo´sci

Zadania i ´cwiczenia laboratoryjne

Rzeszów 2012

Literatura

1. Literatura podstawowa:

• Rasiowa H., Wst ˛ep do matematyki współczesnej, PWN, Warszawa 2003.

• Marek W., Onyszkiewicz J., Elementy logiki i teorii mnogo´sci w zadaniach, PWN, Warszawa 2003.

• Trz ˛esicki K., Logika i teoria mnogo´sci, EXIT, Warszawa 2003.

• Ben-Ari M., Logika matematyczna w informatyce, WNT, Warszawa 2005.

• Clocksin W. F., Mellish C. S, Prolog. Programowanie, Helion, Gliwice, 2003.

2. Literatura dodatkowa:

• Stanosz B., Wprowadzenie do logiki formalnej, PWN, Warszawa 2002.

• Stanosz B., ´

Cwiczenia z logiki

, PWN, Warszawa 2002.

• Mostowski A., Logika matematyczna, http://matwbn.icm.edu.pl/ksspis.php?wyd=10.

• Kuratowski C., Mostowski A., Teoria mnogo´sci, http://matwbn.icm.edu.pl/ksspis.php?wyd=10.

Oprogramowanie

1. Programator sterownika SIEMENS LOGO! Soft Comfort:

• strona WWW: http://www2.automation.siemens.com/logo/index_76.html,

• link: LOGO! Software,

• link: Demo software, upgrades/updates, drivers.

2. Interpreter j ˛ezyka SWI-Prolog:

• strona domowa SWI-Prolog: www.swi-prolog.org,

• linki: Download | Stable release,

• wersja: SWI-Prolog/XPCE for MS-Windows.

3. Aplikacja PropCalcGT do rozwi ˛

azywania zada´n z logiki zdaniowej - wykonana w ramach pracy dyplomowej

przez Grzegorza Totona.

Uwaga: Na mojej stronie domowej

prz-rzeszow.pl/~kwiktor

znajduj ˛

a si ˛e linki do wymienionego oprogramowania.

2

´

Cwiczenie 1

Formuły i funktory zdaniotwórcze.
Równowa˙zno´s´c logiczna. Funkcjonalna
pełno´s´

c. Postacie normalne

1.1

Zadania teoretyczne

1.1.1

Formuły i funktory zdaniotwórcze

1. Zapisa´c formuły zda´n. W ka˙zdym przypadku opisa´c atomy.

(a) Je˙zeli nie spróbuj ˛e, to nie wygram.

Rozwi ˛

azanie:

∼ p ⇒ ∼ q,

p

– spróbuj ˛e, q – wygram.

(b) Nie jest prawd ˛

a, ˙ze je˙zeli spróbuj ˛

e, to wygram.

Rozwi ˛

azanie:

∼ (p ⇒ q),

p

– spróbuj ˛

e

, q – wygram.

(c) Je˙zeli Adam o´swiadczył si ˛e Karolinie, to jest ´slepy lub zakochany.

Rozwi ˛

azanie: p

⇒ (q ∨ r),

p

– Adam o´swiadczył si ˛

e

, q – Adam jest ´slepy, r – Adam jest zakochany.

(d) Karolina przyjmie o´swiadczyny Adama i wyjdzie za niego, wtedy i tylko wtedy, gdy Adam zapisze jej

dom lub podaruje dwa samochody.

Rozwi ˛

azanie:

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

p

– Karolina przyjmie o´swiadczyny Adama, q – Karolina wyjdzie za

Adama

, r – Adam zapisze Karolinie dom, s – Adam podaruje Karolinie dwa samochody.

(e) Alfred czy´sci rewolwer i obmy´sla plan zemsty.

(f) Je´sli Roman wygra wybory, to Adam straci prac ˛

e.

(g) Karol zostanie ministrem lub konsulem.

(h) Sufit jest biały, a ´sciany s ˛

a kolorowe.

(i) Poziom nie jest wysoki.

(j) Albo ja przyjd ˛e, albo ty przyjdziesz.

(k) O ile przeczytam podr ˛ecznik lub b ˛

ed ˛

e chodził na wykłady, to zdam egzamin.

(l) Nieprawda, ˙ze je˙zeli skocz ˛e, to złami ˛e nog ˛e.

(m) Je´sli spotkam kolegów, to o ile nie b ˛

edzie za pó´zno, to pójdziemy do kina.

(n) Nie jest prawd ˛

a, ˙ze je´sli sko´ncz ˛

e studia i kurs j ˛

ezykowy, to znajd ˛

e prac ˛

e.

(o) Wynik jest dobry, je˙zeli jest wi ˛ekszy od 12 i nie przekracza 15.

2. Dla jakich warto´sci logicznych p i q podane formuły s ˛

a prawdziwe.

(a) p ∧ q

Rozwi ˛

azanie: w

(p) = 1, w (q) = 1.

(b) (p ∧ q) ⇒ 0

(c) (p ∨ q) ⇒ 0

(d) (p ∧ ∼ q) ⇒ p

3

1.1.2

Równowa˙zno´s´c logiczna

1. Zbada´c, czy formuły A i B s ˛

a logicznie równowa˙zne.

(a) A = ∼ p ∨ q, B = ∼ (p ∧ ∼ q)

(b) A = ∼ (p ⇒ q), B = (p ⇔ ∼ q) ↓ q

(c) A = ∼ (p ↓ q), B = (∼ p) | (∼ q)

2. Upro´sci´c formuły dla w (p) = 1, a nast ˛epnie dla w (p) = 0.

(a) (p ∨ ∼ q) ∧ q

Rozwi ˛

azanie:

• dla w (p) = 1,

(p ∨ ∼ q) ∧ q ≡ (1 ∨ ∼ q) ∧ q ≡ 1 ∧ q ≡ q

• dla w (p) = 0,

(p ∨ ∼ q) ∧ q ≡ (0 ∨ ∼ q) ∧ q ≡ ∼ q ∧ q ≡ 0

(b) p ∨ q

(c) p ⇒ q

(d) p ⇔ q

(e) p ∨ ∼ p

(f) (p ∧ q) ⇒ p

(g) (p ∧ q) ⇔ p

(h) p ∧ ∼ (p ∨ q)

(i) p ⇔ (∼ p ∧ q)

(j) (∼ p ⇒ q) ⇒ ∼ p

(k) (p ⇔ ∼ p) ∨ (q ⇒ p)

1.1.3

Funkcjonalna pełno´s´

c

1. Zdefiniowa´c funktory. Odpowied´z uzasadni´c u˙zywaj ˛ac tabel warto´sci logicznych.

(a) ∼ za pomoc ˛

a {|}

Rozwi ˛

azanie:

∼ p ≡ p | p

(b) ∨ za pomoc ˛

a {|}

Rozwi ˛

azanie: p

∨ q ≡ ∼ (∼ p ∧ ∼ q) ≡ (∼ p) | (∼ q) ≡ (p | p) | (q | q)

(c) ∧ za pomoc ˛

a {∨, ∼}

(d) ∨ za pomoc ˛

a {∧, ∼}

(e) ∨ za pomoc ˛

a {⇒, ∼}

(f) ⇒ za pomoc ˛

a {|}

(g) ∨ za pomoc ˛

a {↓}

1.1.4

Postacie normalne

1. Podane formuły przedstawi´c w dysjunkcyjnej i koniunkcyjnej postaci normalnej.

(a) p ⇔ q

Odpowied´z:

dpn: (∼ p ∧ ∼ q) ∨ (p ∧ q),

kpn: (∼ p ∨ q) ∧ (∼ q ∨ p).

(b) p ∧ [q ∨ (∼ p ∧ r)]

(c) (p ∨ q) ⇒ (q ∨ r)

(d) (p ∧ q) ⇒ (q ∧ p)

(e) (p ∧ q) ⇔ p

2. Utworzy´c postacie normalne dla formuły podanej w tabeli.

p

q

A

0

0

0

0

1

0

1

0

1

1

1

0

4

1.2

Zadania praktyczne

1.2.1

Wprowadzenie

Logika zdaniowa znajduje zastosowanie w budowie układów cyfrowych. Poszczególnym funktorom zdaniotwór-
czym przyporz ˛

adkowuje si ˛e tzw. bramki logiczne.

Nazwa

Funkcja

Symbol

Symbol w LOGO!

AND

p

∧ q

OR

p

∨ q

NOT

∼ p

NAND

p

| q

NOR

p

↓ q

EXOR

p

⊕ q

Za pomoc ˛

a bramek tworzy si ˛e sieci logiczne (układy kombinacyjne), w których stan wyj´scia zale˙zy tylko od

bie˙z ˛acych stanów wej´s´c. Wej´scia i wyj´scia mog ˛a znajdowa´c si ˛e w jednym z dwóch stanów 0 lub 1. Mog ˛

a to by´c

np. dwa rozró˙znialne napi˛ecia.

Niektóre bramki tworz ˛

a zbiory funkcjonalnie pełne, tzn. wykorzystuj ˛

ac tylko bramki z tego zbioru, mo˙zna

zrealizowa´c dowolnie zło˙zony układ logiczny. Okazuje si˛e, ˙ze takich realizacji jest niesko´nczenie wiele, st ˛ad
wa˙znym zagadnieniem jest upraszczanie (minimalizacja) sieci. Rozró˙znia si ˛e metody: algebraiczne (przeksz-
tałce´n formalnych), algorytmiczne (Karnougha, Quine’a-McKluskey’a) i numeryczne.

1.2.2

Przebieg ´

cwiczenia

1. Uruchomi´c program LOGO! Soft Comfort.

2. Zapozna´c si ˛e z wygl ˛

adem okien i menu programu:

• tworzenie nowego schematu: File | New | Function block diagram,

• zapisywanie schematu: File | New | Save as... (ew. Save),

• narz ˛edzia: Tools:

Wybór

Escape

Funkcje specjalne (SF)

F8

Poł ˛

aczenia

F5

Komentarz

F9

Stałe, wej´scia/wyj´scia (Co)

F6

Zmiana poł ˛

acze´n

F11

Funkcje podstawowe (GF)

F7

Symulacja

F3

5

3. Utworzy´c schemat z trójwej´sciow ˛

a bramk ˛

a AND. Przeanalizowa´c jej działanie.

4. Przeanalizowa´c schemat po przeł ˛

aczeniu do j ˛ezyka drabinkowego (ikona Convert to LAD).

5. Zbada´c, jakie funkcje Q

1

= f

1

(I

1

, I

2

), Q

2

= f

2

(I

1

, I

2

) realizuje podany układ?

I

1

I

2

Q

1

Q

2

6. Zbada´c symulacyjnie jedno z praw identyczno´sci p ∨ 1 ≡ 1.

7. Zbada´c symulacyjnie.

(a) pozostałe prawa identyczno´sci

(b) p ∨ ∼ p ≡ 1

(c) prawo sprzeczno´sci

(d) ∼ (p ∧ q) ≡ ∼ p ∨ ∼ q

(e) drugie prawo de Morgana

8. Zrealizowa´c implikacj ˛e. Sprawdzi´c symulacyjnie tablic ˛e warto´sci logicznych.

(a) za pomoc ˛

a {∨, ∼}

Rozwi ˛

azanie: p

⇒ q ≡ ∼ p ∨ q

(b) za pomoc ˛

a {∧, ∼}

9. Zrealizowa´c (p ⇒ q) ⇒ q.

10. Zrealizowa´c funktory i sprawdzi´c symulacyjnie tablice warto´sci logicznych.

(a) p ⇔ q

(b) p ⊕ q

11. Przekształci´c formuł ˛e (p ∨ q) ⇒ r do kpn i zrealizowa´c.

6