Matematyka Dyskretna i Logika

Część 1:

1. Dowodzenie tautologii.

2. Upraszczanie zdań logicznych.

3. Działania na zbiorach.

4. Analiza zdania z kwantyfikatorami.

5. Indukcja matematyczna.

6. Sprawdzanie wzorów na diagramach Venny.

7. Obliczanie NWD i NWW (algorytm Euklidesa).

8. Równanie diofantyczne z wykorzystaniem rozszerzonego alg. Euklidesa.

9. Kongruencja - na jaką cyfrę kończy się liczba 7⁵⁶.

10. Schemat Hornera- szybkie potęgowanie.

11. Rozwiązywanie równań rekurencyjnych metodą podstawiania i równania charakterystycznego.

12. Zasada włączania i wyłączania (liczby podzielne przez 3, a niepodzielne przez 5 lub 7)

13. Podzbiory, sekwencje-kombinacje, wariacje.

1. Uprość wyrażenie logiczne:

~(p→ ~q) ∧ ~(p∨~s) ∧ ~(~p→ ~t)

2. Mamy zbiory: A=(2;8), B=[-1;5]. Znajdź zbiór (A\B)⊕(A⊕B).

3. Czy następujące zdanie jest prawdziwe (uzasadnij):

∀x∈R ∃! y∈N: x²=y

4. Sprawdź równość zbiorów (diagramy Venny):

(A\B)⊕A = (B∩A)\B

5. Oblicz NWW(34,128) korzystając z algorytmu Euklidesa.

6. Rozwiąż równanie diofantyczne: 8x +3y = 37.

7. Rozwiąż równanie rekurencyjne metodą równania charakterystycznego:

a_n - a_n-1 - 2a_n-2 = 0 _, a₀ = 2, a₁ = 5.

8. Rozwiąż równanie rekurencyjne metodą podstawienia:

a_n =7 a_n-1 +6, a₁ =6.

9. Ile liczb w zbiorze {1..560} jest podzielnych przez 11 i jednocześnie niepodzielnych przez 2 lub 9?

10. Ile 7-elementowych podzbiorów ma zbiór 25-elementowy?

Część 2:

1. Znajdź macierz wierzchołków i macierz incydencji grafu K_2,2.

2. Czy graf z zad.1 jest grafem Eulera lub Hamiltona?

3. Znajdź minimalne drzewo spinające grafu K_5, jeżeli waga każdej krawędzi wynosi 2. Ile wynosi suma wag tego drzewa?

4. Czy graf K_7,9 jest planarny? Uzasadnij bez rysowania grafu.

5. Wyjaśnij problem mostów królewieckich, narysuj odpowiedni graf i podaj jego reprezentację macierzową.

6. Ile jest drzew oznaczonych o 6 wierzchołkach?

7. Narysuj drzewo 5231 z korzeniem 2.

8. Jakie cechy relacji bierzemy pod uwagę?

9. Narysuj wszystkie drzewa nieoznaczone o 5 wierzchołkach.

10. Do czego służą algorytmy Kruskala i Prima? Zastosuj je dla najprostszego grafu.

11. Kiedy w grafie istnieje droga Eulera (twierdzenie)?

12. Tw. Cayley'a.

13. Podaj definicję drzewa.

14. Ile krawędzi ma graf K_n ze wszystkimi pętlami?

15. Kiedy grafy są izomorficzne?

16. Które grafy pełne są planarne?

17. Które grafy dwudzielne pełne są planarne?

18. Jaka droga Hamiltona jest rozwiązaniem problemu komiwojażera?

19. Narysuj 3 grafy Eulera.

20. Narysuj 3 grafy Hamiltona.

21. Podaj przykład macierzy wierzchołków grafu z samymi pętlami.

22. Podaj przykład macierzy incydencji grafu z samymi pętlami.

23. Co to jest graf z wagami?

24. Narysuj graf Eulera, który nie jest grafem Hamiltona.

25. Narysuj graf Hamiltona, który nie jest grafem Eulera.

26. Narysuj graf semi-eulerowski.

27. Narysuj graf semi-hamiltonowski.

28. Narysuj graf, który jest grafem i Eulera, i Hamiltona.

29. Narysuj graf, który nie jest ani Eulera, ani Hamiltona.

30. Czy graf Eulera może mieć pętle?

31. Czy graf Hamiltona może mieć pętle?

32. Podaj definicję grafu semi-eulerowskiego.

33. Podaj definicję grafu semi-hamiltonowskiego.

34. Narysuj przykładowe drzewo binarne.

35. Podaj przykład macierzy wierzchołków grafu z wierzchołkiem izolowanym.

36. Podaj przykład macierzy incydencji grafu z wierzchołkiem izolowanym.

37. Czy wierzchołek może mieć stopień 0?

38. Czy w drzewie może być tylko 1 wierzchołek stopnia 1?

---