Vyrokova_predikatova_logika

Milá kolegyně / milý kolego, součástí Vašeho rozšiřujícího studia informatiky je absolvování předmětu Logika pro učitele 1, jehož cílem je zvládnutí základů výrokové a predikátové logiky pro účely formulace dotazů v databázích, vytváření a formulace znalostí ve znalostních bázích a formální odvozování dalších znalostí. Je možné, že jste se již při Vašem předcházejícím vysokoškolském studiu s logikou setkala/setkal v rámci studia matematiky. Tento předmět se však poněkud liší od logiky pro matematické obory, a to právě svým zaměřením na využití v databázích a znalostních bázích, kterým se řadí k nezbytným základům teoretické informatiky.
Předmět je rozdělen do 10 lekcí. A prostudování každé z nich by Vám mělo trvat přibližně 1.5 hodiny.
Doporučuji Vám studovat text po jednotlivých lekcích, řešit úkoly zadané přímo v textu (výsledky máte vzadu), resp. procvičovat látku na dalších příkladech z textu „Cvičení z logiky“.
Korespondenční úkoly zadané na závěr jednotlivých lekcí mi v průběhu semestru pošlete ve dvou souborech, tj. souhrnně z výrokové logiky (lekce 1-5) a souhrnně z predikátové logiky (lekce 6-10).
Přeji Vám hodně trpělivosti při studiu některých obtížných partií látky a sobě přeji, aby se Vám manipulace s formálně reprezentovanými znalostmi zalíbila.
Alena Lukasová
JAZYK L VÝROKOVÉ LOGIKY

