Bài giảng Hệ chuyên gia (Expert System) - Chương 2: Biểu diễn tri thức nhờ logic vị từ bậc một (Phần 2) - Phan Huy Khánh

HHệệ chuyênchuyên giagia ((ExpertExpert SystemSystem))
 PGS.TS. Phan Huy Khánh
 khanhph@vnn.vn
 Chương 2
 Biểu diễn tri thức
 nhờ logic vị từ bậc một 
 2.2
 ChChươươngng 22
 BiBiểểuu didiễễnn tritri ththứứcc nhnhờờ logiclogic vvịị ttừừ bbậậcc mmộộtt
aaPhPhầầnn 2.22.2 ::
 V Khái niệm lôgic
 V Lôgic mệnh đề
 2/68
 TheThe 44 ColorColor TheoremTheorem
a In 1879, Kempe produced a famous proof of the 4 color 
 theorem:
 V Using only 4 colors
 V Any map of countries can be colored in such a way that 
 no 2 bordering countries have the same color
a In 1890, Heawood showed:
 V The proof not to be a proof at all!
a When is a proof a proof, and when is it not a proof?
a Logic to the rescue!
 3/68
 WhatWhat isis thethe logic?logic?
a Logic is the science of reasoning, proof, thinking,
 or inference
a Logic allows us to analyze a piece of reasoning
 and determine whether it is correct or not
a To use the technical terms, we determine whether
 the reasoning is valid or invalid
a When people talk of logical arguments, though, 
 they generally mean the type being described here
 4/68
 LogicLogic
a Logic is the study of reasoning
a In particular:
 V Logic studies the conditions under which we can say that a 
 piece of reasoning is valid
 V I.e. that something (the conclusion) can be said to follow 
 from something else (the premises, givens, assumptions)
a Ontology (ont = ‘to be’; logica = ‘word’):
 kinds of things one can talk about in the language
 5/68
 ArgumentsArguments inin LogicLogic
a What is an Argument?
 V "An argument is a connected series of statements intended to 
 establish a proposition“
a An argument refers to the formal way facts and rules of 
 inferences are used to reach valid conclusions
a The process of reaching valid conclusions is referred to as 
 logical reasoning
 6/68
 LogicLogic inin generalgeneral
a A logic is a formal system of representing knowledge
a Logics are formal languages for representing information 
 such that conclusions can be drawn
a Syntax defines the sentences (statements) in the language
a Semantics define the "meaning" of sentences
 V i.e., define truth of a sentence in a world
a Proof theory
 V How conclusions are drawn from a set of statements
 7/68
 DeductionDeduction andand InductionInduction
a If the conclusion has to be true assuming the truth of the 
 premises, we call the reasoning deductive
a If the conclusion is merely more likely to be true than false 
 given the truth of the premises, we call the reasoning 
 inductive
a Logic studies both deduction and induction, but does tend 
 to focus on deduction, especially formal logic
 8/68
 NormativeNormative andand DescriptiveDescriptive TheoriesTheories ofof ReasoningReasoning
a Psychology of reasoning is a scientific study of how humans reason:
 V What do humans infer from what?
 V What is the mechanism behind human reasoning?
a As such, psychologists come up with descriptive theories of reasoning: 
 hypotheses as to how humans reason based on empirical studies.
a Logicians, however, try to come up with normative theories of 
 reasoning:
 V What actually follows from what?
a Question: But if not empirical, what is the basis for such theories? 
 (Human!) reason alone?
 9/68
 ImplicationImplication andand TruthTruth
a Logic tells us about implication, not truth
a Example:
 V “All flurps are toogle, but not all flems are toogle, so not all flems
 are flurps” is perfectly logical, but tells us nothing about what-is-
 the-case.
a One exception:
 V Implication itself can be seen as a kind of (necessary) truth
 V So, logic can tells us that certain statements of the form “If 
 then ” are necessarily true (i.e. true in all 
 possible worlds), and hence true in our world as well
 10/68
 LogicLogic andand ScienceScience
a Of course, if I do know that my premises are true, then if 
 the reasoning is (deductively) valid I know the conclusion to 
 be true as well
a But that’s just science: science combines observation (facts) 
 with logic (reasoning), to get to truth (laws of physics, 
 chemistry, etc)
