Zad. 1. (9 pkt.) Czy następująca funkcja zdaniowa:

A ∩ B ∩ C ≠ A ∪ C ∨ A = B ∨ A = ∅

jest prawdziwa dla każdych trzech podzbiorów zbioru {1, 2, 3, 4, 5}? (Tak/Nie)? Nie

Jeśli odpowiedziałeś "Nie", przedstaw kontrprzykład przez wskazanie trzech (niekoniecznie różnych) zbiorów A, B, C ⊆ {1, 2, 3, 4, 5}, dla których ta funkcja staje się zdaniem fałszywym.

Kontrprzykład (opcjonalnie): A = _..{1} B = _.{1, 2} C = {1}

(w ogólnym przypadku: A = C ≠ ∅, B - dowolny nadzbiór właściwy zbioru A)

Zad. 2. (9 pkt.) Uzupełnij poniższe formuły symbolami zmiennych zdaniowych tak, aby powstałe schematy logiczne były tautologiami.Możesz używać wyłącznie symboli zmiennych zdaniowych (np. p, q, r, s). Dopisywanie spójników logicznych jest niedozwolone. Jeżeli uważasz, że w którymś przypadku takie uzupełnienie nie jest możliwe, wpisz obok formuły sformułowanie "brak rozwiązania".

(a) (p → q) ∨ (~ _.r ∨ r) // alternatywnie (p → q) ∨ (~ r ∨ p) lub (p → q) ∨ (~ q ∨ r)

(b) (p → q) ∨ (~ q ∧ p)

(c) [p → (r → q)] ↔ [( _..... ∨ _..... ) ∧ (~ _.....∨ _..... )] brak rozwiązania

Zad. 3. (9 pkt.) Definiujemy następujące predykaty: P(x) - x jest psem, C(x) - x jest człowiekiem oraz W(x, y) - x jest właścicielem y. Wyraź w języku rachunku predykatów pierwszego rzędu następujące zdania: (a) Żaden człowiek nie ma właściciela. (b) Nie każdy pies ma właściciela. (c) Żaden człowiek nie jest właścicielem wszystkich psów.. Nie wolno używać żadnych innych symboli niż nawiasy, wymienione powyżej predykaty, zmienne, kwantyfikatory oraz spójniki logiczne.

(a) ∀_{C (x)} (∼∃_y (W(y, x)))

(b) ∼∀_P(x) (∃_y (W(y, x)))

(c) ∀_{C (x)} (∼∀_P(y) (W(x, y)))

Zad. 4. (9 pkt.) Udowodnij, że dla dowolnej liczby naturalnej n:
. Dowód przedstaw na odwrocie strony.

1. P(n) ⇔
   

2. 1 ≥ 1 ⇒ P(1)

3. Pozostaje udowodnić P(n) ⇒ P(n + 1) dla każdej liczny naturalnej n.
   n ≥ n ⇒
   
   ⇒ // z monotoniczności funkcji √
   
   ⇒
   
   ⇒ // dzielimy stronami przez
   
   
   ⇒ // z założenia indukcyjnego P(n)
   
   ⇒
   
   ⇒
   P(n + 1)
   

Zad. 5. (9 pkt.). W zbiorze A = {1, 2, ..., 10} zdefiniowano relację binarną S:

xSy ⇔ (x < y ∧ (x + y) mod 5 < 2).

Niech R = p(z(S)). Dla zbioru częściowo uporządkowanego (A, R) Wyznacz:

(a) Wszystkie elementy minimalne: 1, 2

(b) Wszystkie elementy maksymalne:_. 8, 9, 10

(c) Kres górny zbioru {1,2,3,4,5}: (jeżeli kres nie istnieje wpisz symbol #) _.9

Na odwrocie przedstaw diagram Hassego tego porządku.

Zad. 6. (10 pkt.) Dla grafu przestawionego powyżej wyznacz:

(a) Wagę minimalnego drzewa spinającego: _.8

(b) Długość optymalnej trasy chińskiego listonosza: 39 + 8 = 47 // w tym przypadku listonosz przechodzi dwukrotnie przez krawędzie minimalnego drzewa spinającego

(c) Indeks chromatyczny: 4 (d) Liczbę chromatyczną: 3

Zad. 7. (10 pkt.) Wyznacz liczbę podgrafów pełnego grafu K₅, które są:

(a) Izomorficzne z grafem K_1,3:
// kombinacje uogólnione 5 -> 1 wierzchołek stp. 3, 3 wierzchołki stp. 1, 1 wierzchołek pominięty

(b) Izomorficzne z grafem K_2,2:
// kombinacje uogólnione 5 -> 2 wierzchołki w pierwszym zbiorze niezależnym, 2 wierzchołki w drugim zbiorze niezależnym, 1

// wierzchołek pominięty, w ten sposób każdy podgraf K_2,2 jest zliczony dwukrotnie

(c) Izomorficzne z grafem C₅:
// każda permutacja wyznacza cykl C₅, w ten sposób każdy cykl jest zliczony 10-cio krotnie (analogia do sadzania 5-ciu gości

// przy okrągłym stole)

(d) Izomorficzne z grafem P₃:
// graf P₃ jest izomorficzny z K_1,2 - patrz pkt. (a)

---