V úvodu této lekce, jejíž prostudování by vám mělo trvat zhruba 1,5 h, se seznámíte s obecným pojmem formálního jazyka a jeho syntaxe, abyste pak s nadhledem mohl(a) posoudit způsob a míru zjednodušení, kterého se ve srovnání s přirozeným jazykem dopouštíte, používáte-li k reprezentaci znalostí jazyka výrokové logiky.
Gramatika jazyka L výrokové logiky vám bude prezentována dvěma způsoby, a to jednak pomocí induktivní definice, jednak Backus - Naurovou formou, která je v informatice hojně užívána.
Vašemu pochopení syntaxe výrokové formule zcela jistě prospěje seznámení se souvislostmi konstrukce formule jazyka z dané abecedy podle daných pravidel s její reprezentací pomocí ohodnoceného binárního stromu. Pomocí této stromové reprezentace též snadno pochopíte, jak se hodnotí složitost konstrukce výrokové formule a další míry její složitosti.
Modelování myšlení formálním jazykem
Klasická logika, později matematika a dnes i matematická informatika se vždy na úrovni stupně svého vývoje pokoušela a dodnes pokouší k objektům a pochodům lidského myšlení vytvořit adekvátní model pomocí určitých sobě vlastních prostředků. Pojem model používaný v této souvislosti má obdobný význam, jako když se například hovoří o modelu v architektuře, v průmyslovém designu nebo též o dětské hračce - např. modelu železnice. Model se ve všech uvedených případech vytváří na základě určitého zjednodušení (abstrakce) modelované reality, a to tak, aby v něm z ní bylo vystiženo co nejlépe „to podstatné“. To, co se při daném pojetí jako podstatné nejeví, model zanedbává. Model jako určitý soubor relevantních objektů je abstraktním rámcem, na základě něhož se realizuje modelování určité skutečnosti.
V rámci vhodně zjednodušeného abstraktního modelu lidského myšlení se pak, podobně jako v  případě přirozeného jazyka, definuje odpovídající reprezentační a zároveň komunikační prostředek, tj. jazyk. Skutečnost, že se jazyk modelování nevyvinul cestou přirozeného vývoje, jak tomu zřejmě bylo u přirozených jazyků, ale byl zkonstruován podle exaktně zadaných gramatických pravidel, vyjadřujeme tím, že takto zkonstruované jazyky spolu s jim odpovídajícími modely nazýváme formálními (obr. 1.1).
FORMÁLNÍ MODEL
reprezentace
vybrané objekty formule - výrazy
v rámci modelu formálního jazyka
denotace
obr. .
Exaktně definovaný formální jazyk může reprezentovat (s jistým zjednodušením daným rámcem modelu) objekty modelované skutečnosti a jejich vzájemné vztahy. Při daném zjednodušení je pak možno do jisté míry zachytit i způsob myšlení o těchto objektech a v rámci tohoto zjednodušení do jisté míry též modelově zkoumat vlastnosti myšlení.
Objekty lidského myšlení o reálném světě jsou pojmy se svými vzájemnými vztahy.
Jazykové výrazy reprezentují objekty modelovaného světa a vztahy mezi nimi.
Objekty modelovaného světa jsou denotáty jazykových výrazů.
Informace a znalosti
Problematika umělé inteligence se dnes zpravidla dělí na dvě problémové oblasti : epistemologickou a heuristickou. V epistemologické části jsou znalosti v rámci modelovaného světa reprezentovány takovou formou, aby z nich mohly vyplynout další znalosti, resp. řešení problémů. Heuristická část se pak zabývá mechanismy, kterými se na bázi znalostí řeší rozhoduje, co se v dané situaci má dělat.
V epistomologické oblasti umělé inteligence, kterou se zde budeme zabývat, jde o manipulaci se znalostmi. Znalosti vycházejí z informací a ty zase vycházejí z dat.
Pojem dat není třeba zpřesňovat, neboť jak je známo, všechny znakové řetězce vstupující do výpočetního procesu lze obecně pokládat za data. Do výpočetního procesu však zřídkakdy vstupují data, která nemají žádný význam, která tedy nejsou nějakým způsobem interpretována.
Definice .
Interpretace dat je přiřazení datům jejich významu (sémantiky).
V informatice je pojem informace jedním ze základních pojmů, proto nestačí převzít jeho poněkud vágní vymezení, na něž jsme zvyklí z přirozeného jazyka. Přesněji vystihuje pojem informace následující definice.
Definice . (informace)
Informaci tvoří data spolu se svou interpretací.
Pojem informace je, jak je zřejmé z uvedených definic, neoddělitelný od sémantiky dat, která jsou jejími nositeli.
Definice . (znalosti)
Znalost je informace, která je použitelná a začlenitelná, resp. odvoditelná v souvislosti s jinými informacemi.
Pro počáteční období rozvoje informatiky bylo charakteristické, v návaznosti na předcházející etapu postupně stále vyspělejších mechanických pomocníků počítání, její zaměření na výpočetní a výpočetně rozhodovací procedury. Počítače totiž v počátcích svého využívání především realizovaly pracné výpočtové postupy, jako jsou např. výpočetní postupy v účetnictví, statistické nebo vědeckotechnické výpočty. Takový druh modelování lidské intelektuální činnosti vychází ze znalostí určitých pracovních postupů, tedy z určitých procedurálních znalostí.
K modelování procedurálních znalostí slouží abstraktní modely převážně orientované na výpočetní pracovní postupy. Modelovaná skutečnost je zde převážně světem informací ve formě čísel a číselných nebo jiných znakových kódů, na nichž probíhají výpočetní postupy formulované (v pojmech základních struktur a operací daného modelu) jako algoritmy. Modely této kategorie se proto nazývají modely algoritmické. Jim pak na reprezentační (jazykové) úrovni odpovídají algoritmické (procedurální) jazyky. Význam odpovídající algoritmickému jazyku má procedurální, resp. operační charakter. V souvislosti s algoritmickými jazyky je tedy na místě hovořit o jejich operační sémantice.
Deklarativní znalosti o objektech (entitách) spočívají v konstatování jejich stavů, vlastností nebo vzájemných vztahů. Počítačovou reprezentací deklarativních znalostí jsou pak vhodně strukturovaná data. Na nich a s nimi pak lze odvozovat další znalosti i provádět operace související se znalostmi procedurálními. Jazykovým výrazům formálních jazyků, modelujících určitá konstatování o objektech vnímaného světa a jejich vzájemných vztazích, jsou přiřazovány významy jako jejich denotáty - objekty modelovaného světa. Sémantika formálních jazyků, které na rozdíl od jazyků procedurálních (algoritmických) řadíme mezi jazyky neprocedurální, je denotační sémantikou.

