N-argumentowe spójniki uniwersalne

Spójnik logiczny k-argumentowy to dowolna funkcja 0, 1^k $\rightarrow$ 0, 1. Spójnik nazwiemy uniwersalnym, jeśli przez składanie go ze sobą i ewentualnie wielokrotne podstawianie argumentów da się otrzymać wszystkie spójniki logiczne o dowolnej liczbie argumentów.

Scharakteryzować wszystkie spójniki uniwersalne i obliczyć granicę $\lim_{{k \rightarrow \infty}}^{}$${\frac{{U_k}}{{S_k}}}$, gdzie U_k to liczba spójników uniwersalnych k -argumentowych, S_k - liczba wszystkich spójników k -argumentowych.

* * *

Spróbujemy oszacować granicę od dołu.

Wiadomo, że z dwuargumentowych NAND lub NOR można zrobić wszystko. Trzeba by więc zastanowić się, z ilu k -spójników można zrobić dwuargumentowe NAND lub NOR, czyli ile co najmniej jest uniwersalnych.

Polega to na podzieleniu k argumentów na dwie niepuste grupy x i y oraz za argumenty w jednej grupie podstawiać pierwszy parametr, a za argumenty w drugiej grupie - drugi parametr dwuargumentowego NAND-a lub NOR-a, którym będzie nasz spójnik k-argumentowy.

Takich podziałów jest ${\frac{{2^k - 2}}{{2}}}$ (mają być niepuste i nie jest ważna kolejność).

Wystarczy, że dla jednego z nich spójnik zachowuje się jak NAND albo NOR.

Rozważmy wszystkie spójniki dające 1 dla samych zer (zera w całej grupie x i y) i 0 dla samych jedynek (jedynki w całej grupie x i y), czyli tak jak NAND i NOR dla takich argumentów, dla pozosta?ych 2^k - 2 kombinacji, 0 lub 1. Jest ich:

2^2k-2

dzielą się one na takie, które dla żadnego podziału na grupy nie zachowują się ani jak NAND ani jak NOR (pozostają tylko dwie możliwości, z założenia w poprzednim akapicie, stąd 2 w podstawie potęgi)

2^(2k-2)/2

oraz takie, które dla przynajmniej jednego podziału zachowują się jak dwuargumentowe NAND i NOR, z których można zrobić każdą funkcję logiczną. Tych właśnie szukamy, jest ich oczywiście

2^2k-2 -2^(2k-2)/2

Iloraz

$${\frac{{2^{2^k - 2} - 2^{(2^k - 2)/2}}}{{2^{2^k}}}}$$

dąży od dołu do 1/4.

* * *

Charakteryzacja spójników uniwersalnych wygląda natomiast tak: (niech $\neg$0 = 1, $\neg$1 = 0, $\neg$(a₁, a₂,..., a_k) = ($\neg$a₁,$\neg$a₂,...,$\neg$a_k) dla a₁, a₂,..., a_k $\in$ 0, 1).

N-argumentowy spójnik A jest uniwersalny, gdy:

• A(0, 0,..., 0) = 1,
• A(1, 1,..., 1) = 0,
• istnieją a₁, a₂,..., a_N $\in$ {0, 1} takie, że
  A(a₁, a₂,..., a_N) = A($$\neg$$(a₁, a₂,..., a_N))

Uzasadnienie:

Jeśli byłoby A(0, 0,..., 0) = 0, to każde wyrażenie zbudowane tylko z użyciem spójnika A miałoby wartość 0, gdyby wszystkie zmienne miały wartość 0 (formalny dowód - indukcja ze względu na budowę wyrażenia). Nie udałoby nam się więc zrobić jednoargumentowego NOTa.

Jeśli byłoby A(1, 1,..., 1) = 1, to każde wyrażenie zbudowane tylko z użyciem spójnika A miałoby wartość 1, gdyby wszystkie zmienne miały wartość 1 (formalny dowód - indukcja ze względu na budowę wyrażenia). Nie udałoby nam się więc zrobić jednoargumentowego NOTa.

Jeśli dla wszystkich (a₁, a₂,..., a_N), gdzie a_i równa się 0 lub 1 byłoby A(a₁, a₂,..., a_N) = $\neg$A($\neg$(a₁, a₂,..., a_N)), to dla każdego wyrażenia zbudowanego tylko z użyciem spójnika A zamiana wartości wszystkich zmiennych na przeciwne (0 na 1, 1 na 0) powodowałaby również zmianę wyniku na przeciwny (formalny dowód - indukcja ze względu na budowę wyrażenia). Nie udałoby nam się więc zrobić na przykład dwuargumentowego ANDa.

Niech teraz A spełnia warunki

• A(0, 0,..., 0) = 1
• A(1, 1,..., 1) = 0,
• istnieją a₁, a₂,..., a_N $\in$ {0, 1} takie, że
  A(a₁, a₂,..., a_N) = A( (a₁, a₂,..., a_N))

Ustalmy jedną N-ke (a₁, a₂,..., a_N) jak wyżej. Niech W(x, y) = A(z₁, z₂,..., z_N), gdzie z_i = x, gdy a_i = 0 oraz z_i = y, gdy a_i = 1. W(x, y) jest dwuargumentowym NORem, jeśli

A(a₁, a₂,..., a_N) = A($$\neg$$(a₁, a₂,..., a_N)) = 1,

oraz W(x, y) jest dwuargumentowym NANDem, jeśli

A(a₁, a₂,..., a_N) = A($$\neg$$(a₁, a₂,..., a_N)) = 0.

O dwuargumentowych NORze i NANDzie zaś wiemy, że są uniwersalne.

Scharakteryzowaliśmy więc wszystkie spójniki uniwersalne i są to dokładnie te, które już zostały policzone w notce. Ich liczba to U_N = 2^2N-2 -2^(2N-2)/2 .

Lech Duraj, Andrzej Komisarski, Michał Śliwka, styczeń, październik, listopad 2004

Linki do oryginalnych dyskusji: [1], [2]