Co to je logický kalkul?
-=-=-=-=-=-=-=-=-=-=-=-=-=
Logic doesn't apply to the real world.
-- Marvin Minsky
Kdysi dávno (1870-1890) se pan Cantor zabýval množinami. Přišel
na to, že pres množiny lze nadefinovat celou matematiku, a tak si
jako správný matematik položil základní otázku - co to je množina?
Došel k závěru, že množina je skupina prvků s nějakou
vlastností:
"Množinou rozumíme každé shrnutí určitých a navzájem různých předmětů
našeho nazírání, nebo myšlení do jediného celku M"
Tuto definici používali matematici několik let, až jednou pan
Russel přišel na spor. Pokud řekneme, že prvek patří do množiny
M právě tehdy, když nepatří do množiny M, nemůžeme ani určit,
jestli je množina prvkem sebe sama, nebo ne. Matematici nevěděli co
stím dělat a proto se toto rozhodli to ignorovat. Tento spor nazvali
eufemicky Russelovým paradoxem. Později se ale vynořili další
problematické definice množiny například:
"Množina M obsahuje nejmenší možné číslo, které nejde vyjádřit
v češtině méně, než 20ti slovy."
Na první pohled tato definice vypadá logicky: Čeština obsahuje
cca 30000 slov, počet vět kratších než 20 slov je tedy menší než
20^30000. Některé z nich vyjadřují nějaké číslo a tak tedy máme
několik čísel, vybereme největší, zvětšíme o 1 a máme naši množinu.
Problém ale je v tom, že samotná definice je kratší, než 20 slov -
vstahuje se i sama na sebe a proto žádné takové číslo neexistuje.
Matematici došli k závěru, že problém je v jazyce. Čeština je
příliš nepřesná na to, aby se přes ní formulovala logika a proto se
rozhodli vytvořit jazyk nový a mnohem přesnější.
Výsledek je jazyk logického kalulu. Logický kalkul obsahuje
proměnné, závorky a logické spojky. Proměné jsou písmenka a mohou
nabývat hodnoty 0 a 1. Skupina těchto proměných a hodnot se
nazývá formule. Ta také může nabývat hodnoty 0 a 1 v závislosti
na použitých proměných. Závorky se používají na upřednostňování.
Logické spojky jsou následující: ! (negace), & (a), || (nebo),
-> (implikace), <=> (ekvivalence). Jejich výsledné hodnoty se určují
podle následujících tabulek:
+--+--+ +---+---+-----+-----+-----+-----+
|a |!a| | a | b | a&b | a|b | a->b|a<=>b|
+--+--+ +---+---+-----+-----+-----+-----+
|1 | 0| | 1 | 1 | 1 | 1 | 1 | 1 |
|0 | 1| | 1 | 0 | 0 | 1 | 0 | 0 |
+--+--+ | 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 1 |
+---+---+-----+-----+-----+-----+
Spojky ! & a | jsou snad jasné. Spojka -> se často používá u
různých podmínek. Například "Pokud budeš hodný, půjdeš do kina"
jde přepsat na: "budeš hodný" -> "půjdeš do kina". Tato věta tedy
neznamená, že pokud bude zlobit, do kina nepůjde. Rodiče by tedy
měli správně používat ekvivalenci "Půjdeš do kina právě tehdy když
budeš hodný".
Množiny
Jak jsem říkal, logický kalkul byl vytvořen kvůli množinám
a proto je nutné s nimi nějak pracovat. Každá množina má jméno.
Budu pro ně používat velká písmena. Můžu zjišťovat, jestli je nějaké
x prvkem množiny pomocí operátoru náležení <. Zapisovat množinu můžu
buď výčtem jejích prvků: M {1,2,3,4}, nebo vlastností M {x: (x<A)
| (x<B)}. Tady říkam, že množina jménem M obsahuje prvky x, které
jsou prvkem množiny A, nebo B.
Další symbol, který můžu nadefinovat je =. To je rovnost.
Množiny se rovnájí, pokud mají všechny prvky stejné. V jazyce teorie
množin můžu nadefinovat: formule (A=B) je zkratka pro ((x<A) <=>
(x<B)). Podobným způsobem můžu nadefinovat podmnožiny apod.
Samotná definice množiny je docela složitá, jestli vás
to zajímá, tak tady je něco o Temnu.
Predikátový počet
Po malém výletu do teorie množin se vrátíme zpátky. Jazyk
logického kalkulu je přece jenom příliš triviální. Jeho rozšířením
je predikátový počet. Ten navíc přidává predikát. Predikát je
cosi jako funkce. Má jméno, parametry a vrací hodnotu buď jedna,
nebo nula. Například na všechny logické spojky lze nahlížet jako
na predikáty s jedním, nebo dvěma prametry - and je predikát se
dvěma parametry A,B a je pravdivý, právě tehdy když A=B=1.
Pomocí predikátů můžeme nadefinovat přirozená čísla. Řekneme,
že 0 je první číslo. Další čísla získáme pomocí predikátu následník
n(x,y). Ten je 1 v případě, že y je následníkem x. Tedy například
n(0,1), ale třeba n(0,ahoj) je nula.
Navíc predikátový počet přidává dva kvantifikátory Ex(...)
(existuje x, pro ktere platí) a Vx(...) (pro všechna x platí)
Predikát můžeme definovat buď výčtem všech parametrů pro které
je predikát pravda (ale třeba pro predikát n to moc praktické není),
nebo formulí. Například můžeme nadefinovat predikát plus2, který
přičte 2:
plus2(x,y) <=> Ez(n(x,z) & n(z,y))
(plus2 je pravda právě tehdy když existuje z,z=x+1,y=z+1) Plus2
je vlastně první program. Lze použít k přičítání (plus2(1,x)), nebo
odčítání (plus2(x,3)) dvojky, nebo kontrolování, jestli b-a=2.
Predikát pro určování, jestli x je číslo může vypadat takto:
cislo(x) <=> Ey((x=0) | (n(y,x) & cislo(y)))
Tento predikát říká: x je číslo, pokud x je 0, nebo x-1 je
číslo. Tedy používá rekurzi k tomu, aby udělal jakousi smyčku
a napočítal od nuly do x (nebo obráceně, v predikátovém počtu to
je jedno). Taky používa predikát následník obraceně k odčítání
jedničky. Samozřejmě, že ho můžu napsat i jinak třeba:
cislo(x) <=> Ey((x=0) | (cislo(y) & n(y,x)))
Tady je několik dalších definic:
sudy(x) <=> Ey((x=0) | (cislo(y) & plus2(y,x)))
lichy(x) <=> (cislo(x) & !sudy(x))
Ale můžu napsat i něco složitějšího, třeba predikát
na sčítání a odčítání:
secteno(x,y,z) <=> (((x=0) & (y=z)) | Em(n(m,x) & secteno(m,y,n) & n(n,z))
Ten říká, že 0+y=y a nebo, že x+y=z právě tehdy, když
(x-1)+y=(z-1). To stačí k tomu, aby sčítání bylo nadefinováné. Pokud
je x nenulové, problém se převede na x o 1 menší atd.
výheň