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}.$