Informatyka MIMUW

W ćwiczeniu 4.2 pokazaliśmy, że
\( \displaystyle p\Rightarrow q \equiv \neg p \vee q, \)
wobec tego
\( \displaystyle (\neg p)\Rightarrow q \equiv \neg \vee q. \)
Udało nam się więc zdefiniować alternatywę za pomocą dostępnych spójników, wobec czego zgodnie z twierdzeniem 5.3 możemy również zdefiniować wszystkie inne funkcje boolowskie. Wynika stąd, że zbiór \( \displaystyle \{\Rightarrow, \neg\} \) jest funkcjonalnie pełny.

Analogicznie do dowodu w twierdzeniu 5.4 pokażemy, że przy pomocy \( \displaystyle NAND \) można zdefiniować \( \displaystyle \neg \) oraz \( \displaystyle \wedge \). Wtedy z twierdzenia 5.3 otrzymamy, że zbiór \( \displaystyle \{NAND\} \) jest funkcjonalnie pełny.
Z definicji spójnika \( \displaystyle NAND \) 4.6 łatwo wynika, że
\( \displaystyle p NAND p \equiv \neg p. \)
W ćwiczeniu 4.2 pokazaliśmy, że
\( \displaystyle p NAND q \equiv \neg (p \wedge q). \)
Wobec tego
\( \displaystyle \neg p NAND q\equiv p \wedge q. \)
i po zapisaniu \( \displaystyle \neg \) za pomocą \( \displaystyle NAND \) otrzymujemy
\( \displaystyle (p NAND q) NAND (p NAND q) \equiv p\wedge q \)

Łatwo sprawdzić, że formuła \( (p \Rightarrow q) \Rightarrow q \) jest równoważna formule \( p\vee q \).

Rozważmy po kolei najmniejsze formuły zbudowane z dwóch zmiennych \( \displaystyle p \) i \( \displaystyle q \). Formuły \( \displaystyle p \) oraz \( \displaystyle q \) definiują funkcje binarne będące rzutowaniami, które oznaczymy przez \( \displaystyle f_p \) oraz \( \displaystyle f_q \). Kolejne formuły to \( \displaystyle p \Rightarrow p \), \( \displaystyle q \Rightarrow q \), obydwie one są tautologiami, więc definiują funkcję stale równą 1, którą oznaczymy przez \( \displaystyle f_T \). Kolejne \( \displaystyle p\Rightarrow q \) oraz \( \displaystyle q\Rightarrow p \) definiują funkcje które oznaczymy przez \( \displaystyle f_{p \Rightarrow q}, f_{p\Rightarrow q} \). Wśród formuł o trzech spójnikach znajdziemy formuły opisujące funkcję \( \displaystyle f_{p \vee q} \), zgodnie z poprzednim ćwiczeniem są to formuły \( \displaystyle (p \Rightarrow q) \Rightarrow q) \) oraz \( \displaystyle (q \Rightarrow p) \Rightarrow p) \). Dociekliwi mogą sprawdzić, że każda z pozostałych formuł o trzech spójnikach definiuje którąś z funkcji opisanych wcześniej. Pokażemy teraz, że każda funkcja zdefiniowana przy pomocy implikacji jest którąś funkcji \( \displaystyle f_p,f_q,f_T,f_{p \Rightarrow q},f_{q \Rightarrow p}, f_{p\vee q} \). Zbiór tych funkcji oznaczymy przez \( \displaystyle F_\Rightarrow \). Pokażemy teraz, że przy pomocy implikacji można zdefiniować co najwyżej 6 różnych funkcji binarnych. Zaczniemy od prostej obserwacji, że każda formuła zbudowana jedynie z implikacji przyjmuje wartość 1, jeśli zmienne są wartościowane na 1. Pokażemy nawet więcej.
Niech \( \displaystyle \Phi \) będzie dowolną formułą o zmiennych \( \displaystyle p,q \) zbudowaną jedynie przy pomocy spójnika \( \displaystyle \Rightarrow \). Jeśli \( \displaystyle p \) jest ostatnią zmienną występującą w \( \displaystyle \Phi \) to każde wartościowanie które wartościuje \( \displaystyle p \) na 1 wartościuje również \( \displaystyle \Phi \) na 1. Przeprowadzimy dowód indukcyjny ze względu na ilość wystąpień spójnika \( \displaystyle \Rightarrow \).

