Wst e p do Teorii Mnogości i Logiki

,

Lista 1

Zadanie 1.1 Wyobraź sobie, że rozwiązujesz test psychologiczny. Badający Cię psycholog kładzie przed Tobą na stoliku cztery karty

E

K

7

4

wyjaśniając, że każda karta ma z jednej strony wydrukowaną liczbę a z drugiej literę. Dodaje, że karty są drukowane według następującej reguły: Jeżeli z jednej strony karty jest samogłoska, to z drugiej musi być liczba nieparzysta. Ile spośród leżących przed Tobą kart wystarczy odwrócić, aby się przekonać o prawdziwości tej reguły?

Zadanie 1.2 Czy zdanie: „Jeżeli 3 jest liczbą parzystą, to o ile 3 jest liczbą nieparzystą, to 3 jest podzielne przez 2.” jest prawdziwe? A co można powiedzieć o prawdziwości zdania: „Jeżeli n jest liczbą parzystą, to o ile n jest liczbą nieparzystą, to 3 jest podzielne przez 2.” ?

Zadanie 1.3 Sprawdzić, czy następujące zdania są tautologiami:

p ⇒ ( q ⇒ p)

p ⇒ ( q ⇒ ( p ∧ q))

[ p ⇒ ( q ⇒ r)] ⇒ [( p ⇒ q) ⇒ ( p ⇒ r)]

[( ¬p) ⇒ p] ⇒ p

( ¬p) ⇒ ( p ⇒ q)

[( p ⇒ q) ∧ ( ¬q)] ⇒ ( ¬p)

p ⇒ [( ¬q ∧ q) ⇒ r]

[( p ∨ q) ⇒ r] ⇒ [( p ⇒ r) ∨ ( q ⇒ r)]

[( p ⇒ q) ∧ ( q ⇒ r)] ⇒ ( p ⇒ r)

Zadanie 1.4 Definiujemy dwa spójniki logiczne ↓ (kreskę Shefera) oraz ⊥ (spójnik Peirce’a): def

def

p ↓ q = ( ¬p ∨ ¬q)

p⊥q = ( ¬p ∧ ¬q) .

Wyrazić koniunkcję, alternatywę, negację, implikację oraz równoważność przy użyciu (wyłącznie):

(a) kreski Shefera,

(b) spójnika Peirce’a.

Zadanie 1.5 Wyrazić alternatywę, implikację oraz równoważność przy użyciu negacji oraz koniunkcji. Wyrazić koniunkcję, implikację oraz równoważność przy użyciu negacji oraz alternatywy.

Zadanie 1.6 Pokazać, że za pomocą koniunkcji i alternatywy nie można zdefiniować negacji ani implikacji.

Zadanie 1.7 Pokazać, że jeśli średnia arytmetyczna liczb x 1 , x 1 , . . . , xn jest większa od liczby a, to co najmniej jedna z tych liczb jest większa od a.

Zadanie 1.8

(a) Przyporządkujmy wartości logicznej 0 liczbę naturalną 0 , zaś wartości logicznej 1 liczbę 1 . Wtedy spójniki logiczne mogą być wyrażone w następujący sposób:

¬p = 1 − p,

p ∧ q = min( p, q) = p · q,

p ∨ q = max( p, q) = p + q − p · q,

p ⇒ q = 1 − p + p · q.

Udowodnić, że przy takiej interpretacji wyrażenie jest tautologią wtedy i tylko wtedy, gdy przy każdym układzie wartości przyjmuje wartość 1 .

(b) Przyporządkujmy wartości logicznej 0 liczbę naturalną 1 , zaś wartości logicznej 1 liczbę 0 . Znaleźć analogiczne do przedstawionych w części (a) wyrażenia spójników logicznych. Udowodnić, że przy takiej interpretacji wyrażenie jest tautologią wtedy i tylko wtedy, gdy przy każdym układzie wartości przyjmuje wartość 0 .

Zadanie 1.9 Rozważmy wyrażenie postaci: ( . . . (( p ⇒ p) ⇒ p) . . . ) ⇒ p . Dla jakich n to wyrażenie jest tautologią?

|

{z

}

n

Zadanie 1.10( ♦) Definiujemy: p 0 = p, p 1 = ¬p. Rozważmy wyrażenie postaci: . . . ( pi 1 ⇒ pi 2 ) ⇒ pi 3 . . . ⇒ pin . Dla

|

{z

}

n

jakich ciągów ( i 1 , i 2 , . . . , in) to wyrażenie jest tautologią?

Zadanie 1.11 ( ♦) Sprawdzić, czy każde zdanie jest równoważne zdaniu w postaci koniunktywno-alternatywnej (tzn.

takiemu, które jest koniunkcją zdań, z których każde jest alternatywą). Jeżeli nie, wyznaczyć klasę zdań, dla których powyższy warunek jest spełniony.

Zadanie 1.12 Udowodnić, że zdanie zbudowane ze zdań atomowych wyłącznie przy użyciu spójnika ⇔ jest tautologią wtedy i tylko wtedy, gdy każde zdanie proste występuje w nim parzystą liczbę razy.

Zadanie 1.13 Załóżmy, że zdanie p zawiera jedynie spójniki ∧, ∨. Niech pc oznacza zdanie otrzymane ze zdania p przez zastąpienie każdego symbolu ∨ symbolem ∧ oraz każdego ∧ przez ∨. Niech p? oznacza zdanie, które otrzymamy z p zastępując każde występujące w p zdanie atomowe jego negacją. Udowodnić, że ¬pc ⇔ p? jest tautologią. Udowodnić, że jeżeli p ⇔ q jest tautologią, to również pc ⇔ qc jest tautologią.

Zadania oznaczone symbolem ( ♦) są przeznaczone do samodzielnego rozwiązania (dla ambitnych). Rozwiązania można oddawać po wykładzie ze „Wstępu do teorii mnogości i logiki” do końca października.