Wykazać, że funktory Sheffera i Peircea to jedyne dwa funktory dwuargumentowe, przy pomocy, których można zdefiniować podane
funkcje logiczne.
Nie wiem jak do końca się za to zabrać, ktoś ma jakiś pomysł?
Funktory Sheffera i Peircea
-
Jan Kraszewski
- Administrator
- Posty: 34296
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
-
Jakub Gurak
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Funktory Sheffera i Peircea
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.
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.