Zadania złożone wszystkie działy

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 = Ac ∩ Bc

Odpowiedź: z prawa de Morgana Ac ∩ Bc = (A ∩ B)c zatem A ∩ B = Ac ∩ Bc ⇔ 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. 1o niech A = {a}, B = {b}

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

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

2o 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 = y2},

  5. r = {(x, y) ∈ R x R: x4 = y3},

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

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

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

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 = x1/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 = x4/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=2x / (2x + 4), Dom (f) = R, Im (f) = R;


ZADANIE 2.7

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

Odpowiedź:

Funkcja jest różnowartościowa gdy f (n1, m1 ) ≠ f (n2, m2 ). Weźmy dla przykładu pary (1, 1) i (2,2).

f (1,1 ) = 21(2∗1 + 1) -1 = 5, f (2,2 ) = 22(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 + 3x, g: R → R, g (x) = x3, 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 + 3x ) = x + 3x + 3 x + 3x

  2. f o g = f (g (x)) = f ( x3 ) = x3 + 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 (x3 + 3 x3) = max ({3, x3 + 3 x3}) – (x3 + 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 = 2N, 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 ⊆ 2N x 2N, dla dowolnych A, B ∈ 2N , A r B wtedy i tyko wtedy, gdy A ∩ B = ∅,

  2. r ⊆ Z3 x Z3, dla dowolnych(x1, x2 , x3 ), (y1 , y2 , y3) ∈ Z3, (x1, x2 , x3 ) r (y1 , y2 , y3) wtedy i tyko wtedy, gdy x2 = y2.

Odpowiedź:

  1. r = { (A, B) ∈ 2N x 2N , 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 = {(x1, x2 , x3 ), (y1 , y2 , y3) ∈ Z3 x Z3, x2 = y2} jest euklidesowska, bo jeśli

x = (x1, x2 , x3 ) to (y1 , x2 , y3) i z = (z1, x2 , z3)


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 ⊆ Z3 x Z3, dla dowolnych(x1, x2 , x3 ), (y1 , y2 , y3) ∈ Z3, (x1, x2 , x3 ) r (y1 , y2 , y3) wtedy i tyko wtedy, gdy 2x2 = y2.

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 = 21/2 zatem widać, że relacja nie zachodzi.

  2. r = {(x1, x2 , x3 ), (y1 , y2 , y3) ∈ Z3 x Z3, 2x2 = y2} sprawdzając, czy dla każdego (x1, x2 , x3 )∈ Z3 istnieje taki (y1 , y2 , y3) ∈ Z3, że (x1, x2 , x3 ) r (y1 , y2 , y3) przyjmuję za przykład x = (1, -2, 3), wtedy y = 2 -2= 1/4 ∈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}, Dp = {x, y, z};

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

  3. r-1 = {( b, a)∈R x {-1, 0, 1} : b = sgn (a)}, D = {-1, 0, 1}, Dp = 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 m2=n2, to m=n,

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

Odpowiedź:

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

  2. Fałsz dla przykładowych n=3, 32<23.

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 ⇔ (x2>y2)) ∨ ((­­∃z)(x+y<z)=>(∀y)( x2>y2)).

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 ⇔ (x2>y2)) zmienne x, y są związane

dla wyrażenia β = ((­­∃z)(x+y<z)=>(∀y)( x2>y2))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)(x2=y2 => 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)(x2>y2 => 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)(2n=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=2k)

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=2k)) – fałsz, np.: dla n=3 nie istnieje k spełniające równanie 3=2k .


Wyszukiwarka

Podobne podstrony:
Zadania złozone wszystkie działy
Bildergeschichte Zadania na wszystkie sprawności językowe
zadania.tematyczne(wszystkie)
Analka - Od Mazura - wszystkie działy, Chemia, Chemia analityczna
Bildergeschichte Zadania na wszystkie sprawności językowe 2
zadania złożone
Przedmiot dzialy i zadania kryminologii oraz metody badan kr
Podejście hodowe zadania, gik, semestr 7, wybrane działy wyceny
Biochemia wszystkie zadania
złożoność algorytmów zadanie
Zadanie - metoda korygowania ceny średniej, gik, semestr 7, wybrane działy wyceny
wszystkie zadania z makroekonomii, Turystyka i Rekreacja UEK, I rok, makroekonomia
MatLab 2 lista z zadaniami na koło, To co się udało zobaczyć, choć nie wiem czy dobrze wszystko zano
ZADANIE 81, ☆☆♠ Nauka dla Wszystkich Prawdziwych ∑ ξ ζ ω ∏ √¼½¾haslo nauka, Podstawy konstrukcji mas
Złożoność obliczeniowa Zadania 2
Modele cyfrowe gałęzi złożonych 2 zadania
Pochodne funkcji zlozonych Za Rozwiazanie zadania domowego id
zadanie - metoda porównywania parami, gik, semestr 7, wybrane działy wyceny

więcej podobnych podstron