Niech
\(\displaystyle{ \circ}\) będzie spójnikiem dwuargumentowym, takim, że zbiór
\(\displaystyle{ \left\{ \circ\right\}}\) jest funkcjonalnie pełny, czyli takim aby przy pomocy wyłącznie spójnika
\(\displaystyle{ \circ}\) można by było zdefiniować dowolny spójnik.
Wtedy spójnik
\(\displaystyle{ \circ}\) na samych wartościach
\(\displaystyle{ 1}\) nie może przyjmować wartości
\(\displaystyle{ 1}\), bo wtedy każda formuła postaci
\(\displaystyle{ \circ \left( x,x\right) }\), gdzie
\(\displaystyle{ x}\) jest zmienną, poza formułą '
\(\displaystyle{ x}\)', a dla pozostałych takich formuł zbudowanych tylko ze spójnika
\(\displaystyle{ \circ}\), wtedy byłyby one stale równe
\(\displaystyle{ 1}\), a więc nie dałoby się zdefiniować negacji przy pomocy spójnika
\(\displaystyle{ \circ}\).
Z podobnych przyczyn spójnik
\(\displaystyle{ \circ}\) na samych zerach nie może przyjmować wartości zero.
Wynika stąd, że musi zachodzić:
\(\displaystyle{ \circ \left( x,x\right) \Longleftrightarrow \neg x}\).
(*)
Przyjmijmy, że:
\(\displaystyle{ \overline{0}= 1}\) i
\(\displaystyle{ \overline{1}=0}\)- jest to zamiana wartości zero-jedynkowych.
Notację tą rozszerzymy na spójniki dwuargumentowe, tzn.:
Dla
\(\displaystyle{ x= \left( x_1, x_2 \right)}\), gdzie
\(\displaystyle{ x_1,x _{2} \in \mathbb{B}= \left\{ 0,1\right\} }\), to definiujemy:
\(\displaystyle{ \overline {x}= \overline{\left( x_1, x_2 \right) }= \left( \overline{x_1}, \overline{x_2}\right) .}\)
Jest to układ zero-jedynkowy o 'przeciwnych' wartościach.
Pokażemy, że dowolny spójnik dwuargumentowy, spełniający
(*) (bo wiemy już, że dla badanych spójników jest to warunek konieczny) pozwala zdefiniować wszystkie inne spójniki, wtedy i tylko wtedy, gdy istnieje para zero-jedynkowa
\(\displaystyle{ x}\), taka, że:
\(\displaystyle{ \circ \left( x\right) = \circ \left( \overline{x}\right).}\)
Tzn. przy pomocy spójnika
\(\displaystyle{ \circ}\) można zdefiniować wszystkie inne spójniki, jeśli na samych zerach daje on wartość jeden, a na samych jedynkach daje on wartość zero, i gdy jest możliwe, aby wartość tego spójnika na pewnej parze była taka sama, jak wartość tego spójnika na parze zupełnie przeciwnej ( zgodnie z wprowadzoną notacją )- to wtedy przy pomocy spójnika
\(\displaystyle{ \circ}\) można zdefiniować dowolny spójnik.
Aby to pokazać, to:
Niech
\(\displaystyle{ \circ }\) będzie spójnikiem dwuargumentowym spełniającym
\(\displaystyle{ }\)(*).
Zaczniemy od pokazania, że jeżeli nie istnieje taka para zero-jedynkowa, to nie wszystkie spójniki można zdefiniować przy pomocy spójnika
\(\displaystyle{ \circ}\).
W takim wypadku, dla każdej pary
\(\displaystyle{ x=\left( x_1, x_2\right)}\) zero-jedynkowej, mamy:
\(\displaystyle{ \overline{\circ \left( x\right)} = \circ \left( \overline{x}\right) .}\)
A zatem zmiana wartościowania zmiennych dla tego spójnika na 'przeciwne' zmienia również wartość formuły na przeciwną. Nie jest więc zaskakującym, że dla dowolnego spójnika zbudowanego wyłącznie ze spójnika
\(\displaystyle{ \circ}\) również tak jest. Wobec czego nie jest możliwe zdefiniowania funkcji stale fałszywej
\(\displaystyle{ F}\), bo jakkolwiek by ona nie była zdefiniowana, to możemy zmienić wartościowanie zmiennych na przeciwne, i wtedy, zgodnie z powyższym, zmieni się wtedy również wartość formuły na przeciwną, a ona jest stale fałszywa, więc nie może się zmienić- sprzeczność. Wobec czego nie jest możliwe zdefiniowanie funkcji fałszu przy pomocy spójnika
\(\displaystyle{ \circ}\), a więc nie wszystkie spójniki można zdefiniować przy pomocy spójnika
\(\displaystyle{ \circ.}\)
Pokażemy teraz, że jeśli istnieje przynajmniej jedna para zero-jedynkowa
\(\displaystyle{ x}\), dla której
\(\displaystyle{ \circ \left( x\right) =\circ\left( \overline{x} \right)}\), to zbiór
\(\displaystyle{ \left\{ \circ\right\}}\) będzie funkcjonalnie pełny, czyli wszystkie spójniki będzie można zdefiniować przy pomocy spójnika
\(\displaystyle{ \circ. }\)
Niech
\(\displaystyle{ x=\left( x_1, x_2\right)}\) będzie taką parą.
Zdefiniujmy spójnik dwuargumentowy
\(\displaystyle{ \oplus}\) w następujący sposób:
\(\displaystyle{ a\oplus b \Longleftrightarrow \circ \left( w_1, w_2\right) , \hbox{ gdzie: } w_i= a, \hbox{ gdy } x_i=1, \hbox{ i } w_i= b, \hbox{ gdy } x_i=0. }\)
Wtedy
\(\displaystyle{ w_i \in \left\{ a,b\right\}}\), więc możemy podstawiać za
\(\displaystyle{ a}\) i za
\(\displaystyle{ b}\) zera i jedynki, i tak samo możemy podstawiać po prawej stronie równoważności zera i jedynki jako argumenty spójnika
\(\displaystyle{ \circ}\), możemy odpowiednio za
\(\displaystyle{ a}\) i za
\(\displaystyle{ b}\) podstawiać wartości prawdy i fałszu, i wartość logiczna naszego spójnika
\(\displaystyle{ \circ}\) na tym układzie będzie wartością logiczną definiowanego spójnika
\(\displaystyle{ \oplus.}\)
Jeśli
\(\displaystyle{ a=b=0}\), to
\(\displaystyle{ w_i \in \left\{ 0\right\} }\), a zatem
\(\displaystyle{ w_1= w_2=0}\), a zatem:
\(\displaystyle{ a\oplus b \Leftrightarrow \circ \left( 0,0\right) = 1.}\)
Podobnie jeśli:
\(\displaystyle{ a=b=1}\), to
\(\displaystyle{ w _{i} \in \left\{ 1\right\}}\), skąd
\(\displaystyle{ w _{1}= w _{2}=1,}\) i:
\(\displaystyle{ a\oplus b \Leftrightarrow \circ \left( 1,1\right)= 0.}\)
Ponieważ
\(\displaystyle{ \circ \left( x\right) =\circ \left( \overline{x}\right)}\), to w pozostałym wypadku spójnik
\(\displaystyle{ \oplus}\) przyjmuje stała wartość
\(\displaystyle{ c \in \left\{ 0,1\right\}}\), a więc możemy go opisać tabelą:
\(\displaystyle{ \begin{array}{|c|c|c|}
\hline
\oplus & 0 & 1 \\ \hline
0 & 1 & c \\ \hline
1 & c & 0 \\ \hline
\end{array}}\)
W zależności od wartości
\(\displaystyle{ c \in \left\{ 0,1\right\}}\), to:
\(\displaystyle{ \oplus \in \left\{ NAND, NOR\right\}.\square}\)
Jako uzupełnienie dodam, że stosunek ilości wszystkich
\(\displaystyle{ n}\)-argumentowych spójników
\(\displaystyle{ \circ}\), takich, że przy pomocy tylko spójnika
\(\displaystyle{ \circ}\) można zdefiniować dowolny spójnik, do ilości wszystkich spójników
\(\displaystyle{ n}\)- argumentowych dąży do
\(\displaystyle{ \frac{1}{4}}\); co oznacza, że dla dużych ustalonych numerów
\(\displaystyle{ n}\), blisko co czwarty spójnik
\(\displaystyle{ n}\)- argumentowy
\(\displaystyle{ \circ}\) ma tą własność, że przy pomocy tylko spójnika
\(\displaystyle{ \circ}\) można zdefiniować dowolny spójnik. Ja myślę, że ciekawym jest już, że w ogóle takie spójnika istnieją (no tak, istnieją: np. dwuargumentowy spójnik
\(\displaystyle{ NAND}\), i dwuargumentowy spójnik
\(\displaystyle{ NOR}\)), a tu mamy taki fenomen, że dla dużych numerów
\(\displaystyle{ n}\) blisko co czwarty spójnik
\(\displaystyle{ n}\) argumentowy ma taką własność- ten zadziwiający fakt udowodniłem tutaj:
TRUDNA GRANICA. 