Matematyka dyskretna - zadania

Plik z zadaniami do pobrania:

Rachunek zdań

W postaci tabelki wartości logicznych, wypisz wszystkie dwuargumentowe funktory zdaniotwórcze (jest ich szesnaście - dlaczego?). Wskaż koniunkcję (iloczyn), alternatywę (sumę), wynikanie (implikację), równoważność oraz inne znane ci, będące ich złożeniami.
Napisz zdania wyrażające prawo rozdzielności iloczynu (koniunkcji) względem sumy (alternatywy) oraz prawo rozdzielności sumy względem iloczynu. Sprawdź, że są to tautologie.
Sprawdź metodą wartościowania, że poniższe zdania są tautologiami:
Używając symboliki rachunku zdań, zapisz prawa de Morgana. Pokaż, że są one tautologiami.
Sprawdź metodą wartościowania, że poniższe zdania (reguły wnioskowania) są tautologiami:
Zbadaj, czy poniższe zdania są tautologiami:
Zapisz symbolicznie poniższe zdania i zbadaj ich prawdziwość:
Jeśli liczba naturalna a dzieli się przez 3, to z faktu, że a nie dzieli się przez 3 wynika, że a dzieli się przez 5.
Jeśli liczba naturalna a dzieli się przez 3 i dzieli się przez 5, to z faktu, iż a nie dzieli się przez 3 wynika, że a nie dzieli się przez 5.
Jeśli figura A jest czworokątem i A ma wszystkie kąty równe, to z faktu, iż A jest czworokątem wynika, że A ma kąty równe.
Wiemy, że Hylas był Grekiem i filozofem lub też z tego, że był filozofem wynika, że był Grekiem. Czy z tego co wiemy o Hylasie wynika, że jeśli nie był filozofem to nie był Grekiem?
Dwie pary wyłączników sprzężonych tak, że w parze jeden jest włączony a drugi wyłączony, pozwalają, niezależnie od siebie, zaświecać i gasić żarówkę (zob. rys. obok). Napisz zdanie logiczne opisujące działanie tego obwodu. Przedstaw wartościowanie napisanego zdania. Udowodnij metodami rachunku zdań, że oba wyłączniki działają i ich działanie jest niezależne. (Sprawdź, że zanegowanie w zdaniu każdego z "wyłączników" z osobna daje taki sam wynik jak zanegowanie całego zdania.)
Bramkę XOR można przedstawić jako układ bramek: OR, NAND oraz AND (zob. rys. obok). Używając funktorów alternatywy, koniunkcji i negacji napisz zdanie logiczne opisujące działanie tego układu. Przedstaw wartościowanie napisanego zdania.
Zdefiniuj sumę przy pomocy iloczynu i negacji; zdefiniuj iloczyn przy pomocy sumy i negacji.
Funktor, który można zdefiniowac jako: F_S(a,b)~ (ab) nazywany jest dysjunkcją, funktorem Sheffera albo kreską Sheffera (zapis: a|b). Przedstaw tabelkę wartości tego funktora (por. bramkę NAND).
Przy pomocy kreski Sheffera zdefiniuj negację, sumę i iloczyn.
na początek

Funkcje zdaniowe
Zapisz przy pomocy symboli rachunku zdań i prostych operacji arytmetycznych następujące zdania dotyczące liczb naturalnych:
Istnieje liczba najmniejsza.
Nie istnieje liczba największa.
Liczby m i n mają takie same podzielniki.
Liczba w jest najmniejszą wspólną wielokrotnością liczb m i n.
Liczba p jest liczba pierwszą.
Pomiędzy liczbami n i 2n istnieje co najmniej jedna liczba pierwsza (tw. Czebyszewa).
Zapisz przy pomocy symboli rachunku zdań i prostych operacji arytmetycznych następujące zdania dotyczące liczb rzeczywistych:
Nie istnieje liczba, której kwadrat jest mniejszy od zera.
Pomiędzy dwoma dowolnymi liczbami istnieje trzecia.
Liczba x nie jest kwadratem żadnej liczby.
Funkcja f(x) ma dokładnie jedno miejsce zerowe.
Funkcja f(x) jest funkcją malejącą.
Przedstaw "własnymi słowami" sens poniższych zdań - zmienne zdaniowe są liczbami naturalnymi:

na początek

