MATEMATYKA DYSKRETNA 1,studia dzienne, lista zadań 1

1. Określić wartość logiczną zdań złożonych:

a) Liczba 4 jest dodatnia lub liczba 4 jest ujemna.
b) Liczba 4 jest dodatnia i liczba 4 jest ujemna.
c) Jeśli 4 jest podzielne przez 2 to 8 jest podzielne przez 2.
d) Jeśli 4 jest podzielne przez 3 to 6 jest podzielne przez 3.
e) Jeśli 6 jest podzielne przez 3 to 4 jest podzielne przez 3.

2. Niech waluacja zdań p, q, r, t będzie następująca: 1,0,0,1. Znaleźć wartość

logiczną każdego z następujących zdań:
a) (p ∨ q) ∨ r;

b) q ⇒ (p ∧ r);

c) q ⇒ (p ⇒ r);

d) p ∨ q ⇔ q ∧ ¬t;

e) (p ⇔ t) ⇒ (¬p ⇔ t);

f) (q ∧ ¬t) ⇒ (p ⇔ t);

h) (p ∨ ¬q) ∨ r ⇒ (t ∧ ¬t).

3. Wiadomo, że zdanie (p ⇒ q) jest fałszywe. Podaj wartość logiczną

zdań:
a) p ∧ q,

b) p ∧ (¬q)

c) p ∨ q,

d) q ⇒ p.

4. Wiadomo, że zdanie (p ∧ q) ⇒ r jest fałszywe. Podaj wartość logiczną

zdań:
a) (p ∨ q) ⇒ r,

b)(p ⇒ q) ⇒ r,

c) (p ∧ r) ⇒ q,

d)p ⇒ (q ∨ r).

5. Podaj zaprzeczenia zdań:

a) Produkt przechowywać w temperaturze 15 - 25

o

C.

b) Bezpłatny przejazd przysługuje osobom powyżej 75 roku życia i mieszkańcom
Polkowic.
c) Obniżka o 10 % przysługuje na wydawnistwa PWN lub WNT.
d) Na bagaż, którego przynajmniej jeden wymiar przekracza 50 cm należy
wykupić bilet bagażowy.

6. Niech zdanie p oznacza " jestem w swetrze", q - "jestem w dżinsach,"

r - "jestem w adidasach" . Przeczytać następujące zdania oraz ich zaprzeczenia
(wykorzystać prawa de Morgana):
a) p ∨ q;

b) p ∨ q ∨ (¬r);

c) p ∧ q;

d) (¬p) ∧ q ∧ r;

1

7. Dla następujących zdań sprawdzić: czy informacja, że zdanie p ma

wartość logiczną 0 wystarczy do wyznaczenia wartości logicznej podanych
zdań złożonych. Jeśli tak, to wyliczyć tę wartość; jeśli nie to pokazać,że obie
wartości są możliwe:
a) (p ⇒ q) ⇒ r;

b) p ∧ (q ⇒ r);

c) ¬(p ∨ q) ⇔ ¬p ∧ ¬q;

d) (p ∧ q) ⇒ (p ∨ r)

e) (p ∧ ¬p) ⇒ q;

f) p ⇒ (q ⇒ p).

8. Uzasadnić następujące prawa logiczne:

a) [p ∧ (q ∨ r)] ⇔ [(p ∧ q) ∨ (p ∧ r)]

(rozdzielność koniunkcji względem

alternatywy);
b) [p ∨ (q ∧ r)] ⇔ [(p ∨ q) ∧ (p ∨ r)]; (jak nazywa się to prawo?)
c) [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r);(przechodniość);
d) (p ⇒ q) ⇔ [(¬q) ⇒ (¬p)] (prawo kontrapozycji);
e) [p ∧ (p ⇒ q)] ⇒ q; (reguła odrywania)
f) (p ⇒ q) ⇔ (¬p ∨ q) ⇔ [¬(p ∧ ¬q)].
g) [(p ∧ q) ⇒ r] ⇔ [p ⇒ (q ⇒ r)]
h) [(p ⇒ q) ∧ (q ⇒ r)] ⇒ [p ⇒ (q ∧ r))].
i) ((¬p) ⇒ p) ⇒ p.

9. Niech P (x) oznacza " x jest politykiem", a Q(x) oznacza - "x jest

muzykalny".
Zapisać z wykorzystaniem kwantyfikatorów i rachunku zdań następujące zdania:
a) Niektórzy politycy są muzykalni.
b) Niektórzy politycy nie są muzykalni.
c) Wszyscy politycy są muzykalni.
d) Żaden polityk nie jest muzykalny.
e) Tylko politycy są muzykalni.
f) Nie tylko politycy są muzykalni.

10. Wykorzystując kreskę Scheffera (p|q ⇔ ¬(p ∧ q)) zapisać następujące

operacje: ¬p, p ∨ q, p ∧ q, p ⇒ q.

