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.
In article <ckbi11$k4...@srv.cyf-kr.edu.pl>, Lech Duraj wrote:
>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.
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
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
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
|
