´

Cwiczenie 2

Tautologie. Konsekwencje logiczne.
Rezolucja. Logika pierwszego rz ˛

edu

2.1

Zadania teoretyczne

2.1.1

Tautologie

1. Sprawdzi´c, czy formuła (p ∨ q) ⇒ (∼ p ⇒ q) jest tautologi ˛

a.

Rozwi ˛

azanie:

(a) metoda zero-jedynkowa

p

q

p ∨ q

∼ p

∼ p ⇒ q

(p ∨ q) ⇒ (∼ p ⇒ q)

0

0

0

1

0

1

0

1

1

1

1

1

1

0

1

0

1

1

1

1

1

0

1

1

(b) skrócona metoda zero-jedynkowa

1.

w [(p ∨ q) ⇒ (∼ p ⇒ q)] = 0

2.

w (p ∨ q) = 1

w (∼ p ⇒ q) = 0

3.

w (∼ p) = 1

w (q) = 0

w (p) = 0

4.

(0 ∨ 0) = 1

5.

0 = 1 SPRZECZNO´S´

C

Komentarz: 1. zakładamy fałszywo´s´c formuły; 2. poniewa˙z funktorem głównym jest implikacja, st ˛

ad jej

poprzednik musi by´c prawdziwy, a nast ˛epnik fałszywy; 3. warunek w (∼ p ⇒ q) = 0 jest fałszyw ˛

a implikacj ˛

a,

st ˛

ad w (∼ p) = 1, tzn. w (p) = 0 i w (q) = 0; 4. podstawiamy w (p) = 0 i w (q) = 0 do warunku w (p ∨ q) = 1;

5. otrzymujemy sprzeczno´s´c, zatem nie udowodnili´smy fałszywo´sci formuły.

(c) metoda przekształcenia do postaci normalnej

(p ∨ q) ⇒ (∼ p ⇒ q) ≡

1.

≡ ∼ (p ∨ q) ∨ [∼ (∼ p) ∨ q] ≡

2.

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

3b.

≡

∼ p ∨ p ∨ q



∧

∼ q ∨ p ∨ q



≡

≡ 1 ∧ 1 ≡ 1

Obydwie dysjunkcje elementarne s ˛

a tautologiami – pierwsza zawiera par ˛e literałów komplementarnych

{p, ∼ p}, druga zawiera par ˛e {q, ∼ q}.

Odpowied´z:

Formuła jest tautologi ˛

a.

7

2. Sprawdzi´c trzema metodami, czy formuła jest tautologi ˛

a.

(a) p ⇒ (p ⇒ q)

(b) (p ∧ q) ⇒ (p ∨ q)

(c) (p ∧ q) ∨ (p ⇒ q)

(d) (p ⇒ q) ⇒ (∼ p ∨ q)

(e) (p ∧ ∼ q) ⇒ ∼ (p ⇒ q)

Odpowied´z:

Tautologiami s ˛

a formuły: b, d, e.

3. Sprawdzi´c trzema metodami, czy formuła jest kontrtautologi ˛

a.

(a) (p ∨ q) ∧ (p ∧ ∼ q)

(b) (p ∧ q) ∧ (p ⇒ ∼ q)

(c) p ∧ ∼ (p ⇒ q)

(d) ∼ [p ⇒ (p ⇒ ∼ q)]

(e) ∼ (p ∨ q) ∧ (∼ p ⇒ q)

Odpowied´z:

Kontrtautologiami s ˛

a formuły: b, e.

4. Sprawdzi´c metod ˛

a skrócon ˛

a, czy formuła jest tautologi ˛

a.

(a) (p ⇔ q) ⇒ [(p ⇒ q) ∨ q]

(b) [(p ⇒ q) ∧ q] ⇒ (p ⇔ q)

(c) (p ⇒ q) ⇔ (∼ q ⇒ ∼ p)

(d) (∼ p ⇒ q) ⇔ (q ⇒ p)

(e) [(p ∧ ∼ q) ∧ (q ⇔ ∼ r)] ⇒ r

(f) [p ⇒ (q ∧ r)] ⇒ [∼ q ⇒ (p ∨ ∼ r)]

(g) (p ⇒ q) ⇒ {(p ⇒ r) ⇒ [p ⇒ (q ∧ r)]}

Odpowied´z:

Tautologiami s ˛

a formuły: a, c, e, g.

5. Sprawdzi´c metod ˛