Algebra zbiorów
Korzystając z pojęcia zbioru: A i pojęcia przynależności elementu do zbioru: aA zdefiniuj zbiór pusty (0), równość i zawieranie (inkluzję) zbiorów, iloczyn, sumę i różnicę zbiorów oraz dopełnienie zbioru.
Sformułuj i udowodnij, przy pomocy pojęcia przynależności elementu do zbioru, prawa:
przemienności i łączności sumy i iloczynu zbiorów;
rozdzielności sumy względem iloczynu zbiorów;
rozdzielności iloczynu względem sumy zbiorów.
Sformułuj prawa de Morgana w algebrze zbiorów i udowodnij je.
Udowodnij poniższe równości (prawa pochłaniania):
A(AB) = A A(AB) = A
Dane są zbiory:
Wyznacz zbiory: AB, AB, A', A \ B, B \ A.
Sprawdź prawdziwość praw de Morgana dla zbiorów A i B określonych następująco:
(a) Ω = {x : –10x10}, A = {xΩ: x<0}, B = {xΩ: |x|3};
(b) Ω = {x : x20}, A = {xΩ: x10}, B = {xΩ: x15}.
Pokaż, że dla dowolnych zbiorów A i B zachodzą równości:
A \ B = A \ (AB) A = (AB)(A \ B)
Udowodnij, że dla dowolnych zbiorów A, B i C zachodzą równości:
A(B \ C) = (AB) \ C
(AB) \ C = (A \ C)(B \ C)
A \ (B \ C) = (A \ B)(AC)
Zakładając, że dla zbiorów A i B zachodzi: A'B' = A' oraz BA, udowodnij, że A = B.
Zbadaj, czy dla dowolnych zbiorów A, B, C prawdziwe są następujące zdania:
Różnica symetryczna zbiorów A i B jest określona jako: A ÷ B = (A \ B)(B \ A). Sprawdź, że:
A ÷ B = B ÷ A (A ÷ B = 0)(A = B)
Pokaż, że zbiór liczb parzystych, zbiór liczb nieparzystych, zbiór liczb całkowitych oraz zbiór liczb wymiernych to zbiory przeliczalne (podaj odpowiednie funkcje odwzorowujące).
na początek

Zliczanie
Na ile sposobów można wylosować 13 kart z talii liczącej 52 karty, losując
(a) bez zwracania?
(b) ze zwracaniem?
Ile różnych symboli można przekazać alfabetem Morse'a jeśli jeden symbol składa się co najwyżej z pięciu znaków (kropka lub kreska)?
Dany jest zbiór A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
Ile jest czteroelementowych podzbiorów zbioru A?
Ile jest wszystkich podzbiorów zbioru A?
Ile czteroelementowych podzbiorów zbioru A składa się z trzech liczb parzystych i jednej nieparzystej?
Ile można utworzyć komisji składających się z czterech mężczyzn i czterech kobiet wybranych z grupy, w której jest ośmiu mężczyzn i sześć kobiet?
Ile numerów rejestracyjnych (składających się trzech liter i czterech cyfr) można utworzyć mając do dyspozycji litery od A do E oraz cyfry od 1 do 6?
Ile można utworzyć komisji składających się z czterech osób wybranych z dziewięcioosobowej grupy?
Odpowiedz ponownie na pytanie, wiedząc że dwie osoby z grupy nie lubią się i nie chcą być w tej samej komisji.
Grupa studencka składa się z 12 mężczyzn i 16 kobiet. Na ile sposobów można wybrać reprezentację tej grupy, składającą się z
(a) siedmiu mężczyzn?
(b) siedmiu kobiet?
(c) siedmiu osób?
(d) trzech mężczyzn i czterech kobiet?
Na ile sposobów można uporządkować ciąg {a, b, c, d, e, f} tak aby
(a) litery a i b sąsiadowały ze sobą?
(b) litery a i b nie sąsiadowały ze sobą?
(c) litery a i b sąsiadowały ze sobą natomiast c i d nie?
W grupie składającej się ze 150 osób, 45 regularnie pływa, 40 jeździ na rowerze, 50 biega. Wiemy ponadto, że są 32 osoby, które biegają ale nie jeżdżą na rowerze, 27 osób, które biegają i pływają oraz 10 osób, które uprawiają wszystkie trzy rodzaje aktywności.
Ile osób biega ale nie pływa i nie jeździ na rowerze?
Jeśli 21 osób jeździ na rowerze i pływa, to ile nie uprawia żadnej z tych dwóch aktywności?
Według pewnych danych statystycznych 75 rodzin (na sto ankietowanych) ma komputer lub samochód, 50 ma komputer, 40 ma samochód a 20 ma i komputer i samochód. Sprawdź czy te dane mogą być prawdziwe.
Koń ma dwie nogi prawe, dwie lewe, dwie przednie i dwie tylne. Oblicz ile koń ma nóg, korzystając z zasady włączania - wyłączania.
Wskazówka: nie ma ośmiu :-).
na początek

