LISTA ZADAŃ NR
1
Z MATEMATYKI DYSKRETNEJ
Logika
1. Które z następujących sformułowań są zdaniami w sensie logicznym? Uzasadnij odpowiedź.
a) Juliusz Cezar był prezydentem USA.
b) 2
n
+ n jest liczbą pierwszą dla nieskończenie wielu
N
∈
n
.
c)
x
y
y
x
+
=
+
dla wszystkich liczb rzeczywistych x, y.
d) Jeśli okrąg jest czworokątem, to
4
2
2
=
+
.
e) Dlaczego logika jest ważna?
f) Idź prosto do szpitala.
g)
0
2
=
A
implikuje
0
=
A
dla wszystkich A.
2. Niech p, q, r będą następującymi zdaniami: p = „pada deszcz”, q = „słońce świeci”, r = „na
niebie są chmury”. Przetłumacz następujące zdania na język polski:
a)
r
q
p
⇒
∧
)
(
,
b)
)
(
~
r
q
p
∨
⇒
,
c)
r
q
p
∧
∨
)
(
~
,
d)
q
r
p
⇒
⇒
)
(
,
e)
)).
(
(
~
r
q
p
∨
⇔
3. Wykaż, że następujące wyrażenia są tautologiami:
a)
)
(~
~
p
p
⇔
prawo podwójnego przeczenia
,
b)
p
p
~
∨
prawo wyłączonego środka
,
c)
)
~
(
~
p
p
∧
prawo sprzeczności
,
d)
)
~
(~
)
(
~
q
p
q
p
∧
⇔
∨
prawo de Morgana
,
e)
)
~
(~
)
(
~
q
p
q
p
∨
⇔
∧
prawo de Morgana
,
f)
p
p
p
⇔
∧
)
(
,
g)
p
p
p
⇔
∨
)
(
,
h)
)
(
)
(
p
q
q
p
∨
⇔
∨
,
przemienność alternatywy
,
i)
)
(
)
(
p
q
q
p
∧
⇔
∧
,
przemienność koniunkcji
,
j)
)
~
(~
)
(
p
q
q
p
⇒
⇔
⇒
,
k)
)
(~
)
(
q
p
q
p
∨
⇔
⇒
,
l)
)
~
(
)
(
~
q
p
q
p
∧
⇔
⇒
,
ł)
q
q
p
p
⇒
⇒
∧
)]
(
[
,
m)
q
p
q
p
⇒
∧
∨
]
~
)
[(
,
n)
p
F
p
~
)
(
⇒
⇒
, gdzie F – dowolne zdanie sprzeczne,
o)
]
)
[(
)]
(
[
r
q
p
r
q
p
∨
∨
⇔
∨
∨
łączność alternatywy
,
p)
]
)
[(
)]
(
[
r
q
p
r
q
p
∧
∧
⇔
∧
∧
łączność koniunkcji
,
r)
)]
(
)
[(
)]
(
[
r
p
q
p
r
q
p
∧
∨
∧
⇔
∨
∧
rozdzielność koniunkcji względem alternatywy
,
s)
)]
(
)
[(
)]
(
[
r
p
q
p
r
q
p
∨
∧
∨
⇔
∧
∨
rozdzielność alternatywy względem koniunkcji
,
t)
)
(
)]
(
)
[(
r
p
r
q
q
p
⇒
⇒
⇒
∧
⇒
przechodniość implikacji
.
4. Sprawdź, czy następujące wyrażenia są tautologiami:
a)
)
(
)
(
p
q
q
p
⇒
⇔
⇒
,
b)
)
(
)]
(
)
[(
q
p
p
q
q
p
∨
⇒
⇒
∧
⇒
,
c)
)]
(
)
[(
]
)
[(
r
q
r
p
r
q
p
⇒
∨
⇒
⇒
⇒
∨
.