a skrócon ˛

a, czy formuła jest kontrtautologi ˛

a.

(a) (p ⇔ q) ∧ ∼ (p ⇒ q)

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

(c) (p ⇒ q) ∧ (∼ q ⇒ ∼ r) ∧ ∼ [(p ∨ r) ⇒ q]

Odpowied´z:

Kontrtautologiami s ˛

a formuły: a, c.

2.1.2

Konsekwencje logiczne

1. Sprawdzi´c poprawno´s´c wnioskowania: Je´sli funkcja ma pochodn ˛

a, to jest ci ˛

agła, a je´sli funkcja jest ci ˛

agła,

to ma pochodn ˛

a, a wi ˛

ec funkcja ma pochodn ˛

a, wtedy i tylko wtedy, gdy jest ci ˛

agła.

Rozwi ˛

azanie:

• schemat wnioskowania mo˙zna zapisa´c w trzech postaciach:

p ⇒ q, q ⇒ p

p ⇔ q

lub

p ⇒ q
q ⇒ p
p ⇔ q

lub

{p ⇒ q, q ⇒ p} |= p ⇔ q

gdzie p – funkcja ma pochodn ˛

a

, q – funkcja jest ci ˛

agła

,

• korzystamy z definicji konsekwencji logicznej :

p

q

p ⇒ q

q ⇒ p

p ⇔ q

0

0

1

1

1

0

1

1

0

0

1

0

0

1

0

1

1

1

1

1

Istniej ˛

a dwa modele i w ka˙zdym z nich wniosek jest prawdziwy.

8

• lub stosujemy twierdzenie, w którym badamy np. metod ˛

a skrócon ˛

a, czy nast ˛epuj ˛

aca formuła jest tautologi ˛

a:

[(p ⇒ q) ∧ (q ⇒ p)] ⇒ (p ⇔ q)

• lub korzystamy z metody rezolucji :

—

przekształcamy przesłanki i negacj ˛e wniosku do postaci klauzulowej:

przesłanki:

p ⇒ q ≡ ∼ p ∨ q
q ⇒ p ≡ ∼ q ∨ p

negacja wniosku:

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

—

tworzymy zbiór klauzul S = {{∼ p, q} , {∼ q, p} , {∼ p , ∼ q} , {p, q}}

—

stosujemy rezolucj ˛e dla utworzonego zbioru S:

1.

{∼ p, q}

2.

{∼ q, p}

3.

{∼ p , ∼ q}

4.

{p, q}

5.

{∼ q}

2, 3

6.

{q}

1, 4

7.

5, 6

lub

{∼ p, q}

{∼ q, p}

{∼ p , ∼ q}

{p, q}

\

\

/

/

\

{∼ q}

/

\

___/_______/

{q}

/

\

/

—

sprawdzenie w Prologu (predykat resolve.pl pobra´c ze strony):

File | Consult ... (załadowa´c resolve.pl)

?- resolve([[~p,q], [~q,p], [~p,~q], [p,q]]).
[[~p, q], [~q, p], [~p, ~q], [p, q]]
[[~p], [~p, q], [~q, p], [~p, ~q], [p, q]]
[[~q], [~p], [~p, q], [~q, p], [~p, ~q], [p, q]]
[[p], [~q], [~p], [~p, q], [~q, p], [~p, ~q], [p, q]]
[[], [p], [~q], [~p], [~p, q], [~q, p], [~p, ~q], [p, q]]
The empty clause is in the set of clauses so it is unsatisfiable.

—

mo˙zna te˙z sprawdzi´c w PropCalcGT

Odpowied´z:

Wnioskowanie jest poprawne.

2. Sprawdzi´c trzema metodami (jak w zadaniu 1.) poprawno´s´c wnioskowania.

(a) Dzisiaj jest pi ˛

atek, a je´sli dzisiaj jest pi ˛

atek, to jutro jest sobota, a wi ˛

ec jutro jest sobota.

Wskazówka:

S = {{p} , {∼ p, q} , {∼ q}}

(b) Je˙zeli Kazimierz spotkał Tadeusza, to wróci pó´zno. Kazimierz nie spotkał Tadeusza. Zatem Kazimierz

nie wróci pó´zno.

(c) Kazimierz był na meczu lub na zebraniu. Gdyby Kazimierz był na meczu, to nie wstałby dzi´s tak

