Czyli, ile jest spójników \(\displaystyle{ \circ}\) ,\(\displaystyle{ n}\)- argumentowych, w stosunku do wszystkich spójników \(\displaystyle{ n}\) -argumentowych, o tej własności, że jedynie przy pomocy \(\displaystyle{ \circ}\) można zdefiniować wszystkie spójniki. Oczywiście, tu trzeba poprawić, liczymy z takich wielkości granicę, przy \(\displaystyle{ n \rightarrow +\infty}\).Niech \(\displaystyle{ F_n}\) oznacza ilość boolowskich funkcji \(\displaystyle{ \text{n}}\) argumentowych, a \(\displaystyle{ P_n}\) ilość boolowskich funkcji \(\displaystyle{ \text{n}}\) argumentowych, takich że przy pomocy każdej z nich da się zdefiniować dowolną funkcję boolowską (czyli jeśli \(\displaystyle{ \circ}\) jest takim spójnikiem, to zbiór \(\displaystyle{ \{\circ\}}\) jest funkcjonalnie pełny). Udowodnij istnienie poniższej granicy, i wyznacz jej wartość
\(\displaystyle{ \lim_{n \rightarrow \infty} \frac{P_n}{F_n}}\).
Początek rozwiązania:
Podkreśliłem z czym mam problem. Nie wiem, co to jest funkcja unarna... I nie jest jasno tu powiedziane, co należałoby indukcyjnie udowodnić. Ktoś pomoże...Ustalmy dowolne \(\displaystyle{ \displaystyle n>1}\). Niech \(\displaystyle{ \displaystyle \circ}\) będzie spójnikiem \(\displaystyle{ \displaystyle n}\) argumentowym takim, że zbiór \(\displaystyle{ \displaystyle \{\circ\}}\) jest funkcjonalnie pełny. Zastanówmy się jaką funkcję unarną definiuje formuła \(\displaystyle{ \displaystyle \circ(x, \dots, x)}\). Funkcja ta nie może na samych \(\displaystyle{ 1}\) dawać wartości \(\displaystyle{ 1}\), gdyż wtedy każda formuła unarna poza formułą \(\displaystyle{ \displaystyle x}\) zbudowana z \(\displaystyle{ \displaystyle \circ}\) byłaby stale równa \(\displaystyle{ 1}\) (indukcyjny dowód pomijamy), a więc nie dałoby się zdefiniować \(\displaystyle{ \displaystyle \neg}\) przyp pomocy \(\displaystyle{ \displaystyle \circ}\). Z tych samych przyczyn formuła \(\displaystyle{ \displaystyle \circ(x, \dots, x)}\) na samych \(\displaystyle{ 0}\) nie może przyjmować wartości \(\displaystyle{ 0}\). Wynika stąd, że konieczne jest aby
\(\displaystyle{ \displaystyle \circ(x, \dots ,x) \equiv \neg x. \quad \mbox{(5.1)}}\)
Jakby się ktoś zastanawiał, to sam szkic dowodu jest od dawna dla mnie zrozumiały.
Ukryta treść:
OK, domyśliłem się o co chodzi, i udało się to udowodnić, ale coś nie jestem pewny czy poprawnie. Proszę o sprawdzenie.Jakub Gurak pisze:I nie jest jasno tu powiedziane, co należałoby indukcyjnie udowodnić
Podobnie, jak się dowodzi, że zbiór \(\displaystyle{ \left\{ \wedge \right\}}\) nie jest funkcjonalnie pełny, przypuszczamy najpierw , że \(\displaystyle{ \circ(1, \dots, 1)=1}\), i dowodzimy indukcyjnie, że każda formuła zbudowana jedynie ze spójnika \(\displaystyle{ \circ}\) i zmiennych, przyjmuje zawsze wartość \(\displaystyle{ 1}\), jeśli wszystkie zmienne są wartościowane na \(\displaystyle{ 1}\). Dowód poprowadzimy przez indukcję, ze względu na ilość wystąpień spójnika \(\displaystyle{ \circ}\).
Baza indukcji. Jeśli \(\displaystyle{ \circ}\) ma zero wystąpień, to formuła musi być postaci \(\displaystyle{ x}\), gdzie \(\displaystyle{ x}\) jest zmienną. Wtedy wartościowanie zmiennej \(\displaystyle{ x}\) na \(\displaystyle{ 1}\), wartościuje oczywiście tą formułę na \(\displaystyle{ 1}\). Baza indukcji jest więc spełniona.
Niech \(\displaystyle{ n>0}\), i przypuśćmy, że wszystkie formuły złożone z mniej niż \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \circ}\) mają żądaną własność. Weźmy dowolną formułę \(\displaystyle{ P}\), gdzie występuje dokładnie \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \circ}\). Rozważmy wartościowanie wszystkich zmiennych \(\displaystyle{ x_{1},x_{2},\ldots, x_{k}}\) na \(\displaystyle{ 1}\). Ponieważ \(\displaystyle{ n>0}\), to \(\displaystyle{ P}\) jest postaci \(\displaystyle{ \circ( P_{1} ,P_{2} \dots, P_{m})}\). Zauważamy, że każda formuła \(\displaystyle{ P_{i}}\) ma mniej niż \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \circ}\). Ponieważ \(\displaystyle{ P\left( x_{1},x_{2},\ldots, x_{k}\right) \Longleftrightarrow \circ( P_{1} ,P_{2} \dots, P_{m})}\), więc aby definicja \(\displaystyle{ P}\) była poprawna, więc po prawej stronie równoważności również możemy używać jedynie (niektórych) ze zmiennych \(\displaystyle{ x_{1},x_{2},\ldots, x_{k}}\). Ale wszystkie zmienne \(\displaystyle{ x_{1},x_{2},\ldots, x_{k}}\) są wartościowane na \(\displaystyle{ 1}\), więc po prawej stronie wszystkie zmienne są wartościowane na \(\displaystyle{ 1}\), i każda formuła \(\displaystyle{ P_{i}}\) ma wszystkie zmienne wartościowane na \(\displaystyle{ 1}\). Ponieważ każda formuła \(\displaystyle{ P_{i}}\) ma mniej niż \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \circ}\), więc na mocy założenia indukcyjnego, każda taka formuła jest wartościowana na \(\displaystyle{ 1}\). Wnioskujemy, że \(\displaystyle{ P\left( 1,\ldots,1\right)}\) ma tą samą wartość, co \(\displaystyle{ \circ\left( 1,\ldots,1\right)}\), a więc \(\displaystyle{ 1}\). Wobec dowolności wyboru formuły \(\displaystyle{ P}\), wszystkie formuły złożone z \(\displaystyle{ n}\) wystąpień spójnika \(\displaystyle{ \circ}\) mają żądaną własność.
Na mocy zasady indukcji własność jest udowodniona.
Wiemy, że każda formuła zbudowana jedynie ze spójnika \(\displaystyle{ \circ}\) przyjmuje zawsze wartość \(\displaystyle{ 1}\), jeśli zmienne są wartościowane na \(\displaystyle{ 1}\). Nie jest więc możliwe zdefiniowanie np. spójnika \(\displaystyle{ F}\) fałszu, gdyż przy jakimkolwiek zdefiniowaniu, jeśli zmienne będziemy wartościować na \(\displaystyle{ 1}\), to zgodnie z powyższym przyjmie on wartość \(\displaystyle{ 1}\), a ten spójnik \(\displaystyle{ F}\) jest zawsze fałszywy, sprzeczność.