Matematyka dyskretna

Zadania złożone

Michał Strzelec Z102

6519
ZBIORY

ZADANIE 1.9

Dla każdego z wymienionych niżej zbiorów podaj, ile elementów zawiera zbiór potęgowy danego zbioru:

1. A = { 1,2,3 },

2. B = P({ 1,2}),

3. C = {{1,2}, {3}},

4. D = P (∅).

Odpowiedź:

1. P(A) = {∅, {1}, {2},{3}, {1,2}, {2,3}, {1,3}, {1,2,3}

2. P(B) = P({∅,{1}, {2}, {1,2}) = {∅, {∅}, {{1}}, {{2}}, {{1,2}}, {∅, {{1}}, {∅,{2}}, {∅{1,2}}, {{1}, {2}}, {{2}, {1,2}}, {∅, {1}, {2}}, {∅,{1}, {1,2}}, {∅, {2}, {1,2}}, {{1}, {2}, {1,2}}, {∅, {1}, {2}, {1,2}}

3. P(C) = {∅, {{1,2}}, {{3}}, {{1,2}, {3}}

4. P(D) = P({∅}) = {∅, {∅}}

ZADANIE 1.11

Sprawdź, czy dla dowolnych zbiorów A oraz B zachodzi A ∩ B = A^c ∩ B^c

Odpowiedź: z prawa de Morgana A^c ∩ B^c = (A ∩ B)^c zatem A ∩ B = A^c ∩ B^c ⇔ A ∩ B = ∅

ZADANIE 1.12

Wymień wszystkie elementy podanych zbiorów:

Odpowiedź:

1. P ({ 1,2}) = {∅, {1,2}},

2. P ({1, {2}) = {∅, {1}, {{2}}, {1,{2}}},

3. P ({0, {0,1}}) = {∅, {0}, {{0,1}},{0, {0,1}}},

4. P ({∅}) = {∅, {∅}},

5. P ({∅, {∅}}) = {∅, {∅}, {{∅}}, {∅, {∅}}},

6. P (∅, {∅, {∅}}) = {∅, {∅}, {{∅, {∅}}}, {∅, {∅, {∅}}}}.

ZADANIE 1.13

Sprawdź, czy dla dowolnych zbiorów A i B zachodzi:

1. P (A ∩ B) = P (A) ∩ P (B)

2. P (A ∪ B) = P (A) ∪ P (B)

Odpowiedź:

1. 1^o niech A = {a}, B = {b}

A ∩ B = ∅, P (A ∩ B) = ∅

P (A) = {∅, {a}}, P(B) = {∅, {b}}, P (A) ∩ P (B) = ∅

2^o niech A = {{a},{a, b}}, B = {{a}, {b}}

A ∩ B = {a}, P (A ∩ B) = {∅, {a}}

P (A) = {∅, {a}, {a, b}, {a, a, b}}

P (B) = {∅, {a}, { b}, {a, b}}

P (A) ∩ P (B) = {∅, {a}, {a, b}}

Zatem w 1 przypadku – zachodzi, a w 2 przypadku - nie zachodzi.

1. niech A = {{a}, {a, b}}, B = {{a}, {b}}

A ∪ B = {{a}, {b}, {a, b}}

P (A ∪ B) = {∅, {{a}}, {{b}}, {{a, b}}, {{a}, {a, b}, {{b}, {a, b}}, {{a}, {b}}, {{a}, {b}, {a, b}}}

P (A) = {∅, {a}, {a, b}, {a, {a, b}}}

P (B) = {∅, {a}, {b}, {a, b}}

P (A) ∪ P (B) = {∅, {a}, {b}, {a, b}, {a, {a, b}}}

Zatem zachodzi dla dowolnych A i B

FUNKCJE

ZADANIE 2.1

Która z podanych relacji jest funkcją? Dla każdej funkcji wyznacz jej dziedzinę i przeciwdziedzinę.

1. r = {(1,2),(2,2), (2,4), (4,4), (4,8), (8,4)},

2. r = {(1,2), (2,2), (3,4), (4,8), (8,5)},

3. r = {(3,2}, (2,1), (3,5), (2,8), (3,6)},

4. r = {(x, y) ∈ Q x Q: x = y²},

5. r = {(x, y) ∈ R x R: x⁴ = y³},

6. r = {(x, y) ∈ Z x Z: 2x + y = max ({x,2})},

7. r = {(x, y) ∈ R x R: IyI =2^x},

8. r = {(x, y) ∈ R x R: (2^x + 4)y=2^x },

Odpowiedź:

1. relacja nie funkcją ponieważ jednemu argumentowi przyporządkowuje te same wartości, np.: para (2,2), (2,4); Dom (f) = {1,2,4, 8}, Im (f) = {2,4,8};

2. relacja jest funkcją; Dom (f) = {1,2,3, 4, 8}, Im (f) = {2,4,5, 8};

3. relacja nie funkcją ponieważ jednemu argumentowi przyporządkowuje te same wartości, np.: para (3,2), (3,5); Dom (f) = {2,3}, Im (f) = {1,2,5,6,8};

4. relacja jest funkcją; y = x^1/2 ; Dom (f) = Q⁺, Im (f) = Q⁺;

1. relacja nie funkcją ponieważ jednemu argumentowi przyporządkowuje te same wartości, np.: para (1,1), (-1,1); y = x^4/3 Dom (f) = R⁺, Im (f) = R⁺;

1. relacja jest funkcją; y = max ({x,2}) – 2x; Dom (f) = Z, Im (f) = Z;

x	-1	0	1	2
y	4	2	0	-2

1. relacja jest funkcją; Dom (f) = R, Im (f) = R;

1. relacja jest funkcją, y=2^x / (2^x + 4), Dom (f) = R, Im (f) = R;

ZADANIE 2.7

Udowodnij, że funkcja f: N x N → N taka, że f (n, m ) = 2ⁿ(2m + 1) -1 jest różnowartościowa.

Odpowiedź:

Funkcja jest różnowartościowa gdy f (n₁, m₁ ) ≠ f (n₂, m₂ ). Weźmy dla przykładu pary (1, 1) i (2,2).

f (1,1 ) = 2¹(2∗1 + 1) -1 = 5, f (2,2 ) = 2²(2∗5 + 1) -1 = 19 z tego wynika, że funkcja jest różnowartościowa.

ZADANIE 2.9

Dane jest przekształcenie f: R → R. Zbadaj, czy jest ono odwzorowaniem różnowartościowym i czy jest odwzorowaniem „na”. Wskaż przeciwdziedzinę funkcji f:

x + 3 dla x > 0

f (x) = 0 dla x = 0

x – 1 dla x < 0

Odpowiedź:

Funkcja jest odwzorowaniem różnowartościowym ponieważ dla różnych wartości x przyporządkowuje różne wartości y.

Funkcja jest funkcją „na”, gdyż zbiorem wartości tej funkcji jest R. Im (f) = R.

ZADANIE 2.13

Dane są funkcje f: R → R, f (x) = x + 3^x, g: R → R, g (x) = x³, h: R → R, h (x) = max ({3, x}) – x. Wyznacz:

1. f o f,

2. f o g,

3. g o h,

4. (f o g) o h,

5. f o (g o h).

Odpowiedź:

1. f o f = f ( f(x)) = f ( x + 3^x ) = x + 3^x + 3 ^{x + 3x}

2. f o g = f (g (x)) = f ( x³ ) = x³ + 3 ^x3

3. g o h = g (h (x)) = g (max ({3, x}) – x) = x ^{max ({3, x}) – x}

4. (f o g) o h = h (f o g) = h (x³ + 3 ^x3) = max ({3, x³ + 3 ^x3}) – (x³ + 3 ^x3)

1. z definicji łączności złożenia funkcji wiemy, że f o (g o h) = (f o g) o h, zatem wynik jest ten sam co w punkcie d) tego zadania.

RELACJE

ZADANIE 4.5

Sprawdź, które z własności: zwrotność, przeciwzwrotność, symetryczność, przeciwsymetryczność, antysymetryczność, przechodniość i spójność posiada relacja r określona w zbiorze A.

1. A – zbiór mieszkańców Warszawy, r = {(a,b) ∈ A x A: a jest bratem b},

2. A – zbiór miast leżących w Azji, r = {(a,b) ∈ A x A: a jest miastem położonym wyżej nad poziomem morza niż miasto b},

3. A = {1, 2, 3}, r = {(1, 2), (2, 3), (3, 1)},

4. A = {x, y, z}, r = {(x, x), (y, x), (y, z), (z, z), (z, y)},

5. A = 2^N, r = {(X, Y) ∈ A x A: X ⊆ Y},

6. A = N, r = {(a, b) ∈ A x A: istnieje k ∈ Z takie, że ab = 3k + 1},

7. A = Z, r = {(a, b) ∈ A x A: max {a, b} = 1},

8. A = Z, r = {(a, b) ∈ A x A: nwd (a, b) = 1},

9. A = R \{0}, r = {(a, b) ∈ A x A: a = 3b},

Odpowiedź:

1. relacja jest przeciwzwrotna, symetryczna i przechodnia,

2. relacja jest przeciwzwrotna, przeciwsymetryczna i przechodnia,

3. relacja jest przeciwzwrotna, przeciwsymetryczna, antysymetryczna i spójna,

4. relacja nie określonych własności,

5. relacja jest zwrotna, przeciwsymetryczna, antysymetryczna i przechodnia,

6. relacja jest symetryczna i przechodnia,

7. relacja jest zwrotna i symetryczna,

8. relacja jest symetryczna,

9. relacja jest przeciwzwrotna, przeciwsymetryczna i antysymetryczna.

ZADANIE 4.10

Relacja r określona w zbiorze X jest euklidesowska, gdy dla dowolnych x, y, z ∈ X, jeśli x r y i x r z, to y r z. Sprawdź, która z relacji spełnia ten warunek.

Sprawdź, które z własności: zwrotność, przeciwzwrotność, symetryczność, przeciwsymetryczność, antysymetryczność, przechodniość i spójność posiada relacja r określona w zbiorze A.

1. r ⊆ 2^N x 2^N, dla dowolnych A, B ∈ 2^N , A r B wtedy i tyko wtedy, gdy A ∩ B = ∅,

2. r ⊆ Z³ x Z³, dla dowolnych(x₁, x₂ , x₃ ), (y₁ , y₂ , y₃) ∈ Z³, (x₁, x₂ , x₃ ) r (y₁ , y₂ , y₃) wtedy i tyko wtedy, gdy x₂ = y₂.

Odpowiedź:

1. r = { (A, B) ∈ 2^N x 2^N , A ∩ B = ∅} nie jest euklidesowska, bo np.:

X = {1, 2}, Y = {3, 4}, Z = {4, 5} wtedy X r Y i X r Z ale ¬ (X r Z),

1. r = {(x₁, x₂ , x₃ ), (y₁ , y₂ , y₃) ∈ Z³ x Z³, x₂ = y₂} jest euklidesowska, bo jeśli

x = (x₁, x₂ , x₃ ) to (y₁ , x₂ , y₃) i z = (z₁, x₂ , z₃)

ZADANIE 4.10

Sprawdź, która z relacji r ⊆ X x X spełnia następujący warunek: dla każdego x ∈ X istnieje taki y ∈ X taki, że x r y.

1. r ⊆ R x R, dla dowolnych x, y ∈ R, x r y wtedy i tyko wtedy, gdy x = y, gdzie y oznacza część całkowitą liczby y,

2. r ⊆ Z³ x Z³, dla dowolnych(x₁, x₂ , x₃ ), (y₁ , y₂ , y₃) ∈ Z³, (x₁, x₂ , x₃ ) r (y₁ , y₂ , y₃) wtedy i tyko wtedy, gdy 2^x₂ = y₂.

Odpowiedź:

1. r = {(x, y) ∈R x R, x = y}, sprawdzając, czy dla każdego x istnieje taki y, że x r y przyjmuję za przykład x = 2¹/₂ zatem widać, że relacja nie zachodzi.

2. r = {(x₁, x₂ , x₃ ), (y₁ , y₂ , y₃) ∈ Z³ x Z³, 2^x₂ = y₂} sprawdzając, czy dla każdego (x₁, x₂ , x₃ )∈ Z³ istnieje taki (y₁ , y₂ , y₃) ∈ Z³, że (x₁, x₂ , x₃ ) r (y₁ , y₂ , y₃) przyjmuję za przykład x = (1, -2, 3), wtedy y = 2 ^-2= ¹/₄ ∈Z, zatem widać, że relacja nie zachodzi.

ZADANIE 4.13

Wyznacz relację odwrotną do relacji r. Określ dziedzinę i przeciwdziedzinę relacji odwrotnej.

1. r = {(x, x), (x, y), (y, y), (y, z), (z, y), (z, s)},

2. r = {(a, b)∈R x R : b = max ({a, b})},

3. r = {(a, b) ∈R x {-1, 0, 1} : b = sgn (a)}.

Odpowiedź:

1. r^-1 = {(x, x), (y, x), (y, y), (z, y), (y, z), (s, z)}, D = {s, x, y, z}, D_p = {x, y, z};

2. r^-1 = {(b, a)∈R x R : b = max ({b, a})}, D = R, D_p = R;

3. r^-1 = {( b, a)∈R x {-1, 0, 1} : b = sgn (a)}, D = {-1, 0, 1}, D_p = R.

RACHUNEK ZDAŃ

ZADANIE 7.2

Niech p, q, r i s będą następującymi zdaniami: p = ”x>0” , q =”y>0”, r = ”wyniki są wyświetlane na ekranie”, s = ”program wykonuje instrukcję x:=x+1”.

Zapisz każde z poniższych zdań w postaci formuły klasycznego rachunku zadań.

1. Jeśli x nie jest dodatnie, to program wykonuje instrukcję x:=x+1,

2. Wyniki są wyświetlane na ekranie wtedy i tylko wtedy gdy x jest dodatnie,

3. Jeśli obie zmienne x i y są dodatnie, to wyniki są wyświetlane na ekranie,

4. Program wykonuje instrukcję x=x+1 dopóty dopóki x jest dodatnie,

5. Warunkiem koniecznym na to, by program wyświetlił wyniki jest, by zmienne x i y miały wartości dodatnie.

Odpowiedź:

1. ¬ p ⇒ s

2. p ⇔ r

3. (p∧q) ⇒ r

4. p ⇒ s

5. (p∧q) ⇒ r

ZADANIE 7.4

Wskaż takie wartości zmiennych n i m, by otrzymane zdania były fałszywe.

1. Jeśli m, n są niezerowymi liczbami całkowitymi takimi, że m²=n2, to m=n,

2. Jeśli n jest liczbą naturalną, to n²<2ⁿ.

Odpowiedź:

1. Fałsz dla przykładowych m=1 i n= -1,

2. Fałsz dla przykładowych n=3, 3²<2³.

ZADANIE 7.6

Zaproponuj zdanie złożone, które:

1. Jest prawdziwe wtedy i tylko wtedy, gdy dokładnie jedna z trzech zmiennych zdaniowych
   p, q, r jest prawdziwa,

2. Jest prawdziwe wtedy i tylko wtedy gdy dokładnie dwie z trzech zmiennych zdaniowych
   p, q, r są prawdziwe.

Odpowiedź:

1. ¬(p∨q)∧r jest prawdziwe ⇒ gdy r jest prawdziwe,

2. p∧q∧r¬(p∧r)∧¬(q∧r) jest prawdziwe gdy p, q – prawdziwe oraz r – fałszywe.

ZADANIE 7.21

Które z podanych rozumowań jest poprawne?

1. Przesłanki: 1. Jeżeli student nie uczył się pilnie, to nie zda egzaminu. 2. Student nie zdał egzaminu.

Wniosek: Student nie uczył się pilnie.

1. Przesłanki: 1. Jeżeli student nie uczył się pilnie, to nie zda egzaminu. 2. Student zdał egzamin.

Wniosek: Student nie uczył się pilnie.

1. Przesłanki: 1. Jeżeli student nie uczył się pilnie, to zda egzamin. 2. Student nie uczył się pilnie..

Wniosek: Student nie zda egzaminu.

1. Przesłanki: 1. Jeżeli student uczył się pilnie, to zda egzamin. 2. Student uczył się pilnie.

Wniosek: Student zda egzamin.

1. Przesłanki: 1. Jeżeli student uczył się pilnie, to zda egzamin. 2. Student nie zdał egzaminu.

Wniosek: Student nie uczył się pilnie.

Odpowiedź:

Poprawne rozumowanie jest wtedy i tylko wtedy gdy jego schemat jest tautologią.

Niech p – „student uczył się pilnie”, q – „student zda egzamin”.

Tautologiami są schematy:

1. [(¬p→¬q)∧¬q]→¬p

2. [(¬p→¬q)∧q]→p

d) [(p→q)∧q]→q

Poprawne rozumowania to a, b, d.

RACHUNEK PREDYKANTÓW

ZADANIE 8.1

W podanych formułach wskaż, które wystąpienia zmiennych są wolne, a które związane:

1. (∃x)(∃y)((x=z)=>(∀z)(xy=z)) ∧ ¬ (∀z)((x+y=z))=> (∀z)(x<z)),

2. ((_­­∀x)(∃y)(x>y ⇔ (x²>y²)) ∨ ((_­­∃z)(x+y<z)=>(∀y)( x²>y²)).

Odpowiedź:

1. dla wyrażenia α = ( _­­∃x)(∃y)((x=z)=>(∀z)(xy=z)) zmienne x, y, z są związane

dla wyrażenia β = (∀z)((x+y=z))=> (∀z)(x<z))zmienne x, z są związane, zmienna y jest wolna

1. dla wyrażenia α = ((_­­∀x)(∃y)(x>y ⇔ (x²>y²)) zmienne x, y są związane

dla wyrażenia β = ((_­­∃z)(x+y<z)=>(∀y)( x²>y²))zmienne y, z są związane, zmienna x jest wolna

ZADANIE 8.3

Podaj przykład formuły rachunku predykatów, która:

1. Jest prawdziwa w strukturze liczb naturalnych i nie jest prawdziwa w strukturze liczb rzeczywistych,

2. Jest prawdziwa w strukturze liczb rzeczywistych i nie jest prawdziwa w strukturze liczb naturalnych.

Odpowiedź:

1. (_­­∀a)(∀b)(1+a+b>0) – jest prawdziwa w strukturze liczb naturalnych i nie jest prawdziwa w strukturze liczb rzeczywistych ponieważ wystarczy podstawić dowolna liczbę rzeczywistą mniejszą od 0 i nierówność nie będzie spełniona,

2. (_­­∃a)(∀b)(2a=b) – jest prawdziwa w strukturze liczb rzeczywistych i nie jest prawdziwa w strukturze liczb naturalnych ponieważ, np. dla b=1 nie istnieje a spełniające dane równanie.

ZADANIE 8.4

Zbadaj prawdziwość podanych formuł rachunku kwantyfikatorów w strukturze liczb całkowitych i naturalnych:

Odpowiedź:

1. (_­­∃x)(∀y)(x≤y)

dla liczb naturalnych – prawda, ponieważ skoro podstawiając najmniejsze naturalne x i y =0 nierówność jest spełniona, to jest ona również spełniona dla wyższych liczb;

dla liczb całkowitych – prawda, ponieważ zawsze można znaleźć x takie aby nierówność jest spełniona;

1. (∀x)(∀y)(∃z)(x+y=z)

dla liczb naturalnych – prawda, ponieważ zawsze można znaleźć liczbę naturalną będącą wynikiem sumy dwóch liczb naturalnych;

dla liczb całkowitych – prawda, ponieważ zawsze można znaleźć liczbę całkowitą będącą wynikiem sumy dwóch liczb całkowitych;

1. (∀x)(∀y)(x²=y² => x=y)

dla liczb naturalnych i całkowitych – prawda, ponieważ, gdy kwadraty liczb są równe to znaczy, że te liczby też są równe;

1. (∀x)(∃y)(x²>y² => x>y)

dla liczb naturalnych i całkowitych – prawda, ponieważ zawsze można znaleźć taki y aby kwadraty liczb spełniały nierówność a to znaczy, że te liczby też spełniają nierówność;

1. (∀m) (_­­∃n)(2m=n)

dla liczb naturalnych i całkowitych – prawda, ponieważ zawsze można znaleźć takie n aby m i n spełniały równanie;

1. (∀n) (_­­∃k)(2ⁿ=k)

dla liczb naturalnych – prawda, ponieważ zawsze można znaleźć liczbę naturalną będącą wynikiem potęgowania liczby 2;

dla liczb całkowitych – fałsz, np.: dla 2^-2= ¼, a ¼ nie należy do liczb całkowitych .

ZADANIE 8.5

Wyznacz wartości logiczne poniższych zdań:

1. (∃r∈R)(∀n∈N)(r>n ⇒ r<n)

2. (∃k∈Z)(∃s∈R)(k+2s = -1) ∧ (2k-s=-14)

3. (∀n)(∃k)((n∈N ∧ k∈N) ⇒ (n=2^k)

Odpowiedź:

1. (∃r∈R)(∀n∈N)(r>n ⇒ r<n) – fałsz

np.: dla r=1 i n=0 prawda, że 1>0, ale nieprawda, że 1<0;

1. (∃k∈Z)(∃s∈R)(k+2s = -1) ∧ (2k-s=-14)

należy przeprowadzić dyskusję dla przypadków:

1. gdy lewa strona koniunkcji jest prawdą - dla k=1 i s=-1 jest spełnione k+2s = -1, to prawa strona jest fałszem, ponieważ 2+1≠-14;

2. gdy prawa strona koniunkcji jest prawdą - dla k=-8 i s=-2 jest spełnione 2k-s=-14 to lewa strona jest fałszem, ponieważ -8-4≠-1;

3. dla pozostałych n nie istnieje k aby obie strony koniunkcji były prawdą;

Biorąc pod uwagę, że zgodnie z algebrą Boole’a koniunkcja jest prawdą tylko wtedy, gdy oba zdania są prawdą, stwierdzam, że zdanie jest fałszywe;

1. (∀n)(∃k)((n∈N ∧ k∈N) ⇒ (n=2^k)) – fałsz, np.: dla n=3 nie istnieje k spełniające równanie 3=2^k .