Indukcja matematyczna i rekurencja
Pokaż, że dla ciągu {a_n}:
jeśli a₁= 1 i a_k+1= 2a_k+1 (postać rekurencyjna) to a_n= 2ⁿ–1 (postać jawna);
jeśli a₁= 4 i a_k+1= 3a_k–2 (postać rekurencyjna) to a_n= 3ⁿ+1 (postać jawna)
Udowodnij, że suma liczb naturalnych od 1 do n jest równa: ½ n(n+1).
Udowodnij, że suma n wyrazów postępu geometrycznego wynosi: a₁(qⁿ–1)/(q–1).
Udowodnij, że dla n początkowych liczb naturalnych:
suma ich kwadratów wynosi n(n+1)(2n+1)/6;
suma ich sześcianów wynosi: [½ n(n+1)]².
Udowodnij, że dla dowolnego n naturalnego n³– n jest podzielne przez 3 oraz n⁵– n jest podzielne przez 5.
Pokaż, że zbiór n-elementowy ma 2ⁿ podzbiorów.
Wychodząc od postaci rekurencyjnej postępu arytmetycznego, udowodnij postać jawną (zwartą) jeśli:
(a) a₀= 2, a₁= 5; (b) a₀= 0, a₁= 2.
na początek

Relacje, własności relacji
Czemu równy jest produkt kartezjański A × B, jeśli:
A = {0, 1}, B = {–1, 0};
A = {–1, 1}, B = {2};
A jest zbiorem liczb całkowitych a B prostą;
A jest odcinkiem, którego końce leżą w punktach 1, 2 na osi OX, B - odcinkiem o końcach w punktach 1, 3 na osi OY.
Udowodnij, które z poniższych wzorów są prawdziwe, a które fałszywe?
A × B = B × A
A(B × C) = (A × B)(A × C)
(A × B)(B × C) = (A × C)
(A \ B) × C = (A × C) \ (B × C)
(A ÷ B) × C = (A × C) ÷ (B × C)
(symbol ÷ oznacza tu różnicę symetryczną - zob. zadanie 26)
Podaj dziedziny i przeciwdziedziny relacji R, S, T określonych następująco:
R = {(a,b), (a,c), (b,c), (c,c)}
S = {(a,a), (a,b), (a,c), (a,d)}
Poniższe relacje RA×A przedstaw w postaci diagramów:
A = {0, 1, 2}, xRyx < y;
A = {1, 2., 3, 4, 5, 6}, xRyx|yx ≠ y;
A = {1, 2, 3, 4}, xRy2|x + y.
Zbadaj własności następujących relacji R, S, T, UX², gdzie X = {a, b, c, d}:
R = {(a,a), (b,b), (a,b)}
S = {(a,a), (b,b), (c,c), (d,d), (a,b), (b,a)}
T = {(a,b), (b,a), (c,a), (a,c), (c,d), (a,d)}
U = {(a,b), (a,c), (b,c), (c,c), (a,a), (b,b)}
1 2 3 4 5

1 + + +

2 + + +

3 +

4 + + +

5 + + +

Zbadaj własności relacji R określonej w zbiorze {1, 2, 3, 4, 5} za pomocą tabelki (zob. tabelka obok). Znak + na skrzyżowaniu m-tego wiersza i n-tej kolumny oznacza, że para (m,n)R.
Sprawdź własności poniższych relacji:
xRyy| x; dla: x,y \ {0}
xRy2| x + y; dla: x,y
xRy2| x – y; dla: x,y
xRy|x| < |y|; dla: x,y
xRy 2| |x – y| dla x,y
xRyx + y = 1; dla: x,y
xRyx + y2; dla: x,y
Zbadaj własności niżej zdefiniowanych relacji:
Ile jest relacji dwuargumentowych określonych w zbiorze {a, b, c} i przyjmujących wartości w zbiorze {0, 1}. Wypisz trzy spośród tych relacji (w tym relację spójną).
Znajdź na płaszczyźnie obrazy relacji R, S, T, U określonych w zbiorze liczb rzeczywistych następująco:
xRyx² + y² < 1
xSyx + y > 1
xTy(x = y) v (–x = y)
xUy|x| < y
Określ własności tych relacji.
I_XX² jest identycznością a RX² dowolną relacją na zbiorze X. Pokaż, że:
(a) jeśli R jest słabo antysymetryczna to R \ I_X jest przeciwsymetryczna;
(b) jeśli R jest przeciwsymetryczna to RI_X jest słabo antysymetryczna.
na początek