a Of course, scientific reasoning is inherently inductive: a 
 finite set of data is always compatible with multiple theories
a Hence: scientific theories can change over time.
 11/68
 LogicLogic andand MathematicsMathematics
a Most of what I just said for logic is true
 for mathematics as well!
 V Scientists use mathematics to help figure out (calculate, 
 compute, etc) what-is-the-case but mathematics alone does 
 not tell us what-is-the-case
 V Like logic, mathematical theorems are proven from a set of 
 definitions or axioms: if those axioms or definitions don’t 
 apply to our world, then the theorem doesn’t say anything 
 about our world either. 
 V The only thing we can claim to be certain of is a statement of 
 the form “If then <some 
 claim>”. 
 V So, theorems like “There is no greatest prime number” are 
 really expressions of “If we define ‘number’ to be ..., and 
 ‘prime’ as  and ‘greater than’ as , then there is no 
 greatest prime number.”
 12/68
 FurtherFurther SimilaritiesSimilarities BetweenBetween
 LogicLogic andand MathematicsMathematics 
a Both logic and mathematics have been around for 
 thousands of years
a Both logic and mathematics study abstractions that can be 
 applied to any subject matter
a Formal logic is probably best seen as a branch of 
 mathematics
a Mathematics can be applied to formal logic
 (mathematical logic)
a Formal logic can be applied to mathematics
 (theorem proving)
 13/68
 FormalFormal LogicLogic
a We can determine that “All flurps are toogle, but not all 
 flems are toogle, so not all flems are flurps” is a valid 
 inference because of the abstract form of the reasoning: 
 “All P’s are Q’s, but not all R’s are Q’s, so not all R’s are P’s”
a Formal logic is just that: studying the validity of reasoning 
 by looking at its abstract form: 
 V Just as in mathematics:
 ™ 1) expressions of abstract symbols are assigned the objects of 
 study, and 
 ™ 2) by manipulating these expressions of abstract symbols, we 
 can figure something out about these objects
 14/68
 LittleLittle HistoryHistory ofof FormalFormal LogicLogic
a Formal logic goes back at least to Aristotle, probably earlier
a In Medieval Times work was being done on categorical 
 syllogisms like the one on previous page (that one would be 
 classified as AOO-2)
a ‘Modern’ formal logic was developed in mid 19th century by 
 people like Georges Boole and Augustus DeMorgan
a They developed the system of propositional or truth-
 functional logic
a The much more powerful system of first-order logic (or 
 predicate logic or quantificational logic) was completed by 
 the turn of the 20th century
a Many other systems of logic have been developed since; 
 just as with mathematics, different systems have different 
 applications
 15/68
 TruthTruth--FunctionalFunctional LogicLogic
a Applies to reasoning dealing with compound sentences built 
 from truth-functional operators like ‘and’, ‘or’, ‘not’,
 and ‘if  then’.
a An operator is truth-functional in that the truth-value of a 
 sentence like “P and Q” is a function of the truth-values of 
 the sentences P and Q
 16/68
 NonNon--standardstandard logicslogics
1. Categorical logic 15. Linear logic
2. Combinatory logic 16. Many-valued logic
3. Conditional logic 17. Modal logic
4. Constructive logic 18. Non-monotonic logic
5. Cumulative logic 19. Paraconsistent logic
6. Deontic logic 20. Partial logic
7. Dynamic logic 21. Prohairetic logic
8. Epistemic logic 22. Quantum logic
9. Erotetic logic 23. Relevant logic
10. Free logic 24. Stoic logic
11. Fuzzy logic 25. Substance logic
12. Infinitary logic 26. Substructural logic
13. Intensional logic 27. Temporal (tense) logic
14. Intuitionistic logic a In short: a lot!
 a In short: a lot!
 17/68
 PropositionalPropositional LogicLogic
a A relatively simple framework for reasoning
a Can be extended for more expressiveness at the cost of 
 computational overhead
a Important aspects
 V Syntax
 V Semantics
 V Validity and inference
 V Models
 V Inference rules
 V Complexity
a Principles of propositional logic
 V Sentences, syntax, semantics, inference
a But major limitations of propositional logic
 18/68
 VVíí ddụụ
