Funktory Sheffera i Peircea

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
junmisugi
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 8 gru 2022, o 23:40
Płeć: Mężczyzna
wiek: 27

Funktory Sheffera i Peircea

Post autor: junmisugi »

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ł?
Jan Kraszewski
Administrator
Administrator
Posty: 34208
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5197 razy

Re: Funktory Sheffera i Peircea

Post autor: Jan Kraszewski »

Zacznij od zdefiniowania negacji.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1399
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Funktory Sheffera i Peircea

Post autor: Jakub Gurak »

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. 8-)
ODPOWIEDZ