Logika - egzamin

[Tweester]

Witam. Wiem że są wakacje, ale potrzebuje waszej pomocy. Mam zadania które dostane na egzaminie na dopytce w celu zaliczenia egzaminu. Próbowałem sam je rozwiązać ale nie wychodziło mi to. Prosze o pomoc.

Zadanie 3.
Niech E = {a,b,c,d} będzie alfabetem. Rozważmy relacje \(\le \subset= E^* x E^*\) taką że dla dowolnych w, v \(\in\) E^* zachodzi w \(\le\) v dokładnie wtedy gdy istnieją słowa x,y \(\in\) E^* takie że v = xyw.

a) wskaż parę słów które są w relacji " \(\le\) "
b) pokaż że relacja \(\le \subset= E^* x E^*\) jest relacją częściowego porządku na zbiorze słow \(E^*\)
c) pokaż że poste (\(E^*, \le\)) nie jest liniowo uporządkowany
d) wskaż element minimalny posetu (\(E^*, \le\)). Czy ten element jest również elementem najmniejszym?
e) pokaż że słowo xy jest ograniczeniem górnym zbioru {x,y} w posecie (\(E^*, \le\))

Zadanie 4.
Niech F(N) będzie rodziną wszystkich skończonych podzbiorów zbioru liczb naturalnych N. Niech X = {0,1} zaś ~= \(\subset\) =F(N) x F(N) taką relacją binarną na F(N) że dla dowolnych A,B \(\in\) F(N) zachodzi A~=B dokładnie wtedy gdy A = B lub ( X \(\notin\) A \(\wedge\) X \(\notin\)B)

a) podaj przykład pary różnych zbiorów które są w relacji "~=". Wskaż parę zbiorów które nie są w tej relacji.
b) pokaż że relacja ~= \(\subset\) =F(N) x F(N) jest relacją równoważności
c) opisz klasę abstrakcji zbioru pustego \([ \emptyset ]\)~=


Zadanie 5.
Pokaż metodą indukcji matematycznej że funkcja f: N \(\to\) Z zdefiniowana rekurencyjnie następująco
\(f(0) = 0\)
\(f(n+1) = f(n) + (-1)^n(n+1)^2\)
jest funkcją o wzorze \(f(n) = (-1)^{n-1} \frac{n(n+1)}{2}\). Następnie:
a) opisz zbiory \(f^{-1}(4)\) oraz \(f^{-1}(-7)\)
b) uzasadni że funkcja f nie jest "na"
c) pokaż że funkcja f jest różnowartościowa
d) oblicz (\(f \circ f \circ f \circ f\))(1)

Nie wszystkie znaki umiałem wstawić dlatego dołączam jeszcze skan http://i.imgur.com/y7Yhc.jpg
Będę wdzięczny naprawdę za wszystkie rozwiązanie zadania. Bardzo ważne dla mnie jest zaliczenie tego egzaminu.

[radagast]

Zadanie 5 (początek)
\(1^ \circ\) \(f(0)=0=(-1)^{0-1} \cdot \frac{0 \cdot (0+1)}{2}\); OK
\(2^ \circ\) zał. ind. :
Istnieje \(n \in N\) t. że \(f(n)= (-1)^{n-1} \cdot \frac{n(n+1)}{2}\)
pokażemy, że :
\(f(n+1) = (-1)^{n} \cdot \frac{(n+1)(n+2)}{2}\)

\(L= f(n+1) =f(n)+ (-1)^n \left(n+1 \right)^2 =^{zal.ind.} (-1)^{n-1} \cdot \frac{n(n+1)}{2}+(-1)^n \left(n+1 \right)^2 =
(-1)^{n-1} \cdot \frac{(n+1)}{2} \left[ n+(-1) \cdot 2 \left( n+1\right) \right] = (-1)^{n-1} \cdot \frac{(n+1)}{2} \left[ -n-2\right] =(-1)^{n} \cdot \frac{(n+1)}{2} \left[ n+2\right] =P\)

zatem na mocy zasady indukcji....

[radagast]

5) ciąg dalszy
a) \(f(n)=4 \Leftrightarrow \left( -1\right)^{n-1} \cdot \frac{n(n+1)}{2} =4 \Leftrightarrow \left( -1\right)^{n-1} \cdot n(n+1) =8\) czyli
dla parzystych n :
\(-n(n+1) =8\)
\(n^2+n+8=0, \Delta <0 ,n \notin N\)


