Giovanni's Blog: Funkcionální úplnost

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

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

platí $\left(\forall x, y \in B\right)\ f(x, y) \in B$ , pak funkce

není n-Shefferovská.
Důkaz. Pokud předpoklad tvrzení platí, pak nelze žádným způsobem z funkce

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

nemůže být n-Shefferovská.

Důsledek. Jestliže pro některé $x \in A_n$ platí f(x, x) = x

, pak funkce

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é

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é

žá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:

Okomentovat