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 \(\displaystyle{ 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:\(\displaystyle{ a \wedge b}\) oraz dla \(\displaystyle{ a \vee b}\) nie da się zdefiniować implikacji. (oczywiste).
Biorę zbiór wszystkich funkcji zbudowanych za pomocą \(\displaystyle{ \wedge}\) oraz \(\displaystyle{ \vee}\) o ilośći zmiennych \(\displaystyle{ \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 \(\displaystyle{ n + 1}\) też należą do tego zbioru.
Weźmy dowolną funkcję o ilości \(\displaystyle{ n}\) zmiennych. Oznaczmy za pomocą \(\displaystyle{ 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 \(\displaystyle{ 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:
\(\displaystyle{ (B \odot i_{n}) \vee a}\)
v(1,0) = 1 czyli nie definiuje implikacji
Przypadek 2 (nie wprost):
\(\displaystyle{ (B \odot i_{n}) \vee b}\)
v(0,0) = 1 więc dla a = 0 i b = 0 \(\displaystyle{ (B \odot i_{n}) = 1}\)
v(1,0) = 0 więc \(\displaystyle{ (B \odot i_{n}) = 0}\)
2.1 Niech \(\displaystyle{ \odot = \vee}\) oraz \(\displaystyle{ i_{n} = b}\), dla b = 1 wyrażenie \(\displaystyle{ (B \odot i_{n}) \vee b}\) definiuje implikacje ale wyrażenie \(\displaystyle{ (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 \(\displaystyle{ (B \odot i_{n}) \vee b, \odot
\in \lbrace \wedge, \vee \rbrace ...}\)
Rozpatruje jeszcze przypadek dla wyrażenia \(\displaystyle{ B \odot (i_{n} \odot i_{n+1})}\)
(żeby wziąć pod uwągę np takie wyrażenie \(\displaystyle{ (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 \(\displaystyle{ \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 \(\displaystyle{ n}\) zmiennymi. np. jezeli \(\displaystyle{ \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 \(\displaystyle{ 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 \(\displaystyle{ 2^{2^{n}}}\) elementów. Stąd w zbiorze S jest co najmniej \(\displaystyle{ |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 ?