Mệnh đề lôgích Giải thích
 Tuỳ theo giá trị của x và y mà có
y > x + 1 giá trị đú ng hoặc sai. Chẳng hạn 
 x=1 và y=3 thì có giá trị đúng
 Đúng nếu t ại thời đ iểm nó i ra 
Hôm nay trời mưa !
 trời mưa thật, sai nếu không phải
2 + 3 = 5 Luôn luôn có giá trị đúng
Luânđôn là thủ đô của nước Đức Luôn luôn có giá trị sai 
Hôm nay là ngà y mấy ? Câu hỏi không ph ải m ệnh đề
 Câu mệnh lệnh cũng không phải 
Mời anh vào đây !
 là một mệnh đề, v.v...
 19/68
 ExamplesExamples
a 2 + 2 = 4
 V Is a proposition which true
a The moon is made of cheese
 V Is a proposition which is false
a It will rain tomorrow
 V Is a proposition
a This statement is false
 V Is not a proposition
a Vote for Mickey Mouse
 V Is not a proposition
 20/68
 SyntaxSyntax
a Symbols
 V Logical constants: true, false /* T, F | 1, 0 | Yes, No  */
 V Propositional symbols: P, Q, R, 
 V Logical connectives
 ™ Conjunction: ∧
 ™ Disjunction: ∨
 ™ Negation: ¬
 ™ Implication: →, (or ⇒)
 ™ Equivalence: ↔, (or ⇔)
 V Parentheses for grouping: ( , )
a Công thức chỉnh (CTC)
 Well-Formed formulas (wffs or sentences): w1, w2
 V Constructed from simple sentences: P, Q, R, 
 V Conjunction, disjunction, implication, equivalence, negation
 ™ (P ∧ Q) → ¬P
 ™ (¬P ∨ Q) ∨ R → S
 21/68
 BNFBNF GrammarGrammar PropositionalPropositional LogicLogic
 ::= | 
 ::= True | False | P | Q | R | ...
 ::= ( ) | 
 |
 |
 ¬¬ 
 ::= ∧∧ | ∨∨ | →→ | ↔↔
Ambiguities are resolved through precedence ¬ ∧ ∨ → ↔ or parentheses
e.g. ¬ P ∨ Q ∧ R → S is equivalent to (¬ P) ∨ (Q ∧ R)) → S 
 22/68
 BNFBNF GrammarGrammar PropositionalPropositional LogicLogic
 ::= | 
 ::= True | False | P | Q | R | ...
 ::= ( ) | 
 |
 |
 ¬¬ 
 ::= ∧∧ | ∨∨ | →→ | ↔↔
Ambiguities are resolved through precedence ¬ ∧ ∨ → ↔ or parentheses
e.g. ¬ P ∨ Q ∧ R → S is equivalent to (¬ P) ∨ (Q ∧ R)) → S 
 23/68
 SemanticsSemantics
a Interpretation of the propositional symbols and constants
 V Symbols can stand for any arbitrary fact
 ‹ Sentences consisting of only a propositional symbols are 
 satisfiable, but not valid
 ‹ The value of the symbol can be true or false
 ‹ Must be explicitly stated in the model
 V The constants True and False have a fixed interpretation
 ‹ True indicates that the world is as stated
 ‹ False indicates that the world is not as stated
a Specification of the logical connectives
 V Frequently explicitly via truth tables
 24/68
 ApplicationsApplications
a User defines the semantics of each propositional symbol:
 V P means “It is hot”
 V Q means “It is humid”
 V R means “It is raining”
a A sentence (well formed formula) is defined as follows: 
 V A symbol is a sentence
 V If S is a sentence, then ¬S is a sentence
 V If S is a sentence, then (S) is a sentence
 V If S and T are sentences, 
 then (S ∨ T), (S ∧ T), (S → T), and (S ↔ T) are sentences
 V A sentence results from a finite number of applications of the above rules
a Eg.
 V Q → P means: “If it is humid, then it is hot”
 V (P ∧ Q) → R means: “If it is hot and humid, then it is raining”
 25/68
 BBààii ttậậpp ttạạii llớớpp