Data ….znakové řetězce
Informace….data spolu s jejich významem (databáze)
Znalosti….informace vzájemně začlenitelné a odvoditelné (znalostní báze)
Znalosti mají procedurální nebo deklarativní charakter.
Procedurální znalosti popisují, jak se realizuje nějaký proces.
Deklarativní znalosti konstatují vlastnosti, vztahy a vzájemné souvislosti objektů modelovaného světa.
Úkol .
Uvažujte, jaké druhy znalostí představují
návod k použití automatické pračky
technický popis automatické pračky
logaritmické tabulky
kapitola o logaritmech a jejich použití ve středoškolské učebnici matematiky
řada vygenerovaných náhodných čísel.
Syntax formálního jazyka
Reprezentaci pojmů jako základních objektů myšlení slouží určitým způsobem zkonstruované jazykové výrazy - řetězce symbolů vhodně zvoleného formálního jazyka. Vztahy mezi pojmy jsou zpravidla reprezentovány složitějšími jazykovými útvary vytvořenými pomocí pevných syntaktických pravidel. K reprezentaci úsudků pak slouží schémata určující, jak modelovat skutečné usuzování - tj. jak přepracovávat formule jazyka.
Modelování v rámci formální logiky se vždy děje pomocí jejího vlastního exaktně definovaného formálního jazyka logiky (ať už jde o logiku výrokovou, predikátovou nebo jinou). Proto je třeba zavést řadu obecných pojmů týkajících se způsobu, jakým je formální jazyk definován.
V případě formálních jazyků je tomu podobně jako u jazyků přirozených, kdy je dána určitá abeceda jazykových symbolů a kdy gramatika určuje způsob, jak vytvářet gramaticky správné věty (formule) jazyka.
Definice . (abecedy jazyka)
Abecedu jazyka tvoří daná množina (konečná nebo spočetná) symbolů - znaků abecedy.
Definice . (gramatiky jazyka)
Gramatiku jazyka tvoří jeho abeceda a soustava gramatických pravidel, umožňující z prvků abecedy jazyka konstruovat jistá zřetězení symbolů jazyka, která jsou jeho (dobře utvořenými) formulemi.
Gramatická (syntaktická) pravidla umožňují jednak formule konstruovat, jednak též rozpoznat, která zřetězení jsou a která nejsou dobře utvořené formule příslušného jazyka.
Máme-li na mysli způsob, jakým je formální jazyk vytvořen, hovoříme zpravidla o jeho syntaxi. Syntax formálního jazyka je dána jeho gramatikou.
Pojem syntaxe formálního jazyka se netýká toho, co jeho jednotlivé jazykové objekty znamenají. Definicí je pouze stanoveno, jakých symbolů abecedy jazyk používá a dále jsou předepsána gramatická pravidla zřetězování symbolů abecedy jazyka do útvarů zvaných formule jazyka. Významy jazykových objektů spadají do oblasti, kterou nazýváme sémantikou jazyka.
Zatímco sémantika přirozených jazyků spočívá v přiřazování pojmů, tj. exaktně nedefinovatelných abstraktních objektů jazykovým výrazům, jde u jazyků formálních o jasně definované přiřazení jedněch objektů jiným objektům, tj. výrazům příslušného formálního jazyka. V tom smyslu se hovoří o interpretaci jazyka, která je vždy dána, jak bude ukázáno dále, nějakou množinou objektů - universem diskursu, denotačním zobrazením přiřazujícím denotáty základním jazykovým elementům a interpretačními pravidly umožňujícími interpretaci komponovaných jazykových výrazů.
Do jaké míry se sémantika formálního jazyka přibližuje sémantice jazyků přirozených, to z velké části závisí na míře zjednodušení, jímž je skutečné lidské vnímání a myšlení formálně modelováno. Právě v této souvislosti se hovoří o určité expresivitě (vyjadřovací síle) formálního jazyka.
Syntax formálního jazyka je určena jeho gramatikou, tj. abecedou a gramatickými pravidly. Sémantika jazyka se týká jeho významové stránky.
Expresivita formálního jazyka je míra schopnosti formálního jazyka přiblížit se svým významem jazyku přirozenému.
POJEM VÝROKU A JEHO PRAVDIVOSTI
Lidské myšlení vždy vychází z nějaké množiny tvrzení neboli výroků o uvažovaném světě. Výroky, jimiž se zabývá výroková logika, jsou taková tvrzení deklarativního typu, o jejichž pravdivostní hodnotě („pravdivý“/„nepravdivý“) má smysl uvažovat. Mezi nimi lze pak rozlišit výroky elementární neboli atomické, které již dále nelze rozložit na výroky jednodušší. Množina všech atomických výroků o modelovaném světě tvoří universum diskursu, v jehož rámci se modelování pomocí formálních prostředků výrokové logiky pohybuje. Při modelování je proto potřeba mít na zřeteli nejen prostředek, jímž modelování probíhá a kterým je zde výroková logika, ale též přesně vymezit, jaký „svět“ je předmětem tohoto modelování.
Logika, kterou zde uvažujeme, je dvouhodnotová. To znamená, že každému tvrzení, které připadá v úvahu jako výrok, lze přiřadit právě jednu ze dvou možných pravdivostních hodnot „pravdivý“/„nepravdivý“, pro něž budou v dalším používány symboly true/false. Je zřejmé, že takto pojatá výroková logika se jako prostředek modelování dopouští prudkého zjednodušení spočívajícího právě v redukci obsahu výroků a tím i universa diskursu pouze na jejich pravdivostní hodnoty.
Jedním ze základních požadavků praktického využití výrokové logiky je rozpoznání výroků od ne-výroků a s tím souvisící možnost stanovení jejich pravdivostních hodnot. Např. dotaz „K čemu mi bude logika ? “ nebo zvolání „Dost už bylo logiky ! “ nejsou větami deklarativního typu, proto nepředstavují výroky a nemá smysl uvažovat o jejich pravdivosti. V případě věty „Den po svém narození přednášel studentům logiku.“ jde o výrok a nikdo nepochybuje o jeho nepravdivosti bez ohledu na to, ke kterému jedinci a které době se vztahuje. Jde-li však o výrok „Tráva je zelená.“, je třeba při posuzování jeho pravdivosti vzít v úvahu čas, resp. stav světa, ke kterému se výrok vztahuje. Není-li rozlišována úroveň jazyková od úrovně metajazykové, představuje „Tato věta je nepravdivá.“ paradoxní tvrzení, jež rovněž nelze považovat za výrok, neboť zde není možné stanovit pravdivostní hodnotu.

