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. Znalez
ć 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ń:
o
a) Produkt przechowywać w temperaturze 15 - 25 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 ZADAC
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 x2 > x);
b) Ź("x sin x > 1 + x2);
c) Ź("x tg x < x (" x > 0);
d) "x Ź(1 < x2 < 5);
e) "x Ź(x > 0 (" sin x < x).
3. Podać przykłady, że nie zachodzą następujące implikacje:
a) "x p(x)'" "xq(x) Ò! "x (p(x) '" q(x));
b) "x p(x) (" q(x) Ò! "xp(x) (" "x q(x).
4. Zbadać prawdziwość zdań;
a) "x"y (x - y)2 = x2 - y2 ;
b) "x"y (x - y)2 = x2 - y2;
c) "x"y (x - y)2 = x2 - y2;
d) "x"y (x - y)2 = x2 - y2.
5. Czy można zmienić kolejność kwantyfikatorów w następujących formach:
a) "x"y (x > y '" x2 < y2);
b) "k"a"A (-k < a < k).
6. Podać zaprzeczenia form z zad.5 oraz form:
a) "x"y x2 + (y - 1)2 = 4;
b) "x"y (x3 > y3 (" 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 ZADAC
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 > x2 - 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:
x-y
a) = 0,

x+y
a+3
b) 0,
b-2
c) x2 - 4y2 > 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 ZADAC
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, x2)}
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 R1 = {(x, x3+1)} odpowiedzieć na pytania od a) do f)podane w zad.2.
4. Określić złożenie relacji Rć%R1 oraz R1ć%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 ZADAC
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) R1 = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d), (b, d), (c, d)};
5
c) R2 = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, c), (a, d)};
d) R3 = {(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 R1 na płaszczyżnie R2 = {(x, y) : x " R, y " R}
określona jako
(x, y)R1(x , y ) Ô! x x '" y y 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) : x2 + y2 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? Znalez
ć 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