szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 sie 2018, o 18:38 
Użytkownik

Posty: 4
Lokalizacja: Kraków
Dzień dobry,

Mam pytanie odnośnie dwóch zadań. Nie jestem pewien co do poprawności moich rozwiązań. W razie gdyby dowody były błędne byłbym wdzięczny za podanie właściwych odpowiedzi.

1. Udowodnij, że za pomocą alternatywy i koniunkcji nie można zdefiniować implikacji ani dyzjunkcji (NAND).

2. Niech S będzie pewnym nieskończonym zbiorem formuł zbudowanych nad zmiennymi p_{1} , p_{2} ,..., p_{n} Wykaż, że istnieje nieskończony podzbiór X zbioru S taki, że wszystkie formuły X są parami równoważne.

Zad 1 :
Indukcja zupełna po ilości wystąpień zmiennych.
Baza:a \wedge  b oraz dla a  \vee  b nie da się zdefiniować implikacji. (oczywiste).
Biorę zbiór wszystkich funkcji zbudowanych za pomocą \wedge oraz \vee o ilośći zmiennych \le n \in \mathbb{N} i zakładam, że nie ma wśród nich zdefiniowanej implikacji. Pokażę, że tak zbudowane formuły o długości n + 1 też należą do tego zbioru.

Weźmy dowolną funkcję o ilości n zmiennych. Oznaczmy za pomocą i_{1} \odot i_{2} \odot i_{3} \odot ...  i_{n-1} \odot i_{n},  \odot \in \lbrace \vee,  \wedge \rbrace , i_{k} \in \lbrace a, b \rbrace   \forall k \in 
 \lbrace 1, 2, 3, ... ,n \rbrace. Dla ułatwienia zapisu niech B = i_{1} \odot i_{2} \odot i_{3} \odot  ...   i_{n-1}
* a,b - to odpowiedni lewy i prawy argument funkcji wartościującej v(a, b)

Przypadek 1:
(B \odot i_{n})  \vee  a
v(1,0) = 1 czyli nie definiuje implikacji

Przypadek 2 (nie wprost):
(B \odot i_{n})  \vee  b
v(0,0) = 1 więc dla a = 0 i b = 0 (B \odot i_{n}) = 1
v(1,0) = 0 więc (B \odot i_{n}) = 0
2.1 Niech \odot = \vee oraz i_{n} = b, dla b = 1 wyrażenie (B \odot i_{n})  \vee  b definiuje implikacje ale wyrażenie (B \odot i_{n}) rónież ją definiuję więc dochodzimy do sprzeczności.
Według moich zapisek tylko ten przypadek korzysta z założenia indukcyjnego.
2.2 ...
... analogicznie postępuję dla przypadków gdzie dla wyrażenia (B \odot i_{n})  \vee  b, \odot 
 \in \lbrace \wedge,  \vee \rbrace ...

Rozpatruje jeszcze przypadek dla wyrażenia B \odot (i_{n} \odot  i_{n+1})
(żeby wziąć pod uwągę np takie wyrażenie (a\wedge b)\vee (a \vee i_{n+1}))
analogicznie jak poprzednie.


Uff pierwsze poszło, nie taki zły ten LaTeX :)

Zadanie 2:
Weźmy jakiś zbiór zbiorów A skłądający się ze zbiorów \lbrace i_{1}, i_{2}, ... , i_{n}\rbrace \forall k \le n \in \mathabb{N},  i_{k}  \in \lbrace 0, 1 \rbrace. Zbiór A określa dane wartościowanie funkcji boolowskiej zbudowanej nad n zmiennymi. np. jezeli \lbrace 1,0,0..., 0 \rbrace zawiera się w A oznaczo to, że dla wartoscowania v(1,0,0....,0) funkcja boolowska zwraca wartość 1. Załóżmy nie wprost, że zbiór X nie istnieje. To znaczy, że w zbiorze S każda para dowolnych funkcji nie jest równoważna. Zauważmy, że przy naszym założeniu dany zbiór A określa dokładnie tylko jedną funkcję zbioru S. Gdyby było inaczej oznaczało by to sprzeczność naszego założenia odnośnie równoważności funkcji. Ale wiemy, że takich zbiorów jest 2^2^n czyli skończona ilość. Dochodzimy do sprzeczności pokazując istnienie zbioru X.

