Označím pravdivostní hodnotu výroku X v nějaké logice jako |X|. V klasickém výrokovém počtu to je samozřejmě zobrazení přiřazující výroku buď 0 nebo 1 podle pravdivostní hodnoty atomických výroků AV1, AV2, ....
V klasické logice např. platí:
|X| = |AVi|, pokud X = AVi
|¬ X| = 1-|X|
|X ∨ Y| = max{|X|, |Y|}
|X & Y| = min{|X|, |Y|}
Pokud si vymyslím logický operátor třeba ⊕ a k němu funkci f a definuji, že platí:
|X ⊕ Y| = f(|X|, |Y|),
pak dělám v klasické výrokové logice poměrně zbytečnou práci, protože, takovýchto funkcí je možných jen 16 a všechny lze vytvořit pomocí funkcí pro již zmíněné operátory, jinými slovy, každý další operátor, který si vymyslím, lze poskládat z již existujících. Stejně tak pro ternární a vícenární operátory. Co do operátorů, je již tato logika nasycena. Pokud přidám k pravdivostním hodnotám 0 a 1 ještě jednu pravdivostní hodnotu – řekněme ½ –, pak to už tvrdit nemohu, protože např. operátor ⊗ X, pro který platí
|⊗ X| = ½,
nelze z ostatních nijak složit. Ale i tato logika má svůj konečný počet logických operátorů, k nimž již není možné vymyslet další tak, aby mohl vzniknout zcela nový výrok. Lze tedy i tuto logiku nasytit konečným počtem operátorů. Pro nekonečný počet pravdivostních hodnot to však neplatí, protože jen různých unárních operátorů je nekonečně mnoho a konečným počtem operátorů nelze v konečném počtu kroků tolik různých operátorů poskládat. Budu si proto nyní všímat jen logik s konečným počtem pravdivostních hodnot. Lze všechny takovéto logiky nasytit konečným počtem operátorů? A pokud ano, lze to vždy učinit nejvýše binárními operátory?
Jestliže logika má 2 ≤ N pravdivostních hodnot, pak je možné definovat nejvýše NN2 binárních operátorů. Z těchto všech binárních operátorů lze pochopitelně poskládat každý unární operátor. Lze z nich poskládat každý ternární operátor, kterých je NN3? Pokusím se dokázat, že tomu tak je, a to takto:
1) Pro N = 2 (tj. pro dvojkovou logiku) toto platí. (Důkaz je v každé (pořádné) učebnici logiky.)
2) Předpokládám nyní, že 3 ≤ N. Označím množinu pravdivostních hodnot V = {v1, ..., vN}. Nechť I ∈ V, O ∈ V a I ≠ O. Chci nyní poskládat n-nární operátor, kde 2 ≤ n, s funkcí f(x1, ..., xn). Využiji unární funkci oi(x), kterou lze poskládat, takovou, že oi(x) = I, jestliže x = vi, a oi(x) = O, jestliže x ≠ vi. Dále definuji funkci rj(o1(x1), ..., oN(x1), ..., o1(xn), ..., oN(xn)) a to tak, že platí: rj = I, jestliže f(x1, ..., xn) = vj, jinak rj = O. Hodnota i hodnoty argumentů této funkce jsou z oboru {O, I} a tedy tuto funkci lze z binárních operátorů poskládat. Protože lze poskládat všechny binární funkce, lze poskládat i funkci si(x1, x1) = vi. Namísto této funkce budu psát pouze si. Znakem t budu značit binární funkci takovou, že t(a, b) = O pro a = O a t(a, b) = b pro a ≠ O. Znakem u budu značit některou binární funkci u(a, b) takovou, že u(a, b) = a pro b = O, a u(a, b) = b pro a = O. Na ostatních hodnotách nezáleží. Definuji funkce wi pro i = 1, ..., N rekurzivním předpisem:
w1 = t(r1, s1),
wi = u(t(ri, si), wi-1).
Funkce wN, je primitivně rekurzivní, je poskládaná jen z binárních operátorů a je to hledaná funkce f. Tím je důkaz hotov.
V klasické logice např. platí:
|X| = |AVi|, pokud X = AVi
|¬ X| = 1-|X|
|X ∨ Y| = max{|X|, |Y|}
|X & Y| = min{|X|, |Y|}
Pokud si vymyslím logický operátor třeba ⊕ a k němu funkci f a definuji, že platí:
|X ⊕ Y| = f(|X|, |Y|),
pak dělám v klasické výrokové logice poměrně zbytečnou práci, protože, takovýchto funkcí je možných jen 16 a všechny lze vytvořit pomocí funkcí pro již zmíněné operátory, jinými slovy, každý další operátor, který si vymyslím, lze poskládat z již existujících. Stejně tak pro ternární a vícenární operátory. Co do operátorů, je již tato logika nasycena. Pokud přidám k pravdivostním hodnotám 0 a 1 ještě jednu pravdivostní hodnotu – řekněme ½ –, pak to už tvrdit nemohu, protože např. operátor ⊗ X, pro který platí
|⊗ X| = ½,
nelze z ostatních nijak složit. Ale i tato logika má svůj konečný počet logických operátorů, k nimž již není možné vymyslet další tak, aby mohl vzniknout zcela nový výrok. Lze tedy i tuto logiku nasytit konečným počtem operátorů. Pro nekonečný počet pravdivostních hodnot to však neplatí, protože jen různých unárních operátorů je nekonečně mnoho a konečným počtem operátorů nelze v konečném počtu kroků tolik různých operátorů poskládat. Budu si proto nyní všímat jen logik s konečným počtem pravdivostních hodnot. Lze všechny takovéto logiky nasytit konečným počtem operátorů? A pokud ano, lze to vždy učinit nejvýše binárními operátory?
Jestliže logika má 2 ≤ N pravdivostních hodnot, pak je možné definovat nejvýše NN2 binárních operátorů. Z těchto všech binárních operátorů lze pochopitelně poskládat každý unární operátor. Lze z nich poskládat každý ternární operátor, kterých je NN3? Pokusím se dokázat, že tomu tak je, a to takto:
1) Pro N = 2 (tj. pro dvojkovou logiku) toto platí. (Důkaz je v každé (pořádné) učebnici logiky.)
2) Předpokládám nyní, že 3 ≤ N. Označím množinu pravdivostních hodnot V = {v1, ..., vN}. Nechť I ∈ V, O ∈ V a I ≠ O. Chci nyní poskládat n-nární operátor, kde 2 ≤ n, s funkcí f(x1, ..., xn). Využiji unární funkci oi(x), kterou lze poskládat, takovou, že oi(x) = I, jestliže x = vi, a oi(x) = O, jestliže x ≠ vi. Dále definuji funkci rj(o1(x1), ..., oN(x1), ..., o1(xn), ..., oN(xn)) a to tak, že platí: rj = I, jestliže f(x1, ..., xn) = vj, jinak rj = O. Hodnota i hodnoty argumentů této funkce jsou z oboru {O, I} a tedy tuto funkci lze z binárních operátorů poskládat. Protože lze poskládat všechny binární funkce, lze poskládat i funkci si(x1, x1) = vi. Namísto této funkce budu psát pouze si. Znakem t budu značit binární funkci takovou, že t(a, b) = O pro a = O a t(a, b) = b pro a ≠ O. Znakem u budu značit některou binární funkci u(a, b) takovou, že u(a, b) = a pro b = O, a u(a, b) = b pro a = O. Na ostatních hodnotách nezáleží. Definuji funkce wi pro i = 1, ..., N rekurzivním předpisem:
w1 = t(r1, s1),
wi = u(t(ri, si), wi-1).
Funkce wN, je primitivně rekurzivní, je poskládaná jen z binárních operátorů a je to hledaná funkce f. Tím je důkaz hotov.
Žádné komentáře:
Okomentovat