Wst

,

ep do Teorii Mnogości i Logiki

Lista 2

Zadanie 2.1 Które z następujących schematów wnioskowań są poprawne ?

p→q,p

q

(p∨r)→q

p→q,r→q

(p∧r)→q

p→q,r→q

p→q,p∧r

q∧r

p→q

(p∧r)→q

p→q

p→(r→q)

.

Zadanie 2.2 Następujące zdania zapisać w postaci twierdzeń, wyróżniając w każdym z nich założenia i tezę.
„Wszystkie liczby naturalne są całkowite.“
„Suma dowolnych dwóch liczb dodatnich jest dodatnia.“
„Kwadrat liczby dodatniej n jest podzielny przez dwa tylko wtedy, gdy liczba n jest podzielna przez 2. “
„Kwadrat liczby dodatniej n jest podzielny przez dwa wtedy i tylko wtedy, gdy liczba n jest podzielna przez 2. “
„Żadna liczba naturalna, która nie jest podzielna przez 5, nie jest podzielna przez 25.“

Zadanie 2.3 Literami φ, ψ, β oznaczamy formuły, w których (jedyną) zmienną wolną jest x. Sprawdzić, czy następujące

schematy wnioskowania są poprawne.

∀

x

(φ(x)→ψ(x))

(∃

x

φ(x))→(∃

x

ψ(x))

∀

x

(φ(x)→ψ(x))

∃

x

ψ(x)

∀

x

(ψ(x)∨φ(x)) , ψ(x

0

)

¬φ(x

0

)

∀

x

(φ(x)∧ψ(x)→β(x)) , ¬φ(x

0

)

¬β(x

0

)

∀

x

(φ(x)∧ψ(x)→β(x)) , ψ(x

0

)

β(x

0

)

∀

x

((φ(x)∨ψ(x))→β(x)) , ψ(x

0

)

β(x

0

)

Zadanie 2.4 Literami φ, ψ, β oznaczamy formuły, w których (jedynymi) zmiennymi wolnynymi są x, y. Sprawdzić, czy

następujące schematy wnioskowania są poprawne.

∀

x

∀

y

(φ(x,y)→¬φ(y,x))

∀

x

¬φ(x,x)

∀

y

∃

x

(φ(x,y)→ψ(x,y)) , φ(x

0

,y

0

)

ψ(x

0

,y

0

)

∀

y

∃

x

(φ(x,y)∧ψ(x,y))

(∀

y

∃

x

φ(x,y)) ∧ (∀

y

∃

x

ψ(x,y))

∃

x

∀

y

(φ(x,y)→ψ(x,y)) , φ(x

0

,y

0

)

ψ(x

0

,y

0

)

∃

y

∀

x

(φ(x,y)∨ψ(x,y))

(∃

y

∀

x

φ(x,y)) ∨ (∃

y

∀

x

ψ(x,y))

∃

x

∀

y

(φ(x,y)∧ψ(x,y))

(∃

x

∀

y

φ(x,y)) ∧ (∃

x

∀

y

ψ(x,y))

Zadanie 2.5 Przedstawić przykłady ilustrujące niepoprawność poniższych schematów wnioskowania:

∀

x

(φ(x)∨ψ(x))

∀

x

φ(x)

∀

x

∃

y

(φ(x,y)∨ψ(x,y))

∀

x

∃

y

φ(x,y)

∃

x

∀

y

(φ(x,y)∨ψ(x,y)) , ¬ψ(x

0

,y

0

) , ∀

y

(φ(x

0

,y)∨ψ(x

0

,y))

∀

y

φ(x

0

,y)

∀

x

∃

y

(φ(x,y)∧ψ(x,y))

∃

y

∀

x

(φ(x,y)→ψ(x,y))

Zadanie 2.6 Korzystając z definicji kwantyfikatorów o ograniczonym zakresie, napisać negacje następujących formuł:

• (∀n ∈ N) n < 2 ∨ n

2

¬ 4

• (∃k ∈ Z) k

2

= −1

• (∀n ∈ N) (∃k ∈ Z) (n + k = 1)
• (∃k ∈ Z) (∀n ∈ N) (n + k = 1)

Zadanie 2.7 Zapisać następujące zdania i formuły za pomocą kwantyfikatorów, symboli logicznych, symboli działań (+,
·) oraz relacji (<, >, ­, ¬) i innych klasycznych symboli matematycznych:

• x jest liczbą parzystą.
• x jest liczbą pierwszą.
• n jest najmniejszą wspólną wielokrotnością liczb naturalnych k oraz m.
• 0 jest najmniejszą liczbą naturalną.
• Istnieje najmniejsza liczba naturalna.
• Nie istnieje najmniejsza liczba całkowita.
• Każda liczba naturalna jest iloczynem liczb pierwszych.
• Dowolne dwie liczby naturalne mają najmniejszą wspólną wielokrotność.
• Kwadrat liczby rzeczywistej jest nieujemny.
• Pomiędzy dowolnymi dwoma różnymi między sobą liczbami niewymiernymi znajduje się liczba wymierna.