1. Baza indukcji. Jeśli \( \displaystyle \Rightarrow \) ma zero wystąpień to jedyną formułą w której ostatnią zmienną jest \( \displaystyle p \) jest formuła \( \displaystyle p \). Badana własność jest oczywiście spełniona.
2. Krok indukcyjny. Niech \( \displaystyle n\in \) takie, że \( \displaystyle n>0 \). Przypuśćmy, że wszystkie formuły o mniejszej liczbie spójników od \( \displaystyle n \) mają żądaną własność. Weźmy dowolną formułę \( \displaystyle \Phi \) o \( \displaystyle n \) spójnikach, w której ostatnią występującą zmienną jest \( \displaystyle p \). Ponieważ \( \displaystyle n>0 \) to \( \displaystyle \Phi \) jest postaci \( \displaystyle \phi \Rightarrow \psi \). Ponieważ \( \displaystyle p \) jest również ostatnią zmienną w \( \displaystyle \psi \) oraz w \( \displaystyle \psi \) jest mniej niż \( \displaystyle n \) spójników to z założenia indukcyjnego każde wartościowanie, które wartościuje \( \displaystyle p \) na 1, wartościuje również \( \displaystyle \psi \) na 1. Z tabeli 4.1 wynika, że również formuła \( \displaystyle \phi \Rightarrow \psi \) jest wtedy wartościowana na 1, a więc posiada badaną własność. Wobec dowolności wybory \( \displaystyle \Phi \) wszystkie formuły o \( \displaystyle n \) spójnikach posiadają badaną własność.

Analogiczny dowód dla zmiennej \( \displaystyle q \) pomijamy. Wiemy teraz że jeśli formuła zbudowana jedynie z implikacji kończy się jakąś zmienną to wartościowania tej zmiennej na 1 wartościuje całą formułę na 1. Dla tabeli funkcji binarnej oznacza to, że ostatni wiersz lub ostatnia kolumna są stale równe 1. Nietrudno sprawdzić, że tabeli o takiej własności jest dokładnie 6. Wobec tego przy pomocy implikacji nie da się zdefiniować więcej niż 6 funkcji binarnych. Oznacza to, że funkcje \( \displaystyle f_p,f_q,f_T,f_{p \Rightarrow q},f_{q \Rightarrow p}, f_{p\vee q} \) są wszystkimi funkcjami binarnymi, które da się zdefiniować przy pomocy samej implikacji.

1. Oznaczmy zbiór formuł w których jedynym spójnikiem jest \( \wedge \) przez \( F_\wedge \). Udowodnimy, że każda formuła z \( F_\wedge \) przyjmuje zawsze wartość 1, jeśli jej zmienne są wartościowane na 1. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika \( \wedge \) w formule. Dowód będzie indukcyjny ze względu na rozmiar formuły.

Baza indukcji: Każda formuła z \( F_\wedge \) o rozmiarze 0 jest postaci \( \mathrm {x} \), gdzie \( \mathrm {x} \) jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła \( \mathrm {x} \) też jest wartościowana na 1. A więc każda formuła o rozmiarze 0 ma postulowaną własność.

Krok indukcyjny: Ustalmy dowolne \( n>0 \) i przyjmijmy, że wszystkie formuły o mniejszym rozmiarze mają postulowaną własność. Niech \( \nu \) będzie dowolną formułą z \( F_\wedge \) o rozmiarze \( \mathrm {n} \). Skoro \( n>1 \) to \( \nu \) musi być postaci \( \phi\wedge \psi \). Rozważmy wartościowanie które wszyskim zmiennym przypisuje wartość 1. Ponieważ rozmiary \( {\phi} \) oraz \( {\psi} \) są silnie mniejsze od \(\mathrm {n} \) to z założenia indukcyjnego otrzymujemy, że dla naszego wartościowania obie przyjmują wartość 1. Wobec tego zgodnie z tabelą 4.2 cała formuła \( \phi\wedge \psi \) też przyjmuje wartość 1. Dowiedliśmy więc, że każda formuła o rozmiarze \( \mathrm {n} \) ma postulowaną własność.