Teraz pokażemy, że X jest nieskończony. Najwiekszy liczebnie zbiór który może warunkować nie istnienie zbioru X ma 2^{2^{n}} elementów. Stąd w zbiorze S jest co najmniej |S| - 2^{2^{n}} funkcji które się "dublują", są równoważne z conajmniej jedną fnkcją bool'owską. Stąd wynika, że X jest nieskończony.

Co do tego 2 - giego mam najwięcej wątpliwości. Jeżeli ten dowód jest poprawny to czy da to się opisać w sposób bardziej formalny ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 1 sie 2018, o 23:02 
Administrator

Posty: 22649
Lokalizacja: Wrocław
mik155 napisał(a):
Zad 1 :
Indukcja zupełna po ilości wystąpień zmiennych.
Baza:a \wedge  b oraz dla a  \vee  b nie da się zdefiniować implikacji. (oczywiste).
Biorę zbiór wszystkich funkcji zbudowanych za pomocą \wedge oraz \vee o ilośći zmiennych \le n \in \mathbb{N} i zakładam, że nie ma wśród nich zdefiniowanej implikacji. Pokażę, że tak zbudowane formuły o długości n + 1 też należą do tego zbioru.

Weźmy dowolną funkcję o ilości n zmiennych. Oznaczmy za pomocą i_{1} \odot i_{2} \odot i_{3} \odot ...  i_{n-1} \odot i_{n},  \odot \in \lbrace \vee,  \wedge \rbrace , i_{k} \in \lbrace a, b \rbrace   \forall k \in 
 \lbrace 1, 2, 3, ... ,n \rbrace. Dla ułatwienia zapisu niech B = i_{1} \odot i_{2} \odot i_{3} \odot  ...   i_{n-1}
* a,b - to odpowiedni lewy i prawy argument funkcji wartościującej v(a, b)

Przypadek 1:
(B \odot i_{n})  \vee  a
v(1,0) = 1 czyli nie definiuje implikacji

Przypadek 2 (nie wprost):
(B \odot i_{n})  \vee  b
v(0,0) = 1 więc dla a = 0 i b = 0 (B \odot i_{n}) = 1
v(1,0) = 0 więc (B \odot i_{n}) = 0
2.1 Niech \odot = \vee oraz i_{n} = b, dla b = 1 wyrażenie (B \odot i_{n})  \vee  b definiuje implikacje ale wyrażenie (B \odot i_{n}) rónież ją definiuję więc dochodzimy do sprzeczności.
Według moich zapisek tylko ten przypadek korzysta z założenia indukcyjnego.
2.2 ...
... analogicznie postępuję dla przypadków gdzie dla wyrażenia (B \odot i_{n})  \vee  b, \odot 
 \in \lbrace \wedge,  \vee \rbrace ...

Rozpatruje jeszcze przypadek dla wyrażenia B \odot (i_{n} \odot  i_{n+1})
(żeby wziąć pod uwągę np takie wyrażenie (a\wedge b)\vee (a \vee i_{n+1}))
analogicznie jak poprzednie.

Jakoś mnie to nie przekonuje.
Po pierwsze, ten dowód robi się zazwyczaj po liczbie spójników w tej formule, jest wtedy prostszy i szybszy.
Po drugie, Twoje rozumowanie nie wygląda poprawnie. Już zapis i_{1} \odot i_{2} \odot i_{3} \odot ... i_{n-1} \odot i_{n} jest niepoprawny, bo formuły konstruowanej za pomocą koniunkcji i alternatyw nie można zapisywać bez nawiasów. To, co robisz później, jest dla mnie mocno niejasne - pomijając już (nie)poprawność formalną tych zapisów w żaden sposób nie czuję się przekonany, że rozpatrzyłeś wszystkie przypadki.

JK
Góra
Mężczyzna Offline
PostNapisane: 11 sie 2018, o 20:23 
Użytkownik

Posty: 4
Lokalizacja: Kraków
Podejście nr. 2:

