Logika a logicke´ programova´nı´ te´mata ke zkousˇce Poslednı´ aktualizace: 16. prosince 2009
Zkousˇka je pı´semna´, skla´da´ se obvykle ze sedmi ota´zek (mu˚zˇe by´t vı´ce nebo me´neˇ, podle na´rocˇnosti ota´zek), z toho jsou obvykle dva prˇ´ıklady. Nejme´neˇ jeden z teˇchto prˇ´ıkladu˚ je z poslednı´ch oblastı´ zde uvedeny´ch (tj. Klauzula´rnı´ logika, KAS, Logicke´ programova´nı´). Hlavnı´m zdrojem informacı´ ke zkousˇce jsou skripta na stra´nce vyucˇujı´cı´ho http://fpf.slu.cz/˜vav10ui/log2.html vcˇetneˇ prˇ´ıkladu˚ v prˇ´ıloze. Definice, veˇty a du˚kazy mohou by´t i vlastnı´mi slovy (nemusı´te se je ucˇit zpameˇti), ale musejı´ obsahovat vsˇechny potrˇebne´ na´lezˇitosti.
1. Za´kladnı´ znalosti: (a) K zadane´ formuli vy´rokove´ logiky sestrojte ekvivalentnı´ formuli v konjunktivnı´ norma´lnı´ formeˇ. (b) V predika´tove´ logice definujte pojmy struktura, denotace, valuace individuove´ promeˇnne´, valuace termu, interpretace formule. Ukazˇte vsˇechny tyto pojmy na jednoduche´m prˇ´ıkladu. (c) V predika´tove´ logice definujte pojmy formule splnitelne´ ve strukturˇe, platne´ ve strukturˇe, logicky platne´. Napisˇte DeMorganovy za´kony pro kvantifika´tory. (d) Jaky´ je rozdı´l mezi se´manticky´mi a syntakticky´mi metodami dokazova´nı´? Ke kazˇde´mu typu du˚kazu˚ napisˇte dva za´stupce. Definujte pojmy deduktivnı´ u´sudek, odvozovacı´ pravidlo a du˚kaz. Z jake´ho vztahu vycha´zı´ princip neprˇ´ıme´ho du˚kazu a du˚kazu sporem? 2. Forma´lnı´ syste´my: (a) Jaky´ je rozdı´l mezi prˇ´ımy´m a neprˇ´ımy´m du˚kazem? (b) Jaky´ je postup vytva´rˇenı´ logicky´ch syste´mu˚? Definujte pojmy forma´lnı´ syste´m, logicky´ syste´m, teorie. Soustrˇed’te se na jejich odlisˇnosti a prˇ´ıpadne´ na´slednosti prˇi jejich vytva´rˇenı´. 1
(c) Co to jsou axiomy (logicke´, specia´lnı´), odvozovacı´ pravidla? Napisˇte prˇ´ıklad (jake´hokoliv) logicke´ho a (jake´hokoliv) specia´lnı´ho axiomu. (d) Axiomaticke´ a prˇedpokladove´ forma´lnı´ syste´my – jaky´ je mezi nimi rozdı´l, cˇ´ım jsou urcˇeny? (e) Definujte vlastnosti forma´lnı´ch du˚kazovy´ch metod – se´manticka´ korektnost a u´plnost, bezespornost, minima´lnost. Jaky´ je vztah mezi bezespornostı´ a korektnostı´? (f) Napisˇte du˚kaz korektnosti se´manticke´ho tabla. (g) Napisˇte du˚kaz u´plnosti se´manticke´ho tabla. 3. Syste´m prˇirozene´ dedukce: (a) Definujte Syste´mu prˇirozene´ dedukce vy´rokove´ logiky (jazyk, dedukcˇnı´ pravidla). (b) Napisˇte veˇtu o substituci vcˇetneˇ postupu du˚kazu. (c) Napisˇte rozsˇ´ırˇenou veˇtu o substituci vcˇetneˇ postupu du˚kazu. Jaky´ je vy´znam te´to veˇty – k cˇemu je na´m uzˇitecˇna´? (d) Definujte prˇ´ımy´ du˚kaz formule z prˇedpokladu˚. (e) Napisˇte veˇtu o dedukci a jejı´ du˚kaz. (f) Definujte neprˇ´ımy´ du˚kaz formule z prˇedpokladu˚. (g) Jak postupujeme v du˚kazu s prˇ´ımou a neprˇ´ımou hypote´zou? Vysveˇtlete pojmy prˇ´ıma´ a neprˇ´ıma´ hypote´za. Napisˇte veˇtu o prˇ´ıme´ hypote´ze a jejı´ du˚kaz. (h) Co je to veˇtveny´ du˚kaz z hypote´z – prˇ´ımy´ a neprˇ´ımy´? Napisˇte veˇtu o prˇ´ıme´m veˇtvene´m du˚kazu vcˇetneˇ jejı´ho du˚kazu. (i) Naznacˇte postup du˚kazu korektnosti Syste´mu prˇirozene´ dedukce vy´rokove´ logiky (postup musı´ by´t cely´, ale pokud se dı´lcˇ´ı kroky opakujı´, naprˇ´ıklad pro ded. pravidla, lze uve´st jen dva cˇi trˇi z nich a u ostatnı´ch poznamenat, zˇe postup je zde podobny´). (j) Napisˇte lemma o neutra´lnı´ formuli vcˇetneˇ du˚kazu. (k) Napisˇte lemma o se´mantice a dokazatelnosti vcˇetneˇ naznacˇenı´ du˚kazu. (l) Naznacˇte postup du˚kazu u´plnosti Syste´mu prˇirozene´ dedukce vy´rokove´ logiky. (m) Dokazˇte bezespornost Syste´mu prˇirozene´ dedukce vy´rokove´ logiky. (n) Definujte Syste´m prˇirozene´ dedukce predika´tove´ logiky (jazyk, dedukcˇnı´ pravidla vcˇetneˇ potrˇebny´ch omezenı´). (o) Naznacˇte postup du˚kazu korektnosti Syste´mu prˇirozene´ dedukce predika´tove´ logiky (postup musı´ by´t cely´, ale pokud se dı´lcˇ´ı kroky opakujı´, naprˇ´ıklad pro ded. pravidla, lze uve´st jen jeden z nich – navı´c oproti vy´rokove´ logice, prˇ´ımy´m du˚kazem logickou u´vahou – a u ostatnı´ch poznamenat, zˇe postup je zde podobny´). 2
(p) Soucˇa´stı´ pı´semky mu˚zˇe by´t ktery´koliv prˇ´ıklad z teˇch, ktere´ jsou ve skriptech uvedeny u Syste´mu prˇirozene´ dedukce. 4. Klauzula´rnı´ logika: (a) Definujte klauzule a Hornovy klauzule vcˇetneˇ prˇepisu na implikaci. (b) Definujte term, ba´zovy´ term, atom, ba´zovy´ atom, klauzuli pro klauzula´rnı´ logiku. (c) Univerza´lnı´ a existencˇnı´ tvrzenı´ – kdy pouzˇ´ıva´me promeˇnnou, kdy existencˇnı´ konstantu a kdy existencˇnı´ funktor – vztah prˇi prˇepisu z predika´tove´ logiky, uved’te take´ prˇ´ıklady. (d) Se´mantika jazyka klauzula´rnı´ logiky – definujte strukturu, aplikovatelnou strukturu, denotacˇnı´ zobrazenı´, valuaci promeˇnne´ a termu. (e) Se´mantika jazyka klauzula´rnı´ logiky – definujte interpretaci atomu (vcˇetneˇ predika´tu s existencˇnı´mi parametry) a interpretaci klauzule, definujte klauzuli nepravdivou a pravdivou ve strukturˇe, platnou a neplatnou ve strukturˇe, logicky platnou (logicky´ za´kon). (f) Co to znamena´, kdyzˇ je v klauzuli klauzula´rnı´ logiky pra´zdna´ mnozˇina v antecedentu nebo konsekventu? Co kdyzˇ jsou pra´zdne´ obeˇ? Jak se rˇesˇ´ı konjunkce a disjunkce atomu˚ v antecedentu a konsekventu – z jaky´ch vztahu˚ (z vy´rokove´ logiky) vycha´zı´ postup? (g) Jak se prova´dı´ negace atomu˚ (ba´zovy´ch i teˇch, ktere´ nejsou ba´zove´)? Jak prova´dı´me negaci cele´ klauzule, co je to popı´rajı´cı´ mnozˇina klauzule? Ukazˇte take´ na jednoduche´m prˇ´ıkladu (s ru˚zneˇ kvantifikovany´mi promeˇnny´mi). (h) Jaka´ jsou omezenı´ pro pouzˇitı´ predika´tu rovnosti? (zdu˚vodneˇte, ukazˇte na prˇ´ıkladu) (i) Definujte substituci termu˚ za promeˇnne´. Definujte existencˇnı´ substituci. Obojı´ ukazˇte na prˇ´ıkladu. (j) Odvod’te rezolucˇnı´ odvozovacı´ pravidlo klauzula´rnı´ logiky z rezolucˇnı´ho pravidla predika´tove´ logiky. (k) Definujte pojmy unifikace, unifika´tor, obecneˇjsˇ´ı a nejobecneˇjsˇ´ı unifika´tor, mnozˇinu neshod (i k cˇemu slouzˇ´ı). (l) Napisˇte algoritmus nalezenı´ nejobecneˇjsˇ´ıho unifika´toru. (m) Definujte znalostnı´ ba´zi klauzula´rnı´ logiky a popisˇte zpu˚sob jejı´ho vytvorˇenı´ (vcˇetneˇ reprezentace struktury pro interpretaci). (n) Definujte strukturu aplikovatelnou na znalostnı´ ba´zi, model znalostnı´ ba´ze, napisˇte, kdy je klauzule logicky´m du˚sledkem znalostnı´ ba´ze. (o) Mozˇne´ prˇ´ıklady: • prˇepis veˇty prˇirozene´ho jazyka na klauzuli klauzula´rnı´ logiky a naopak (vcˇetneˇ existencˇnı´ch tvrzenı´, rˇesˇenı´ negace atomu a konjunkce a disjunkce atomu˚), 3
• • • •
negace klauzule, vytvorˇenı´ znalostnı´ ba´ze, provedenı´ substituce, odvozova´nı´ ze znalostnı´ ba´ze (prˇ´ıpadneˇ souhrnny´ prˇ´ıklad – sestavte ba´zi a odvod’te z nı´ . . .
5. Klauzula´rnı´ axiomaticky´ syste´m: (a) definujte Klauzula´rnı´ axiomaticky´ syste´m (jazyk, logicke´ axiomy, specia´lnı´ axiomy, odvozovacı´ pravidla). (b) Vypisˇte pomocna´ odvozovacı´ pravidla Klauzula´rnı´ho axiomaticke´ho syste´mu. (c) Definujte prˇ´ımy´ du˚kaz klauzule ze znalostnı´ ba´ze a neprˇ´ımy´ du˚kaz klauzule ze znalostnı´ ba´ze. (d) Naznacˇte du˚kaz korektnosti Klauzula´rnı´ho axiomaticke´ho syste´mu (musı´ by´t vsˇechny cˇa´sti du˚kazu, i kdyzˇ ty, ktere´ lze prˇeve´st na predika´tovou logiku, mohou by´t jen naznacˇeny). (e) Mozˇne´ prˇ´ıklady: vytvorˇenı´ znalostnı´ ba´ze podle zadany´ch veˇt a odvozenı´ dane´ho za´veˇru (le´pe neprˇ´ımy´m du˚kazem, je vhodne´ pouzˇ´ıt linea´rnı´ metodu). 6. Logicke´ programova´nı´: (a) Co je to Prolog, jaky´ je to typ jazyka? Napisˇte alesponˇ jednu implementaci Prologu. Co je to program v Prologu (fakty, pravidla, teˇlo a hlava klauzule), jak v Prologu pracujeme (program a dotazy, jak s cˇ´ım zacha´zı´me), jak probı´ha´ prˇepis klauzulı´ klauzula´rnı´ logiky do Prologu? (b) Co je to internı´ databa´ze Prologu, konzultova´nı´ a rekonzultova´nı´ programu a jak se prova´dı´ (menu i prˇ´ıkazy)? Jak lze vypsat seznam vsˇech klauzulı´ v databa´zi, ktere´ majı´ v hlaveˇ urcˇity´ konkre´tnı´ predika´t? (c) Co je to anonymnı´ promeˇnna´, kdy ji pouzˇ´ıva´me, jaky´ ma´ vy´znam v programu a jaky´ v dotazu? Napisˇte prˇ´ıklad. Pokud chceme anonymnı´ promeˇnnou unifikovat na vı´ce mı´stech klauzule, jak to provedeme? (d) Jak se prova´dı´ negace atomu? Co se deˇje s promeˇnny´mi, jake´ proble´my mohou s negacı´ nastat a jak je rˇesˇ´ıme? Uved’te prˇ´ıklad spra´vne´ho a nespra´vne´ho rˇesˇenı´ (takove´ho, ktere´ mu˚zˇe zpu˚sobit chybne´ vyhodnocenı´ klauzule). (e) Jake´ jsou dva zpu˚soby reprezentace disjunkce atomu˚ v Prologu? Aritmeticke´ a relacˇnı´ opera´tory v Prologu – pouzˇ´ıvajı´ se jako termy nebo atomy? (f) Jak lze cˇi nelze pouzˇ´ıt predika´t rovnosti? Co to znamena´, zˇe relacˇnı´ opera´tor prova´dı´/neprova´dı´ unifikaci (prˇirˇazenı´) a zˇe je/nenı´ provedena interpretace argumentu˚? (g) Co se v Prologu deˇje prˇi vyhodnocenı´ X = 25, X is 1 + 1 a 2 =:= 1+1? (vy´razy mohou by´t na pı´semce jine´) 4
(h) Do klauzule polovina(X,Y) :- Y is X / 2. prˇidejte oveˇrˇenı´, zˇe X je rea´lne´ cˇ´ıslo. (mu˚zˇe by´t trochu jina´ klauzule, doplnˇujeme trˇeba take´ oveˇrˇenı´, zˇe jde o cele´ cˇ´ıslo apod.) (i) Definujte rezolucˇnı´ uza´veˇr mnozˇiny klauzulı´ (cela´ definice, vcˇetneˇ zobrazenı´ R). (j) Napisˇte veˇtu o Robinsonoveˇ rezolucˇnı´m principu a naznacˇte jejı´ du˚kaz. (k) Co znamena´ v logicke´m programova´nı´ generova´nı´ do sˇ´ırˇky, generova´nı´ do hloubky, linea´rnı´ metoda? (l) Definujte linea´rnı´ vy´pocˇetnı´ strom klauzule, popisˇte prohleda´va´nı´ stromu do hloubky a do sˇ´ırˇky. Jak se lze vyhnout zacyklenı´ vy´pocˇtu prˇi jednom z teˇchto typu˚ prohleda´va´nı´? (m) Napisˇte, jak je rezoluce pouzˇita v Prologu, co je to cı´lova´ klauzule a cı´l, jak jsou pouzˇ´ıva´ny unifikace, k cˇemu prˇi vy´pocˇtu slouzˇ´ı za´sobnı´k (co se do neˇho ukla´da´ a kdy, kdy se data vyjı´majı´), co je to navracenı´ (backtracking). (n) Vysveˇtlete, jak Prolog zacha´zı´ s dotazy (v jake´m tvaru – pozitivnı´m cˇi negovane´m – jsou dotazy poda´va´ny, jak je Prolog cha´pe/zpracova´va´). (o) Naznacˇte algoritmus vy´pocˇtu klauzule (dotazu) v Prologu pro prˇ´ıpad, zˇe v klauzuli nejsou zˇa´dne´ promeˇnne´. (p) Popisˇte mozˇnosti rˇ´ızenı´ vy´pocˇtu v Prologu – predika´ty call, fail a predika´t rˇezu – vy´znam jednotlivy´ch predika´tu˚, mozˇnosti vyuzˇitı´ (lze uka´zat i na prˇ´ıkladech). Jak je definova´n predika´t not? (q) Mozˇne´ prˇ´ıklady: • prˇepis veˇty nebo klauzule klauzula´rnı´ logiky do Prologu (vcˇetneˇ anonymnı´ch promeˇnny´ch, negacı´ apod.), • vytvorˇenı´ programu z veˇt prˇirozene´ho jazyka nebo podle znalostnı´ ba´ze klauzula´rnı´ logiky (je trˇeba dodrzˇet vhodne´ porˇadı´ klauzulı´ a atomu˚ v klauzulı´ch, aby nedocha´zelo k zacyklenı´ vy´pocˇtu), • prˇepis veˇty na dotaz.
5
