Zadanie, które krąży w Instytucie Informatyki UJ:

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

Scharakteryzować wszystkie spójniki uniwersalne i obliczyc granicę
U_k/S_k przy k->niesk. (U_k - liczba spójników uniwersalnych
k-argumentowych, W_k - liczba wszystkich spójników k-argumentowych).

Zadanie jest ciekawe, a wynik może być zaskakujący.

--
Pozdrawiam
Lech Duraj

Ciii,ciii, licze, jak na razie to cos oczywistego,jeli limes istnieje
to nalezy do <0,1/4>  ... :P

--
Uzi, the Elder Linear Algebra God.
"czy mnożąc 10 przez 0.(9) mnożysz także ostatnią cyfrę tego szeregu
0,999999999999999999... ?" ksRobak na pl.sci.matematyka

UZI napisał:

Ciekawe. To sugeruje, że przez trudniejszą część już przeszedłeś...

--
Pozdrawiam
Lech Duraj

news:ckhhui$hlq$2@srv.cyf-kr.edu.pl...

Zadanie po instytucie krąży, ale rozwiązanie chyba nie :-) Chociaż sam wynik
końcowy jest mi znany. Przynajmniej z
http://groups.google.pl/groups?hl=pl&lr=&selm=btfg0q%24fr9%241%40news...
l :-)

Spróbuję ograniczyć 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 _conajmniej_ 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 (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^(2^k - 2)           (1)

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^((2^k - 2)/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^(2^k - 2)  -  2^((2^k - 2)/2)

Iloraz

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

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

Jeśli chodzi o ograniczenie od góry, to myślę, że trzeba tworzyć spójniki
"niemalejące" (z których nigdy nie zrobi się NOT).

Niech będzie częściowy porządek \< na {0,1}^k (po wyrazach, koniunkcja)
Spójnik f jest niemalejący, jeśli

    a, b \in {0,1}^k oraz a \< b  =>  f(a) \< f(b).

Ale w tym momencie nie potrafię policzyć ile tego jest.

pzdr.
MŚ

Użytkownik "Michał Śliwka" <michal.sliwka_USUN...@wp.pl>
napisał w wiadomości news:ckhq4h$5vv$1@nemesis.news.tpi.pl...

Krocej:
http://groups.google.pl/groups?selm=btfg0q%24fr9%241%40news.onet.pl

Maciek

Ach, ale tam jest jeszcze "scharakteryzować *wszystkie* spójniki
uniwersalne".

--
Pozdrawiam
Lech Duraj

news:ckhhui$hlq$2@srv.cyf-kr.edu.pl...

Zadanie po instytucie krąży, ale rozwiązanie chyba nie :-) Chociaż sam wynik
końcowy jest mi znany. Przynajmniej z
http://groups.google.pl/groups?hl=pl&lr=&selm=btfg0q%24fr9%241%40news...
l :-)

Spróbuję ograniczyć 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 _conajmniej_ 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 (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^(2^k - 2)           (1)

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^((2^k - 2)/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^(2^k - 2)  -  2^((2^k - 2)/2)

Iloraz

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

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

Jeśli chodzi o ograniczenie od góry, to myślę, że trzeba tworzyć spójniki
"niemalejące" (z których nigdy nie zrobi się NOT).

Niech będzie częściowy porządek \< na {0,1}^k (po wyrazach, koniunkcja)
Spójnik f jest niemalejący, jeśli

    a, b \in {0,1}^k oraz a \< b  =>  f(a) \< f(b).

Ale w tym momencie nie potrafię policzyć ile tego jest.

pzdr.
MŚ