Wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Matematyka Dyskretna 2021/22 A

Total questions: 28

Worksheet time: 2hrs 20mins

Name
Class
Date
1.

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

Zdanie złożone P implikuje logicznie zdanie złożone Q, jeżeli zdanie Q ma wartość logiczną prawdy zawsze wtedy, gdy

zdanie P ma wartość logiczną prawdy.

b)

Zdanie złożone P implikuje logicznie zdanie złożone Q, jeżeli zdanie Q ma wartość logiczną fałszu zawsze wtedy, gdy zdanie

P ma wartość logiczną fałszu.

c)

Zdanie złożone P implikuje logicznie zdanie złożone Q, jeżeli zdanie Q ma wartość logiczną prawdy zawsze wtedy, gdy

zdanie P ma wartość logiczną fałszu.

d)

Zdanie złożone P implikuje logicznie zdanie złożone Q, jeżeli zdania P i Q mają zawsze różne wartości logiczne dla

wszystkich możliwych sposobów przypisania wartości logicznych ich zmiennym zdaniowym.

2.
a)

e^x jest wykładniczą funkcją tworzącą sekwencji liczb 1, 1, 1/(2!), 1/(3!)....

b)

e^x jest funkcją tworzącą sekwencji liczb 1,1,1....

c)

e^x jest funkcja tworzącą sekwencji liczb 1, 1, 1/(2!), 1/(3!)...

d)

e^x jest wykładniczą funkcją tworzącą sekwnecji liczb 1,1,1,1,1,1...

e)

e^x jest funkcją tworzącą sekwnencji liczb 1,1,1,1,0,0,0,0...

3.

Wybierz wszystkie poprawne:

a)

Zdaniem odwrotnym do zdania p -> q jest zdanie p -> -q

b)

zdaniem przeciwstawnym do zdania p -> q jest zdanie -p -> -q

c)

zdanie złożone jest tautologią, jeżeli jest ono fałszywe niezależnie od wartości logicznych jego zdań składowych

d)

zdaniem odwrotnym do zdania p -> q jest zdanie -p -> -q

e)

zdaniem przeciwstawnym do zdania p->q jest zdanie -q -> p

4.

Wybierz wszystkie poprawne

a)

5 i 10 są liczbami względnie pierwszymi

b)

2 i 3 są liczbami względnie pierwszymi

c)

1 jest najmniejszą liczbą pierwszą

d)

2 jest najmniejszą liczbą pierwsza

e)

0 jest najmniejszą liczbą pierwszą

5.

Miech A, E i © będą podzbiorami pewnej przestrzeni U. Wśród poniższych zdań wskaź prawa

algebry zbiorów.

(n = iloczyn)

(-A = negacja A)

a)

(A n B) u C= (A u C) n (B u C)

b)

A u ( A n B) = -A

c)

A n (A u B) = A

d)

-(A u B) = -A u -B

e)

A u (A n B) = B

6.

Wsród poniższych zdań wskaź reguły podstawiania.

a)

Jeżeli zdanie złożone P zawiera zdanie Q, R jest

zdaniem takim, że Q<=>R jeśli w P zastąpimy

jedno lub więcej wystąpień Q przez R, to

otrzymamy zdanie złożone P1 takie że P<=>P1

b)

Jeżeli zdanie złożone P jest tautologią i wszystkie

wystąpienia pewnej zmiennej p (zdania

składowego) występującej w zdaniu P zastąpimy

zdaniem R, to otrzymane zdanie złożone P1 bedzoe również tautologią

c)

Jeżeli zdanie złożone P zawiera zdanie Q, R jest

zdaniem takim, że R => Q i wfP zastąpimy

dokładnie jedno wystąpienie Q przez R, to

otrzymamy zdanie złożone P1, takie, że P<=>P1

d)

Jeżeli zdanie złożone P zawiera zdanie Q, R jest

zdaniem takim, że Q => R o w P zastąpimy dokładnie jedno wystąpienie Q przez R, to otrzymamy zdanie żlożone P1 takie, że P<=>P1

e)

Jeżeli zdanie złożone P jest zdaniem sprzecznym i

wszystkie wystąpienia pewnej zmiennej p (zdania

składowego) występującej w zdaniu P zastąpimy

zdaniem R, to otrzymane zdanie złożone P1 będzie tautologią

7.
a)

A

b)

B

c)

C

d)

D

e)

E

8.
a)

A

b)

B

c)

C

d)

D

e)

E

9.

wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

jeżeli a,b,c ∈ P to równanie diofantyczne ax+by=c ma rozwiązania całkowite x=x0 y=y0 wtedy i tylko wtedy gdy lcm(a,b) dzieli c

