Przypomnę najpierw, że spójnikiem \(\displaystyle{ k}\)-argumentowym, gdzie \(\displaystyle{ k=1,2,3,\ldots}\) nazywamy dowolną funkcję, która każdemu ciągowi \(\displaystyle{ k}\)-wyrazowemu złóżonemu z \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\) przypisuje \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) (gdzie \(\displaystyle{ 0}\) oznacza fałsz, \(\displaystyle{ 1}\) oznacza prawdę- oczywiście).
Oto przykład spójnika trójargumentowego:
Czyli w zależności od wartości zdań składowych spójnik zwraca wartość prawdy bądź fałszu.
Przedstawię swój pomysł (który wydaje się być zgodny z dowodem z ważniaka, ale nie wiem).
Niech \(\displaystyle{ k\in\NN_+}\), i niech \(\displaystyle{ \circ}\) będzie dowolnym spójnikiem \(\displaystyle{ k}\)-argumentowym. Niech \(\displaystyle{ F}\) będzie zbiorem wszystkich układów na których spójnik \(\displaystyle{ \circ}\) przyjmuje wartość prawdy( jeśli ten zbiór jest pusty, czyli mówiąc normalniej spójnik \(\displaystyle{ \circ}\) przymuje zawsze wartość fałszu, to możemy go przedstawić jako \(\displaystyle{ \circ(x _{1},\ldots,x_k ) =x_1 \wedge \left( \neg x_1\right) }\) ). Rozważmy dowolny taki układ \(\displaystyle{ (x_1,x_2,\ldots, x_k)}\). Będziemy łączyć te zmienne koniunkcją, z tą różnicą, że gdy \(\displaystyle{ x=0}\), to zamiast \(\displaystyle{ x}\) jako składnik koniunkcji, będziemy brać (\(\displaystyle{ \neg x}\)), i łączymy te literały koniunkcją. Otrzymujemy zatem formułę odpowiadającą temu wierszowi. Postępujemy tak dla dowolnego wiersza z \(\displaystyle{ F}\). A następnie łączymy te wiersze spójnikiem alternatywy (gdyż mamy przypadki układów dla których spójnik \(\displaystyle{ \circ}\) przyjmuje wartość prawdy, więc te przypadki łączymy spójnikiem lub). Tak wygląda konstrukcja. Jedynymi użytymi tutaj spójnikami są \(\displaystyle{ \wedge, \neg , \vee.}\)
Ten bardzo ogólny fakt można łatwo wzmocnić, tzn. z niego wiele wynika, np.
Zbiory \(\displaystyle{ \left\{ \wedge , \neg \right\} ,\left\{ \vee , \neg \right\} }\) są również funkcjonalnie pełne (zbiór \(\displaystyle{ \left\{ \wedge , \neg \right\}}\) jest funkcjonalnie pełny, tzn. że przy pomocy jedynie spójników \(\displaystyle{ \wedge , \neg}\) można zdefiniować dowolny spójnik (niekoniecznie dwuargumentowy, również trzy- i więcej argumentowy), podobnie przy pomocy jedynie spójników \(\displaystyle{ \vee , \neg}\) można zdefiniować dowolny spójnik).
Dowód:
Dowód wynika z praw de Morgana. Mamy \(\displaystyle{ \neg \left( x \vee y\right) = \neg x \wedge \neg y.}\)
Wobec czego \(\displaystyle{ x \vee y= \neg \left( \neg \left( x \vee y\right)\right) = \neg \left( \neg x \wedge \neg y.\right) }\)
A więc zdefiniowaliśmy alternatywę przy pomocy spójników \(\displaystyle{ \neg , \wedge}\) . Ponieważ \(\displaystyle{ \left\{ \wedge , \neg \right\} \cup \left\{ \vee \right\} =\left\{ \wedge , \neg,\vee\right\}}\), a ten zbiór jest funkcjonalnie pełny więc również zbiór \(\displaystyle{ \left\{ \wedge , \neg \right\} }\) jest funkcjonalnie pełny.
Podobnie aby wykazać, że zbiór \(\displaystyle{ \left\{ \vee , \neg \right\}}\) zdefiniujemy koniunkcję przy pomocy spójników alternatywy i negacji, czyli przy pomocy dozwolonych spójników. Z praw de Morgana otrzymujemy
\(\displaystyle{ \neg \left( x \wedge y\right)= \neg x \vee \neg y, }\) a zatem
\(\displaystyle{ x \wedge y= \neg \left( \neg \left( x \wedge y\right)\right) = \neg \left( \neg x \vee \neg y\right) }\),
A więc zdefiniowaliśmy koniunkcję przy pomocy spójników \(\displaystyle{ \neg , \vee }\). Zatem ponieważ zbiór \(\displaystyle{ \left\{ \wedge , \vee , \neg \right\}}\) jest funkcjonalnie pełny, więc również nasz zbiór \(\displaystyle{ \left\{ \vee , \neg \right\}}\) jest funkcjonalnie pełny.\(\displaystyle{ \square}\)
Na koniec wykażemy, że zbiór \(\displaystyle{ \left\{ \Rightarrow , \neg \right\} }\) jest funkcjonalnie pełny.
W tym celu zdefiniujemy alternatywę przy pomocy dostępnych spójników ( \(\displaystyle{ \Rightarrow , \neg}\) ). Mamy
prawo:
\(\displaystyle{ x \Rightarrow y= \neg x \vee y.}\)
Wobec czego również
\(\displaystyle{ \left( \neg x\right) \Rightarrow y= \neg \left( \neg x \right) \vee y=x \vee y,}\)
a więc zdefiniowaliśmy alternatywę za pomocą dostępnych spójników. Ponieważ zbiór \(\displaystyle{ \left\{ \vee , \neg \right\}}\) jest funkcjonalnie pełny, więc również \(\displaystyle{ \left\{ \Rightarrow , \neg \right\}}\) jest funkcjonalnie pełny. \(\displaystyle{ \square}\)