Ćwiczenia 2.

Klasyczny Rachunek zdań i rachunek predykatów -

zadania.

mgr Zofia Makara

1 marca 2004

1

Wprowadzenie

Zdaniem prostym nazywa się zdanie, w którym nie ma spójników funkto-
rów zdaniotwórczych, zaś zdaniem złożonym to, w którym one występują.

Predykat pierwszego rzędu jest to funktor zdaniotwórczy od argumen-
tów będących nazwami jednostkowymi (w zależnośći od liczby argumentów
wyróżniamy predykaty jedno-, dwu-, n- argumentowe). W wyrażeniach ra-
chunku predykatów występują wszystkie symbole rachunku zdań, kwantyfi-
katory: ogólny ∀ lub

V

(zwany również uniwesalnym lub dużym) i szczegó-

łowy ∃ lub

W

(zwany również egzystencjonalnym lub małym) oraz zmienne

reprezentujące predykaty.
Jeżeli dana zmienna występuje pod kwantyfikatorem mówi się o niej, że jest
zmienną związaną. W przeciwnym przypadku jest zmienną wolną.

Ciekawostka 1 Wszystkich funktorów n− argumentowych jest 2

2

n

.

Prawdziwość zdań można wykazywać nie tylko metodą zero-jedynkową, ale
również dowodzić: metodą wprost - polegającą na wykazaniu prawdziwości
wniosku na podstawie przesłanek, lub nie wprost - doprowadzając do absur-
du (wykazując, że zaprzeczenie wniosku daje sprzeczność z założeniemi).
Wykorzystuje się przy tym tak zwane reguły dołączania wierszy do dowodu:

• Reguła odrywania

p

⇒ q

p
q

• Reguła odrywania alternatywy

p

∨ q

¬p
q

1

lub

p

∨ q

¬q
p

• Reguła odrywania koniunkcji

p

∧ q

p

lub

p

∧ q

q

• Reguła odrywania równoważności

p

⇔ q

p

⇒ q

lub

p

⇔ q

q

⇒ p

• Reguła odrywania negacji

¬¬p
p

• Reguła dołączania alternatywy

p
p

∨ q

lub

q
p

∨ q

• Reguła dołączania koniunkcji

p
q
p

∧ q

• Reguła dołączania równoważności

p

⇒ q

q

⇒ p

p

⇔ q

2

• Reguła dołączania negacji

p
¬¬p

• Toll

p

⇒ q

¬q
¬p

lub

p

⇒ ¬q

q
¬p

lub

¬p ⇒ ¬q
q
p

lub

¬p ⇒ q
¬q
p

• Reguła dołączania kwantyfikatora ogólnego

p(x)
∀x ∈ X

p(x)

• Reguła dołączania kwantyfikatora szczegółowego

p(a)
∃x ∈ X

p(x)

a ∈ X.

• Reguła odrywania kwantyfikatora ogólnego

∀x ∈ X

p(x)

p(a)

a ∈ X.

• Reguła odrywania kwantyfikatora szczegółowego

∃x ∈ X

p(x)

p(a)

a ∈ X.

3

Przykłady dowodzenia wprost:

Przykład 1

∀x(p(x) ⇒ q(x)) ⇒ (∀xp(x) ⇒ ∀xq(x)

1. ∀x(p(x) ⇒ q(x))

zał;

2. ∀xp(x)

zał;

3. p(x) ⇒ q(x)

[−∀]:1;

4. p(x)

[−∀]:2;

5. q(x)

[RO]:3,4;

∀yp(y)

[+∀]:5;

Przykład 2

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

1. (p ⇒ q) ∧ (q ⇒ r)

zał;

2. p

zał;

3. (p ⇒ q)

[ROK]:1;

4. (q ⇒ r)

[ROK]:1;

5. q

[RO]:3,2;

r

[RO]:4,5;

2

Prawa rachunku kwantyfikatorów

∀x ∈ Xp(x) ⇒ p(a), a ∈ X,

∀x ∈ Xp(x) ⇒ ∃x ∈ Xp(x),

p(a) ⇒ ∃x ∈ Xp(x),

¬[∃x ∈ Xp(x)]) ⇔ ∀x ∈ X¬p(x),

¬[∀x ∈ Xp(x)] ⇔ ∃x ∈ X¬p(x),

∀x ∈ X(p(x) ∧ q(x)) ⇔ ∀x ∈ Xp(x) ∧ ∀x ∈ Xq(x),

[∀x ∈ Xp(x) ∨ ∀x ∈ Xq(x)] ⇒ ∀x ∈ X[p(x) ∨ q(x)],

∃x ∈ X(p(x) ∧ q(x)) ⇒ [∃x ∈ Xp(x) ∧ ∃x ∈ Xq(x)],

∃x ∈ X(p(x) ∨ q(x)) ⇔ ∃x ∈ Xp(x) ∨ ∃x ∈ Xq(x),

∀x ∈ X∀y ∈ Y r(x, y) ⇔ ∀y ∈ Y ∀x ∈ Xr(x, y),

∃x ∈ X∃y ∈ Y r(x, y) ⇔ ∃y ∈ Y ∃x ∈ Xr(x, y),

∃x ∈ X∀y ∈ Y r(x, y) ⇔ ∀y ∈ Y ∃x ∈ Xr(x, y).

4

3

Zadania na ćwiczenia

1. Zdefiniować wszystkie cztery funktory jednoargumentowe, przy wyko-

rzystaniu funktora Sheffera.

Przykład 3

p

¬p p/p

1

0

0

0

1

1

2. Zapisz za pomocą zmiennych zdaniowych, sprawdź prawdziwość zdań

i podaj wszystkie zdania proste tego zdania złożonego:

• Liczba naturalna a jest liczbą pierwszą, to jeżeli a jest złożona,

to jest a równa 4.

Przykład 4 p - a jesl liczbą pierwszą.
¬p - a jesl liczbą złożoną.
q - a = 4.
p ⇒ (¬p ⇒ q)
Zdania proste: ”Liczba naturalna a jest liczbą pierwszą”, ”a jest
złożona”, ”a równa 4”.

• Jeżeli a jest liczbą parzystą, to z faktu, że a nie jest liczbą parzystą

wynika, że jest podzielne przez 4.

• Jeżeli figura A ma sumę kątów równą 360 lub figura A ma cztery

boki, to nie jest prawdą, że suma kątów nie jest równa 360 stopni
i liczba boków nie jest równa 4.

• Jeżeli pan Kowalski sprzedał samochód i pan Kowalski kupił mo-

tocykl, to nie jest prawdą, że pan Kowalski nie sprzedał samo-
chodu lub nie pan Kowalski nie kupił motocykla.

• Jeżeli Jan Kowalski studiuje, to jest to równoważne, że nie jest

prawdą, że Jan Kowalski nie studiuje.

• Jeżeli z faktu, że funkcja f jest różniczkowalna w x

0

, wynika,

że jest ona ciągła w x

0

, to z faktu, że funkcja jest ciągła w x

0

,

wynika, że jest ona różniczkowalna w x

0

.

3. Korzystając z praw arytmetyki i rachunku zdań znaleść rozwiązanie

nierówności:

• x

2

− 4 ¬ 0.

Rozwiązaniem jest forma zdaniowa:

[((x − 2) ¬ 0) ∧ ((x + 2) ­ 0)] ∨ [((x − 2) ­ 0) ∧ ((x + 2) ¬ 0)];

5

•

x

2

−1

x

2

−4

­ 0;

•

x

2

−1

x

2

+2

­ 0;

4. Ocenić wartość logiczną zdania i zapisać jego negację:

•

∀x ∈ N (x

2

­ (2x − 3));

•

∀x ∈ N (

x

2

(2x − 3)

¬ 1);

•

∃x ∈ R(x

2

+ y

2

¬

1

10

);

•

∃x ∈ R

+

(

x − 1

x + 1

< 1)

4

Sprawozdanie z ćwiczeń

1. Zdefiniować co najmniej sześć funktorów dwuargumentowych, przy

wykorzystaniu funktora Sheffera.

2. Podaj następujące prawa logiki i sprawdż je metodą ”zero-jedynkową”:

prawo podwójnego przeczenia, prawo wyłączonego środka, prawo sprzecz-
nośći, prawa de Morgana i prawo transpozycji.

3. Zapisz za pomocą zmiennych zdaniowych, sprawdź prawdziwość zdań

i podaj wszystkie zdania proste tego zdania złożonego:

• Jeżeli Jan Kowalski ma dom i Anna Kowalska ma dom, to wynika

z tego, że nie jest prawdą, że Jan Kowalski ma dom lub Anna
Kowalska nie ma domu.

• Jeżeli Nowak był poetą i Kowalski nie był poetą to jest równo-

ważne, że nie jest prawdą, że obaj byli poetami.

• Jeżeli a dzieli się przez 3 i a dzieli się przez 2, to z faktu, że a nie

dzieli się przez 2 wynika, że a nie dzieli się przez 3 lub dzieli się
przez 2 i dzieli się przez 3.

4. Korzystając z praw arytmetyki i rachunku zdań znaleść rozwiązanie

nierówności:

•

x

2

+x+12

x−1

¬ 0;

6

• (x − 1)(x

2

+ 1)(x − 1) ­ 0.

5. Ocenić wartość logiczną zdania i zapisać jego negację:

•

∀x ∈ R((x

2

− 1) ­ (2x − 2));

•

∀x ∈ R((x

2

− 1) > (2x − 2));

•

∃x ∈ R(sin x ¬ −

1

2

);

•

∃x ∈ R

+

(

x + 1

x − 1

< 1)

6. DLA CHĘTNYCH: podać przykład dowodzenia nie wprost.

7. DLA CHĘTNYCH: udowodnić metodą wprost: [(p ∨ q) ∧ ¬p] ⇒ q.

8. DLA CHĘTNYCH: udowodnić metodą wprost:

(p ⇒ q) ⇒ [(p ∧ r) ⇒ q].

7