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

⇒

∨

⇒

⇒

⇒

∨

.

5. Określ:
a) koniunkcję za pomocą alternatywy i negacji,
b) alternatywę za pomocą koniunkcji i negacji,
c) alternatywę za pomocą implikacji i negacji.

6. Czy następujące zdanie jest prawdziwe? Jakie można zapisać jego zaprzeczenie?
a) Istnieje liczba naturalna n, której kwadrat wynosi 7.
b) Istnieje liczba rzeczywista x taka, że

0

2

1

=

+

+

+

x

x

.

Jak równoważnie zapisać zdanie

)]

(

[

~

x

W

x

∨

, gdzie

)

(

x

W

jest pewną formą zdaniową.

7. Czy następujące zdanie jest prawdziwe? Jakie można zapisać jego zaprzeczenie?
a) Każda liczba naturalna n jest złożona.
b) Każda liczba rzeczywista spełnia warunek

x

x

≥

2

.

Jak równoważnie zapisać zdanie

)]

(

[

~

x

W

x

∧

, gdzie

)

(

x

W

jest pewną formą zdaniową.

8. Podaj wartości logiczne następujących wyrażeń:

a)

n

m

m

n

=

∈

∈

∨

∧

2

N

N

,

b)

m

n

m

n

=

∈

∈

∨

∧

2

N

N

,

c)

m

n

n

m

=

∈

∈

∧

∨

2

N

N

.

Czy prawdziwa jest implikacja

)

,

(

)

,

(

y

x

W

y

x

W

x

y

y

x

∨

∧

∧

∨

⇒

?

Czy prawdziwa jest implikacja odwrotna? Jeśli nie, podaj kontrprzykład.

9. Podaj wartości logiczne następujących wyrażeń, gdzie dziedziną jest zbiór

R

.

a)

1

=

∃

∀

xy

y

x

,

b)

1

=

∃

∃

xy

y

x

,

c)

2

2

2

)

(

y

x

y

x

y

x

+

=

+

∀

∀

.

d)

2

2

2

)

(

y

x

y

x

y

x

+

=

+

∃

∀

,

e)

2

2

2

)

(

y

x

y

x

x

y

+

=

+

∀

∃

,

Dorota Majorkowska-Mech