Úkol .
Uvažujte, které z následujících jazykových výrazů jsou výroky. Které z nich jsou atomické a které komponované ? Druhé z nich rozložte na atomy a pro všechny výroky stanovte jejich pravdivostní hodnoty, resp. diskutujte, na čem jejich pravdivost závisí.
Naši sportovci se předčasně vrátili z mistrovství, neboť prohráli rozhodující zápas.
Škoda, že nedopadli lépe.
Kdyby hokejisté vyhráli s Ruskem a Kanadou, neohrozili by svoji medailovou pozici.
Příklad .
Uvažujme modelovaný „svět“ jako situaci jisté tříčlenné rodiny ve večerních hodinách, kterou je možno modelově zjednodušeně popsat těmito výroky :
„Otec sleduje v televizi fotbal, pije pivo a kouří.“ f & p & k
„Matka umývá nádobí.“ n
„Syn hraje na počítači hru.“ h
Písmena f, p, k, n, a h zde představují symboly výrokové logiky pro atomické výroky
„Otec sleduje v televizi fotbal.“f
„Otec pije pivo.“p
„Otec kouří.“k
popisující modelově zjednodušenou situaci v tříčlenné rodině X. Symboly & zde vyjadřují současnou platnost atomických výroků f, p, k.
Protože výroková logika je postavena na zjednodušení, které spočívá v tom, že význam elementů zvaných atomické výroky je redukována pouze na jejich pravdivostní hodnoty, lze modelovou situaci v rodině X charakterizovat tak, že všechny zavedené symboly pro dané elementární výroky mají pravdivostní hodnoty true. Jinak tomu bude např. v rodině Y, kde je otec nekuřák a místo kouření mlsá sušenky. Pravdivostní hodnota výrokového symbolu k tedy bude false.
Modelovaný svět (skutečným světem je tříčlenná rodina) je zde zastoupen modelově zjednodušeným světem, tj. množinou výroků, vypovídajících „to podstatné“ o modelovaném světě a tvořících modelové universum diskursu. V jazyce výrokové logiky jsou pak atomické výroky reprezentovány symboly f, p, k, n, h. Jazykové symboly označující atomické výroky mají v modelu výrokové logiky jen dva možné významy a to „pravdivý“ (true) nebo „nepravdivý“ (false).
Symboly pro atomické výroky neboli atomy, které byly v rámci modelování uvažované reality zavedeny, jsou prvky formálního jazyka výrokové logiky odpovídajícího speciálně vytvořenému modelu. Dalším prvkem formálního jazyka je zde logická spojka & umožňující spojení atomů v komponované celky.
Dříve, než budou pravidla vytvoření formálního jazyka výrokové logiky zpřesněna, bude věnována pozornost expresivitě logických spojek neboli schopnosti logických spojek přiblížit se svými vlastnostmi vlastnostem spojek přirozeného jazyka.
Expresivita logických spojek
Expresivita formálního jazyka je úměrná tomu, do jaké míry je tento jazyk schopen postihnout způsob, jakým jsou ve výrazech přirozeného jazyka spojeny atomické výroky ve složitější významově soběstačné celky. V případech formálních jazyků používajících logických spojek jsou to právě ony, které tato spojení zprostředkovávají.
Logické spojky byly zavedeny tak, aby měly v přirozených jazycích své „protějšky“. Toto vzájemné přiřazení je však značně limitováno. Pěti výrokovými spojkami (, &, (, (, ( nelze vyjádřit celou bohatost spojení vět v jazyce přirozeném.
Např. spojka „nebo“ přirozeného jazyka, která bývá zpravidla reprezentována spojkou (, může nebo nemusí být vylučující.
Ve větě
„Ema si koupila boty nebo kabelku.“
nemá spojka „nebo“ vysloveně vylučující smysl, proto je při modelování možno použít logickou spojku (.
Ve větě
„Jana udělala zkoušku z logiky na výbornou nebo velmi dobrou.“
jde jednoznačně o smysl vylučující, proto spojku ( použít nelze.
Spojka „a“ rovněž ne vždy odpovídá logickému &. Na příklad
dvojice vět
„Zaplaval si a vrátil se do hotelu.“ a
„Vrátil se do hotelu a zaplaval si.“,
která by měla vystihovat vlastnost komutativnosti spojky &, vyjadřuje spíše jistou časovou následnost způsobující, že se zde jeví jako vhodnější použít spojky ( , která komutativní není.
Mnohé spojky přirozeného jazyka vůbec nejsou pravdivostně - funkční. Např. ve větě
„Pavel nešel do školy, ale (nýbrž) za školu.“
spojka „ale“ („nýbrž“) nemá svůj přímý protějšek ve formální výrokové logice, lze však pro ni s úspěchem použít logickou spojku & :
„Pavel nešel do školy.“ & „Pavel šel za školu.“
Velmi důležitou spojkou je spojka ( implikace, neboť modeluje jak odvozování v matematice, tak i v jiných oblastech logického uvažování. Protože umožňuje vyjádřit, že z určitých předpokladů vyplývají určité závěry, je základní spojkou pro použití v umělé inteligenci. První z operandů implikace se nazývá antecedent, druhý konsekvent.
Výrok je tvrzení deklarativního typu, o jehož pravdivostní hodnotě („pravdivý“/„nepravdivý“) má smysl uvažovat. Výroky jsou elementární neboli atomické, které již dále nelze rozložit na výroky jednodušší, nebo komponované.
GRAMATIKA JAZYKA L VÝROKOVÉ LOGIKY
Stromová reprezentace výrokové formule
Definice . (stromu a cesty)
Strom je množina S prvků nazývaných uzly částečně uspořádaná relací ( s nejmenším prvkem r ( S, který se nazývá kořen stromu. Přitom pro každý uzel stromu, který není kořenem, platí, že množina jeho předchůdců je dobře uspořádána relací ( .
Strom, jehož každý uzel má nejvýše n následníků, se nazývá n-árním stromem.
Cestou stromem S je každá maximální lineárně uspořádaná podmnožina S.
Uzel stromu S, který nemá následníka, je listem stromu.
Následující definice úrovní stromu bude tzv. induktivní definicí, která se vyznačuje tím, že je v ní definována
báze, v níž je stanoveno, jaké objekty jsou objekty výchozími (bázovými),
indukce, která stanoví pravidla, jak lze z již vytvořených objektů získat objekty další,
generalizace která vymezuje induktivně definovanou množinu pomocí její báze a indukce jako celek..
Definice . (úrovní stromu)
báze : nultá úroveň stromu S náleží jeho kořeni
indukce : (k+1)-ní úroveň stromu S tvoří ty jeho uzly, které jsou bezprostředními následníky uzlů k-té úrovně.
generalizace : každou z úrovní stromu S tvoří pouze uzly určené pomocí báze a příslušného počtu kroků indukce.
Definice . (hloubky stromu)
Hloubka stromu je takové maximální n, pro něž existuje uzel n-té úrovně.
Definice . (ohodnoceného stromu)
Ohodnocený strom je strom S spolu s funkcí přiřazující každému jeho uzlu objekt, který je jeho návěštím.
Stromová reprezentace konstrukce formule vychází z těchto pojmů teorie grafů:
Strom je množina S uzlů částečně uspořádaná relací ( s nejmenším prvkem r ( S, který se nazývá kořenem stromu. Přitom pro každý