1
MATEMATYKA DYSKRETNA -Elektronika
Lista 1- Rachunek zdań
1. Sprawdz
za pomocą metody zerojedynkowej, czy poniższe pary wyrażeń są równo-
ważne:
a) p =Ò! q oraz <" p (" q; b) <" (p '" q) oraz p =Ò! q; c) p =Ò! (p =Ò! q) oraz p =Ò! q.
2. Wykaż, że ponizsze formuły rachunku zdań są tautologiami:
a) p =Ò! (<" p =Ò! q); b) [<" p'"(p("q)] =Ò! q; c) [p =Ò! (q'"r)] =Ò! [(<" q(" <" r) =Ò!<" p];
d) [(p (" q) =Ò! r)] =Ò! [(<" p =Ò! (q =Ò! r)];
3. Które z podanych implikacji są prawdziwe dla dowolnej liczby n?
a) Jeżeli n jest liczbą parzystą, to n + 1 jest liczbą nieparzystą.
b) Jeżeli n jest liczbą pierwszą, to n + 1 jest liczbą złożoną.
c) Jeżeli n dzieli się przez 3, to suma cyfr liczby 3n dzieli się przez 9.
d) Jeżeli n nie dzieli się przez 10, to n jest liczbą nieparzystą lub nie dzieli się przez 5.
4. WiedzÄ…c, że implikacja (<" p) =Ò! q jest faÅ‚szywa, okreÅ›l wartość logicznÄ…: a) ko-
niunkcji zdaÅ„ p oraz q; b) alternatywy zdaÅ„ p oraz q; c) implikacji q =Ò! p.
5. Które z poniższych formuÅ‚ sÄ… równoważne formule p =Ò! q:
a) q =Ò! p; b) <" q =Ò!<" p; c) <" p (" q; d) <" (p'" <" q); e) <" q (" p?
6. Przyjmijmy, że gdy Jacek chrapie, to Agatka śni. Które z poniższych zdań są praw-
dziwe przy tym założeniu?
a) Gdy Agatka nie śni, to Jacek nie chrapie.
b) Gdy Jacek nie chrapie, to Agatka nie śni.
c) Nie jest możliwe, aby Jacek chrapał, a Agatka nie śniła.
d) Gdy Agatka śni, to Jacek chrapie.
e) Jacek nie chrapie lub Agatka śni.
7. George Bernard Shaw twierdził, że przekłady są jak kochanki  wierne nie są pięk-
ne, piękne nie są wierne. Które z poniższych zdań są równoważnym sformułowaniem
poglądu, że przekład nie może być zarazem wierny i piękny.
a) Jeżeli przekład jest wierny, to nie jest piękny.
b) Jeżeli przekład jest piękny, to nie jest wierny.
c) Jeżeli przekład nie jest wierny, to jest piękny.
d) Jeżeli przekład nie jest piękny, to jest wierny.
8. Każda karta z jednej strony jest czerwona albo niebieska, z drugiej zaś ma narysowane
kółko albo trójkąt. Na stole widzimy cztery takie karty, widoczna strona jest w nich
kolejno czerwona, niebieska, trójkątem i kółkiem. Jacek twierdzi, że karty niebieskie
mają na odwrocie kółko. Które karty Placek musi odwrócić, aby sprawdzić, czy Jacek
mówi prawdę?
9. Zbadaj, czy poniższe schematy wnioskowania są poprawne:
(<" p) (" q, p (p '" q) =Ò! r, <" q p =Ò! (q (" r), <" r
a) b) c)
q p =Ò! r p =Ò! q
10. Uzasadnij fałszywość poniższych zdań, podając odpowiednie kontrprzykłady.
a) Jeżeli p jest liczbą pierwszą, to 2p + 1 też jest liczbą pierwszą.
b) Suma dwu liczb złożonych nie jest liczbą pierwszą.
c) Jeżeli liczba n jest dodatnia, parzysta, to liczba n2 + 1 jest pierwsza.
d) Jeżeli n jest liczbą naturalną, to liczba n2 + n + 1 jest pierwsza.
2
11. Które z poniższych hipotez można obalić, podając liczbę 7 jako kontrprzykład?
a) Każda liczba pierwsza jest dwucyfrowa.
b) Żadna liczba pierwsza nie jest jednocyfrowa.
c) Wszystkie liczby pierwsze sÄ… nieparzyste.
d) Niektóre liczby pierwsze są nieparzyste.
12. W brydżu 52 karty rozdaje się pomiędzy czterech graczy, po 13 kart. Pośród po-
niższych zdań wskaż zawsze prawdziwe, zawsze fałszywe i takie, których prawdziwość
zależy od konkretnego rozdania.
a) Przynajmniej jeden z graczy dostał damę pik.
b) Nie każdy z graczy ma asa.
c) Któryś z graczy ma przynajmniej cztery kiery.
d) Co najmniej jeden z graczy ma więcej niż dwa asy.
e) Nie każdy z graczy ma co najmniej dwa asy.
f) Żaden z graczy nie ma tylu samo kart czarnych co czerwonych.
g) Żaden z graczy nie ma tylu samo pików co trefli.
h) Dokładnie trzech graczy ma wszystkie karty w tym samym kolorze.
13. W czasie kampanii wyborczej panowie Alfa, Beta i Gamma złożyli następujące
oświadczenia:
Alfa: Beta zawsze kłamie.
Beta: Gamma zawsze kłamie.
Gamma: Alfa zawsze kłamie.
Uzasadnij, że przynajmniej dwa z tych oświadczeń są fałszywe. Wskazówka: Pokaż, że
z prawdziwości któregokolwiek z tych oświadczeń wynika fałszywość dwu pozostałych.
14. Wykaż, że spośród czterech poniższych zdań dokładnie dwa są prawdziwe:
Alfa: Beta zawsze kłamie.
Beta: Gamma przynajmniej czasem mówi prawdę.
Gamma: Delta przynajmniej czasem kłamie.
Delta: Alfa zawsze mówi prawdę.
15. Które z poniższych zdań są prawdziwe?
A. Spośród tych czterech zdań dokładnie jedno jest fałszywe.
B. Spośród tych czterech zdań dokładnie dwa są fałszywe.
C. Spośród tych czterech zdań dokładnie trzy są fałszywe.
D. Spośród tych czterech zdań dokładnie cztery są fałszywe.