středa 19. května 2010

Funkcionální úplnost

V binární logice lze z operátoru NAND nebo NOR sestrojit libovolný jiný operátor, což lze snadno dokázat. Důkaz je uveden v každé knize typu "logik für frauzimmer". Že to jsou jediné operátory, které samotné tvoří funkcionálně úplnou množinu operátorů, lze také dokázat poměrně snadno.

Definice. Funkce f je n-Shefferovská (nebo Shefferova), jestliže lze z ní konečným způsobem složit libovolnou funkci g:\ A_n \times A_n \mapsto A_n, kde A_n = \{0, 1, \dots, n-1\}.

Věta. Jestliže existuje existuje množina \emptyset \not= B \subset A_n taková, že pro funkci f platí \left(\forall x, y \in B\right)\ f(x, y) \in B, pak funkce f není n-Shefferovská.
Důkaz. Pokud předpoklad tvrzení platí, pak nelze žádným způsobem z funkce f složit funkci, která by pro nějaké x, y \in B nabývala hodnoty z neprázdné množiny A_n \setminus B. Proto funkce f nemůže být n-Shefferovská.

Důsledek. Jestliže pro některé x \in A_n platí f(x, x) = x, pak funkce f není n-Shefferovská.

Binárních operátorů na množině A_2 je jen 16. Ovšem ty, pro které platí f(x, x) \not= x, jsou jen čtyři. Dva z nich jsou však jenom unární operátory, které nemohou být 2-Shefferovské. Proto existují jen dvě 2-Shefferovské funkce.

Zajímavá je otázka: Kolik je obecně n-Shefferovskáých funkcí? Žádný vzorec se mi nepodařilo ani vymyslet, ani nalézt. Zdá se, že existuje pro každé konečné n alespoň jedna. V oxfordském matematickém slovníku jsem nalezl tento předpis pro n-Shefferovskou funkci:

f(x, y) = \left(\max\{x, y\} + 1\right)\ \mathrm{mod}\ n.

Říkají jí "Wenn funkce", což bude asi nějaké nedorozumění. Důkaz, že se skutečně jedná o n-Shefferovskou funkci jsem zatím nenašel. Pro žádné nekonečné n žádná n-Shefferovská funkce neexistuje, protože funkcí g:\ N \times N \mapsto N je nespočetně mnoho, kdežto konečným způsobem lze složit jen spočetně mnoho funkcí.

Žádné komentáře: