FAQ dostępne jest pod adresem:

"http://ux1.mat.mfc.us.edu.pl/~pgladki/faq/"

W tym tygodniu zacząłem - przy pomocy Michała Śliwki i
Mateusza Kwaśnickiego, którym chciałbym serdecznie
podziękować za pomoc - edytować dział "Problemy otwarte
psm". Na razie omówione zostały:

1. Działania łączne w zbiorze n-elementowym.
2. N-argumentowe spójniki uniwersalne.
3. Podmacierz o największej sumie elementów.
4. Trójkąty o długościach boków i polu powierzchni całkowitych.
5. Naturalny homeomorfizm zbioru Cantora i hiperprzestrzeni
jego zwartych podzbiorów.
6. Liczba n-bitowych kodów Gray'a.

Zapraszam do współpracy w redagowaniu FAQ!

Z poważaniem

Jeśli chodzi o "N-argumentowe spójniki uniwersalne":

W notce, którą widzę jest uzasadnienie, że liminf_{k->oo} U_k/S_k >= 1/4.
Z drugiej strony jestem pewien, że ktoś już uzasadniał,
że limsup_{k->oo} U_k/S_k <= 1/4.
Mamy nawet lepiej: U_k/S_k<=1/4 dla wszystkich k.
(Było to proste uzasadnienie, sprowadzało się do zauważenia,
że interesujące nas spójniki muszą na (1,1,...,1) dawać 0, a na (0,0,...,0)
dawać 1. W przeciwnym razie nie wyprodukowalibyśmy 1-argumentowej negacji.)

Tak więc pełne uzasadnienie, że lim_{k->oo} U_k/S_k = 1/4 już się
(jak mi się zdaje) pojawiło.

# N-argumentowy spójnik A jest uniwersalny, gdy:
# A(0,0,...,0)=1
# A(1,1,...,1)=0,
# istnieją a_1,a_2,...,a_N równe 0 lub 1 takie, że
#   A(a_1,a_2,...,a_N) = A(~(a_1,a_2,...,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 maiał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ść z, gdyby wszystkie zmienne maiały
wartość z (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_1,a_2,...,a_N), gdzie a_i równa się 0 lub 1 byłoby
A(a_1,a_2,...,a_N)=~A(~(a_1,a_2,...,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łoby również amianę 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_1,a_2,...,a_N równe 0 lub 1 takie, że
#   A(a_1,a_2,...,a_N) = A(~(a_1,a_2,...,a_N))

Ustalmy jedną N-kę (a_1,a_2,...,a_N) jak wyżej.
Niech W(x,y) = A(z_1,z_2,...,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_1,a_2,...,a_N) = A(~(a_1,a_2,...,a_N)) = 1,
oraz W(x,y) jest dwuargumentowym NANDem, jeśli
   A(a_1,a_2,...,a_N) = A(~(a_1,a_2,...,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^(2^N - 2) - 2^((2^N - 2)/2).