dla nieparzystych n :
\(-n(n+1) =-8\)
\(n^2+n-8=0, \Delta =33 ,n \notin N\)

wniosek: \(f^{-1}(4)= \emptyset\)

\(f(n)=-7 \Leftrightarrow \left( -1\right)^{n-1} \cdot \frac{n(n+1)}{2} =-7 \Leftrightarrow \left( -1\right)^{n-1} \cdot n(n+1) =-14\) czyli
dla parzystych n :
\(-n(n+1) =-14\)
\(n^2+n-14=0, \Delta =57 ,n \notin N\)


dla nieparzystych n :
\(-n(n+1) =14\)
\(n^2+n+14=0, \Delta <0 ,n \notin N\)

wniosek: \(f^{-1}(-7)= \emptyset\)

[radagast]

5)
b)
funkcja f nie jest "na" zbiór Z, bo nie przyjmuje wartości 4 (-7, też nie ale to juz nie ważne, wystarczy, że nie przyjmuje 4)

Funkacja f "na" jakis zbior jest. Każda funkcja jest "na" swój zbiór wartości , ale jaki on jest na szczęście wyznaczać nie każą

[radagast]

5)
c)
\(f(n)=f(k) \Leftrightarrow \left( -1\right)^{n-1} \cdot \frac{n(n+1)}{2} =\left( -1\right)^{k-1} \cdot \frac{k(k+1)}{2} \Rightarrow \left( \frac{n(n+1)}{2} =\frac{k(k+1)}{2} \right) \vee \left( \frac{n(n+1)}{2} =-\frac{k(k+1)}{2} \right)
\Leftrightarrow \left(n(n+1)=k(k+1) \right) \vee \left(n=k=0 \right) \Leftrightarrow \left(n^2+n=k^2+k \right)\vee \left(n=k=0 \right) \Leftrightarrow \left(n^2-k^2=k-n \right)\vee \left(n=k=0 \right)
\Leftrightarrow (n-k)(n+k)=k-n \vee \left(n=k=0 \right) \Leftrightarrow n=k \vee n+k=-1 \vee n=k=0 \Leftrightarrow n=k\)

zatam z tego , ze \(f(n)=f(k)\) wywnoiskowałam pracowicie, ze \(n=k\) , co świadczy o różnowartościowości funkcji f

(może to i można jakoś prościej ale mi nie chciało wyjść)

[radagast]

5)
d)
\(\left(f \circ f \circ f \circ f \right) \left( 1\right)=f \left( f \left(f \left( f(1)\right) \right) \right)\)
No i po kolei liczymy:
\(f(1)= \left(-1 \right) ^{1-1} \cdot \frac{1 \cdot (1+1)}{2} =1\)

a wiec nie będzie trudno
\(f \left( f \left(f \left( f(1)\right) \right) \right) =f \left( f \left(f \left( 1\right) \right) \right)= f \left( f \left(1 \right) \right)=f(1)=1\)

[radagast]

4)
a)
\(A= \left\{ 2,5,7\right\}\\B= \left\{ 3,5\right\}\)
\(A \simeq B\) (bo żaden za zbiorów Ai B nie zawiera zbioru{0,1})

\(A= \left\{ 0,1,7\right\}\\B= \left\{ 3,5\right\}\)
\(A \not\simeq B\) (bo ani A nie równa się B , ani nie jest prawdą, ze żaden za zbiorów Ai B nie zawiera zbioru{0,1})

[radagast]

4)
b)
relacja \(\simeq\) jest zwrotna ( każdy zbiór jest w relacji ze sobą)
relacja \(\simeq\) jest symetryczna ( jeśli \(A \simeq B\) to \(B \simeq A\) )