a Chuyển các câu sau sang lôgic mệnh đề :
 1. Quạ tắm thì ráo, sáo tắm thì mưa
 2. Ông ăn chả, bà ăn nem
 3. Tạ i anh, tại ả, tại cả đôi bên
 4. (Ch ơ ai) đi mô rồi cũng nhớ về Hà Tịnh
 5. Bở i chưng bác mẹ em nghèo 
 Cho nên em phải băm bèo thái rau
 Mần reng tui có thể ?
 6. Trăng khoe trăng tỏ hơn đèn Dạ, đây :
 1. Lập các câu đơn (NNTN) 
 Cớ sao trăng phải chịu luồn đám mây
 Cớ sao trăng phải chịu luồn đám mâytheo tình huống/sự kiện
 7. Các chú học trò con 2. Đặt tên các biến MĐề
 7. Các chú học trò con 3. Tìm các phép nối lôgic 
 Đang lúc tuổi còn non
 Đang lúc tu ổi còn non tương ứng
 Các chú phải chăm học 4. Kiểm tra tính hợp thức
 Các chú phải chăm học 
 Có học mới nên khôn 5. Nhận kết quả
 Có học mới nên khôn 
 26/68
 EnglishEnglish TranslationsTranslations ofof NegationNegation
a Assume:
 V P represents the fact Penguins eat fish
 V Q represents the fact I have three children
a Then Negation:
 V ¬Q: Penguins do not like fish
 V ¬Q: I do not have three children
a Other Notation: ~P, ~Q
 P
 27/68
 EnglishEnglish TranslationsTranslations ofof ConjunctionConjunction
a Assume:
 P represents the fact This subject is boring
 Q represents the fact I am tired
a Then Conjunction P ∧ Q:
 V This subject is boring and I am tired
 V This subject is boring although I am tired
 V This subject is boring but I am tired
 P Q
 28/68
 EnglishEnglish TranslationsTranslations ofof DisjunctionDisjunction
a Assume:
 P represents the fact This subject is boring
 Q represents the fact I am tired
a Disjunction P ∨ Q 
 V P : Sue is a football player.
 V Q: Bob is lazy
 V P ∨ Q: Sue is a football player or Bob is lazy
 V Note: Disjunction is inclusive
 P Q
 29/68
 EnglishEnglish TranslationsTranslations ofof ConditionalConditional
a Assume:
 P represents the fact It is Tuesday Giải thích
 Q represents the fact We are in Belgium vì reng rứa ? 
a Then Conditional P → Q 
 V If it is Tuesday then we are in Belgium
 V It’s being Tuesday implies we are in Belgium
 V It’s Tuesday only if we are in Belgium
 V It’s being Tuesday is sufficient for us to be in Belgium
 P → Q ≡ ¬P ∨ Q P Q
 30/68
 If_ThenIf_Then VariationsVariations
a If-then statements appear in various forms in practice
a More Translations P → Q:
 V If P then Q
 V P implies Q
 V P only if Q
 V P is sufficient for Q
 V Q is necessary for P
 V Q provided that P
 V Q if P
 V If P, Q
 V Q whenever P
 V It is necessary for P that Q
 31/68
 EnglishEnglish TranslationsTranslations ofof DefinitionDefinition ¬¬PP →→ QQ
a Translations
 V If not P then Q
 V Unless P, Q
 V Q, unless P
a Examples
 V Unless Max is at home, Claire won’t get the message
 ¬HOME(max) → ¬GETSMESSAGE(claire)
 V b is cube, unless it is large
 ¬LARGE(b) → CUBE(b)
 32/68
 EnglishEnglish TranslationsTranslations ofof BiconditionalBiconditional PP ↔↔ QQ
a Translations Giải thích
 V P if and only if Q vì reng rứa ? 
 V P just in case Q 
 V P is a necessary and sufficient condition for Q
a Equivalencies
 V P and Q are sufficient and necessary for each other
 V P ↔ Q
 V (P → Q) ∧ (Q → P)
 V (P ∧ Q) ∨ (¬P ∧ ¬ Q) 
 P Q
 33/68
 MaryMary’’ss ExamExam ExampleExample
a Assume:
 Today Mary has a Law exam or a Computer Science exam or both
 She doesn’t have a Law exam
 Therefore she must have a Computer Science exam