Wiemy już że każda \( F_\wedge \) przyjmuje zawsze wartość 1, jeśli jej zmienne są wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie np. spójnika \( F \) gdyż definująca go formuła musiałby przyjąć wartość 0 na takim wartościowaniu.

2. Dowód analogiczny do poprzedniego.

Przyjrzyj się formułom zbudowanym z \( \Leftrightarrow \) toggleSH(22)

Spójnik \( \Leftrightarrow \) jest przemienny. Rozważmy formułę \( x\Leftrightarrow x \Leftrightarrow y \). Łatwo zauważyć, że definiuje ona funkcję \( f(x,y)=y \), która nie jest przemienna.

Ustalmy dowolne \( \displaystyle n>1 \). Niech \( \displaystyle \circ \) będzie spójnikiem \( \displaystyle n \) argumentowym takim, że zbiór \( \displaystyle \{\circ\} \) jest funkcjonalnie pełny. Zastanówmy się jaką funkcję unarną definiuje formuła \( \displaystyle \circ(x, \dots, x) \). Funkcja ta nie może na samych 1 dawać wartości 1, gdyż wtedy każda formuła unarna poza formułą \( \displaystyle x \) zbudowana z \( \displaystyle \circ \) byłaby stale równa 1 (indukcyjny dowód pomijamy), a więc nie dałoby się zdefiniować \( \displaystyle \neg \) przyp pomocy \( \displaystyle \circ \). Z tych samych przyczyn formuła \( \displaystyle \circ(x, \dots, x) \) na samych 0 nie może przyjmować wartości 0. Wynika stąd, że konieczne jest aby

\( \displaystyle \circ(x, \dots ,x) \equiv \neg x. \quad \mbox{(5.1)} \)

Łatwo zauważyć, że \( \displaystyle n-argumentowych \) spójników spełniających powyższą równoważność jest dokładnie \( \displaystyle 2^{2^{n}-2} \) (równoważność ta ustala wartość funkcji na dwóch wartościowaniach). Skoro wszystkie spójniki które są funkcjonalnie pełne mają powyższą własność to

\( \displaystyle P_n \leq 2^{2^{n}-2}. \)

Wynika stąd, że jeśli granica \( \displaystyle \lim_{n arrow \infty} \frac{P_n}{F_n} \) istnieje to jest nie większa od \( \displaystyle \frac{1}{4} \).

Dla dowolnego \( \displaystyle a\in \mathbb{B} \) przez \( \displaystyle \bar{a} \) będziemy oznaczać element \( \displaystyle 1-x \) (czyli \( \displaystyle \bar{0}=1 \) i \( \displaystyle \bar{1}=0 \)). Notację tą w naturalny sposób rozszerzymy na elementy \( \displaystyle \mathbb{B}^n \). Czyli dla \( \displaystyle x=(x_1,\dots,x_n) \in \mathbb{B}^n \) mamy \( \displaystyle \bar{x}= \overline{(x_1,\dots,x_n)}= (\bar{x_1},\dots,\bar{x_n}) \).

Pokażemy, że dowolny spójnik \( \displaystyle n \) argumentowy spełniający \( \mbox{(5.1)} \) pozwala zdefiniować wszystkie inne spójniki wtedy i tylko wtedy gdy istnieje \( \displaystyle x\in \mathbb{B}^n \) dla którego \( \displaystyle \circ(\bar{x})= \circ(x) \). Niech \( \displaystyle \circ \) będzie spójnikiem \( \displaystyle n \) argumentowym spełniającym \( \mbox{(5.1)} \).

Zaczniemy od pokazania, że jeśli nie istnieje taki \( \displaystyle x \) to nie wszystkie funkcje da się zdefiniować przy pomocy \( \displaystyle \circ \). W takim wypadku, dla każdego \( \displaystyle x\in \mathbb{B}^n \) mamy \( \displaystyle \circ(\bar{x})= \overline{\circ(x)} \). Z ostatniej obserwacji wynika również, że dla dowolnej formuły \( \displaystyle \phi \) zbudowanej przy pomocy \( \displaystyle \circ \), wartość \( \displaystyle \phi \) przy wartościowaniu odpowiadającym \( \displaystyle x \) jest równa wartości \( \displaystyle \neg \phi \) przy wartościowaniu odpowiadającym \( \displaystyle \bar{x} \) (prosty indukcyjny dowód tego faktu pomijamy). Oznacza to że zmiana wartościowania na "przeciwne" zmienia też wartość formuły na przeciwną. Wobec tego nie jest możliwe zdefiniowanie żadnej funkcji stałej przy pomocy \( \displaystyle \circ \), a więc zbiór \( \displaystyle \{\circ\} \) nie jest funkcjonalnie pełny.