wcze´snie. Kazimierz wstał wcze´snie. A zatem Kazimierz był na zebraniu.

Odpowied´z:

Poprawne jest wnioskowanie: a, c.

3. Sprawdzi´c trzema metodami, czy U |= B.

(a) U = {p ⇒ q, q ⇒ p} , B = p ∨ q

Wskazówka:

S = {{∼ p, q} , {∼ q, p} , {∼ p} , {∼ q}}

(b) U = {p ⇒ q, q ⇒ p} , B = p ⊕ q

(c) U = {p ⇒ q, p ∨ q} , B = q

(d) U = {(p ∧ q) ⇒ r} , B = p ⇒ r

Odpowied´z:

Zbiór

U

implikuje logicznie

B

w przypadku c.

9

2.1.3

Logika pierwszego rz ˛

edu

1. Zapisa´c formuły zda´n.

(a) Niektórzy ludzie s ˛

a Polakami.

Rozwi ˛

azanie:



x

[P (x) ∧ Q (x)] lub ∼



x

[P (x) ⇒ Q (x)],

P (x) – x jest człowiekiem, Q (x) – x jest Po-

lakiem

.

(b) ˙Zadna rzecz nie jest trwała.

Rozwi ˛

azanie:

∼



x

[P (x) ∧ Q (x)] lub



x

[P (x) ⇒ ∼ Q (x)],

P (x) – x jest rzecz ˛

a

, Q (x) – x jest trwały.

(c) Niektóre ptaki nie s ˛

a orłami.

(d) Nie ka˙zdy bogacz jest sk ˛

apcem.

(e) ˙Zadna góra nie jest wieczna.

(f) Niektóre pi ˛ekne auta nie s ˛

a drogie.

(g) Nie ka˙zde pi ˛ekne auto jest drogie.

(h) Ka˙zdy człowiek jest m ˛e˙zczyzn ˛

a lub kobiet ˛

a.

(i) Nie tylko samochody s ˛

a pojazdami.

2. Okre´sli´c, dla jakich argumentów funkcja zdaniowa jest zdaniem prawdziwym.

(a) x

2



x,

x

∈ R

(b) x

2



x,

x

∈ N

(c) |x + 1| = 1, x ∈ R

(d)

y∈R

x

2

+ y

2

= 1, x ∈ R

3. Zaznaczy´c na płaszczy´znie zbiór punktów o współrz ˛ednych (x, y) , dla którego funkcja zdaniowa jest

zdaniem prawdziwym.

(a) |x| > y

(b) ∼ (|x| > y)

(c) (x  y) ∨



x

2

+ y

2



1



(d) (x  y) ∧



x

2

+ y

2

<

1



(e) x · y  1

10

2.2

Zadania praktyczne

1. Zrealizowa´c za pomoc ˛

a bramek NAND, a nast ˛epnie za pomoc ˛

a bramek NOR podane formuły.

(a) ∼ p

(b) p ∧ q

(c) p ∨ q

(d) p ⇒ q

(e) p ⇔ q

(f) p ⊕ q

(g) (p ∨ q) ∧ r

(h) (p ∧ q) ∨ (r ∧ s)

2. Dana jest tablica warto´sci logicznych pewnej formuły. Zrealizowa´c j ˛

a tylko za pomoc ˛

a bramek NAND.

p

q

A

0

0

1

0

1

0

1

0

0

1

1

1

Rozwi ˛

azanie:

• na podstawie tablicy piszemy dysjunkcyjn ˛

a posta´c normaln ˛

a:

A = (∼ p ∧ ∼ q) ∨ (p ∧ q)

• wyprowadzamy negacj ˛e przed nawias (prawa podwójnego przeczenia i de Morgana):

A = (∼ p ∧ ∼ q) ∨ (p ∧ q) ≡ ∼ [∼ (∼ p ∧ ∼ q) ∧ ∼ (p ∧ q)]

• realizacja:

3.

Zrealizowa´c formuł ˛e z powy˙zszego zadania tylko za pomoc ˛

a bramek NOR.

Wskazówka:

Na podstawie tablicy przedstawi´c formuł ˛e w koniunkcyjnej postaci normalnej i dalej post ˛epowa´c

podobnie.

4. Zrealizowa´c formuł ˛e podan ˛

a w tabeli. Wybra´c bramk˛e NAND lub NOR.

p

q

r

A

0

0

0

1

0

0

1

1

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

11