Grafy
Przedstaw w postaci grafu następującą relację: A lubi B, C i D; E lubi B i C; B i C lubią się nawzajem.
Narysuj graf, którego macierz sąsiedztwa przedstawiona jest obok. Jakie własności ma relacja, którą przedstawia graf? Jakie cechy grafu zawiązane są z własnościami relacji (takimi jak zwrotność, symetryczność, spójność ...)?
Napisz macierze sąsiedztwa grafów przedstawionych obok. Wypisz elementy relacji określonych przez te grafy. Jakie własności mają relacje określone przez te grafy? Czym różni się graf, macierz sąsiedztwa i relacja w przypadku (a) od grafu, macierzy sąsiedztwa i relacji w przypadku (b)?

Narysuj graf mający 6 wierzchołków i ciąg stopni {3, 3, 5, 5, 5, 5}. Czy istnieje graf prosty mający taki ciąg stopni i 6 wierzchołków?
Wyjaśnij czemu nie są izomorficzne grafy:
Sprawdź, które twierdzenie jest prawdziwe, a które fałszywe:
(a) każde dwa grafy izomorficzne mają ten sam ciąg stopni;
(b) każde dwa grafy mające ten sam ciąg stopni są izomorficzne (zob zadanie poprzednie);
Wyznacz macierz sąsiedztwa i macierz incydencji grafu:
Narysuj grafy mając dane ich macierze sąsiedztwa. Zanim narysujesz określ, na podstawie własności macierzy, czy graf jest prosty czy skierowany.
Narysuj graf, którego macierz incydencji jest:
Wyznacz macierze grafów skierowanych:

na początek

Składanie relacji

R º S oznacza złożenie (superpozycję, iloczyn względny) relacji R i S taki, że:

Udowodnij poniższe twierdzenia:
Warunkiem koniecznym i wystarczającym aby relacja T była przechodnia jest T º TT.
Złożenie (iloczyn względny) identyczności na zbiorze X i identyczności na zbiorze Y jest równe identyczności na iloczynie zbiorów X i Y.
Na przykładzie relacji f = {(2,1), (3,1), (4,1), (5,2), (6,2)} oraz g = {(3,2), (3,3), (3,4), (5,5)} sprawdź, że składanie relacji nie jest przemienne, tzn. f º g ≠ g º f.
Dane są relacje:
f = {(1,1), (1,2), (3,2), (4,1), (4,2), (4,4)} oraz g = {(0,2), (0,3), (1,2), (1,3), (3,2), (4,4)}.
Znajdź: f º g^–1, g º f oraz g¹⁰ (10-krotne złożenie relacji g ze sobą).
na początek

Relacja równoważności
Dla danego zbioru X oraz relacji RX×X zbadaj, czy R jest relacją równoważności. Jeśli jest, wskaż klasy abstrakcji:
X = , xRyx – y = 2;
X = , xRyx²y²;
X = {1, 2, 3}, xRyx + y ≠ 3;
X = {1, 2, ... 16}, xRy4| x² – y²;
X = \ {0}, xRyk| x + y (dla k2 i k);
X = \ {0}, xRyk| x – y (dla k2 i k);
X = \ {0}, xRyx·y jest liczbą nieparzystą;
X = \ {0}, xRyx·y = t² (dla t);
X = , xRyx – y ;
X = P(Y), ARBAB v BA (gdzie Y jest ustalonym zbiorem co najmniej dwuelementowym, P(Y) oznacza zbiór wszystkich podzbiorów Y);
X = P(Y), ARBa(AB) (gdzie a jest ustalonym elementem zbioru Y);
Dane są relacje równoważności R, SX². Zbadaj, czy są relacjami równoważności relacje określone następująco:
RS, RS, X² \ R.
Dany jest podział zbioruna dwa zbiory: zbiór liczb parzystych i nieparzystych. Wskaż relację równoważności, której klasami abstrakcji są te zbiory.
Dany jest podział płaszczyzny × na pięć zbiorów odpowiadających czterem ćwiartkom płaszczyzny i sumie osi wspolrzędnych OxOy. Znajdź relację równoważności, której klasami abstrakcji są te zbiory.
Płaszczyznę × dzielimy na zbiory będące okręgami o środkach w początku układu współrzędnych. Znajdź relację równoważności, której klasami abstrakcji są te zbiory.
na początek

