[DM 12]

[1/12] Przyjmujemy uniwersum X = {1, 2, 3, 4, 5}.

Definiujemy P(x, y) ⇔ -1 ≤ x - y ≤ 1.

Które z poniższych zdań są pradziwe:

(a) ∃_x(∃_y P(x, y))

(b) ∃_x(∀_y P(x, y))

(c) ∀_x(∃_y P(x, y))

Dla jakich elementów uniwersum poniższe funkcje zdaniowe przyjmują wartość “prawda”?

(e) ∃_x(P(x, y))

(f) ∀_x(P(x, y))

[2/12] W języku predykatów wyraź następujące zdania (lub funkcje zdaniowe):

1. “Nie istnieje największa liczba naturalna”. Przyjmujemy, że W(x, y) oznacza, że x > y oraz N(x) oznacza x ∈ N.

2. “Fryzjer goli tych wszystkich i tylko tych, którzy sami się nie golą”. Przyjmujemy, że G(x, y) oznacza, że x goli y, a f oznacza fryzjera, który jest elementem uniwersum (stała indywiduowa).

3. “n jest wielokrotnością 2 i 7”

4. “n nie jest kwadratem liczby całkowitej”

5. “Każda liczba naturalna ma dzielnik będący liczbą pierwszą”, przyjmując, że P(x) oznacza, że x jest liczbą pierwszą

6. “Dla dowolnych dwóch różnych liczb rzeczywistych można znaleźć trzecią, która od jednej z dwóch pierwszych jest większa, a od drugiej mniejsza.

[3/12] Przedstaw poniższe formuły w postaci równoważnej takiej, że wszystkie kwantyfikatory są zgrupowane na początku formuły i żaden z kwantyfikatorów nie ma ograniczonego zasięgu zmiennej. (Wskazówka: zastosuj zmiany nazw zmiennych kwantyfikatorów jeśli to konieczne)

1. ∀_x(P(x)) ∨ ∀_x(Q(x))

2. ∀_x(P(x)) → ∀_x(Q(x))

3. ∀_x(P(x)) → ∀_x(Q(x) ∨ ∀_x(R(x)))

4. ∀_P(x)[ ∃_Q(y)(R(y)) → ∀_S(y)(P(x, y))]

[4/12] Sprawdź, czy następujące formuły są tautologiami rachunku kwantyfikatorów:

2. ∀_x (P(x) ↔∀_x (Q(x))) → ∀_x (P(x) ↔ Q(x))

3. ∀_x (P(x) → Q) ↔ (∀_x (P(x)) → Q)

4. ∀_x (P(x) →∀_x (Q(x))) → ∀_x (P(x) → Q(x))

5. ∀_x (P(x) ∨ Q(x)) ↔ (∀_x (P(x)) ∨ ∀_x(Q(x)))

6. ∃_x (P(x) → Q(x)) → (∃_x (P(x)) → ∃_x (Q(x)))

7. ∀_x(P(x) → Q(x)) ↔ ∀_x (P(x) →∀_x(Q))

8. ∀_x (∀_y P(x, y)) → ∀_x P(x, x)

9. ∃_x (∃_y P(x, y)) → ∃_x P(x, x)

10. ∀_x (P(x) →∀_x (P(x)))

11. ∀_x (∃_x (P(x)) → P(x))

12. ∃_x(∀_y(P(x,y)) ↔ ∀_y(∃_x(P(x,y))

[5/12] W zbiorze liczb naturalnych mamy predykat P(n). Wyrazić za pomocą kwantyfikatorów zdania:

• liczb spełniających P(n) jest co najwyżej skończenie wiele,

• nieskończenie wiele liczb spełnia P(n),

• P(n) spełniają wszystkie liczby, poza co najwyżej skończoną liczbą.

[6/12] Wykaż prawa De Morgana dla kwantyfikatorów ograniczonych:

w oparciu o praw De Morgana dla kwantyfikatorów o nieograniczonym zakresie:

[7/12] Pokaż, że dla dowolnej rodziny zbiorów {A_n}_n∈N zachodzi inkluzja i podaj przykład rodziny, dla której nie zachodzi inkluzja odwrotna (wskazówka: sprowadź problem do zdania teorii kwantyfikatorów). Wyraźnie zaznacz z jakich praw rach. predykatów korzystasz.

---