PJWSTK-MATEMATYKA DYSKRETNA 2001/02

KOLOKWIUM 2

Imię i Nazwisko:

Grupa:

Indeks:

1. Które z poniższych relacji binarnych ~ są relacjami równoważności:

• Relacja ~ określona w zbiorze liczb całkowitych Z \ {0}:

x ~ y wttw x/y > 0

• Relacja ~ określona w zbiorze liczb całkowitych Z:

x ~ y wttw x + y  1

2. Rozważmy relację binarną w zbiorze liczb całkowitych Z:

x ~ y wttw x - y jest wielokrotnością 5.

Udowodnić, że ~ jest relacją równoważności. Ile klas abstrakcji ma ta relacja. Wskazać kilka elementów

klasy abstrakcji [3].

3. Które z relacji przedstawionych w Zad 1 są relacjami częściowego porządku?

4. Rozważmy relację ~ w zbiorze R x R:

(a, b) ~ (c, d) wttw a³  c³ , b³  d³

Czy ~ jest relacją częściowego porządku, dlaczego?

5. Rozważmy zbiór liczb rzeczywistych R z relacją  Znaleźć:

• sup {x  R: x³  15}

• inf { x  R: x²  8}

6. Zbuduj matrycę logiczną dla następującej formuły rachunku zdań:

(p ∨ ¬q) → (p → q)

7. Które z poniższych formuł są tautologiami rachunku zdań

• (p ∧ q) → (q ∨ p)

• (p ∨ ¬q) → (¬p ∧ q)

8. Czy następująca reguła wnioskowania jest poprawna, dlaczego?:

9. 
   Zapisać w postaci formuły rachunku kwantyfikatorów następujące zdania:

• Dla każdych liczb rzeczywistych x, y istnieje liczba rzeczywista z taka, że y < z oraz z < x

• Istnieje liczba naturalna a taka, że b jest wielokrotnością a dla wszystkich liczb naturalnych b

10. Udowodnić indukcyjnie wzór

1 + 3 + 5 + ... + (2n+1) = (n+1)²

T. Lan Le E-mail: [e-mail]

---