Logika dla informatyków

Lista zadań nr 0

3 października 2002

Zadanie 1. Oto fragment raportu policji sporządzony przez młodego aspiranta:

Świadek nie był zastraszony lub też, jeśli Henry popełnił samobójstwo, to testament odnaleziono. Jeśli świadek był zastraszony, to Henry nie popełnił samobójstwa. Jeśli testament odnaleziono, to Henry popełnił samobójstwo. Jeśli Henry nie popełnił samobójstwa, to testament odnaleziono.

Co komendant policji może wywnioskować z powyższego raportu (poza oczywiastym faktem, że należy zwolnić aspiranta)? Odpowiedz na pytania: „Czy świadek był zastraszony? Czy Henry popełnił samobójstwo? Czy testament odnaleziono?”

Zadanie 2. Pośród członków pewnego klubu lingwistycznego każdy uczy się francuskiego, niemieckiego lub hiszpańskiego. Wiadomo, że 20 uczy się francuskiego, 12 francuskiego i hiszpańskiego, 16 niemieckiego, 16 hiszpańskiego, 4 francuskiego i niemieckiego, 7 niemieckiego i hiszpańskiego, 3 wszystkich trzech języków. Ilu członków liczy klub? Ilu z nich uczy się dokładnie dwóch języków?

Zadanie 3. Oto przykład trzech wnioskowań przez indukcję:

1. „Pokażę, że wszystkie liczby naturalne są parzyste. Oczywiście 0 jest liczbą parzystą. Niech n będzie dowolną liczną naturalną i załóżmy, że dla wszystkich k < n, k jest parzyste. Niech n_{1} i n_{2} będzie dowolnym rozbiciem liczby n na sumę liczb mniejszych (tzn. n D n_{1} C n_{2}). Ponieważ n_{1} oraz n_{2} są mniejsze od n, n_{1} i n_{2} są parzyste a więc n jest parzyste jako suma dwóch liczb parzystych.

2. „Pokażę, że wszystkie dodatnie liczby naturalne są nieparzyste. Oczywiście 1 jest liczbą nieparzystą. Niech n będzie dowolną liczbą naturalną i załóżmy, że dla wszystkich k < n, k jest nieparzyste. Niech 1, n_{1} i n_{2} będzie dowolnym rozbiciem liczby n na sumę trzech liczb mniejszych (tzn. n D n_{1} C n_{2} C 1). Ponieważ n_{1} oraz n_{2} są mniejsze od n, n_{1} i n_{2} są nieparzyste a więc n jest nieparzyste jako suma dwóch liczb nieparzystych i liczby 1.

3. „Pokażę, że wszystkie proste na płaszczyźnie są równoległe. Rozważmy jednoelementowy zbiór prostych na płaszczyźnie. Oczywiście wszystkie proste należące do tego zbioru są do siebie równoległe. Załóżmy, że w każdym n-elementowym zbiorze prostych wszystkie proste są do siebie równoległe. Rozważmy teraz n C 1-elementowy zbiór prostych. Ustalmy w nim jedną prostą p. Na mocy założenia indukcyjnego wszystkie pozostałe n prostych jest do siebie równoległe. Ustalmy teraz inną prostą q. Na mocy założenia indukcyjnego wszystkie pozostałe n prostych jest również do siebie równoległe. Ponieważ relacja równoległości prostych jest przechodnia, wszystkie n C 1 prostych jest równoległe. Na mocy zasady indukcji matematycznej każdy zbiór prostych na płaszczyźnie zawiera wyłącznie proste równoległe. W szczególności dotyczy to zbioru wszystkich prostych na płaszczyźnie.

Które z tych rozumowań jest poprawne? Wskaż błędy popełnione w błędnym rozumowaniu.

W poniższych zadaniach napisz odpowiednie formuły logiczne nie używając znaku negacji.

Zadanie 4. Funkcja f : ℝ → ℝ jest ciągła, jeśli

∀x_{0} ∈ ℝ.∀ϵ > 0.∃δ > 0.∀x.▷|x − x_{0}| < δ ⇒ |f ▷x◁ − f ▷x_{0}◁| < ϵ◁

Zapisz formułę „funkcja f nie jest ciągła.”

Zadanie 5. Liczba g ∈ ℝ jest granicą (w sensie Cauchy’ego) funkcji f : ℝ → ℝ w punkcie x_{0}, jeśli

∀ϵ > 0.∃δ > 0.∀x.▷0 < |x − x_{0}| < δ ⇒ |f ▷x◁ − g| < ϵ◁

Zapisz formułę „liczba g nie jest granicą funkcji f w punkcie x_{0}.”

Zadanie 6. Liczba g ∈ ℝ jest granicą (w sensie Heinego) funkcji f : ℝ → ℝ w punkcie x_{0}, jeśli

∀▷x_{n}◁_{n∈ℕ}.▷ lim_{n→∞} x_{n} D x_{0} ∧ ∀n.x_{n} D̸ x_{0}◁ ⇒ lim_{n→∞} f ▷x_{n}◁ D g

Zapisz formułę „liczba g nie jest granicą funkcji f w punkcie x_{0}.”