logika pragmatyczna sem. zimowy 2007/2008, lista 4

1

Lista 4

1. Mamy dane wyrażenie ∃ (x + y = z) gdzie x, y, z należą do zbioru liczb naturalnych. Które y

zmienne w tym wyrażeniu są wolne a które związane? Dla jakich wartości zmiennych wolnych zdanie to jest prawdziwe a dla jakich fałszywe?

2. Niech x i z należą do zbioru liczb naturalnych. Odczytać wyrażenie ∃ ∀ (x ≤ z). Jaką x

z

własność liczb naturalnych ono wyraża? Czy w tym wyrażeniu występują zmienne wolne?

Jaka jest wartość logiczna tego wyrażenia? Czy wartość logiczna tego wyrażenia ulegnie zmianie gdy x i z należą do zbioru liczb całkowitych?

3. Niech n i m będą zmiennymi należącymi do zbioru liczb naturalnych bez liczby 0 a zdanie p(m, n) oznacza, że m dzieli n. Odczytać następujące zdania i podać ich wartość logiczną: (a) ∃ ∀ p(m, n)

(b) ∃ ∀ p(m, n)

(c) ∀ ∃ p(m, n)

(d) ∀ ∃ p(m, n)

n

m

m

n

n

m

m

n

(e) ∀ ∀ p(m, n)

(f) ∃ ∃ p(m, n)

n

m

n

m

4. Zapisz w rachunku predykatów następujące zdania:

(a) Każdy wieloryb jest ssakiem.

(b) Żaden ssak nie jest rybą.

(c) Niektórzy poeci są malarzami.

(d) Istnieje dokładnie jeden klucz pasujący do drzwi od mojego mieszkania.

(e) Istnieją co najmniej dwa klucze pasujące do drzwi od mojego mieszkania.

5. Niech x, y należą do zbioru wszystkich ludzi. Niech predykat P (x, y) oznacza że x jest ojcem y. Używając tego predykatu i kwantyfikatorów zapisz następujące zdania:

(a) Każdy człowiek ma ojca.

(b) Nie każdy człowiek jest ojcem.

(c) Istnieje człowiek, który ma dwóch synów.

(d) Nie istnieje człowiek który ma dwóch ojców.

6. Pokaż, że implikacja logiczna [∃ p(x) ∧ ∃ q(x)] → ∃ [p(x) ∧ q(x)] jest fałszywa podając x

x

x

odpowiednie predykaty p(x) i q(x) dla których ona nie zachodzi.

7. Pokaż, że implikacja logiczna ∃ ∀ p(x, y) → ∀ ∃ p(x, y) jest fałszywa podając odpowiedni x

y

x

y

predykat p(x, y) dla których ona nie zachodzi.

8. Znaleźć zanegowane wyrażenia dla następujacych formuł:

(a) ∀ P (x) → ∃ Q(y) (b) ∀ [P (x) → ∀ Q(y)] (c) ∀ [P (x) → Q(x)] ∧ ∃ [S(x)∧ ∼ R(x)]

x

y

x

y

x

x

9. Napisz zaprzeczenie wyrażenia ∃ ∀ ∃ [z > y → z < x2] bez użycia spójnika ∼. Zmienne x

y

z

x, y, z należą do zbioru liczb rzeczywistych. Które ze zdań jest prawdziwe - oryginalne czy zanegowane?

10. Napisz zaprzeczenie wyrażenia P = ∀ ∀ [x < y → ∃ x < z < y] bez użycia spójnika ∼.

x

y

z

Wyznacz wartość logiczną zdania P jeżeli dziedziną x, y, z jest

(a) zbiór liczb rzeczywistych

(b) zbiór liczb naturalnych.

11. Przedstawić graficzne (diagram Venna) następujące związki logiczne predykatów:

(a) P (x) ∧ Q(x) ∧ R(x)

(b) P (x) ∧ (Q(x) ∨ R(x))

(c) P (x)∧ ∼ Q(x)

(d) P (x) → Q(x)

(e) (P (x) ∧ Q(x)) → R(x)

(f) P (x) ≡ R(x)

12. Posługując się diagramami Venna pokazać następujące równoważności:

(a) [P (x) → Q(x)] ≡ [∼ P (x) ∨ Q(x)]

(b) ∼ [P (x) ∨ Q(x)] ≡ [∼ P (x)∧ ∼ Q(x)]

13. Sprawdź tabelką czy następujące wyrażenia są prawami rachunku predykatów:

(a) ∼ ∀ [P (x) → P (x)] → P (x)

(b) P (x) → ∀ [P (x) ≡ P (x)]

x

x

(c) ∃ P (x) → ∀ P (x)

(d) ∀ [P (x) ∧ Q(x)] → [∀ P (x) ∧ ∀ Q(x)]

x

x

x

x

x

(e) ∃ [P (x) ∨ Q(x)] → [∃ P (x) ∨ ∃ Q(x)]

(f) ∀ [P (x) → Q(x)] → ∃ [P (x) → Q(x)]

x

x

x

x

x