Wst e p 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

( p∨r) →q

( p∧r) →q

p→q,p∧r

p→q

p→q

.

q

p→q,r→q

p→q,r→q

q∧r

( p∧r) →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 0) ( ∃xφ( x)) →( ∃xψ( x))

∃xψ( x)

¬φ( x 0)

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

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

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

¬β( x 0)

β( 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))

∀y∃x ( φ( x,y) →ψ( x,y)) , φ( x 0 ,y 0)

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

∀x ¬φ( x,x)

ψ( x 0 ,y 0)

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

∃x∀y ( φ( x,y) →ψ( x,y)) , φ( x 0 ,y 0)

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

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

ψ( x 0 ,y 0)

( ∃y∀xφ( x,y)) ∨ ( ∃y∀xψ( 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∃y ( φ( x,y) ∨ψ( x,y))

∀xφ( x)

∀x∃yφ( x,y)

∃x∀y ( φ( x,y) ∨ψ( x,y)) , ¬ψ( x 0 ,y 0) , ∀y ( φ( x 0 ,y) ∨ψ( x 0 ,y))

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

∀y φ( x 0 ,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.