a Then 
 L: Mary has a Law exam today
 C: Mary has a Computer Science exam today
 Premises: L ∨ C, ¬L
 Conclusion: C 
 34/68
 MoreMore examplesexamples ofof PLPL
a Assume
 V P represents the fact “Penguins eat fish”
 V Q represents the fact “Penguins like fish”
a then
 V P ∧ Q Penguins eat fish and penguins like fish
 V P ∨ Q Penguins eat fish or penguins like fish
 V Q → P Penguins eat fish therefore penguins like fish
 V P ↔ Q Penguins eat fish therefore penguins like fish
 and penguins like fish therefore penguins eat fish
a Fitness Example
 S: If I exercise then I will get fit, and I do exercise, so I will 
 get fit.
 E: I do exercise.
 F: I will get fit.
 S: (E → F) ∧ E → F
 35/68
 SomeSome termsterms
a The meaning or semantics of a sentence determines its 
 interpretation
a Given the truth values of all symbols in a sentence,
 it can be “evaluated” to determine its truth value
 (True or False)
a A valid sentence or tautology
 V A sentence that is True under all interpretations
 (equivalent with True)
 V Also called: “logically true”
 V Example: P∨¬P, “It’s raining or it’s not raining”
 36/68
 MoreMore termsterms
a An inconsistent sentence or contradiction 
 V A sentence that is False under all interpretations
 (equivalent with False)
 V Also called: “logically false”
 V Example: P∧¬P , “It’s raining and it’s not raining”
a As with equivalence: look at the truth tables
a P entails Q, written P |= Q, means that whenever P is 
 True, so is Q
a In other words, all models of P are also models of Q
 37/68
 TruthTruth TablesTables
a Truth Tables for Connectives
 P Q ¬ P P ∧ Q P ∨ Q P → Q P ↔ Q
 False False True False False True True
 False True True False True True False
 True False False False True False False
 True True False True True True True
 V One row for each possible combination of truth values for the 
 symbols in the sentence
 V The final value must be true for every sentence
 V A variation of the model checking approach
 V Not very practical for large sentences
 38/68
 TerminologyTerminology
a A literal is either a propositional variable, or the negation 
 of a propositional variable
 propositional variables
 disjunction of literals
 (P(P ∧∧ ¬¬RR ∧∧ Q)Q) →→ ((¬¬PP ∨∨ RR ∨∨ Q)Q) 
 literals
 conjunction of literals
 39/68
 SpecialSpecial FormsForms
a A formula is in Disjunctive Normal Form (DNF) if it is a 
 disjunction 
 D1 ∨ D2 ∨  ∨ Dn
 where each Di is a conjunction of literals
a A formula is in Conjunctive Normal Form (CNF) if it is a 
 conjunction 
 C1 ∧ C2 ∧  ∧ Cn
 where each Ci is a disjunction of literals
 40/68
 ExampleExample
a Disjunctive Normal Forms
 (¬P ∧ ¬R) ∨ (¬P ∧ Q) ∨ (Q ∧ ¬R) ∨ Q
 (¬P ∧ ¬R ∧ ¬Q) ∨ (¬P ∧ ¬R ∧ Q) ∨ (¬P ∧ R ∧ Q)
 ∨ (P ∧ ¬R ∧ Q) ∨ (P ∧ R ∧ Q) 
 ∨ (P ∧ ¬R ∧ Q) ∨ (P ∧ R ∧ Q) 
a Conjunctive Normal Forms
 (¬P ∨ ¬R ∨ Q) ∧ (¬P ∨ R ∨ Q) ∧ (P ∨ ¬R ∨ Q)
 (¬P ∨ Q) ∧ (¬R ∨ Q) 
 P ∧ Q 
 41/68
 LogicalLogical EquivalenceEquivalence
Two propositions are (logically) equivalent if and only if for each case 
their truth values are the same (“≡”)
also called identities
 Examples: 
 P ≡ (P∨P) “1+1=2” ↔ “1+1=2 or 1+1=2”
 ¬¬P ≡ P “He did not not do it” ↔ “He did it”
 ¬(P∧Q) ≡ ¬ P ∨ ¬Q 
 “If P then not P” ≡ “ not P”
 Proving that two propositions are equivalent 
 can be done by comparing their two truth tables
 42/68
 ExampleExample ofof EquivalenceEquivalence