Zadanie I:
Indukcja po ilości formuł. Bierzemy zbiory A, B o ilości spójników \le k, k \in \lbrace 0, 1, 2, 3...\rbrace.
Zakładamy, że nie da się za ich pomocą zdefiniować implikacji. Weźmy funkcję wartościującą v(a, b).

Baza:
a, b. - nie definiują implikacji

Pokażemy, że A \vee B oraz A \wedge B nie definiuje implikacji.

1) Żeby A  \wedge B definiowało implikację
\begin{tabular}{|c|c|c|} \hline
a & b & v(a,b) dla A oraz B\\
\hline
0 & 0 & 1 \\
\hline 
\end{tabular}
Co jest sprzeczne ponieważ łatwo wykazać, że dla dowolniej formuły stworzonej z \vee ,  \wedge nad dwoma zmiennymi v(0,0) = 0.
Stąd wyrażenie A \wedge  B nie definiuję implikacji.

2) Żeby A  \vee B definiowało implikację wtedy:
\begin{tabular}{|c|c|c|} \hline
a & b & v(a,b) dla A lub B\\
\hline
0 & 0 & 1 \\
\hline 
\end{tabular}
Co jest sprzeczne ponieważ łatwo wykazać, że dla dowolniej formuły stworzonej z \vee ,  \wedge nad dwoma zmiennymi v(0,0) = 0.
Stąd wyrażenie A \vee  B nie definiuję implikacji.

*W punkcie nr 1 można skorzystać z zał. indkcyjnego i pominąć dowód że zawsze v(0,0) = 0 ale w pkt. 2 i tak będzie potrzebny.

Wydaje mi się, że rozpatrzyłem wszystkie przypadki ponieważ: "Jeżeli A jest formułą i B jest formuła to A \diamond B jest formułą. Nic inne nie jest formułą."

Czy to rozwiązanie oraz rozwiązanie zadania 2 - giego z pierwszego wpisu jest poprawne ?
Czy zadanie I można rozwiązać bez użycia indukcji ?
Góra
Mężczyzna Offline
PostNapisane: 11 sie 2018, o 21:21 
Administrator

Posty: 22649
Lokalizacja: Wrocław
mik155 napisał(a):
Zadanie I:
Indukcja po ilości formuł. Bierzemy zbiory A, B o ilości spójników \le k, k \in \lbrace 0, 1, 2, 3...\rbrace.

W ogóle tego nie rozumiem - po jakiej ilości formuł? W czym? Zbiory czego? To się w ogóle kupy nie trzyma.

mik155 napisał(a):
Zakładamy, że nie da się za ich pomocą zdefiniować implikacji. Weźmy funkcję wartościującą v(a, b).

W tym miejscu? To wygląda jak krok indukcyjny.

mik155 napisał(a):
Pokażemy, że A \vee B oraz A \wedge B nie definiuje implikacji.

1) Żeby A  \wedge B definiowało implikację
\begin{tabular}{|c|c|c|} \hline
a & b & v(a,b) dla A oraz B\\
\hline
0 & 0 & 1 \\
\hline 
\end{tabular}
Co jest sprzeczne ponieważ łatwo wykazać, że dla dowolniej formuły stworzonej z \vee ,  \wedge nad dwoma zmiennymi v(0,0) = 0.

Przykro mi, ale to "łatwo wykazać" to jest dokładnie to, co pokazuje się w tym dowodzie indukcyjnym.

Ogólnie masz dobry pomysł, ale formalizujesz dowód fatalnie.

mik155 napisał(a):
Czy (...) rozwiązanie zadania 2 - giego z pierwszego wpisu jest poprawne ?

Powiem jedno - tego się zupełnie nie da czytać. Idea być może jest dobra, ale prezentacja nieczytelna. Ten dowód da się zapisać czytelnie i zrozumiale w kilku linijkach.

JK
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Najmniejsza wspólna wielokrotność-dowód.  hUmanitO  8
 Przeprowadź dowód indukcyjny nierówności  Anonymous  15
 Dowód indykcyjny permutacji bez powtózeń  noiprox  3
 Dowod indukcyhjny nierownosci.  pavlo4  2
 Dowód wzoru  Tys  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl