plik

Ćwiczenia 2.

Klasyczny Rachunek zdań i rachunek predykatów -

zadania.

mgr Zofia Makara

1 marca 2004

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

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

łowy ∃ lub

(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

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

⇒ q

p
q

• Reguła odrywania alternatywy

∨ q

¬p
q

lub

∨ q

¬q
p

• Reguła odrywania koniunkcji

∧ q

lub

∧ q

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

⇔ q

⇒ q

lub

⇔ 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

⇒ q

⇒ p

⇔ q

• Reguła dołączania negacji

p
¬¬p

• Toll

⇒ q

¬q
¬p

lub

⇒ ¬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.

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;

[RO]:4,5;

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).

Zadania na ćwiczenia

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

rzystaniu funktora Sheffera.

Przykład 3

¬p p/p

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

, wynika,

że jest ona ciągła w x

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

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

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

nierówności:

• x

− 4 ¬ 0.

Rozwiązaniem jest forma zdaniowa:

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

•

−1

−4

•

−1

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

•

∀x ∈ N (x

(2x − 3));

•

∀x ∈ N (

(2x − 3)

¬ 1);

•

∃x ∈ R(x

+ y

);

•

∃x ∈ R

(

x − 1

x + 1

< 1)

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+12

x−1

¬ 0;

• (x − 1)(x

+ 1)(x − 1) 0.

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

•

∀x ∈ R((x

− 1) (2x − 2));

•

∀x ∈ R((x

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

•

∃x ∈ R(sin x ¬ −

);

•

∃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].