a How to prove “Q ∧ (¬R→P) ↔ (R∧Q)∨(P∧Q)”?
a Earlier we saw
 while for the other proposition
 43/68
 BiconditionalBiconditional vs.vs. EquivalenceEquivalence
a Don’t confuse
 the equivalence ≡ with the biconditional ↔
 (only the biconditional has a truth table) 
a For example:
 P ≡ P is a proposition/tautology, 
 a statement within logic, 
 P ≡ P is mathematically correct,  about logic
 P ≡¬P is a contradiction (False), P Q P ↔Q
 P ≡¬P is incorrect
 T T T
 Hence P↔P ≡¬(P↔¬P), and so on
 T F F
 F T F
 F F T
 44/68
 ““TheThe LawsLaws ofof LogicLogic”” 11
1) Double negation law: ¬¬P ≡ P
2) De Morgan’s laws: ¬ (P∧Q) ≡ ¬P∨¬Q and
 ¬(P∨Q) ≡ ¬ P ∧¬Q 
3) Commutative laws: P∧Q ≡ Q∧P and 
 P∨Q ≡ Q ∨ P 
4) Associative laws: P∧(Q∧R) ≡ (P∧Q)∧R and
 P∨(Q∨R) ≡ ( P∨ Q)∨R 
5) Distributive laws: P∧(Q∨R) ≡ ( P∧ Q)∨(P∧R) and
 P∨(Q∧R) ≡ ( P∨ Q)∧(P∨R) 
 Augustus De Morgan 
 (June 27, 1806 – March 18, 1871)
 45/68
 ““TheThe LawsLaws ofof LogicLogic”” 22
6) Idempotent laws: P∧P ≡ P and 
 P∨P ≡ P 
7) Identity laws: P∨False ≡ P and 
 P∧True ≡ P 
8) Inverse laws: P∨¬P ≡ True and 
 P∧¬P ≡ False 
9) Domination laws: P∨True ≡ True and 
 P∧False ≡ False 
10)Absorption laws: P∨(P∧Q) ≡ P and 
 P∧(P∨Q) ≡ P 
 46/68
 ProvingProving EquivalencesEquivalences
Here is how to prove our “Q ∧ (¬R→P) ≡ (R∧Q)∨(P∧Q)”
Q ∧ (¬R→P) ≡ Q∧(¬¬R∨P) [P→Q ≡ ¬P∨Q rule]
 ≡ Q∧(R∨P) [double negation] 
 ≡ (Q∧R)∨(Q∧P) [distributive law]
 ≡ (R∧Q)∨(Q∧P) [commutative law]
 ≡ (R∧Q)∨(P∧Q) [commutative law]
 47/68
 RulesRules ofof InferenceInference
a In real life when proving mathematical statements often 
 we do not establish an equivalence but a consequence
 V Theorems are true/correct mathematical statements
 V Axioms are “self-evident” theorems
 V Using the rules of inference we can make a (valid) argument to 
 derive other theorems from the axioms
 V An argument is valid if and only if the validity of the hypotheses 
 implies the validity of the conclusion
a Typically, an argument uses hypotheses or premises to
 reach a conclusion
a Example:
 “Assuming the hypotheses H1, H2, H3
 it follows that conclusion C holds”
a How to do this is described by the rules of inference
 48/68
 TheoremTheorem
a Every formula is logically
 equivalent to formula in disjunctive normal form
a Example:
 (P → Q ) ∧ (R → Q)
 is logically equivalent to:
 (¬P ∧ ¬R ∧ ¬Q) ∨ (¬P ∧ ¬R ∧ Q) ∨
 (¬P ∧ R ∧ Q) ∨ (P ∧ ¬R ∧ Q) ∨ (P ∧ R ∧ Q)
 49/68
 ShapeShape ofof anan ArgumentArgument
 H1 premises or 
 hypotheses
 H2
 “therefore” 
 symbol H3
 ∴C conclusion
The therefore symbol “∴” is a bit old fashioned
 50/68
 SomeSome SmallSmall ArgumentsArguments
 P P∨ Q
 P → Q ¬P∨ Q
 P → R ∴Q “inverse 
 fallacy”
 ∴ Q∧ R
 P → Q
 Valid ¬P
 Arguments
 ∴¬Q
