Deductive Systems CCIS 227
Popular in Course
Popular in Computer & Information Science
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
CHEM 111 (Section 64)
verified elite notetaker
verified elite notetaker
This 20 page Class Notes was uploaded by Ida Kunde on Monday October 5, 2015. The Class Notes belongs to CCIS 227 at Clark Atlanta University taught by Peter Molnar in Fall. Since its upload, it has received 40 views. For similar materials see /class/219532/ccis-227-clark-atlanta-university in Computer & Information Science at Clark Atlanta University.
Reviews for Deductive Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/05/15
Arti cial Intelligence Propositional Calculus First order Predicate Logic Peter Molnar Objectives inbrief 0 De nition of Propositional Calculus Syntax and Semantics 0 Proof of logical equivalence using truth tables and identities 0 Application of our new knowledge in exercises indepth 0 De nition of Propositional Calculus Syntax and Semantics 0 Proof of logical equivalence using truth tables and identities 0 Application of our new knowledge in exercises ltinzactiongt 0 De nition of Propositional Calculus Syntax and Semantics 0 Proof of logical equivalence using truth tables and identities 0 Application of our new knowledge in exercises Boole approached logic in a new way reducing it to a sim ple algebra incorporating logic into mathematics He also worked on differential equations the calculus of nite dif ferences and general methods in probability 0 httpwwwhistorymcsstandrewsacuk historyMathematiciansBoolehtml o httpenwikipediaorgwikiGeorgeBoole 1 Gates And Boolean Logic 11 lates Device Level implementation of logical gates with transistors bipolar and MOS Metal Oxide Semiconductor TTL Transistor Transistor Logic fast high load power hungry 5 Volts MOS PMOS NMOS CMOS slower but take less space use less power Time required to switch from one state to the other is typically a few nanoseconds 10795 Most CPUs are built in CMOS only 33 Volts 2 we Culhrol W l sis Enf39ll rum 32 12 Logic 0 Logic 0 Boolean logic is a subset of Boolean algebia which oleals with sets of elements All lules anol opeiations of logic can be applieol to s O A Boolean Variable assumes the Values Llue 0 false 0 In a computei a ooolean vaiiable can be iepiesenteol by a single bf bit 0 A bit string is a sequence of ZeIO 0 mole bits stiing is the numbe of bits in the stiing The length of the 0 Usually bit stiings ale of paiticulai lengths a lo 32 etc 0 Bit operations couespond to the logical connectives applied on hits at the same position of the bit stiings 2 21 22 23 Propositional Calculus Propositional Calculus Symbols propositional symbols P Q R S truth symbols true false connectives A V n a or i i or Propositional Calculus Sentences Every propositional symbol and truth symbol is a sentence For example true P Q and R are sentences The negation of a sentence is a sentence For example P false The conjunction of two sentences is a sentence For example P Q The disjunction of two sentences is a sentence For example P V Q The implication of two sentences is a sentence For example P a Q The equivalence of two sentences is a sentence For example P E Q Terminology Legal sentences are also called wellformed formulas In an expression P Q P and Q are called the conjuncts In an expression P V Q P and Q are called the disjuncts In an implication P a Q P is the premise or antecedent and Q is the conclusion of consequent 24 25 26 Parenthesis Parenthesis are used to group symbols into sub expressions and to de ne the order of evaluation and meaning Propositional Calculus Semantics The interpretation of a set of propositions is the assignment of a truth value either T or F to each propositional symbol The symbol true is always assigned T and false is assigned F The interpretation of the truth value of sentences is determined by negation P is F if the assignment of P is T and T if the assignment of P is F conjunction P Q is T if both conjuncts have the value T oth erwise it is F disjunction P V Q is F if both conjuncts have the value F oth erwise it is T implication P a Q is F only if the premise is T and the impli cation is F otherwise it is T equivalence E is T only if both expressions have the same truth assignment for all possible interpretations otherwise it is F Converse and Contrapositive For the proposition P a Q the proposition Q a P is called its con verse and the proposition Q a P is called its contrapositive For example for the proposition 77lf it rains then I get wet Converse lfl get wet then it rains Contrapositive If I dont get wet then it does not rain The converse of a proposition is not necessarily logically equivalent to it that is they may or may not take the same truth value at the same time o The contrapositive of a proposition is always logically equivalent to the proposition Therefore7 If it rains7 then I get wet and If I dont get wet7 then it does not rain are logically equivalent 27 From English to Proposition lf then statements appear in various forms in practice The following list presents some of the variations These are all logically equivalent7 that is as far as true or false of statement is concerned there is no difference between them Thus if one is true then all the others are also true7 and if one is false all the others are false i If P 7 then Q i P irnplies Q 7 If P7 Q i P only if Q i P is suf cient for Q 7 Q if P i Q whenever P i Q is necessary for P i It is necessary for P that Q o For instance7 instead of saying lf she srniles then she is happy 7 we can say lf she srniles7 she is happy 7 She is happy whenever she srniles 7 She srniles only if she is happy etc without changing their truth values 0 Only if can be translated as then For exarnple7 She srniles only if she is happy is equivalent to lf she srniles7 then she is happy Note that She srniles only if she is happy rneans lf she is not happy7 she does not srnile 7 which is the contrapositive of lf she srniles7 she is happy You can also look at it this way She srniles only if she is happy rneans She srniles only when she is happy So any time you see her smile you know she is happy Hence lf she srniles7 then she is happy Thus they are logically equivalent Also lf she smiles she is happy is equivalent to lt is necessary for her to smile that she is happy For lf she smiles she is happy means lf she smiles she is always happy That is she never fails to be happy when she smiles Being happy is inevitable consequencenecessity of smile Thus if being happy is missing then smile can not be there either Being happy is necessary for her to smile or equiva lently lt is necessary for her to smile that she is happy 2 8 Reasoning Reasoning is done on propositions using inference rules For exam ple if the two propositions if it snows then the school is closed and it snows are true then we can conclude that the school is closed is true In everyday life that is how we reason To check the correctness of reasoning we must check whether or not rules of inference have been followed to draw the conclusion from the premises However for reasoning in English or in general for reasoning in a natural language that is not necessarily straightforward and it often encounters some dif culties 1 Connectives are not necessarily easily identi ed as we can get a avor ofthat from the previous topic on variations of if then state ments 3 If the argument becomes complicated involving many statements in a number of different forms twisted and tangled up it can easily get out of hand unless it is simpli ed in some way One solution for that is to use symbols and mechanize it Each sen tence is represented by symbols representing building block sentences and connectives For example if P represents it snows and Q rep resents the school is closed then the previous argument can be ex pressed as PgtQ PgtQ or To convert English statements into a symbolic form we restate the given statements using the building block sentences those for which symbols are given and the connectives of propositional logic not and or if then if and only if and then substitute the symbols for the building blocks and the connectives For example let P be the proposition lt is snowing Q be the propo sition l will go the beach and R be the proposition l have time Then rst l will go to the beach if it is not snowing is restated as lf it is not snowing I will go to the beach Then symbols P and Q are substituted for the respective sentences to obtain P a Q Similarly lt is not snowing and l have time only if I will go to the beach is restated as lf it is not snowing and l have time then I will go to the beach and it is translated as P R a Q 29 Identities These identities can be used to Change an expression into a syntactically different but logically equivalent form aaP E P 0 PVQ EnP Q the contrapositive law P a Q E uQ a uP de Morgans law uP v Q E uP A uQ and uP A Q E uP v uQ the commutative laws P A Q E Q A P and P v Q E Q v P the associative law P A Q A R E P A Q A 1 the associative law P v Q v R E P v Q v 1 the distributive law P v Q A R E P v Q A P v R the distributive law P A Q v R E P A Q v P A R 210 Proof of Equivalence o By using identities or truth tables 0 Example proof of P V Q E P a Q 3 Exercises 31 Exercise 1 o The exclusive or operator 8 may be de ned by the following truth table o Create an equivalent propositonal calculus expression using only A V and Prove their equivalence using a truth table 32 Solution V 33 Exercise 2 o The logical operator lt gt is read if and only if P lt gt Q is de ned as being equivalent to P a Q Q a P 0 Based on this de nition show that P lt gt Q is equivalent to P V Q a P Q by a series of substitutions using the identities 4 Predicate Calculus 0 ln Propositional Calculus each atomic symbol P Q denotes a proposi tion of some complexity that is either true or false There is no access to the components of the proposition For example instead letting a single symbol denote the entire sentence it rained on Tuesday we 41 42 can create a predicate weather that describes the relationship between a date and the weather condition weathertuesdayrain Through inference rules we can manipulate predicate calculus expres sions7 accessing their intgernal components and inferring new sentences Predicate calculus also allows expressions to contain variables7 which allow for the general assertions about classes of entities Eg we could state for all values of X7 where X is a day of the week7 the statement weatherX rain is true ie7 it rains every day of the week Symbols in Predicate Calculus Alphabet 1 Letters of the English alphabet7 upper and lower case 2 Digits 09 3 Underscore 77 to improve readability Symbols start with a letter7 followed by any of the characters listed above Examples for symbols George fire3 tonLandJerry bill ABC friendsof Symbols and Terms Truth symbols true and false reserved symbols Constant symbols are symbol expressions beginning with a lower case letter Variable symbols beginning with upper case character Function symbols7 beginning with a lower case character Functions have an attached arity indicating the number of elements of the do main mapped onto each element of the range A predicate calculus term is either a constant7 a variable or a function Functions use parenthesis to enclose their comma separated arguments 11 43 44 45 Predicates Symbols may also represent predicates start with lower case letter7 just like functions and constants A predicate names the relationship between zero or more objects in the world The number of objects is related to the arity of the predicate Examples likes equals on near partof Lower Case 7 Upper Case Notation Textbooks differ in their notation with respect to upper and lower case letters some use variables in upper case7 and everything else in lower case others do it in reverse Whichever notation is chosen7 predicates and static symbols are of the same case7 and variables of the other Predicates and functions can be easily identi ed by their parentheses variables are preceded by quan ti ers Sentences An atomic sentece is a predicate of arty n followed by n term enclosed in parenthesis and separated by commsa Sentences are delimited by a period Examples likesgeorge7 kate likesgeorge7 susie likesgeorge7 sarah7 tuesday likesXgeorge friendsfatherdavid7 fatherandrew Truth values are also atomic sentences Atomic sentences are also called atomic expression7 atoms7 or propositions Atomic sentences can be combined by logical operators connectives to form a new sentence 46 Variable Quanti ers 0 Variable Quanti ers V universal7 3 existential o More rules to combine sentences 47 i If X is a variable and s a sentence7 then VXs is a sentence i If X is a variable and s a sentence7 then 3X5 is a sentence 7 Examples 3X friends7 paul VXlz39kesXz cecream m0thereve able m0thereve cam fatheradam7 able fatheradam7 cam VXVlfatherX7 Y V 7notherX7 Y a parentX7 Y VXVYVZparentX7 Y parentX7 Z a siblingY Z Representation of English sentences in Firstorder Logic If it doesnt rain on Monday Tom will go to the mountains7 Emma is a Doberman pinscher and a good dog77 All basketball players are tall77 Some people like anchovies77 If wishes were horses7 beggars would ride77 Nobody likes taxes 77 51 Inference in Propositional and Predicate Logic Inference Rules Modus Ponens from an implication and the premise of the implica tion you can infer the conclusion ori oz B AndElimination from a conjunction you can infer any of the con juncts alengozn 0 AndIntroduction from a sequence of sentences you can infer their conjunctions 041042 O n alengozn OrIntroduction from a sentence you can infer its disjunction with anything 0 041V042VV04n DoubleNegation Elimination a a Unit Resolution 04 V 57 n5 a Resolution OtV n VV na v or equivalently or V y a i V 52 Syntax and Semantics Quanti ers 53 Substituting the name johnof an object for a variable PERSON7 bind ing variables johnPERSON Universal quanti cation V V ANIMAL catANIMAL mammalANIMAL For all animals that are cats we can imply they are mammals77 is true for all possible values of ANIMAL Existential quanti cation 3 3 ANIMAL sz steMANIMAL7 spot catANIMAL There exists an animal that is the sister of Spot and it is also a cat77 is true for at least one value Quanti ers Summary Negation Negation Equivalence When True When False Statement HxPQ Vm PQ For every x There is an x Pz is false for which Pz is true VxPQ Hm PQ There is an x Pz is true for for which PW is false every m o Nested quanti ers are quanti ers that appear within the scope of another quanti er VxVy gt 0 y lt 0 a my lt 0 V96 C96 V 31 C11 Fwy o The bf order of quanti ers is crucial bf Statement When True When False VXVYpX Y VYVXpX Y pX Y is true for ev ery pair of X Y There is a pair X Y for which pX Y is false VX3YpX Y For every X there is a Y for which pX Y is true There is an X such that pX Y is false for every Y HXVYpX Y There is an X for which pX Y is true for every Y For every X there is a Y for which pX Y is false 3X3Ypx Y 3Y3Xpx Y There is a pair X Y for which pX Y is true pX Y is false for ev ery pair X Y o Negation of quanti ers is applied in sequence from outside in 6 Using FirstOrder Logic 0 Domain a section of the world about which we wish to express some knowledge use of axioms and de nitions to capture basic facts of the domain 0 Example V MC m0therM C gt femaleM AparentMC V W H husbandH W gt maleH spouseH W V X maleX gt femaldX V P C parentP C gt childC P V G C grandparentG C gt 3P parentG P parentP C V X Y siblingX Y gt X 31 Y 3P parentP X parentP Y 61 Prolog Examples 0 Syntax similar to rst order logic predicate calculus o Exceptions 04 i B a beta alpha ozA 6 alpha beta on 6 alpha beta l alpha beta 0 No equivalence gt 62 Inference Rules Involving Quanti ers Notation SUBST Xsam7 Ypam l k65X Y likessampam 0 Universal Elimination For any sentence a variable V7 and ground term 1 9 V V 04 SUBSTltV9agt For example7 from V x lz39kesXz ceC ream7 we can use substitution Xben and infer l k65ben ceCream o Existential Elimination For any sentence oz variable V7 and con stant symbol k that does not appear elsewhere in the knowledge base 3 V 04 SUBSTVka For example from 3 X kz39llX7 victim we can infer kz39llmurderervictim7 as long as murderer does not appear elsewhere 0 Existential Introduction For any sentence oz variable V that does not occur in a and ground term 9 that does occur in a 3 V SUBSTgVa For example from l k65jerry ceCream we can infer 3 z l k65z ceCream 1 ground term does not include variables 17 63 Using Inference Rules The law says that it is a crime for an American to sell weapons to hostile Nations The country Nono an enemy of America has some missiles and all of its missiles were sold to it by Colonel West who is American77 V X Y Z americanX A weaponY A nationZ A hostileZ AsellsX Y Z criminalX 00 enemy mono america to 3 X ownsnono X A missileX 2 V X ownsnono X A missileX sellswest nono X 3 V X missileX weaponX 4 V X enemyXamerica hostileX 5 americanwest 6 nationnono 7 nation america 64 Using Inference Rules cont d 0 Process of nding proof can be formulated as as search process lnitial state KB sentences 179 Operators applicable inference rules Goal Test KB containing criminal west 0 Important characteristics The proof is 14 steps long The branching factor increases as the knowledge base grows because some inference rules combine existing facts Universal Elimination can have an enormous branching factor because we can replace the variable by any ground term Most common step combining atomic sentences into conjunctions instantiating universal rules to match and then apply Modus Ponens 65 66 67 Generalized Modus Ponens Combine And Introduction7 Universal Elimination7 and Modus Ponens 7712352160711 0wnsn0n0m1 V X 771235214X 0107150107107 X i sellswestn0n0X infer in one step sellswest7 71071077711 Find some X in the knowledge base such that X is a missile and Nono owns X7 and then infer that West sells the missile to Nono Even if we knew V Y 0wnsYm1 more general assertion7 we can nd the substitutions Xml and Ynono Generalized Modus Ponens cont d Generalized Modus Ponens For atomic sentences pi p and q7 where there is a substitution 6 such that SUBST6pg SUBST9017 for all 239 101102pn7 plpgApn q SUBST6q p3 is missildml 102 is 0wnsYml7 6 is XmLYnono7 p1 is 771235214X p2 is ownsnonoX7 q is sellswest7 7107107X7 and SUBST6q is sellswest7 71071077711 Generalized Modus Ponens Canonical Form Attempt to build an inference mechanism with one inference rule a Generalized Modus Ponens a sentence is either an atomic sentence or an implication with a conjunction of atomic sentences on the left premise and a single atomic sentence on the right Horn sentences Horn Normal Form One can convert sentences into Horn sentences when they are entered into the KB7 using Existential Elimination and And Elimination eg 3 X 0wnsn0n0X 771235214X is converted into two atomic Horn sentences 0wnsn0n0m1 and missildml 19 68 69 The universal quanti er is dropped since the existential quanti er is eliminated Generalized Modus Ponens Uni cation The uni cation routine UNIFY takes two atomic sentences p and q and returns a substitution that would make p and q look the same If there is no such substitution7 then UNIFY returns fail UNIFYpq 6 where SUBST6p SUBST6q 6 is called the uni er of the two sentences Uni cation Example Assertion kn0w5j0hnX hatesj0hnX Use Modus Ponens to nd out who he hates Knowledge base knowsj0m7 jane knowsY7 lean knowsY7 m0therY k7wwsX7 Elisabeth X and Y are implicitly universally quanti ed Uni cation UNIFYknostbmX7 knowsj0hnjane UNIFYknowsjohn7 X7 knowsY7 eon UNIFYknowsjohn7 X7 knowsY7 motherY UNIFYknowsjohn7 X7 knowsX7 Elisabeth Xjane Xleon7 Yjohn Yjohn7 Xmother john fail VVVV The last uni cation fails because X cannot take the value john and elz sabeth at the same time A way to solve this problem is to stan dardize apart the two sentences being uni ed rename variables to avoid the con ict 20
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'