LISTA ZADAŃ 2

1. Zapisać z wykorzystaniem kwantyfikatorów i symboli oraz podać zaprzeczenia:

a) Są liczby naturalne podzielne przez 5 i podzielne przez 4.
b) Potęga stopnia parzystego dowolnej liczby rzeczywistej jest liczbą nieujemną.

2. Korzystając z praw de Morgana dla kwantyfikatorów przekształcić

wyrażenia::

2

a) ¬(∀

x

x

2

> x);

b) ¬(∃

x

sin x > 1 + x

2

);

c) ¬(∃

x

tg x < x ∨ x > 0);

d) ∀

x

¬(1 < x

2

< 5);

e) ∃

x

¬(x > 0 ∨ sin x < x).

3. Podać przykłady, że nie zachodzą następujące implikacje:

a) ∃

x

p(x)∧ ∃

x

q(x) ⇒ ∃

x

(p(x) ∧ q(x));

b) ∀

x

p(x) ∨ q(x) ⇒ ∀

x

p(x) ∨ ∀

x

q(x).

4. Zbadać prawdziwość zdań;

a) ∀

x

∀

y

(x − y)

2

= x

2

− y

2

;

b) ∃

x

∀

y

(x − y)

2

= x

2

− y

2

;

c) ∀

x

∃

y

(x − y)

2

= x

2

− y

2

;

d) ∃

x

∃

y

(x − y)

2

= x

2

− y

2

.

5. Czy można zmienić kolejność kwantyfikatorów w następujących formach:

a) ∀

x

∃

y

(x > y ∧ x

2

< y

2

);

b) ∃

k

∀

a∈A

(−k < a < k).

6. Podać zaprzeczenia form z zad.5 oraz form:

a) ∃

x

∃

y

x

2

+ (y − 1)

2

= 4;

b) ∀

x

∀

y

(x

3

> y

3

∨ y > x).

7. W następującym twierdzeniu: " Jeśli liczba nauralna jest podzielna

przez 15 to jest podzielna przez 5" :
a) podać warunek wystarczajacy podzielności przez 5;
b) podać warunek konieczny podzielności przez 15;?
c) czy prawdziwe jest twierdzenie odwrotne?

8. Odpowiedzieć na pytania jak w zad.13 dla twiedzenia "Jeśli wielomian

stopnia drugiego ma dwa różne pierwiastki to jego wyróżnik jest dodatni."

9. Przeprowadzić dowody twierdzeń i wskazać metodę dowodzenia:

a) Jeśli liczba naturalna jest podzielna przez 12 to jest podzielna przez 3.
b) Jeśli kwadrat liczby naturalnej jest liczbą parzystą to liczba ta jest parzysta.

LISTA ZADAŃ 3

1. Wyznaczyć dopełnienie, sumę, iloczyn, różnicę, różnicę symetryczną

zbiorów A oraz B jeśli:

3

a) A = [0, 3],

B = (1, 4),

b) A = (1, 3],

B = (−∞, 5)

c) A = {n ∈ N : 3|n}, B = {n ∈ N : 2|n},
d) A = {(x, y) : x + y < 0}, B = {(x, y) : y > x

2

− 1}.

2. Pokazać, korzystając z diagramów Vienna, że zachodzą następujące

własności:
a) A ∪ (B ∪ C) = (A ∪ B) ∪ C,
b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
c) (A − B) − C = A − (B ∪ C),

3. Udowodnij lub pokaż kontrprzykład:

a) A ∪ B = A ∩ B,
b)

A ∩ B = A ∩ B.

4. Wyznaczyć zbiory rozwiązań i przedstawić w układzie współrzędnych:

a)

x−y
x+y

6= 0,

b)

a+3

b−2

¬ 0,

c) x

2

− 4y

2

> 0.

5. Przeanalizuj poniższe zdania. Wskaż te, które są prawdziwe. Podaj

kontrprzykład dla fałszywych.
a) A ∩ B = A ∩ C implikuje B = C,
b) A ∪ B = A ∪ C implikuje B = C,
c) (A ∪ B) ⊂ A ∩ B implikuje A = B.

6. Uzasadnić, że

a) (A × B) ∪ (A × C) = A × (B ∪ C),
b) (A × B) ∩ (A × C) = A × (B ∩ C)

7. Za pomocą operacji sumy, iloczynu, różnicy, dopełnienia na zbiorach

A = {1, 2, 6, 7, 8}, B = {2, 3, 4, 7, 8},
C = {4, 5, 6, 7, 8} wyznaczyć zbiór D = {4}.

LISTA ZADAŃ 4

1.Niech {X = a, b, c, d}, Y = {1, 2, 3, 4, 5, }, dla relacji R = {(a, 1), (b, 2), (b, 5), (c, 4), (d, 3)};

a) określić obrazy zbiorów A = {b, c}, B = {c, d}, A ∪ B, A ∩ B;

4