∴Q∨¬Q P
 Invalid 
 Q
 Arguments
 ∴P∧ R
 51/68
 AboutAbout ArgumentsArguments
We can check arguments with the help of truth tables
An argument is valid if for all cases where the hypotheses 
are True, the Conclusion is True as well
Arguments are to conditionals (“→”), what
Equivalences (“↔”) are to biconditionals (“↔” )
Arguments are correct or incorrect / valid or invalid;
a conditional is True or False 
 52/68
 AboutAbout ArgumentsArguments
a For propositions P, Q, 
 if P→Q is a tautology, 
 then P logically implies Q
 This is denoted by “P → Q”
a Arguments are correct or incorrect / valid or invalid;
 a conditional is True or False
a Arguments are to conditionals (“→”), 
 what Equivalences (“↔”) are to biconditionals (“↔”)
 53/68
 CheckingChecking ArgumentsArguments
a An argument (H1∧  ∧Hn) → C is valid if
 V for all cases where the hypotheses Hj are True
 V the Conclusion C is True as well
a We can check arguments with the help of truth tables
 But just as with equivalences there are other ways of 
 proving the validity of an argument
 54/68
 RulesRules ofof InferenceInference II
 P → Q P → Q
 Rule of Detachment 
 P (Modus Ponens) Q→ R Syllogism
 ∴ Q ∴ P → R
 P → Q P
 Modus 
 ¬Q Tollens Q Conjunctio n
∴ ¬P ∴ P ∧ Q
 55/68
 RulesRules ofof InferenceInference IIII
 P∨ Q
 Rule of Disjunctive P ∧ Q
 ¬P Syllogism Conjunctive 
 ∴ P Simplification
∴ Q
 P
 P → False Rule of Disjunctive 
 ∴ ¬P MầContradictionn reng tui lấy ví dụ ? ∴ P ∨ Q Amplification
 1. Tìm không gian các sự kiện, 
 nhân vật thật 
 2. Tìm các phát biểu tương 
 ứng với các biến trong luật
 3. Gán nghĩa cho tứng thành 
 phần của luật
 4. Nhận kết quả
 56/68
 RulesRules ofof InferenceInference IIIIII
 P ∧ Q P → R
 Conditional Proof by 
 P → (Q→ R) Proof Q→ R Cases
∴ r ∴ (P ∨ Q) → R
 P → Q P → Q
 R→ S R→ S
 Constructive Destructive 
 P ∨ R Dilemma ¬Q ∨ ¬S Dilemma
 ∴ Q ∨ S ∴ ¬P ∨ ¬R
 57/68
 ProvingProving ValidityValidity ofof ArgumentsArguments
Using basic inference steps and equivalence rules one can 
prove the validity of arguments
 p → q
Example: Yes, according 
 → ¬ Valid?
 q p to truth tables
 ∴¬p
But also, p → q And because 
 P→¬P ↔¬P∨¬P ↔¬P 
 q → ¬p Syllogism
 we have the validity 
 ∴ → ¬
 p p proven a second time
 58/68
 LongerLonger ArgumentsArguments
Example: ((¬P∨¬Q)→(R∧S)) ∧ (R→T) ∧ (¬T) → P
1) R→T [Premise] 
2) ¬T [Premise]
3) ¬R [Steps 1, 2 and Modus Tollens]
4) ¬R ∨¬S [Step 3 and Disjunctive Amplification]
5) ¬(R ∧S) [Step 4 and DeMorgan’s Law]
6) (¬ P∨¬Q)→ (R∧S) [Premise] 
7) ¬( ¬P∨¬Q) [Steps 5, 6 and Modus Tollens]
8) ¬¬ P∧¬¬Q [Step 7 and DeMorgan ’s Law]
9) P∧ Q [Step 8 and Double Negation] 
10) P [Step 9 and Conjunctive Simplification]
 59/68
 GeneralGeneral RemarksRemarks
a Propositions that only use ∧, ∨, ¬, (, ) are the objects in 
 Boolean algebra (without the implication “→”)
 V Note: the Laws of Logic do not use “→”
