Wrocław, 1 października 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania – lista 1
1. Które z wypowiedzi są zdaniami lub funkcjami zdaniowymi:
a) Księżyc jest zrobiony z żółtego sera.
b) On faktycznie jest wysokim mężczyzną.
c) Słońce krąży dookoła Ziemi.
d) W ciągu wieków składniki te uformowały rafy.
e) Niech żyje przyjaźń między narodami!
f) Dwa jest liczbą parzystą.
g) Która drużyna zdobędzie mistrzostwo kraju w piłce nożnej?
h) Oczekuje się, że w przyszłym roku obroty na giełdzie znacznie wzrosną.
i) x
2
– 4 = 0
j) Długi honorowe należy spłacać w ciągu 24 godzin.
k) Mężczyzna jest wyższy od kobiety.
l) Należy raczej zapobiegać niż leczyć.
m) Kalifornię co roku nawiedza trzęsienie ziemi o sile 7 stopni w skali Richtera.
n) Król Jagiełło był raczej wysokim mężczyzną.
2. Jaką wartość logiczną mają zdania:
a) 8 jest liczbą nieparzystą lub 6 jest liczbą parzystą.
b) 8 jest liczbą nieparzystą oraz 6 jest liczbą parzystą.
c) Jeżeli 8 jest liczbą nieparzystą, to 6 jest liczbą parzystą.
d) Jeżeli 8 jest liczbą nieparzystą oraz 6 jest liczbą parzystą, to 6 jest większe od 8.
3. Które ze zdań są negacją danego zdania:
a) Wynikiem obliczeń jest 2 albo 3.
(i)
Wynikiem nie jest ani 2 ani 3.
(ii)
Wynikiem nie jest 2 lub nie jest 3.
(iii)
Wynikiem nie jest 2 i nie jest 3.
b) Ogórek jest zieloną rośliną nasienną.
(i)
Ogórek nie jest zielony, ale jest rośliną nasienną.
(ii)
Ogórek nie jest zielony lub nie jest rośliną nasienną.
(iii)
Ogórek nie jest zielony i nie jest rośliną nasienną.
4. Wskaż poprzednik i następnik implikacji w zdaniach:
a) Pomyślny wzrost roślin jest uwarunkowany prawidłowym nawadnianiem.
b) W przypadku modyfikacji programu pojawią się w nim błędy.
c) Błędy w programie pojawią się tylko w przypadku jego modyfikacji.
d) Oszczędność energii jest związana z dobrą izolacją ścian i szczelnością okien.
5. W podanych zdaniach złożonych rozpoznaj zdania proste i łączące je spójniki:
a) Edmund Hillary i Tenzing Norgay są pierwszymi zdobywcami Mont Everestu.
b) Indochiny leżą w strefie tropikalnej i mają gorące lata, ale zimy w części północnej są chło-
dne.
c) Niezależnie od tego jak wysoko skaczesz, księżyca nie osiągniesz, chyba, że polecisz tam
rakietą.
6. Dla poniższych zdań sprawdzić, czy informacja, że q = F jest wystarczająca do wyliczenia
wartości logicznej zdania złożonego. Jeśli tak, to wartość tę wyznaczyć, jeśli nie, to pokazać, że
obie wartości są możliwe.
a) (
)
b) (
)
c)
(
)
7. Rozpatrz następujące wnioskowanie:
Jeżeli Cezar pozostanie w domu, to nie zostanie zabity przez spiskowców.
Jeżeli Cezar nie zostanie zabity przez spiskowców, to wygłosi przemówienie w Senacie.
Zatem: Jeżeli Cezar pozostanie w domu, to wygłosi przemówienie w Senacie.
Wyjaśnić przyczyny paradoksalnego wniosku.
8. Podać elementy następujących zbiorów:
a) {a}
b) {{a}}
c) {{a, b}, {a}}
d) {{{a}}, {a}, a}
e) {x
Nat | x
2
< 7}
f) {x
Wymierne | x
2
= 2}
g) {x
Wymierne | (x + 1)
2
< 0}
9. Niech A, B, C, D będą parami rozłącznymi, niepustymi zbiorami. Jakie warunki powinny
spełniać te zbiory, aby zachodziły następujące równości:
a) {B, C} = {B, C, D}
b) {{A, B}, C} = {{A}, C}
c) {{A, B}, {D}} = {{A}}
d) {{A,
}, B} = {{
}}
10. Wykazać, że równość zbiorów {{A}, {A, B}} = {{C}, {C, D}} zachodzi wtedy i tylko wtedy,
gdy A = C oraz B = D.
11. Obliczyć A
B, A
B, A\B, B\A dla następujących zbiorów A i B:
a) A = {{a, b}, c}
B = {c, d}
b) A = {{a, {a}}, a}
B = {a, {a}}
12. Sprawdzić i uzasadnić, które spośród niżej podanych równości zachodzą bądź nie zachodzą dla
dowolnych zbiorów A, B, C, D:
a) (A
B)\C = (A\C)
(B\C)
b) (A\B)
(C\D) = (A
C)\(B
D)
c) (A
B)
B = B
d) (A
B)
( A\B) = A
e) (A\B) = A\(A
B)
f) (A\B)
B = A
13. Niech U będzie pewnym ustalonym zbiorem, zwanym uniwersum. Jeżeli A
U, to A’ =
def
U\A
nazywa się dopełnieniem zbioru A. Pokazać, że dla podzbiorów z uniwersum U zachodzą prawa
de Morgana:
a) (A
B)’ = A’
B’
b) (A
B)’ = A’
B’
14. Ile elementów ma najmniejsza, niepusta rodzina zbiorów A z pewnego uniwersum U taka, że:
a) jeżeli A
A i B
A, to A
B
A,
b) jeżeli A
A i B
A, to A
B
A.
15. Niech card(A) oznacza liczbę elementów zbioru skończonego A. Pokazać, że dla skończonych
zbiorów A oraz B zachodzi:
a) card(2
A
) = 2
card(A)
b) card(A
B) = card(A) + card(B) – card(A
B)
16. Dla dowolnych zbiorów skończonych A, B i C znaleźć wzory określające:
a) card(A
B
C)
b) card(2
A
B
)
c) card(A\B)
17. Dowieść, że dla rodzin zbiorów {A
i
| i
I}, {B
i
| i
I} oraz {C
i,j
| i
I, j
J} zachodzą równości:
a)
I
i
i
I
i
I
i
i
i
i
B
A
B
A
)
(
b)
I
i
I
i
J
j
j
i
J
j
j
i
C
C
,
,