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.
>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.
Fajnie. Dzięki, że Ci się chce :-) Z uwag co do formy: Warto by na dole przy każdym z problemów dorzucić link do odpowiedniego wątku na groups.google.com (jako coś a la references). Ponadto, może warto wytłuścić/pokolorować wszędzie główne pytanie. Przeglądając niektóre problemy miałem wątpliwości co do tego, jakie jest pytanie.
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.
>Jeśli chodzi o "N-argumentowe spójniki uniwersalne":
Charakteryzacja spójników uniwersalnych wygląda natomiast tak: (niech ~0=1, ~1=0, ~(a_1,a_2,...,a_k)=(~a_1,~a_2,...,~a_k) dla a_1,a_2,...,a_k z {0,1})
# 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).
>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.
> 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
> Paweł Gładki
http://mathworld.wolfram.com/ - do BIBLIOTEK ONLINE powinieneś Pawle dodać powyższy link, będący uniwersalnym i przydatnym zbiorem.
Proponowałbym jednoczesnie pogrupowanie tychże, BIBLIOTEK w KATEGORIE, jeśli jest to naturalnie możliwe i sensowne (czyt. jeśli ich treść różni się czymś).
|