oczywistość tych faktów skwituję brakiem uzasadnienia (jeśli jednak koniecznie chesz uzasadnienia to napisz)
przechodniość relacji \(\simeq\):
\(A \simeq B \wedge B \simeq C \Rightarrow\) \(\left\{A=B \vee \left[ \left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq B \right] \right\} \wedge \left\{B=C \vee \left[ \left\{0,1 \right\} \not \subseteq B \wedge \left\{0,1 \right\} \not \subseteq C \right] \right\}\)
Rozbijmy tę skomplikowaną koniunkcję na cztery przypadki:
\(\left( A=B \wedge B=C \right) \vee
\left( A=B \wedge \left[ \left\{0,1 \right\} \not \subseteq B \wedge \left\{0,1 \right\} \not \subseteq C \right] \right) \vee
\left( \left[ \left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq B \right] \wedge B=C\right ) \vee
\left( \left[ \left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq B \right] \wedge \left[ \left\{0,1 \right\} \not \subseteq B \wedge \left\{0,1 \right\} \not \subseteq C \right] \right )\)

w każdym z tych czterech przypadków zachodzi
\(\left\{A=C \vee \left[\left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq C \right] \right\}\)
( w pierwszym A=C,
w drugim, trzecim i czwartym \(\left[ \left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq C \right]\))

czyli istotnie : \(A \simeq C\), co świadczy o przechodniości badanej relacji.
No to ona jest relacją równoważności
CBDO

[radagast]

4)
c)
Zbiór pusty jest w relacji z każdym podzbiorem zbioru liczb naturalnych nie zawierającym elementów 0,1 (obu na raz, bo jednen z nich może sobie zawierać).
Jednocześnie zbiór pusty jest w relacji wyłącznie z takim zbiorami.

Tak wiec klasą abstrakcji zbioru pustego jest zbiór wszystkich podzbiorów zbioru F(N) nie zawierających jednocześnie elementów 1,0

[Tweester]

Witam! Dziękuję za tyle odpowiedzi i czekam jeszcze na ostatnie zadanie. Jak możesz to napisz uzasadnienie do zadania 4. do tego że realcja jest zwrotna i symetryczna

[radagast]

relacja \(\simeq\) jest zwrotna jeżeli dla każdego \(A\) zachodzi \(A \simeq A\) czyli \(A=A \vee \left[ \left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq A \right]\),
a ponieważ \(A=A\) to zachodzi.


relacja \(\simeq\) jest symetryczna jeżeli dla każdego \(A\) zachodzi \(A \simeq B \Rightarrow B\simeq A\) czyli \(\left\{A=B \vee \left[ \left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq B \right] \right\} \Rightarrow \left\{B=A \vee \left[ \left\{0,1 \right\} \not \subseteq B \wedge \left\{0,1 \right\} \not \subseteq A \right] \right\}\),
a ponieważ symetryczna jest zarówno równość zbiorów (jesli \(A=B\) to \(B=A\) )
jak i koniunkcja (jeśli \(\left\{0,1 \right\} \not \subseteq A \wedge \left\{0,1 \right\} \not \subseteq B\) to \(\left\{0,1 \right\} \not \subseteq B \wedge \left\{0,1 \right\} \not \subseteq A\)) to zachodzi

[radagast]

Zadania 3 niestety nie zrobię (nie umiem , co nie znaczy , ze jest trudne )

[Tweester]

Witam ponownie! Czy może na forum jest już ktoś kto potrafiłby rozwiązać to 3 zadanie?

Dodam jeszcze jedno mało zadanko jeżeli można.

2. Sprawdz czy następuje równość
a) \(A \times B = B \times A\)
b) \((A \setminus B) \cap (C \setminus D) = (A \cap C) \setminus (B \cup D)\)

dla dowolnych zbiorów A,B,C,D. Jeśli któraś jest fałszywa podać kontrprzykład - wskaż zbiory dla których niezachodzi.

[radagast]

2a) to oczywista nieprawda.
Np \(A= \left\{1 \right\} ,B= \left\{2 \right\}\)
\(A \times B= \left\{ (1,2)\right\}\)
\(B \times A= \left\{ (2,1)\right\}\)

[radagast]

2b) jest niestety prawdą i to trzeba udowodnić:
A więc:
\(x \in (A \setminus B) \cap (C \setminus D) \Leftrightarrow
x \in A \wedge x \notin B \wedge x \in C \wedge x \notin D \Leftrightarrow
x \in A \wedge x \in C\wedge x \notin B \wedge x \notin D \Leftrightarrow
x \in A \wedge x \in C\wedge x \notin B \wedge x \notin D \Leftrightarrow
x \in A \cap C\wedge x \notin B \cup D \Leftrightarrow
(A \cap C) \setminus (B \cup D)\)