Ćwiczenia #1

1. Uporządkuj następujące funkcje tak, aby każda poprzednia funkcja była funkcją wolniej rosnącą niż funkcja po niej następująca (wszystkie logarytmy są przy takiej samej podstawie 2):

log n , (log n)ⁿ _, n ^{log n} , log(nⁿ) , 2 ^{log n} , n , n³ , (1 + 1/n)ⁿ

2. Wykaż, że 2ⁿ < 10n! < 6nⁿ , dla n >2

3. Ciąg (2, x+3, 8) jest ciągiem arytmetycznym. Wynika stąd, że:

a) x < 1 ; b) x = 1 ; c) x = 2 ; d) x>2

4. Ciąg (8, -4, x) jest ciągiem geometrycznym. Wynika stąd, że:

a) x = -16 ; b) x = -2 ; c) x = 2 ; d) x = 16

5. 5√12 to

1. √17 ; b) √60 , c) √250 , d) √300

n

6. Σ 3^k = ? , dla n = 5

k=0

7. Uprość wyrażenia: (p ⇒¬p) ∧ (¬p ⇒ p) ; (q ⇒ p) ∧ (¬p ⇒ q) ∧ (q ⇒ q)

8. Sprawdź, że następujące wyrażenia są tautologiami: ¬p ⇒ ¬(p ∧ q)

¬(p ⇒ q) ⇔ p ∧ ¬q; (q ⇒ p) ⇔ (¬p ⇒ ¬q)

9. Dana jest baza faktów: a, b, c oraz baza reguł:

R1: If f and e, then g

R2: If a and c, then e

R3: If a and b, then d

R4: If d and e, then f

Czy g należy do bazy faktów (daje sie wyprowadzić z ww. bazy)?

10. Jakim jest zbiór wszystkich pierwiastków wymiernych równania: x² - 2 = 0

11. Sprawdź na diagramach Venna następujące wzory: A ∪ (A ∩ B) = A ;

A \ B = A ∩ B ; (A \ B) ∩ B = ∅ ; A ∩ (B ∪ A) = A ; (A ∪ B)' = A' ∩ B'

12. (S. Lem) W przestworzach istniej hotel INFINITY, który ma nieskończoną liczbę pokoi ponumerowanych liczbami 1 , 2 , 3 , 4 , … Pewnego dnia w tym hotelu chciała się zatrzymać nieskończona delegacja Marsjan, ale niestety wszystkie pokoje były zajęte. Poratuj dyrektora tego hotelu I wskaż mu, co ma zrobić, aby jednak znaleźć wolne pokoje dla całej delegacji Marsjan.

13. Potrafisz bez większego problemu porządkować trzy dowolne liczby, wykonując dwa porównania. Podaj algorytm porządkowania dowolnych czterech liczb, w którym jest wykonywanych nie więcej niż pięć porównań.

14. Posługując się diagramami Venny, udowodnij następujące zawieranie się zbiorów:

A ⊕ B ⊆ (A ⊕ C) ∪ (B ⊕ C)

15. Wyznacz zbiór: {0,1,2,3} ⊕ {2,3,4,5,6} , {0,1,2,3}∪ {2,3,4,5,6} ,

{0,1,2,3} ∩ {2,3,4,5,6}

16. Załóżmy, że alfabet składa się z dwóch znaków Σ = (a,b). Wyobraź sobie słownik zawierający wszystkie niepuste słowa z Σ*, ułożone w porządku alfabetycznym. Jak daleko w tym słowniku musimy szukać słowa ba?

17. Podaj przykład ilustrujący równoważność: ¬(∀y Q(y)) ⇔ ∃y [¬Q(y)]

¬(∃y Q(y)) ⇔ ∀y [¬Q(y)]

18. Czy zdania te są prawdziwe: ∀y > 0 ∀y < 0 ∃z∈R [y < z < y] ;

∃x∈R ∀y∈R [x < y] ; ∀y∈R [2y > y]

19. Sprawdź prawdziwość:

∀x∈R ∃!z∈R ∀y∈R [x + y = z] , ∃!x∈R ∀y∈R [x*y = 0] ,

∀y∈R∃!x∈R [x*y = 0]

¬∀x P(x) ⇒ ∃ x P(x) , ∃ x P(x) ⇒ ¬∀x P(x) , ¬∃ x P(x) ⇒ ∀x P(x)

∀x∈{1,2,3} [P(x) ∧ Q(x)] ⇔ (∀x∈{1,2,3} P(x) ∧ ∀x∈{1,2,3} Q(x))

∃x∈{1,2,3} [P(x) ∧ Q(x)] ⇔ (∃x∈{1,2,3} P(x) ∧ ∃x∈{1,2,3} Q(x))

20. Zapisz z pomocą kwantyfikatorów: n*n = 25 , X + 0 = X , x = 3

21. Sprawdź równoważności: (p ⇒ ¬p) ∧ (¬p ⇒ p) ⇔ 0 ,

(q ⇒ p) ∧ (¬p ⇒ q) ∧ (q ⇒ q) ⇔ p ∨ ¬q

22. Podaj przykład ilustrujący równoważność: ¬(∃y Q(y)) ⇔ ∀y [¬Q(y)]

¬(∃x ∀y [y > x]) ⇔ ∀x∃y [y ≤ x]

23. Wykaż, że wśród dowolnych trzech liczb całkowitych muszą być dwie takie, których suma jest parzysta.

24. Przedstaw liczbę n = 29529 w postaci iloczynu liczb pierwszych.

25. Wyznacz NWD i NWW dla dwóch liczb: 448 i 721.

26. Wyznacz zbiór: {0,1,2,3} ⊕ {2,3,4,5,6}

27. Wyznacz NWD (52,12) i NWW (52,12)

28. Sprawdź, czy następujące wyrażenie jest tautologią:

(q ⇒ p) ⇔ (¬p ⇒ ¬q), ¬ (q ⇒ p) ⇔ (¬p ⇒ ¬q) ,

((p ∨ r) ∧ (q ∨ ¬r)) ⇒ (p ∨ q) , ((p ∨ r) ∧ (q ∨ ¬r)) ⇒ (p ∨ q)

((p ∨ r) ∧ (q ∨ ¬r)) ⇒ (p ∨ q) , (p ∨ r) ⇒ ((p ∨ q)∧ (q ∨ ¬r)),

((p ∧ r) ∨ (q ∧ ¬r)) ⇒ (p ∧ q) , (p ∧ q) ⇒ ((p ∧ r) ∨ (q ∧ ¬r)),

(¬a ∨ b) ∧ (¬b ∨ c) ⇒ (¬c ∧ a) ⇔ b , ((p ∨ q) ∧ ¬p) ⇔ (¬p ∨ q)

29. Wykaż następujące równoważności: p ⇒ (q ⇒ r) ⇔ (p ∧ q) ⇒ r

¬(p ∧ r) ⇔ ¬p ∨ ¬q , p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (q ∧ r) ,

p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (q ∨ r) , (p ⇒ q) ⇒ (¬p ⇒ ¬q) ⇔ ¬q ∨ p

30. Niech A = {1,2,3,4,8,16}, B = {2,4,6,8,10} ` C = {1,3,7,15}.

Wyznacz: B ∪ (C ∩ B) , (B ∪ A) ∩ (A ∪ C) , C \ (B \ A)

---