b)

jeżeli a,b,c ∈ P to równanie diofantyczne ax+by=c ma rozwiązania całkowite x=x0 y=y0 wtedy i tylko wtedy gdy a i b są liczbami pierwszymi

c)

jeżeli a,b,c ∈ P to równanie diofantyczne ax+by=c ma rozwiązania całkowite x=x0 y=y0 wtedy i tylko wtedy gdy c dzieli gcd(a,b)

d)

jeżeli a,b,c ∈ P to równanie diofantyczne ax+by=c ma rozwiązania całkowite x=x0 y=y0 wtedy i tylko wtedy gdy gcd(a,b) dzieli c

e)

jeżeli a,b,c ∈ P to równanie diofantyczne ax+by=c ma rozwiązania całkowite x=x0 y=y0 wtedy i tylko wtedy gdy c dzieli lcm(a,b)

10.

Niech A, B i C będą podzbiorami pewnej przestrzeni U. Wśród poniższych zdań wskaż prawa algebry

zbiorów.

(n=iloczyn)

(-A= negacja A)

a)

-(A n B) = -A n -B

b)

(A n B) n C = A u (B n C)

c)

A u (A n B) = A

d)

A n (A u B) = -A

e)

-(A u B) = -A n -B

11.

Niech G=(V, E) będzie dowolnym grafem i niech X,Y ⊂ v. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

Minimalna liczba wierzchołków, które rozdzielają X od Y równa jest liczność zbioru X+

b)

Minimalna liczba wierzchołków, które rozdzielają X od Y równa jest liczności zbioru Y.

c)

Minimalna liczba wierzchołków, które rozdzielają X od Y równa jest min+|X|, |Y|+.

d)

Minimalna liczba wierzchołków, które rozdzielają X od Y równa jest maksymalnej liczbie rozłącznych ścieżek z X do Y.

e)

Minimalna liczba wierzchołków, które rozdzielają X od Y równa jest minimalnej liczbie rozłącznych ścieżek z X do Y.

12.

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

x+2^2 x^2 +3^2 + x^3 + 4^2 x^4 +... jest funkcją tworzącą sekwnecji liczb 1^2, 2^2, 3^2....

b)

1+2^2 x+3^2 x^2+ 4^2 x^3... jest funkcją tworzącą sekwnmecji liczb 1^2, 2^2, 3^2...

c)

1+2^2+x+3^2 x^2+ 4^2 x^3... jest funkcją tworzącą sekwnmecji liczb 0^2, 1^2, 2^2, 3^2...

d)

1+2^2 x+3^2 x^2+ 4^2 x^3... jest wykładniczą funkcją tworzącą sekwnmecji liczb 1^2, 2^2, 3^2...

e)

x+2^2 x^2 +3^2 + x^3 + 4^2 x^4 +... jest funkcją tworzącą sekwnecji liczb 0^2, 1^2, 2^2, 3^2....

13.

Niech H będzie grafem sprzężonym pewnego grafu G. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

w grafie G istnieje droga Eulera wtedy i tylko wtedy, gdy w grafie H istnieje obwód Eulera.

b)

w grafie G istnieje droga Eulera wtedy i tylko wtedy, gdy w grafie H istnieje ścieżka Hamiltona.

c)

w grafie G istnieje cykl Hamiltona wtedy i tylko wtedy, gdy w grafie H istnieje ścieżka Hamiltona.

d)

W grafie G istnieje ścieżka Hamiltona wtedy i tylko wtedy, gdy w grafie H istnieje cykl Hamiltona.

e)

w grafie G istnieje ścieżka Hamiltona wtedy i tylko wtedy, gdy w grafie H istnieje droga Eulera.

14.

Wśród poniższych zdań wskaż wszystkie zdania

prawdziwe.

a)

Liczby całkowite a i b są względnie

pierwsze, jeżeli istnieją liczby całkowite x i

v, takie że ax+by=2.

b)

Liczby całkowite a i b są względnie

pierwsze, jeżeli ged(a, b)=1.

c)

C. Liczby całkowite a i b są względnie

pierwsze, jeżeli gced(a, b)=0.

d)

Liczby całkowite a i b są względnie

pierwsze, jeżeli istnieją liczby całkowite x i

v, takie że ax+by=1.

e)

Liczby całkowite a i b są względnie

pierwsze, jeżeli istnieją liczby całkowite x i

v, takie że ax+by=v2.

15.
a)

a

b)

b

c)

c

d)

d

e)

e

16.

Wybierz wszystkie poprawne:

a)

Relację, która jest jednocześnie relacją przechodnią, symetryczną i spójną w zbiorze X nazywamy relacją liniowo

porządkującą zbiór X.