Pokażemy teraz, że jeśli istnieje przynajmniej jeden element \( \displaystyle x\in \mathbb{B}^n \) dla którego \( \displaystyle \circ(x)=\circ(\bar{x}) \) to zbiór \( \displaystyle \{\circ\} \) jest funkcjonalnie pełny. Niech \( \displaystyle x \) będzie tym elementem. Zdefiniujemy formułę o dwóch zmiennych \( \displaystyle p \) oraz \( \displaystyle q \). Nowa formuła będzie postaci

\( \displaystyle \phi= \circ(v_1,\dots,v_n), \)

gdzie \( \displaystyle v_i \) jest zmienną p jeśli \( \displaystyle x_i \) jest równe 1 i zmienną \( \displaystyle q \) w przeciwnym przypadku. Zobaczmy jaką funkcję binarną definiuje formuła \( \displaystyle \phi \). Jeśli \( \displaystyle p \) oraz \( \displaystyle q \) są wartościowane na 0, to \( \displaystyle \phi \) jest wartościowane zgodnie z \( \displaystyle \circ(0,\dots,0) \) a więc na 1. Jeśli \( \displaystyle p \) oraz \( \displaystyle q \) są wartościowane na 1 \( \displaystyle \phi \) jest wartościowane zgodnie z \( \displaystyle \circ(1,\dots,1) \) a więc na 0. W pozostałych przypadkach wartościowanie odpowiada albo \( \displaystyle x \) albo \( \displaystyle \bar{x} \), a funkcja \( \displaystyle \phi \) przyjmuje tą samą wartość, oznaczmy ją przez \( \displaystyle c \). Podsumowując otrzymujemy

\( \phi \)	0	1
0	1	\( \displaystyle c \)
1	\( \displaystyle c \)	0

W zależności od wartości \( \displaystyle c \) formuła \( \displaystyle \phi \) definiuje funkcję \( \displaystyle NAND \) albo \( \displaystyle NOR \). W obu tych przypadkach przy pomocy formuły \( \displaystyle \phi \) da się zdefiniować wszystkie funkcje boolowskie. Ponieważ \( \displaystyle \circ \) jest jedynym spójnikiem występującym w \( \displaystyle \phi \) to również zbiór \( \displaystyle \{\circ\} \) jest funkcjonalnie pełny.

Po scharakteryzowaniu, które spójniki pozwalają zdefiniować wszystkie inne, pozostało jedynie oszacować ich liczbę. Wszystkich spójników \( \displaystyle n \) argumentowych spełniających \( \mbox{(5.1)} \) jest \( \displaystyle \frac{1}{4} \cdot 2^{2^n} \). Wszystkich spójników \( \displaystyle n \) argumentowych spełniających \( \displaystyle \circ(\bar{x})= \overline{\circ(x)} \) jest \( \displaystyle 2^{2^{n-1}} \) (z każdej pary przeciwnych wartościowań wybieramy jedno). Po odrzuceniu połowy funkcji które nie spełniają \( \mbox{(5.1)} \) otrzymujemy \( \displaystyle \frac{1}{2} \cdot 2^{2^{n-1}} \). Wobec tego pozostaje dokładnie

\( \displaystyle \frac{1}{4} \cdot 2^{2^n} - \frac{1}{2} \cdot 2^{2^{n-1}} \)

funkcji które spełniają \( \mbox{(5.1)} \) oraz nie spełniają \( \displaystyle \circ(\bar{x})= \overline{\circ(x)} \). Możemy teraz obliczyć granicę

\( \displaystyle \lim_{n arrow \infty} \frac{ \frac{1}{4} \cdot 2^{2^n} - \frac{1}{2} \cdot 2^{2^{n-1}}}{2^{2^n}} = \lim_{n arrow \infty} \frac{1}{4} (1- 2 \cdot \frac{1}{2^{2^{n-1}}})=\frac{1}{4}. \)