a This is what you typically have in IF  THEN construction
a The implication becomes useful when you want to connect 
 Boolean algebra with the rules of inference
a “False → P ↔ True” follows from proof by contradiction
 V It holds that (P∧¬P) → P hence (P∧¬P) → P ↔ True
 V Take the two cases P ↔ True and P ↔ False
 60/68
 Terminology:Terminology: 44 ConditionalsConditionals
a For the propositions P and Q and the conditional P → Q, 
 we have the three other conditionals:
 converse: Q → P
 inverse: ¬P → ¬Q of 
 ¬ → ¬ ly one
 On alent 
 contrapositive: ¬Q → ¬P equiv
 ese is
 th → Q
 with P
 the contrapositive, hence: (P→Q) ↔ (¬Q→¬P).
We also have for the other two: (Q→P) ↔ (¬P→¬Q) 
but not: (P→Q) ↔ (Q→P) or (P→Q) ↔ (¬P→¬Q)
 61/68
 ExampleExample ofof InferencingInferencing
a Consider the following argument:
 1. Today is Tuesday or Wednesday
 2. But it can't be Wednesday, since the doctor's office is open 
 today, and that office is always closed on Wednesdays
 today, and that office is always closed on Wednesdays
 3. Therefore today must be Tuesday
a This sequence of reasoning (inferencing) can be 
 represented as a series of application of modus ponens to 
 the corresponding propositions as follows
 P → Q
 P
 ∴ Q
 63/68
 ExampleExample ofof InferencingInferencing (Cont)(Cont)
a The modus ponens is an inference rule which deduces 
 Q from P -> Q and P
 T Today is Tuesday
 W Today is Wednesday
 D The doctor's office is open today
 C The doctor's office is always closed on Wednesdays
a The above reasoning can be represented by propositions as follows
 1. T V W 
 2. D 
 C P → Q
 ------------
 ¬W P
 ------------
 ∴ Q
 3. T
 64/68
 ExampleExample ofof InferencingInferencing (Cont)(Cont)
a To see if this conclusion T is correct, let us first find the 
 relationship among C, D, and W
 C can be expressed using D and W
 That is, restate C first as the doctor's office is always closed
 if it is Wednesday
 if it is Wednesday 
 Then C ≡ (W → ¬D)
 Thus substituting (W → ¬D) for C, we can proceed as follows
 D 
 W → ¬D
 → ¬
 ------------
 ------------ 
 ¬W
 ¬ 
 which is correct by modus tollens
 65/68
 ExampleExample ofof InferencingInferencing (Cont)(Cont)
a From this ¬W combined with T V W of 1. above,
 ¬W
 T V W 
 ------------ 
 T 
which is correct by disjunctive syllogism
Thus we can conclude that the given argument is correct
To save space we also write this process as follows eliminating one of the ¬W's: 
 D
 W → ¬D
 ------------ 
 ¬W 
 T V W 
 ------------ 
 T 
 66/68
 LimitationsLimitations ofof PropositionalPropositional LogicLogic 11
aa PropositionalPropositional LogicLogic ::
 V is good for facts, not individuals
 But hard to identify individuals (terms)
 V E.g., Mary, John, 17, Canada
aa WeWe couldcould trytry aa variablevariable JohnIsTallJohnIsTall,, butbut supposesuppose wewe 
 thenthen wantwant toto encodeencode aa rulerule thatthat talltall peoplepeople areare goodgood 
 atat basketballbasketball
 V E.g., TallPeople → GoodAtBasketball
 Given a knowledge base that consists of
 V JohnIsTall
 V TallPeople → GoodAtBasketball
 67/68
 LimitationsLimitations ofof PropositionalPropositional LogicLogic 22
aa Can'tCan't directlydirectly talktalk aboutabout propertiesproperties ofof individualsindividuals
 oror relationsrelations betweenbetween individualsindividuals
 V E.g., how to represent the fact that John is tall?
aa WeWe havehave nono wayway toto concludeconclude thatthat JohnJohn isis goodgood atat 
 basketballbasketball!! 
aa Generalizations,Generalizations, patterns,patterns, regularitiesregularities can'tcan't easilyeasily bebe 
 representedrepresented
 V E.g., all triangles have 3 sides
 68/68