Przypomnijmy najpierw:
Formułami logiki zdaniowej są wszystkie zmienne zdaniowe oraz wszystkie formuły postaci \(\displaystyle{ \left( \alpha \Rightarrow \beta \right) }\), gdzie \(\displaystyle{ \alpha}\) i \(\displaystyle{ \beta}\) są dowolnymi formułami (spójnik \(\displaystyle{ \Rightarrow}\) nazywamy implikacją), oraz formuły postaci \(\displaystyle{ \neg \alpha}\) , gdzie \(\displaystyle{ \alpha}\) jest dowolną formułą (spójnik \(\displaystyle{ \neg}\) nazywamy negacją).
Powyższa definicja mówi, że formułami są te napisy, które można utworzyć ze zmiennych zdaniowych przez skończoną ilość operacji \(\displaystyle{ \neg}\) i \(\displaystyle{ \Rightarrow}\) .
Uwaga! Jeśli do alfabetu języka należą zmienne zdaniowe \(\displaystyle{ p_1}\) i \(\displaystyle{ p_2}\), to formalnie napis \(\displaystyle{ p_1 \Rightarrow p_2}\) nie jest formułą, gdyż brakuje w nim nawiasów, a napis \(\displaystyle{ \left( p_1 \Rightarrow p_2\right)}\) już jest poprawną formułą. Przyjmiemy jednak dalej, że w takim przypadku nie będzie konieczne pisanie nawiasów, gdyż można je jednoznacznie uzupełnić. Również dla wielu implikacji w jednej formule przyjmujemy, że nawiasy ustawiamy od prawej do lewej, np. formuła \(\displaystyle{ p_1 \Rightarrow p_2 \Rightarrow p_3}\) oznacza formalnie formułę \(\displaystyle{ \left( p_1\Rightarrow \left( p_2 \Rightarrow p_3\right) \right)}\).
Rozmiarem formuły nazywamy ilość występujących w niej spójników;
Np. formuła \(\displaystyle{ \neg \neg p}\), ma rozmiar \(\displaystyle{ 2}\), a formuła \(\displaystyle{ \left( p_1 \Rightarrow p_2\right)}\) ma rozmiar \(\displaystyle{ 1.}\)
I mamy ćwiczenie (z ważniaka):
Ustalmy zmienną, np. \(\displaystyle{ x}\); i przypuśćmy, że jedyną zmienną zdaniową, jaką wolno nam użyć, jest \(\displaystyle{ x}\). Ile jest wszystkich różnych formuł o rozmiarze \(\displaystyle{ 3}\)?
ROZWIĄZANIE:
Dla liczby naturalnej \(\displaystyle{ n}\) oznaczmy przez \(\displaystyle{ f_n}\) liczbę formuł o rozmiarze \(\displaystyle{ n}\) (czyli liczbę formuł, w której jest \(\displaystyle{ n}\) spójników). Interesuje nas wartość \(\displaystyle{ f_3.}\)
Przyglądając się znaczkom implikacji \(\displaystyle{ \left( \alpha \Rightarrow \beta \right)}\) i negacji \(\displaystyle{ \neg \alpha }\) możemy zrozumieć, że każda taka formuła o rozmiarze \(\displaystyle{ 3}\) powstaje z dwóch formuł o rozmiarze \(\displaystyle{ 1}\) poprzez połącznie ich spójnikiem \(\displaystyle{ \Rightarrow;}\) albo powstaje z dwóch formuł o rozmiarach \(\displaystyle{ 2}\) i \(\displaystyle{ 0}\) lub o rozmiarach \(\displaystyle{ 0}\) i \(\displaystyle{ 2}\) poprzez połącznie ich spójnikiem \(\displaystyle{ \Rightarrow}\); albo powstaje z jednej formuły o rozmiarze \(\displaystyle{ 2}\) poprzez dodanie spójnika negacji \(\displaystyle{ \neg}\) . Co więcej, każda taka formuła, powstaje tylko w jeden sposób. Stąd otrzymujemy wzór:
\(\displaystyle{ f_3= f_1 \cdot f_1+2f_2+f_2= f_1 ^{2}+3f_2.}\)
Dla formuł o rozmiarze \(\displaystyle{ 2}\), mamy podobnie:
Przyglądając się znaczkom implikacji i negacji możemy zrozumieć, że każda taka formuła o rozmiarze \(\displaystyle{ 2}\) powstaje z dwóch formuł z których jedna ma rozmiar \(\displaystyle{ 1}\), a druga ma rozmiar \(\displaystyle{ 0}\), poprzez połączenie ich znakiem implikacji (również uwzględniamy tu możliwość, że pierwsza taka formuła ma rozmiar \(\displaystyle{ 0}\), a druga ma rozmiar \(\displaystyle{ 1}\)); albo powstaje z formuły o rozmiarze \(\displaystyle{ 1}\) poprzez dodanie negacji \(\displaystyle{ \neg }\).
A zatem:
\(\displaystyle{ f_2= 1 \cdot f_1+ f_1 \cdot 1+f_1= 3f_1.}\)
Zauważmy, że są dokładnie dwie formuły o rozmiarze \(\displaystyle{ 1}\)( są to \(\displaystyle{ \neg x}\) oraz \(\displaystyle{ x \Rightarrow x}\) ); oraz jest dokładnie jedna formuła o rozmiarze \(\displaystyle{ 0}\)- jest to: \(\displaystyle{ x.}\)
W związku z czym:
\(\displaystyle{ f_3= f_1 ^{2}+3f_2= 3f_2 +f_1 ^{2}= 9f_1+ f_1 ^{2}= 9 \cdot 2+ 2 ^{2}= 22.}\)
Skoro jest ich niewiele, to możemy wszystkie je wypisać; oto:
LISTA TAKICH FORMUŁ::
Jeszcze jedno zadanie z ważniaka:
Wpierw przypomnijmy, że spójnik binarny \(\displaystyle{ \circ}\) nazywamy przemiennym, jeśli zawsze zachodzi równoważność:
\(\displaystyle{ x\circ y \Leftrightarrow y\circ x}\).
I mamy zadanie:
Ile spójników binarnych jest przemiennych?
Wypisz je wszystkie. ROZWIĄZANIE:
Dla spójnika \(\displaystyle{ \circ}\) istotne jest tylko aby było: \(\displaystyle{ 1\circ 0= 0\circ 1,}\) gdyż dla pozostałych układów \(\displaystyle{ \left( 1,1\right)}\) i \(\displaystyle{ \left( 0,0\right)}\) równoważność oczywiście zachodzi.
Spójniki binarne wygodnie jest przedstawiać w tabeli kwadratowej, np. alternatywa ma następującą tabelę:
\(\displaystyle{ \begin{array}{|c|c|c|}
\hline \vee & 0 & 1 \\ \hline
0 & 0 & 1 \\ \hline
1 & 1 & 1 \\ \hline
\end{array}}\)
Warunek przemienności oznacza, że wartość spójnika \(\displaystyle{ \circ}\) w polu \(\displaystyle{ \left( 0,1\right)}\) jest równa wartości w polu \(\displaystyle{ \left(1,0 \right).}\) Ponieważ pozostałe możliwości są nieistotne, to mamy \(\displaystyle{ \left( 2 \cdot 2\right) \cdot 2=8}\) możliwości (w pozostałych dwóch polach możemy wybrać \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\)), a w polach \(\displaystyle{ \left( 0,1\right)}\) i \(\displaystyle{ \left( 1,0\right)}\) mamy wspólną wartość (\(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\)), skąd mamy \(\displaystyle{ 8}\) spójników przemiennych. Są nimi:
\(\displaystyle{ 1. \ F \ (\hbox{ spójnik fałszu}); \\
2. \ \wedge. \\
3. \ XOR. \\
4. \ \vee. \\
5. \ NOR. \\
6. \ \Leftrightarrow . \\
7. \ NAND. \\
8. \ T \ ( \hbox{spójnik prawdy}).\square}\)
Jeszcze jedno (fenomenalne- jest to fenomenalny dowód) zadanie z ważniaka:
Jakie funkcje binarne da się zdefiniować przy pomocy jedynie spójnika implikacji \(\displaystyle{ \Rightarrow }\) oraz zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\) ??
Zauważmy najpierw równoważność:
\(\displaystyle{ x \vee y \Leftrightarrow \left( x \Rightarrow y\right) \Rightarrow y.}\)
Gdyż:
Lewa strona jest fałszywa, dokładnie wtedy, gdy \(\displaystyle{ x=0}\) i \(\displaystyle{ y=0. }\)
Prawa strona natomiast jest fałszywa, dokładnie wtedy, gdy implikacja \(\displaystyle{ x \Rightarrow y}\) jest wartościowa na \(\displaystyle{ 1}\), a zmienna \(\displaystyle{ y}\) na \(\displaystyle{ 0}\). W takim przypadku \(\displaystyle{ x}\) nie może być wartościowane na \(\displaystyle{ 1}\), a więc to zachodzi dokładnie wtedy, gdy (gdyż implikacja o fałszywym poprzedniku jest zawsze prawdziwa), więc to zachodzi dokładnie wtedy, gdy: \(\displaystyle{ x}\) jest wartościowane na \(\displaystyle{ 0}\), i \(\displaystyle{ y}\) jest wartościowane na \(\displaystyle{ 0}\).
A zatem, lewa strona równoważności jest fałszywa, dokładnie wtedy, gdy prawa strona jest fałszywa, a więc te formuły są równoważne.
Przejdźmy do naszego zadania:
ROZWIĄZANIE:
Rozważmy, po kolei, najkrótsze formuły zbudowane ze zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\) oraz ze spójnika implikacji \(\displaystyle{ \Rightarrow .}\)
Formuły \(\displaystyle{ x}\) oraz \(\displaystyle{ y ,}\) definiują funkcje binarne będące rzutowaniami, które oznaczymy jako \(\displaystyle{ f_{x}}\) oraz \(\displaystyle{ f_{y}}\). Kolejne formuły to: \(\displaystyle{ x\Rightarrow x}\), oraz \(\displaystyle{ y\Rightarrow y}\), obydwie one są tautologiami, więc definiują one funkcję stałą, stale równą \(\displaystyle{ 1}\), którą oznaczymy przez \(\displaystyle{ f_{T}}\). Kolejne formuły \(\displaystyle{ x\Rightarrow y}\) oraz \(\displaystyle{ y\Rightarrow x}\), definiują funkcję które oznaczymy przez \(\displaystyle{ f_{x\Rightarrow y}}\) i \(\displaystyle{ f_{y\Rightarrow x}}\). Wśród formuł o dwóch spójnikach znajdziemy formuły \(\displaystyle{ (x\Rightarrow y)\Rightarrow y)}\) oraz \(\displaystyle{ (y\Rightarrow x)\Rightarrow x}\), które, na mocy powyżej wspomnianej równoważności, definiują alternatywę \(\displaystyle{ x \vee y}\), której funkcję binarną oznaczymy jako: \(\displaystyle{ f _{x \vee y}}\).
Można łatwo sprawdzić, że każda z pozostałych formuł o dwóch spójnikach definiuje jedną z funkcji wymienionych wcześniej (na mocy prawa: \(\displaystyle{ \left( a \Rightarrow \left( b \Rightarrow c\right)\right) \Leftrightarrow \left( \left( a \wedge b\right) \Rightarrow c\right) }\)).
Pokażemy teraz, że przy pomocy implikacji można zdefiniować co najwyżej \(\displaystyle{ 6}\) funkcji binarnych; zbiór takich funkcji binarnych oznaczymy jako \(\displaystyle{ F _{ \Rightarrow }. }\)
W tym celu:
Wykażemy teraz indukcyjnie, że dowolna formuła zbudowana ze zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\) oraz spójnika implikacji, której ostatnią zmienną jest \(\displaystyle{ x}\), to każde wartościowanie które ostatnią zmienną \(\displaystyle{ x}\) wartościuje na \(\displaystyle{ 1}\), wtedy, przy takim wartościowaniu, cala formuła przyjmuje wartość \(\displaystyle{ 1}\).
Niech \(\displaystyle{ \gamma}\) będzie dowolną formułą z \(\displaystyle{ F _{ \Rightarrow }, }\) której ostatnią zmienną jest \(\displaystyle{ x}\). Wykażemy, że każde wartościowanie \(\displaystyle{ w}\), które zmiennej \(\displaystyle{ x}\) przypisuje \(\displaystyle{ 1}\), również całej formule \(\displaystyle{ \gamma}\) przypisuje wartość \(\displaystyle{ 1.}\)
Dowód jest indukcyjny, ze względu na ilość wystąpień spójnika \(\displaystyle{ \Rightarrow }\).
Jeśli spójnik \(\displaystyle{ \Rightarrow}\) ma \(\displaystyle{ 0}\) wystąpień, to jedyną formułą, której ostatnią zmienną jest \(\displaystyle{ x}\) jest formuła: \(\displaystyle{ \gamma=x}\). Wtedy każde wartościowanie, które zmiennej \(\displaystyle{ x}\) przypisuje wartość \(\displaystyle{ 1}\), wartościuje również formule \(\displaystyle{ \gamma=x}\) na \(\displaystyle{ 1}\). Badana własność jest więc spełniona.
Krok indukcyjny:
Niech \(\displaystyle{ n}\) będzie liczbą naturalną, taką, że: \(\displaystyle{ n>0}\).
Przypuśćmy, że wszystkie formuły o ilości spójników \(\displaystyle{ \Rightarrow}\) mniejszej od \(\displaystyle{ n}\) mają żądaną własność. Pokażemy, że wszystkie formuły w których jest dokładnie \(\displaystyle{ n}\) spójników \(\displaystyle{ \Rightarrow}\) mają żądaną własność.
Niech \(\displaystyle{ \gamma}\) będzie dowolną formułą w której jest dokładnie \(\displaystyle{ n}\) spójników \(\displaystyle{ \Rightarrow}\) , i w której ostatnią zmienną jest \(\displaystyle{ x}\). Niech \(\displaystyle{ w}\) będzie wartościowaniem, które zmiennej \(\displaystyle{ x}\) przypisuje \(\displaystyle{ 1}\). Pokażemy, że przy tym wartościowaniu formuła \(\displaystyle{ \gamma}\) przyjmuje wartość \(\displaystyle{ 1}\). Ponieważ \(\displaystyle{ n>0}\), a rozpatrujemy tutaj tylko spójnik \(\displaystyle{ \Rightarrow}\), to któraś implikacja jest 'ostatnia, a więc formuła formuła \(\displaystyle{ \gamma}\) jest postaci \(\displaystyle{ \gamma= \alpha \Rightarrow \beta}\) . Przyglądając się takim znaczkom możemy zrozumieć , że wtedy zmienna \(\displaystyle{ x}\) jest również ostatnia we formule \(\displaystyle{ \beta}\). Przyglądając się takim znaczkom, ponieważ formuła \(\displaystyle{ \gamma}\) ma dokładnie \(\displaystyle{ n}\) spójników \(\displaystyle{ \Rightarrow}\) , więc widzimy, że formuła \(\displaystyle{ \beta}\) ma mniej niż \(\displaystyle{ n}\) spójników \(\displaystyle{ \Rightarrow}\), a więc, na mocy założenia indukcyjnego otrzymujemy, że każde wartościowanie które zmiennej \(\displaystyle{ x}\) przypisuje wartość \(\displaystyle{ 1}\) również formule \(\displaystyle{ \beta}\) przypisuje wartość \(\displaystyle{ 1}\), a więc w szczególności, ponieważ \(\displaystyle{ w\left( x\right)=1}\), więc również \(\displaystyle{ w\left( \beta \right)=1}\). Z własności implikacji mówiącej, że jeśli następnik implikacji jest prawdziwy, to cala implikacja jest prawdziwa (można łatwo się o tym przekonać) otrzymujemy, że formuła \(\displaystyle{ \gamma = \alpha \Rightarrow \beta}\) jest wartościowana na \(\displaystyle{ 1}\), przy wartościowaniu \(\displaystyle{ w,}\) co należało pokazać. Wobec dowolności wyboru wartościowania \(\displaystyle{ w}\) oraz formuły \(\displaystyle{ \gamma}\) krok indukcyjny został dowiedziony.
Zasada indukcji matematycznej dowodzi, że badana własność zachodzi dla dowolnej liczby wystąpień spójnika \(\displaystyle{ \Rightarrow.}\)
Analogicznie można udowodnić, że dla dowolnej formuły \(\displaystyle{ \gamma}\) z \(\displaystyle{ F _{ \Rightarrow } }\), której ostatnią zmienną w tej formule \(\displaystyle{ \gamma}\) jest \(\displaystyle{ y}\), to każde wartościowanie które zmiennej \(\displaystyle{ y}\) przypisuje wartość \(\displaystyle{ 1}\), również całej formule \(\displaystyle{ \gamma}\) przypisuje wartość \(\displaystyle{ 1}\)- można to analogicznie udowodnić (indukcyjnie).
Wiemy zatem, że jeśli formuła zbudowana ze zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\) oraz spójnika implikacji kończy się zmienną wartościowaną na \(\displaystyle{ 1}\), to cala formuła jest wartościowana na \(\displaystyle{ 1}\). Oznacza to, że w tabeli funkcji binarnej ostatni wiersz jest stale równy \(\displaystyle{ 1}\) lub ostatnia kolumna jest stale równa \(\displaystyle{ 1}\). Takich tabel jest dokładnie \(\displaystyle{ 6}\), gdyż jeśli ostatni wiersz jest stale równy \(\displaystyle{ 1}\) :
\(\displaystyle{ \begin{array}{|c|c|c|}
\hline & 0 & 1 \\ \hline
0 & & \\ \hline
1 & 1 & 1 \\ \hline
\end{array}}\)
to mamy cztery możliwości,
w przeciwnym przypadku mamy, że ostatnia kolumna jest stale równa \(\displaystyle{ 1}\) i w dolnym wierszu mamy \(\displaystyle{ 0}\):
\(\displaystyle{ \begin{array}{|c|c|c|}
\hline & 0 & 1 \\ \hline
0 & & 1 \\ \hline
1 & 0 & 1 \\ \hline
\end{array}}\)
kolejne dwie możliwości.
Łącznie mamy sześć możliwości.
Wobec czego przy pomocy implikacji nie da się zdefiniować więcej niż \(\displaystyle{ 6}\) funkcji binarnych, a sześć funkcji binarnych udało nam się znaleźć. Wobec czego wskazane sześć funkcji binarnych: \(\displaystyle{ f_{x}, f_{y}, f _{T}, f _{x \Rightarrow y}, f _{y \Rightarrow x} , f _{x \vee y}; }\) są funkcjami które można zdefiniować przy pomocy samej implikacji.\(\displaystyle{ \square}\)
Podkreślmy jeszcze fenomen tego dowodu:
Po krótkich rozważaniach udało nam się wskazać \(\displaystyle{ 6}\) funkcji binarnych, a potem okazało się, że nie da się zdefiniować więcej niż \(\displaystyle{ 6}\) takich funkcji. Oznacza to, że trafiliśmy doskonale te \(\displaystyle{ 6}\) funkcji binarnych, co było trzeba. Co za strzał.
Dodajmy jeszcze, że:
Jeśli mamy udowodnione prawo odnośnie zaprzeczania koniunkcji:
\(\displaystyle{ \neg \left( \alpha \wedge \beta \right) \Leftrightarrow \left( \neg \alpha \right) \vee \left( \neg \beta \right),}\)
to możemy udowodnić drugie prawo de Morgana odnośnie zaprzeczania alternatywy :
\(\displaystyle{ \neg \left( \alpha \vee \beta \right) \Leftrightarrow \left( \neg \alpha\right) \wedge \left( \neg \beta\right) ;}\)
gdyż (wynika to z prawa: \(\displaystyle{ \neg \left( \neg \alpha \right) \Leftrightarrow \alpha}\) ),
gdyż :
DOWÓD TEGO FAKTU:
Podstawiając w pierwszym prawie za \(\displaystyle{ \alpha}\) podstawiając \(\displaystyle{ \neg \alpha}\) , a za \(\displaystyle{ \beta}\) podstawiając \(\displaystyle{ \neg \beta}\) otrzymujemy równoważność:
\(\displaystyle{ \neg \left( \neg \alpha \wedge \neg \beta \right) \Leftrightarrow \neg \left( \neg \alpha \right) \vee \neg \left( \neg \beta \right); }\)
Stosując dwukrotnie do prawej strony prawo o negacji negacji danej formuły, otrzymujemy:
\(\displaystyle{ \neg \left( \neg \alpha \wedge \neg \beta \right) \Leftrightarrow \alpha \vee \beta ; }\)
Zaprzeczając obie strony, otrzymujemy:
\(\displaystyle{ \left( \neg \alpha \wedge \neg \beta \right) \Leftrightarrow \neg \left( \neg \left( \neg \alpha \wedge \neg \beta \right) \right) \Leftrightarrow \neg \left( \alpha \vee \beta \right).\square }\)
Na koniec dodajmy, takie nieznane prawo, mówiące, że jeśli dwie formuły \(\displaystyle{ \alpha}\) i \(\displaystyle{ \beta}\) są równoważne: \(\displaystyle{ \alpha \Leftrightarrow \beta }\) , to ich koniunkcja jest równoważna obydwóm składnikom tej koniunkcji: \(\displaystyle{ \left( \alpha \wedge \beta\right) \Leftrightarrow \alpha, \beta; }\)
a ich alternatywa jest wtedy równoważna obydwóm składnikom tej alternatywy: \(\displaystyle{ \left( \alpha \vee \beta \right) \Leftrightarrow \alpha , \beta.}\)
Można łatwo się o tym przekonać.