b) określic przeciwobrazy zbiorów W = {2, 5} , Z = {1, 3, 5} , W ∪ Z,
W ∩ Z;
c) określić relację odwrotną R

−1

;

d) czy relacja R jest "na"
e) czy relacja R jest funkcją?

2. Niech X = Y = R, gdzie R oznacza zbiór liczb rzeczywistych, dla

relacji R = {(x, x

2

)}

a) określić obrazy zbiorów A = (−∞, −2), B = (−4, −1) ∪ (1, 2], A ∪ B,
A ∩ B;
b) określić przeciwobrazy zbiorów W = [1, 4] , Z = (0, 1) , U = (9, ∞),
W ∪ Z, W ∩ Z;
c) określić relację odwrotną R

−1

;

d) czy relacja R jest "na"
e) czy relacja R jest funkcją?
f) czy relacja R

−1

jest funkcją?

3. Niech X = Y = R, gdzie R oznacza zbiór liczb rzeczywistych, dla

relacji R

1

= {(x, x

3

+1)} odpowiedzieć na pytania od a) do f)podane w zad.2.

4. Określić złożenie relacji R◦R

1

oraz R

1

◦R. Czy złożenia te są funkcjami?

5. Dla każdej z podanych poniżej relacji sprawdzić czy jest zwrotna,

symetryczna, przechodnia, słabo antysymetryczna, spójna:
a) X = {1, 3, 6}, R = {(1, 1), (1, 3), (1, 6), (3, 3), (3, 1), (3, 6), (6, 1), (6, 3), (6, 6)};
b) X = {1, 3, 6},

R = {(1, 1), (1, 3), (1, 6), (3, 6), (6, 3), (6, 6)};

c) X = R, xRy ⇔ x ¬ y;
d) X = Z, gdzie Z jest zbiorem liczb całkowitych, xRx ⇔ x−y jest podzielne
przez 5;
e) X jest zbiorem prostych, xRy ⇔ x jest równoległa do y;
f) X jest zbiorem prostych, xRy ⇔ x jest prostopadła do y;
g) X jest zbiorem wszystkich podzbiorów pewnego zbioru Ω ARB ⇔ A ⊂ B.

6. Wskazać, która z relacji opisanych w przykładach od a) do g) w zad.5

jest relacją równoważności. Określić klasy abstrakcji w tych relacjach.

LISTA ZADAŃ 5

1. Sprawdzić,która z relacji jest częściowym porządkiem w zbiorze X =
{a, b, c, d}
a) R = {(a, a), (b, b), (c, c), (d, d), (a, c), (b, c), (c, d), (a, d)};
b) R

1

= {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d), (b, d), (c, d)};

5

c) R

2

= {(a, a), (b, b), (c, c), (d, d), (a, b), (b, c), (a, d)};

d) R

3

= {(a, a), (b, b), (c, c), (a, d), (b, d), (c, d)}.

Narysować diagramy Hassego dla relacji, które są częściowym porządkiem.

2. Narysuj diagramy Hassego następujących zbiorów cześciowo uporządkowanych:

a) X = {1, 2, 3, 4, 6, 8, 12, 24} , z relacją | , gdzie m |n oznacza,że m jest
dzielnikiem n.
b) Zbiór wszystkich podzbiorów zbioru {2, 4, 7} z relacją ⊆ jako częściowym
porządkiem.

3. Podać, jeśli są, w zbiorach opisanych w zad.1 oraz zad.2 elementy

minimalne, maksymalne, element największy, element najmniejszy.

4. Podaj przykład zbioru częściowo uporządkowanego z życia codziennego

lub innych wykładów.
Czy w podanym zbiorze są elementy minimalne , maksymalne, najmniejsze,
największe? Jeśli tak to jakie?
Jakie są relacje odwrotne do częściowych porządków z Twojego przykładu?

5. Sprawdzić, że relacja R

1

na płaszczyżnie R

2

= {(x, y) : x ∈ R, y ∈ R}

określona jako
(x, y)R

1

(x

0

, y

0

) ⇔ x ¬ x

0

∧ y ¬ y

0

jest częściowym porządkiem. Określić

elementy minimalne, maksymalne, element największy, najmniejszy względem
tego częściowego porządku w zbiorach:
a) A = {(x, y) : x

2

+ y

2

¬ 1};

b

∗

) B={(x,y):|x| + |y| ¬ 1};

c

∗

) C={(x,y):max{|x| , |y|} ¬ 1}.

6. Czy częściowe porządki opisane w przykładach zad.1 oraz zad.2 są

porządkami liniowymi? Znaleźć wszystkie maksymalne łańcuchy w przykładach
zad.1 oraz zad.2.

7. Uporządkować leksykograficznie zbiór wszystkich 4 literowych słów

zbudowanych
z liter a , c.

8. Uporządkować leksykograficznie elementy zbioru X, gdzie X = {a, b, c},

Y = {1, 2}.

6