Funkcje jako relacje
Dana jest ustalona liczba rzeczywista x₀> 0 aoznacza zbiór wszystkich liczb rzeczywistych dodatnich. Zbadaj, która z podanych niżej relacji jest funkcją. Naszkicuj wykresy tych relacji.
Zbadaj czy poniższe relacje są funkcjami:
R×, xRyx² = y²;
R⁺×⁺, xRyx² = y²;
R×, xRyx² = y³;
R×, xRyx³ = y²;
Niech X = {1, 2, 3} oraz Y = {2, 3, 4}. Zbadaj, czy następujące relacje są funkcjami f: X—›Y:
{(1,3), (2,4), (3,3)},
{(1,4), (2,5), (3,3)},
{(3,2), (3,4), (2,2)},
{(1,2), (1,4), (4,2)},
{(1,3), (2,4)},
{(1,4), (2,1)}.
Interpretując relację R× jako podzbiór płaszczyzny, podaj sens geometryczny tego iż:
relacja R jest funkcją,
relacja R^–1 jest funkcją,
relacja R jest funkcją różnowartościową.
Które z poniższych odwzorowań płaszczyżny Ouv w płaszczyznę Oxy jest bijekcją (przekształceniem wzajemnie jednoznacznym) jednej płaszczyzny w drugą:
x = u + v, y = u – v;
x = u² – v², y = u² + v²;
x = u + v, y = uv;
x = ½ u (e^v + e^–v), y = ½ u (e^v – e^–v).
Dla każdego z podanych niżej przekształceń f:—› sprawdź czy jest ono:
odwzorowaniem różnowartościowym (injekcją),
odwzorowaniem "na" (surjekcją).
Jeśli nie jest "na" - znajdź zbiór wartości (przeciwdziedzinę),
jeśli nie jest różnowartościowe - wskaż przykładowe x₁ i x₂ takie że: x₁ ≠ x₂ ale f(x₁) = f(x₂).
f(x) = 2^x
f(x) = x³
f(x) = int x (część całkowita liczby)
f(x) = x²
f(x) = x³ – x²
f(x) = sin x
Dane jest przekształcenie f: —› określone wzorem: f(x) = 1 + int x.
Sprawdź czy odwzorowaniwe f jest "na" (jest surjekcją).
Sprawdź czy odwzorowanie f jest różnowartościowe (jest injekcją).
Znajdź f ^–1( {0} ).
Znajdź f (⁺).
Znajdź f ( {, 2, 2} ).
Dane jest przekształcenie f: × —› określone wzorem: f(n,k) = nk.
Sprawdź czy odwzorowaniwe f jest "na" (jest surjekcją).
Sprawdź czy odwzorowanie f jest różnowartościowe (jest injekcją).
Znajdź f (× {2} ).
Znajdź f ^–1( {0} ).
Znajdź f ^–1( Par ), (Par: zbiór liczb parzystych)
Dane jest przekształcenie f: × —› określone wzorem: f(x,y) = |x² – y²|.
Sprawdź czy odwzorowaniwe f jest "na" (jest surjekcją).
Sprawdź czy odwzorowanie f jest różnowartościowe (jest injekcją).
Znajdź f ^–1( {0} ).
Znajdź f ((\ Par) × Par), (Par: zbiór liczb parzystych).
Znajdź f (× {0} ).
na początek

Relacje porządkujące
Relacja R ( \ {0} )² jest określona następująco: xRy ( n nx = y ).
Pokaż, że jest to relacja częściowo porządkująca, znajdź wszystkie elementy minimalne, udowodnij, że w zbiorze ( \ {0}, R) nie ma elementów maksymalnych.
Sprawdź czy zbiory , , są uporządkowane (częściowo, liniowo, dobrze) przez relację (niewiększy).
Zbadaj czy relacja > (większy) może być relacją porządkującą.
Niech X będzie zbiorem, zaś 2^X rodziną wszystkich podzbiorów zbioru X. Udowodnij, że relacja (inkluzji) częściowo porządkuje zbiór 2^X.
Dany jest zbiór (X, R) liniowo uporządkowany. Pokaż, że jeśli X jest skończony to (X, R) jest dobrze uporządkowany.
Dany jest zbiór T = {2, 3, ..., 15} oraz relacja | (podzielności) ograniczoną do elementów zbioru T).
Narysuj diagram relacji i sprawdź czy jest to relacja porządkująca.
Wskaż elementy wyróżnione zbioru (T, |).
Wskaż wszystkie łańcuchy długości 3.
Dany jest zbiór T = {2ⁿ: n} {3} wraz z relacją | (podzielności).
Narysuj diagram relacji i sprawdź czy jest to relacja porządkująca.
Czy w zbiorze (T, |) są elementy minimalne, maksymalne?
Czy w zbiorze (T, |) jest element najmniejszy?
na początek