b)

Relację, która jest jednocześnie relacją przechodnią, symetryczną i przeciwzwrotną w zbiorze X nazywamy relacją liniowo

porządkującą zbiór X.

c)

Relację, która jest jednocześnie relacją zwrotną, antysymetryczną i spójną w zbiorze X nazywamy relacją liniowo

porządkującą zbiór X.

d)

Relację, która jest jednocześnie relacją przechodnią, antysymetryczną, zwrotną i spójną w zbiorze X nazywamy relacją

liniowo porządkującą zbiór X.

e)

Relację, która jest jednocześnie relacją zwrotną, przechodnią i antysymetryczną w zbiorze X nazywamy relacją liniowo

porządkującą zbiór X.

17.

Wybierz wszystkie poprawne:

a)

Graf G = (V,E) jest grafem dwudzielnym, jeżeli występuje w nim parzysta liczba rozłącznych ścieżek Hamiltona.

b)

Graf G = (V,E) jest grafem dwudzielnym, jeżeli V = V1; u V2, V1 ⊂ V2 oraz dla każdej krawędzi {x,y} ∈ E zachodzi

x ∈ V1 i y ∈ V2

c)

Graf G = (V,E) jest grafem dwudzielnym, jeżeli jego zbiór wierzchołków można podzielić na dwa rozłączne podzbiory w

taki sposób, że żadna krawędź występująca w tym grafie nie jest incydentna z dwoma wierzchołkami należącymi do tego

samego podzbioru.

d)

Graf G = (V,E) jest grafem dwudzielnym, jeżeli występuje w nim parzysta liczba rozłącznych cykli.

e)

Graf G = (V,E) jest grafem dwudzielnym, jeżeli

V= V1 u V2, V1 n V2 = Ø oraz dla każdej krawędzi {x,y} ∈E

zachodzi x∈V1 i y∈V2

18.

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

skojarzenie w grafie G=(V,E) jest to największy podgraf pełny tego grafu.

b)

skojarzenie w grafie G=(V,E) jest to jego drzewo rozpinające.

c)

skojarzenie w grafie G=(V,E) jest to ścieżka przechodząca przez wszystkie jego wierzchałki.

d)

skojarzenie w grafie G=(V,E) jest to droga przechodząca przez wszystkie jego krawędzie.

e)

skojarzenie w grafie G=(V,E) jest to zbiór krawędzi, z których żadne dwie nie mają wspólnego wierzchołka końcowego.

19.

Wśród poniższych zdań wskaż wszystkie zdania będące definicjami drzewa.

a)

Graf G=(V,E) jest drzewem, jeżeli posiada korzeń

b)

Graf G=(V,E) jest drzewem, jeżeli nie zaiwera cykli i |V|=|E|-1

c)

Graf G=(V,E) jest drzewem, jeżeli nie zawiera cykli i jeżeli x,y∈V oraz {x,y}∉E to dodanie do G krawędzi {x,y} spowoduje powstanie grafu G` zawierającego dokładnie jeden cykl

d)

Graf G=(V,E) jest drzewem, jeżeli nie zawiera cykli i |V|=|E|+1

e)

Graf G=(V,E) jest drzewem, jeżeli nie jest spójny i |V|=|E|+1

20.
a)

a

b)

b

c)

c

d)

d

e)

e

21.

Niech G = (V, E) będzie grafem nieskierowanym bez wierzchołków izolowanych. Wśród poniższych zdań wskaż zdania prawdziwe.

a)

G zawiera cykl Hamiltona wtedy i tylko wtedy, gdy G jest spójny i każdy wierzchołek G ma nieparzysty stopień.

b)

G zawiera drogę Eulera wtedy i tylko wtedy, gdy G jest spójny i zawiera dokładnie dwa wierzchołki o stopniu nieparzystym.

c)

G zawiera obwód Eulera wtedy i tylko wtedy, gdy G jest spójny i każdy wierzchołek G ma parzysty stopień.

d)

G zawiera drogę Eulera wtedy i tylko wtedy, gdy G jest spójny i zawiera dokładnie dwa wierzchołki o stopniu parzystym.

e)

G zawiera cykl Hamiltona wtedy i tylko wtedy, gdy G jest spójny i każdy wierzchołek G ma parzysty stopień.

22.

Wybierz wszystkie poprawne:

a)

Relację, która jest jednocześnie relacją zwrotną, antysymetryczną i spójną wzbiorze X nazywamy relacją liniowo

porządkującą zbiór X.

b)

Relację, która jest jednocześnie relacją przechodnią, antysymetryczną, zwrotną i spójną w zbiorze X nazywamy relacją

liniowo porządkującą zbiór X.

c)

Relację, która jest jednocześnie relacją przechodnią, symetryczną i przeciwzwrotną w zbiorze X nazywamy relacją liniowo

porządkującą zbiór X.

d)

Relację, która jest jednocześnie relacją zwrotną, przechodnią i antysymetryczną w zbiorze X nazywamy relacją liniowo

porządkującą zbiór X.

e)

Relację, która jest jednocześnie relacją przechodnią, symetryczną i spójną wzbiorze X nazywamy relacją liniowo

porządkującą zbiór x.

23.

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

1+2x+3x^2+4x^3.... jest funkcją tworząca sekwencji liczb 1,2,3,4,....

b)

x+x^2+x^3... jest funckja tworzącą sekwencji liczb 0,1,2,3....

c)

1+2x+3x^2+4x^3.... jest funkcją tworząca sekwencji liczb 0,1,2,3,4,....

d)

1+2x+3x^2+4x^3.... jest wykładniczą funkcją tworząca sekwencji liczb 1,2,3,4,....

e)

x+x^2+x^3... jest funckja tworzącą sekwencji liczb 1,2,3....

24.

wśród ponizszych zdań wskaz wszystkie zdania prawdziwe.

a)

Między dwoma dowolnymi wierzchołkami x i y y nalezącymi do sieci minimalna przepustowość przekroju, który rozdziela x od y równa jest maksymalnej

wartości przepływu z x do y

b)

Między dwórna dowolnymi wierzchołkami x i y należącymi do sieci maksymalna przepustowość przekroju, który rozdziela x od y równa jest minimalnej

wartości przepływu z x do y

c)

Między dwórna dowolnymi wierzchołkami x i y należącymi do sieci minimalnejprzepustowość przekroju, który rozdziela x od y równa jest minimalnej

wartości przepływu z x do y

d)

Między dwórna dowolnymi wierzchołkami x i y należącymi do sieci maksymalna przepustowość przekroju, który rozdziela x od y równa jest maksymalnej

wartości przepływu z x do y

25.

Niech A, B, C będą podzbioramio pewnej przestrzeni U. Wśród poniższych zdań wskaż prawa algebry zbiorów.

a)

(A u B) n C = (A n C) u (B n C)

b)

-(A n B) = -A n -B

c)

-(A u B) = -A u -B

d)

(A n B) u C = (A u C) n (B u C)

26.

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

Jeżeli b1, b2.. bn są wynikiem pewnego turnieju to ich suma nie może być większa od n po 2

b)

Jeżeli b1, b2.. bn są wynikiem pewnego turnieju to ich suma może być mniejsza od n po 2

c)

Jeżeli b1, b2.. bn są wynikiem pewnego turnieju to dla pewnego r takiego że 2<=r<=n można wybrać r sposród tych liczb w tak sposób, że suma wybranych liczb jest mniejsza niż r po 2

d)

Jeżeli b1, b2.. bn są wynikiem pewnego turnieju to dla pewnego r takiego że 2<=r<=n nie można wybrać r sposród tych liczb w tak sposób, że suma wybranych liczb jest mniejsza niż r po 2

e)

Jeżeli b1, b2.. bn są wynikiem pewnego turnieju to ich suma nie może być ani większa ani mniejsza od n po 2

27.

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

W grafie de Bruijna B(d, k) może wystąpić co najwyżej k etykiet o długości d

b)

W grafie de Bruijna B(d, k) może wystąpić co najwyżej d etykiet o długości k

c)

Graf de Bruijna B(d, k) zawiera k^d łuków.

d)

Graf de Bruijna B(d, k) zawiera k^d wierzchołków.

e)

Graf de Bruijna B(d, k) zawiera d^k wierzchołków.

28.

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

a)

Między dwoma dowolnymi wierzchołkami z i y należącymi do sieci minimalna przepustowość przekroju, który rozdziela z od y równa jest out(z).

b)

Między dwoma dowolnymi wierzchołkami z i y należącymi do sieci minimalna przepustowość przekroju, który rozdziela z od y równa jest minimalnej wartości przepływu z z do y.

c)

Między dwoma dowolnymi wierzchołkami z i y należącymi do sieci minimalna przepustowość przekraju, który rozdziela z od y równa jest maksymalnej wartości przepływu z z do y.

d)

Między dwoma dowolnymi wierzchołkami z i y należącymi do sieci maksymalna przepustowość przekroju, który rozdziela z od y równa jest maksymalnej wartości przepływu z « do y.

e)

Między dwoma dowolnymi wierzchołkami z i y należącymi do sieci maksymalna przepustowość przekroju, który rozdziela z od y równa jest minimalnej wartości przepływu z z do y.