HHệệ
chuyên gia chuyên gia
Expert System)) ((Expert System
PGS.TS. Phan Huy Kháánhnh PGS.TS. Phan Huy Kh khanhph@vnn.vn khanhph@vnn.vn
Chương 2 Biểu diễn tri thức bậc một
logic vị
nhờ
từ
2.2
Chương 22 Chương
BiBiểểu diu diễễn tri th
n tri thứức nhc nhờờ
logic vịị logic v
bbậậc mc mộộtt
ttừừ
n 2.2 : (cid:97)(cid:97) PhPhầần 2.2 :
m lôgic i niệệm lôgic (cid:86)(cid:86) KhKháái ni
Lôgic mệệnh đnh đềề (cid:86)(cid:86) Lôgic m
2/2/6868
The 4 Color Theorem The 4 Color Theorem
produced a famous proof of the 4 color Kempe produced a famous proof of the 4 color
(cid:97)(cid:97) InIn 1890,
In 1879, Kempe (cid:97)(cid:97) In 1879, theorem: theorem: Using only 4 colors (cid:86)(cid:86) Using only 4 colors map of countries can be colored in such a way that (cid:86)(cid:86) AnyAny map of countries can be colored in such a way that
color no 2 bordering countries have the same color no 2 bordering countries have the same showed: Heawood showed: 1890, Heawood proof not to be a proof at all! (cid:86)(cid:86) TheThe proof not to be a proof at all! When is a proof a proof, and when is it not a proof? (cid:97)(cid:97) When is a proof a proof, and when is it not a proof? Logic to the rescue! (cid:97)(cid:97) Logic to the rescue!
3/3/6868
What is the logic? What is the logic?
(cid:97)(cid:97) Logic is the science of
reasoning, , proof thinking,, proof, , thinking
Logic is the science of reasoning inference or or inference
Logic allows us to analyze a piece of reasoning (cid:97)(cid:97) Logic allows us to analyze a piece of reasoning and determine whether it is correct or not and determine whether it is correct or not
(cid:97)(cid:97) When people talk of
To use the technical terms, we determine whether (cid:97)(cid:97) To use the technical terms, we determine whether invalid the reasoning is validvalid or or invalid the reasoning is
, though, arguments, though, logical arguments
When people talk of logical they generally mean the type being described here they generally mean the type being described here
4/4/6868
Logic Logic
Logic is the study of reasoning (cid:97)(cid:97) Logic is the study of reasoning
(cid:86)(cid:86) Logic
Logic studies the conditions under which we can say that a studies the conditions under which we can say that a piece of reasoning is validvalid piece of reasoning is
(cid:86)(cid:86) I.eI.e. that something (the conclusion) can be said to
follow . that something (the conclusion) can be said to follow assumptions) something else (the premises, givens, assumptions)
fromfromsomething else (the premises, givens,
(cid:97)(cid:97) Ontology
particular: (cid:97)(cid:97) In In particular:
; logica = ‘‘wordword’’):): (ont = ‘‘to be
to be’’; logica = Ontology (ont = kinds of things one can talk about in the language kinds of things one can talk about in the language
5/5/6868
Arguments in Logic Arguments in Logic
(cid:97)(cid:97) What is an
"An argument is a connected series of statements intended to (cid:86)(cid:86) "An argument is a connected series of statements intended to establish a proposition““ establish a proposition
Argument?? What is an Argument
An argument refers to the formal way facts and rules of (cid:97)(cid:97) An argument refers to the formal way facts and rules of inferences are used to reach valid conclusions inferences are used to reach valid conclusions
The process of reaching valid conclusions is referred to as (cid:97)(cid:97) The process of reaching valid conclusions is referred to as logical reasoning logical reasoning
6/6/6868
Logic in general Logic in general
(cid:97)(cid:97) A logic is a
(cid:97)(cid:97) Logics
A logic is a formal system formal system of representing knowledge of representing knowledge
(cid:97)(cid:97) Syntax
Logics are are formal languages for representing information formal languages for representing information drawn such that conclusions can be drawn such that conclusions can be
(cid:97)(cid:97) Semantics
Syntax defines the defines the sentences sentences ((statements statements)) inin the language the language
truth of a sentence in a
i.e., define truth
sentences define the "meaning" of sentences of a sentence in a worldworld
How conclusions are drawn from a set of statements (cid:86)(cid:86) How conclusions are drawn from a set of statements
Semantics define the "meaning" of (cid:86)(cid:86) i.e., define Proof theory (cid:97)(cid:97) Proof theory
7/7/6868
Deduction and Induction Deduction and Induction
(cid:97)(cid:97) If the conclusion
(cid:97)(cid:97) If the conclusion is merely
true than false more likely to betrue than false
If the conclusion has to be true assuming the truth of the has to betrue assuming the truth of the deductive premises, we call the reasoning deductive premises, we call the reasoning If the conclusion is merely more likely to be given the truth of the premises, we call the reasoning given the truth of the premises, we call the reasoning inductive inductive Logic studies both deduction and induction, but does tend (cid:97)(cid:97) Logic studies both deduction and induction, but does tend logic to focus on deduction, especially formal logic to focus on deduction, especially formal
8/8/6868
Normative and Descriptive Theories of Reasoning Normative and Descriptive Theories of Reasoning
(cid:97)(cid:97) Psychology of reasoning is a scientific study of how humans reas
(cid:97)(cid:97) As such, psychologists come up with
as to how humans reason based on empirical
theories of reasoning: descriptivetheories of reasoning: studies. empiricalstudies. theories of normativetheories of
(cid:97)(cid:97) Logicians, however, try to come up with
follows from what? actuallyfollows from what?
(cid:97)(cid:97) Question: But if not empirical, what is the basis for such theor
Psychology of reasoning is a scientific study of how humans reason:on: What do humans infer from what? (cid:86)(cid:86) What do humans infer from what? What is the mechanism behind human reasoning? (cid:86)(cid:86) What is the mechanism behind human reasoning? As such, psychologists come up with descriptive hypothesesas to how humans reason based on hypotheses Logicians, however, try to come up with normative reasoning: reasoning: (cid:86)(cid:86) What What actually Question: But if not empirical, what is the basis for such theories? ies? (Human!) reason alone? (Human!) reason alone?
9/9/6868
Implication and Truth Implication and Truth
toogle, but not all
, but not all flems
toogle, so not all
flems are are toogle
flems , so not all flems is perfectly logical, but tells us nothing about what--isis--
truth itself can be seen as a kind of (necessary) truth , logic can tells us that certain statements of the form ““If If
are necessarily true (i.e. true in all
truth Logic tells us about implication, not truth (cid:97)(cid:97) Logic tells us about implication, not Example: (cid:97)(cid:97) Example: flurps are are toogle (cid:86)(cid:86) ““All All flurps are are flurps flurps”” is perfectly logical, but tells us nothing about what case. thethe--case. exception: (cid:97)(cid:97) One One exception: Implication itself can be seen as a kind of (necessary) (cid:86)(cid:86) Implication (cid:86)(cid:86) SoSo, logic can tells us that certain statements of the form
10/10/6868
Logic and Science Logic and Science
(cid:97)(cid:97) But that
(cid:97)(cid:97) Of course, scientific reasoning is inherently
(cid:97)(cid:97) Hence
Of course, if I do know that my premises are true, then if (cid:97)(cid:97) Of course, if I do know that my premises are true, then if the reasoning is (deductively) valid I know the conclusion to the reasoning is (deductively) valid I know the conclusion to be true as wellwell be true as s just science: science combines observation (facts) But that’’s just science: science combines observation (facts) with logic (reasoning), to get to truth (laws of physics, with logic (reasoning), to get to truth (laws of physics, chemistry, etc)etc) chemistry, Of course, scientific reasoning is inherently inductive : a inductive: a theories finite set of data is always compatible with multiple theories finite set of data is always compatible with multiple Hence: scientific can change over time. theoriescan change over time. : scientific theories
11/11/6868
Logic and Mathematics Logic and Mathematics
(cid:97)(cid:97) Most of what I just said for logic is
(cid:86)(cid:86) Like logic, mathematical theorems are proven
There is no greatest prime number”” are are
(cid:86)(cid:86) So, theorems like
If we define ‘‘number
to be ..., and number’’ to be ..., and , then there is no greater than’’ as as ……, then there is no
and ‘‘greater than
Most of what I just said for logic is truetrue
mathematics as well!
forfor mathematics as well!
Scientists use mathematics to help figure out (calculate,
(cid:86)(cid:86) Scientists use mathematics to help figure out (calculate,
case but mathematics alone does
compute, etc) what--isis--thethe--case but mathematics alone does
compute, etc) what
not tell us what--isis--thethe--casecase
not tell us what
Like logic, mathematical theorems are proven fromfroma set of
a set of
definitions or axioms: if those axioms or definitions don’’t t
definitions or axioms: if those axioms or definitions don
t say anything
apply to our world, then the theorem doesn’’t say anything
apply to our world, then the theorem doesn
about our world either.
about our world either.
The only thing we can claim to be certain of is a statement of
(cid:86)(cid:86) The only thing we can claim to be certain of is a statement of
If
12/12/6868
Between Further Similarities Between Further Similarities Logic and Mathematics Logic and Mathematics
(cid:97)(cid:97) Mathematics can be applied to formal
(cid:97)(cid:97) Formal logic can be applied to
Both logic and mathematics have been around for (cid:97)(cid:97) Both logic and mathematics have been around for thousands of years thousands of years Both logic and mathematics study abstractions that can be (cid:97)(cid:97) Both logic and mathematics study abstractions that can be applied to any subject matter applied to any subject matter Formal logic is probably best seen as a branch of (cid:97)(cid:97) Formal logic is probably best seen as a branch of mathematics mathematics Mathematics can be applied to formal logic logic mathematical logic) ((mathematical logic) mathematics Formal logic can be applied to mathematics theorem proving) ((theorem proving)
13/13/6868
Formal Logic Formal Logic
(cid:97)(cid:97) We can determine that
toogle, so not all flurps are are toogle flems are are flurps , but not all toogle, but not all is a valid flurps”” is a valid
s are Q’’s, so not all R s, but not all R’’s are Q s are Q’’s, but not all R
We can determine that ““All All flurps , so not all flems flems are are toogle flems inference because of the abstract form of the reasoning: inference because of the abstract form of the reasoning: s are PP’’ss”” s, so not all R’’s are ““All PAll P’’s are Q Formal logic is just that: studying the validity of reasoning (cid:97)(cid:97) Formal logic is just that: studying the validity of reasoning by looking at its abstract form: by looking at its abstract form: Just as in mathematics: (cid:86)(cid:86) Just as in mathematics: 1) expressions of abstract symbols are assigned the objects of (cid:153)(cid:153) 1) expressions of abstract symbols are assigned the objects of study, and study, and 2) by manipulating these expressions of abstract symbols, we (cid:153)(cid:153) 2) by manipulating these expressions of abstract symbols, we objects can figure something out about these objects can figure something out about these
14/14/6868
Little History of Formal Logic Little History of Formal Logic
(cid:97)(cid:97) ‘‘Modern
formal logic was developed in mid 19thth century by century by
Formal logic goes back at least to Aristotle, probably earlier (cid:97)(cid:97) Formal logic goes back at least to Aristotle, probably earlier In Medieval Times work was being done on categorical (cid:97)(cid:97) In Medieval Times work was being done on categorical syllogisms like the one on previous page (that one would be syllogisms like the one on previous page (that one would be classified as AOO--2)2) classified as AOO Modern’’ formal logic was developed in mid 19 people like Georges Boole people like Georges Boole and Augustus
(cid:97)(cid:97) The much more powerful system of first
DeMorgan and Augustus DeMorgan developed the system of propositional or truth-- (cid:97)(cid:97) TheyThey developed the system of propositional or truth
logic functional logic functional The much more powerful system of first--order logic (or order logic (or predicate logic or quantificational logic) was completed by predicate logic or quantificational logic) was completed by the turn of the 20thth century century the turn of the 20 Many other systems of logic have been developed since; (cid:97)(cid:97) Many other systems of logic have been developed since; just as with mathematics, different systems have different just as with mathematics, different systems have different applications applications
15/15/6868
Functional Logic Truth--Functional Logic Truth
(cid:97)(cid:97) An operator is truth
Applies to reasoning dealing with compound sentences built (cid:97)(cid:97) Applies to reasoning dealing with compound sentences built functional operators like ‘‘andand’’, , ‘‘oror’’, , ‘‘notnot’’,, from truth--functional operators like from truth then’’.. andand ‘‘if if …… then
value of a functional in that the truth--value of a values of is a function of the truth--values of P and Q”” is a function of the truth
An operator is truth--functional in that the truth sentence like ““P and Q sentence like the sentences P and QQ the sentences P and
16/16/6868
standard logics NonNon--standard logics
1.1. 2.2. 3.3. 4.4. 5.5. 6.6. 7.7. 8.8. 9.9. 10.10. 11.11. 12.12. 13.13. 14.14.
Categorical logic Categorical logic Combinatory logic Combinatory logic Conditional logic Conditional logic Constructive logic Constructive logic Cumulative logic Cumulative logic Deontic logic Deontic logic Dynamic logic Dynamic logic Epistemic logic Epistemic logic Erotetic logic Erotetic logic Free logic Free logic Fuzzy logic Fuzzy logic Infinitary logic Infinitary logic Intensional logic Intensional logic Intuitionistic logic Intuitionistic logic
15.15. Linear logic Linear logic 16.16. ManyMany--valued logic valued logic 17.17. Modal logic Modal logic 18.18. NonNon--monotonic logic monotonic logic 19.19. Paraconsistent logic Paraconsistent logic Partial logic 20.20. Partial logic Prohairetic logic 21.21. Prohairetic logic Quantum logic 22.22. Quantum logic Relevant logic 23.23. Relevant logic Stoic logic 24.24. Stoic logic Substance logic 25.25. Substance logic Substructural logic 26.26. Substructural logic Temporal (tense) logic 27.27. Temporal (tense) logic In short: a lot! (cid:97)(cid:97) In short: a lot!
17/17/6868
Logic Propositional Logic Propositional
relatively simple framework for reasoning (cid:97)(cid:97) AA relatively simple framework for reasoning be extended for more expressiveness at the cost of (cid:97)(cid:97) CanCan be extended for more expressiveness at the cost of
Sentences, , syntax syntax, , semantics inference semantics, , inference
computational overhead computational overhead aspects Important aspects (cid:97)(cid:97) Important Syntax (cid:86)(cid:86) Syntax Semantics (cid:86)(cid:86) Semantics Validity and inference (cid:86)(cid:86) Validity and inference Models (cid:86)(cid:86) Models Inference rules (cid:86)(cid:86) Inference rules Complexity (cid:86)(cid:86) Complexity Principles of propositional logic (cid:97)(cid:97) Principles of propositional logic (cid:86)(cid:86) Sentences But major limitations of propositional logic (cid:97)(cid:97) But major limitations of propositional logic
18/18/6868
VVíí
ddụụ GiGiảải thi thííchch
MMệệnh đnh đềề lôglôgííchch
y my màà
y > x + 1 y > x + 1
ccóó a x vàà ccủủa x v c sai. Chẳẳng hng hạạn n ng hoặặc sai. Ch ccóó
i mưa !! Hôm nay trờời mưa Hôm nay tr TuTuỳỳ trtrịị theo giáá theo gi gigiáá trtrịị đ đúúng ho gigiáá y=3 thìì x=1 vàà y=3 th x=1 v ĐĐúúng nng nếếu tu tạại thi thờời đi i mưa thậật, sai n trtrờời mưa th trtrịị đ đúúngng i ra i điểểm nm nóói ra t, sai nếếu không ph u không phảảii
2 + 3 = 5 2 + 3 = 5 Luôn luôn cóó Luôn luôn c gigiáá trtrịị đ đúúngng
Luânđôn làà Luânđôn l ththủủ đô c Luôn luôn cóó đô củủa nưa nướớc Đc Đứứcc Luôn luôn c trtrịị gigiáá saisai
Hôm nay làà Hôm nay l ngngàày my mấấy ?y ? i không phảải mi mệệnh đnh đềề Câu hCâu hỏỏi không ph
ng không phảải i o đây !! i anh vàào đây MMờời anh v Câu mCâu mệệnh lnh lệệnh cnh cũũng không ph llàà , v.v... mmộột mt mệệnh đnh đềề, v.v...
19/19/6868
Examples Examples
(cid:86)(cid:86) Is a proposition which
Is a proposition which truetrue
2 + 2 = 4 (cid:97)(cid:97) 2 + 2 = 4
(cid:86)(cid:86) Is a proposition which is
false Is a proposition which is false
The moon is made of cheese (cid:97)(cid:97) The moon is made of cheese
(cid:86)(cid:86) Is a
proposition Is a proposition
It will rain tomorrow (cid:97)(cid:97) It will rain tomorrow
This statement is false (cid:97)(cid:97) This statement is false proposition (cid:86)(cid:86) Is Is notnota a proposition
Vote for Mickey Mouse (cid:97)(cid:97) Vote for Mickey Mouse proposition (cid:86)(cid:86) Is Is notnota a proposition
20/20/6868
Syntax Syntax
false /* T, F | 1, 0 | Yes, No
/* T, F | 1, 0 | Yes, No …… */*/
truetrue, , false , R, …… PP, , QQ, R,
∧∧ ∨∨ ¬¬ →→, (or ↔↔, (or
, (or ⇒⇒)) , (or ⇔⇔))
(cid:97)(cid:97) Công th
Symbols (cid:97)(cid:97) Symbols Logical constants: (cid:86)(cid:86) Logical constants: Propositional symbols: (cid:86)(cid:86) Propositional symbols: Logical connectives (cid:86)(cid:86) Logical connectives onjunction: (cid:153)(cid:153) CConjunction: Disjunction: (cid:153)(cid:153) Disjunction: egation: (cid:153)(cid:153) NNegation: (cid:153)(cid:153) IImplication: mplication: Equivalence: (cid:153)(cid:153) Equivalence:
Formed formulas (wffswffs or sentences):
for grouping:: (( , , )) Parentheses for grouping (cid:86)(cid:86) Parentheses nh (CTC) Công thứức chc chỉỉnh (CTC) WellWell--Formed formulas ( Constructed from simple sentences: PP, , QQ, R, (cid:86)(cid:86) Constructed from simple sentences: Conjunction, disjunction, implication, equivalence, negation (cid:86)(cid:86) Conjunction, disjunction, implication, equivalence, negation (cid:153)(cid:153) ((P P ∧∧ Q) Q) →→ ¬¬PP (cid:153)(cid:153) ((¬¬P P ∨∨ Q) Q) ∨∨ RR →→ SS
or sentences): ww11, , ww22 , R, ……
21/21/6868
BNF Grammar Propositional Logic BNF Grammar Propositional Logic
::=::=
AtomicSentence> |
<
ComplexSentence>
<
AtomicSentence>
<
::= TrueTrue ::=
False | | False
| | PP
| | RR
| ... | ...
::= ::=
||
Sentence>
<
((<
||
||
||
Connective>
<
::=::=
∧∧
→→
∨∨
Ambiguities Ambiguities
parentheses or or parentheses
↔↔ are resolved through precedence ¬¬ are resolved through precedence
∧∧
∨∨
→→
↔↔
RR
SS
SS
e.ge.g. . ¬¬
P P ∨∨
∧∧
→→
is equivalent to to ((¬¬ is equivalent
P) P) ∨∨
(Q (Q ∧∧
R)) R)) →→
22/22/6868
BNF Grammar Propositional Logic BNF Grammar Propositional Logic
::=::=
AtomicSentence> |
<
ComplexSentence>
<
AtomicSentence>
<
::= TrueTrue ::=
False | | False
| | PP
| | RR
| ... | ...
::= ::=
||
Sentence>
<
((<
||
||
||
Connective>
<
::=::=
∧∧
→→
∨∨
Ambiguities Ambiguities
parentheses or or parentheses
↔↔ are resolved through precedence ¬¬ are resolved through precedence
∧∧
∨∨
→→
↔↔
RR
SS
SS
e.ge.g. . ¬¬
P P ∨∨
∧∧
→→
is equivalent to to ((¬¬ is equivalent
P) P) ∨∨
(Q (Q ∧∧
R)) R)) →→
23/23/6868
Semantics Semantics
(cid:97)(cid:97) Interpretation
(cid:86)(cid:86) Symbols
of the propositional symbols and constants Interpretation of the propositional symbols and constants
(cid:139)(cid:139) The value of the symbol can be
false The value of the symbol can be truetrue or or false
Must be explicitly stated in the model (cid:139)(cid:139) Must be explicitly stated in the model
arbitrary fact can stand for any arbitrary fact Symbols can stand for any Sentences consisting of only a propositional symbols are (cid:139)(cid:139) Sentences consisting of only a propositional symbols are satisfiable, but not valid satisfiable, but not valid
(cid:86)(cid:86) The The constants
indicates that the world is as stated (cid:139)(cid:139) TrueTrue indicates that the world is as stated
(cid:139)(cid:139) False
False indicates that the world is not as stated indicates that the world is not as stated of the logical connectives Specification of the logical connectives
(cid:97)(cid:97) Specification
(cid:86)(cid:86) Frequently
and False constants TrueTrue and have a fixed interpretation False have a fixed interpretation
Frequently explicitly via truth tables explicitly via truth tables
24/24/6868
Applications Applications
(cid:97)(cid:97) UserUser defines the
of each propositional symbol: semantics of each propositional symbol:
defines the semantics It is hot”” P means ““It is hot
(cid:86)(cid:86) P means
(cid:86)(cid:86) Q means
It is humid”” Q means ““It is humid It is raining”” R means ““It is raining
(cid:86)(cid:86) R means
A sentence (well formed formula) is defined as follows: (cid:97)(cid:97) A sentence (well formed formula) is defined as follows:
A symbol is a sentence (cid:86)(cid:86) A symbol is a sentence If S is a sentence, then
(cid:86)(cid:86) If S is a
(cid:86)(cid:86) If S is a
If S is a sentence, then
sentence, then ¬¬S is a sentence S is a sentence (S) is a sentence sentence, then (S) is a sentence
(cid:86)(cid:86) If S and T are
T) are sentences T), and (S (S ↔↔ T) are sentences
If S and T are sentences, sentences, then (S (S ∨∨ T), (T), (S S ∧∧ T), (T), (S S →→ T), and then A sentence results from a finite number of applications of the above
(cid:86)(cid:86) A sentence results from a finite number of applications of the a
rules bove rules
(cid:97)(cid:97) Eg.Eg.
If it is humid, then it is hot”” ““If it is humid, then it is hot
If it is hot and humid, then it is raining”” ““If it is hot and humid, then it is raining
means: (cid:86)(cid:86) Q Q →→ P P means: R means: (cid:86)(cid:86) (P (P ∧∧ Q) Q) →→ R means:
25/25/6868
BBàài ti tậập tp tạại li lớớpp
(cid:97)(cid:97) ChuyChuyểển cn cáác câu sau sang lôgic m mưa rrááo, so, sááo to tắắm thm thìì mưa
ttắắm thm thìì
1.1. 2.2. 3.3. 4.4.
đi mô rồồi ci cũũng nh
vvềề
HHàà
TTịịnhnh
5.5.
em nghèèoo em ngh
QuQuạạ ăn nem Ông ăn chảả, b, bàà ăn nem Ông ăn ch đôi bên i anh, tạại i ảả, t, tạại ci cảả đôi bên TTạại anh, t ng nhớớ hơ ai) ) đi mô r (C(Chơ ai i chưng báác mc mẹẹ
c câu sau sang lôgic mệệnh đnh đềề ::
Mần reng tui có
thể
?
6.6.
i rau i băm bèèo tho tháái rau hơn đèènn
BBởởi chưng b Cho nên em phảải băm b Cho nên em ph Trăng khoe trăng tỏỏ hơn đ Trăng khoe trăng t CCớớ sao trăng ph
m mây……
kiện
7.7.
c trò con hhọọc trò con
Dạ, đây : 1. sao trăng phảải chi chịịu luu luồồn đn đáám mây 2. 3.
Lập các câu đơn (NNTN) theo tình huống/sự Đặt tên các biến MĐề Tìm các phép nối lôgic tương ứng Kiểm tra tính hợp thức Nhận kết quả
4. 5.
CCáác chc chúú Đang lúúc tuc tuổổi còn non i còn non Đang l i chăm họọcc phphảải chăm h CCáác chc chúú i nên khôn hhọọc mc mớới nên khôn CCóó
26/26/6868
Negation English Translations of Negation English Translations of
(cid:86)(cid:86) PP represents the fact
Penguins eat fish represents the fact Penguins eat fish
(cid:86)(cid:86) Q Q represents the fact represents the fact I have three children I have three children Negation: Then Negation: (cid:97)(cid:97) Then (cid:86)(cid:86) ¬¬Q:Q:
like fish Penguins do notnot like fish Penguins do
(cid:86)(cid:86) ¬¬Q:Q: have three children I do notnot have three children I do Other Notation: ~P~P, , ~Q~Q
(cid:97)(cid:97) Other Notation:
Assume: (cid:97)(cid:97) Assume:
PP
27/27/6868
Conjunction English Translations of Conjunction English Translations of
represents the fact P P represents the fact
This subject is boring This subject is boring
I am tired I am tired
(cid:97)(cid:97) Then
Assume: (cid:97)(cid:97) Assume:
Q Q represents the fact represents the fact Then Conjunction (cid:86)(cid:86) This subject is boring
I am tired This subject is boring andand I am tired
(cid:86)(cid:86) This subject is boring
This subject is boring although
I am tired although I am tired
(cid:86)(cid:86) This subject is boring
I am tired This subject is boring butbut I am tired
Conjunction P P ∧∧ QQ::
PP QQ
28/28/6868
Disjunction English Translations of Disjunction English Translations of
represents the fact P P represents the fact
This subject is boring This subject is boring
I am tired I am tired
(cid:97)(cid:97) Disjunction P
Q Q represents the fact represents the fact Disjunction P ∨∨ QQ (cid:86)(cid:86) P :P :
Sue is a football player. Sue is a football player.
Bob is lazy Q: Sue is a football player oror Bob is lazy
(cid:86)(cid:86) Q:Q: Bob is lazy Bob is lazy (cid:86)(cid:86) P P ∨∨ Q: Sue is a football player Note: Disjunction is inclusive (cid:86)(cid:86) Note: Disjunction is inclusive
Assume: (cid:97)(cid:97) Assume:
PP QQ
29/29/6868
Conditional English Translations of Conditional English Translations of
It is Tuesday It is Tuesday We are in Belgium We are in Belgium
Giải thích vì
reng rứa ?
(cid:97)(cid:97) Then
we are in Belgium then we are in Belgium
we are in Belgium implies we are in Belgium we are in Belgium only if we are in Belgium
for us to be in Belgium sufficient for us to be in Belgium
Q Q ≡≡
Assume: (cid:97)(cid:97) Assume: P P represents the fact represents the fact represents the fact Q Q represents the fact Conditional P P →→ QQ Then Conditional (cid:86)(cid:86) IfIf it is Tuesday it is Tuesday then s being Tuesday implies (cid:86)(cid:86) ItIt’’s being Tuesday s Tuesday only if (cid:86)(cid:86) ItIt’’s Tuesday s being Tuesday is sufficient (cid:86)(cid:86) ItIt’’s being Tuesday is
¬¬P P ∨∨
P P →→ PP QQ
30/30/6868
If_Then Variations If_Then Variations
Translations P P →→ Q:Q:
If P, QQ Q whenever P (cid:86)(cid:86) Q whenever P
It is necessary for P that Q (cid:86)(cid:86) It is necessary for P that Q
then statements appear in various forms in practice (cid:97)(cid:97) IfIf--then statements appear in various forms in practice (cid:97)(cid:97) More More Translations If P then Q (cid:86)(cid:86) If P then Q P implies Q (cid:86)(cid:86) P implies Q P only if Q (cid:86)(cid:86) P only if Q P is sufficient for Q (cid:86)(cid:86) P is sufficient for Q Q is necessary for P (cid:86)(cid:86) Q is necessary for P Q provided that P (cid:86)(cid:86) Q provided that P (cid:86)(cid:86) Q if PQ if P (cid:86)(cid:86) If P,
31/31/6868
English Translations of Definition ¬¬P P →→ English Translations of Definition
If not P then Q (cid:86)(cid:86) If not P then Q
Unless P, Q (cid:86)(cid:86) Unless P, Q
Q, unless P (cid:86)(cid:86) Q, unless P
Translations (cid:97)(cid:97) Translations
(cid:86)(cid:86) Unless Max is at home, Claire won
t get the message Unless Max is at home, Claire won’’t get the message
¬¬HOME(max)
GETSMESSAGE(claire) HOME(max) →→ ¬¬GETSMESSAGE(claire)
b is cube, unless it is large (cid:86)(cid:86) b is cube, unless it is large ¬¬LARGE(b)
CUBE(b) LARGE(b) →→ CUBE(b)
Examples (cid:97)(cid:97) Examples
32/32/6868
English Translations of Biconditional P P ↔↔ English Translations of Biconditional
P if and only if Q (cid:86)(cid:86) P if and only if Q
Giải thích vì
reng rứa ?
P just in case Q (cid:86)(cid:86) P just in case Q
P is a necessary and sufficient condition for Q (cid:86)(cid:86) P is a necessary and sufficient condition for Q
Translations (cid:97)(cid:97) Translations
P and Q are sufficient and necessary for each other (cid:86)(cid:86) P and Q are sufficient and necessary for each other (cid:86)(cid:86) P P ↔↔ QQ (cid:86)(cid:86) (P (P →→ Q) Q) ∧∧ (Q (Q →→ P)P) (cid:86)(cid:86) (P (P ∧∧ Q) Q) ∨∨ ((¬¬P P ∧∧ ¬¬ Q) Q)
Equivalencies (cid:97)(cid:97) Equivalencies
PP QQ
33/33/6868
MaryMary’’s s ExamExam
Example Example
Mary has a Law exam or a Computer Science exam or bothboth Mary has a Law exam or a Computer Science exam or
(cid:97)(cid:97) ThenThen
L: L: Mary has a Law exam
today Mary has a Law exam today
today Mary has a Computer Science exam today
C, C, ¬¬LL
C: C: Mary has a Computer Science exam Premises: L L ∨∨ Premises: Conclusion: CC Conclusion:
Assume: (cid:97)(cid:97) Assume: Today Today t have a Law examexam She doesn’’t have a Law She doesn she must have a Computer Science examexam Therefore she must have a Computer Science Therefore
34/34/6868
examples of PL More More examples of PL
Penguins eat fish”” represents the fact ““Penguins eat fish Penguins like fishfish”” represents the fact ““Penguins like
penguins like fish therefore penguins like fish penguins like fishfish therefore penguins like therefore penguins eat
penguins like fish
like fish therefore
penguins eat fishfish
Assume (cid:97)(cid:97) Assume (cid:86)(cid:86) PP represents the fact (cid:86)(cid:86) QQ represents the fact then (cid:97)(cid:97) then (cid:86)(cid:86) P P ∧∧ QQ Penguins eat fish penguins like fish Penguins eat fish andand penguins like fish Penguins eat fish or penguins like fish (cid:86)(cid:86) P P ∨∨ QQ Penguins eat fish or penguins like fish eat fish therefore Penguins eat fish (cid:86)(cid:86) QQ →→ PP Penguins Penguins eat fish eat fish therefore (cid:86)(cid:86) P P ↔↔ QQ Penguins andand penguins
get fit. get fit.
E: I do exercise. E: I do exercise. F: I will get fit. F: I will get fit. S: S: (E (E →→
E E →→
FF
F) F) ∧∧
Fitness Example (cid:97)(cid:97) Fitness Example S: If I exercise then I will get fit, and I do exercise, so I will ll S: If I exercise then I will get fit, and I do exercise, so I wi
35/35/6868
Some terms Some terms
of a sentence determines its semantics of a sentence determines its
(cid:97)(cid:97) Given the truth values of all symbols in a
The meaning or semantics (cid:97)(cid:97) The meaning or interpretation interpretation
evaluated”” to determine its to determine its truth
(cid:97)(cid:97) A A valid sentence
sentence, Given the truth values of all symbols in a sentence, value truth value itit can be can be ““evaluated False)) ((TrueTrue or or False
tautology valid sentence or or tautology
(cid:86)(cid:86) Also called:
(cid:86)(cid:86) Example:
A sentence that is True under all interpretations (cid:86)(cid:86) A sentence that is True under all interpretations (equivalent with TrueTrue)) (equivalent with
s not raining”” s raining or it’’s not raining Also called: ““logically true logically true”” Example: PP∨¬∨¬PP, , ““ItIt’’s raining or it
36/36/6868
MoreMore
terms terms
(cid:97)(cid:97) An An inconsistent sentence
A sentence that is False under all interpretations (cid:86)(cid:86) A sentence that is False under all interpretations (equivalent with False) (equivalent with False)
(cid:86)(cid:86) Also called:
logically false”” Also called: ““logically false
(cid:86)(cid:86) Example:
s not raining”” s raining and it’’s not raining
Example: PP∧¬∧¬P P , , ““ItIt’’s raining and it
contradiction inconsistent sentence or or contradiction
(cid:97)(cid:97) P entails Q
As with equivalence: look at the truth tables (cid:97)(cid:97) As with equivalence: look at the truth tables
, written P |= Q , means that whenever P is P |= Q, means that whenever P is
P entails Q, written True, so is Q True, so is Q
In other words, all models of P are also models of Q (cid:97)(cid:97) In other words, all models of P are also models of Q
37/37/6868
Truth Tables Truth Tables
(cid:97)(cid:97) Truth Tables for
Connectives Truth Tables for Connectives
False False True True
False True False True
True True False False
False False False True
False True True True
True True False True
True False False True
One row for each possible combination of truth values for the (cid:86)(cid:86) One row for each possible combination of truth values for the symbols in the sentence symbols in the sentence The final value must be truetrue for every sentence for every sentence (cid:86)(cid:86) The final value must be A variation of the model checking approach (cid:86)(cid:86) A variation of the model checking approach Not very practical for large sentences (cid:86)(cid:86) Not very practical for large sentences
P Q Q P Q ¬ P ∧ P ∨ P → Q P ↔ Q
38/38/6868
Terminology Terminology
(cid:97)(cid:97) A A literal
is either a propositional
literal is either a of aof a propositional variable, or the negation propositional variable, or the negation variable propositional variable
propositional variables
(P (P ∧∧
¬¬R R ∧∧
Q) Q) →→
((¬¬P P ∨∨
R R ∨∨
Q) Q)
disjunction of literals
literals
conjunction of literals
39/39/6868
Special Forms Special Forms
Disjunctive Normal Form (DNF) if it is a (DNF) if it is a
A formula is in Disjunctive Normal Form (cid:97)(cid:97) A formula is in disjunction disjunction
…… ∨∨ ∨∨ DD 22
DD ∨∨ nn literals is a conjunction of literals is a conjunction of where where DD 11 each DD each ii
Conjunctive Normal Form (CNF) if it is a (CNF) if it is a
A formula is in Conjunctive Normal Form (cid:97)(cid:97) A formula is in conjunction conjunction
…… ∧∧ ∧∧ CC 22
CC ∧∧ nn literals is a disjunction of literals is a disjunction of CC 11 where each CC where each ii
40/40/6868
Example Example
Q)Q)
R R ∧∧
¬¬R) R) ∨∨ Q) Q) ∨∨
QQ ((¬¬P P ∧∧
((¬¬P P ∧∧ ((¬¬P P ∧∧ (P (P ∧∧ ∨∨
Q) Q) ∨∨ ((¬¬P P ∧∧ R R ∧∧
(Q (Q ∧∧ ¬¬R R ∧∧ Q) Q)
(P (P ∧∧
¬¬R) R) ∨∨ ¬¬R R ∧∧ ¬¬R R ∧∧
((¬¬P P ∧∧ ¬¬Q) Q) ∨∨ Q) Q) ∨∨
Q)Q)
Disjunctive Normal Forms (cid:97)(cid:97) Disjunctive Normal Forms
Q) Q) ∧∧
(P (P ∨∨
¬¬R R ∨∨
¬¬R R ∨∨ Q) Q) ∧∧
Q) Q) ∧∧ ((¬¬R R ∨∨
((¬¬P P ∨∨ Q)Q)
((¬¬P P ∨∨ ((¬¬P P ∨∨ QQ P P ∧∧
Conjunctive Normal Forms (cid:97)(cid:97) Conjunctive Normal Forms R R ∨∨
41/41/6868
Logical Logical
Equivalence Equivalence
if and only if for each case if and only if for each case
equivalent Two propositions are (logically) equivalent Two propositions are (logically) their truth values are the same ((““≡≡””)) their truth values are the same identities also called identities also called
1+1=2 or 1+1=2”” ““1+1=2 or 1+1=2
1+1=2”” ““1+1=2
↔↔ He did not not do it”” ““He did not not do it
He did it”” ““He did it
↔↔
Examples: Examples: (P(P∨∨P)P) P P ≡≡ PP ¬¬¬¬P P ≡≡ ¬¬(P(P∧∧Q) Q) ≡≡ ¬¬P P ∨∨ If P then not P”” ““If P then not P
¬¬QQ ≡≡
not P”” ““not P
Proving that two propositions are equivalent can be done by comparing their two truth tables
42/42/6868
Example of Equivalence Example of Equivalence
(cid:97)(cid:97) How to prove
(cid:97)(cid:97) Earlier we saw
How to prove ““QQ ∧∧ ((¬¬RR→→P)P) ↔↔ ((RR∧∧Q)Q)∨∨(P(P∧∧Q)Q)””?? Earlier we saw……
while for the other proposition…
43/43/6868
Biconditional Biconditional
vs. Equivalence vs. Equivalence
(cid:97) Don’t confuse
with the biconditional ↔
the equivalence ≡ (only the biconditional has a truth table)
(cid:97) For example:
P P ≡
↔
QPQP TT
T
is a proposition/tautology, a statement within logic, is mathematically correct, … about logic P
FT
F
TF
F
FF
T
P ≡ P ≡ ¬P is a contradiction (False), P ≡ ¬P is incorrect Hence P↔P ≡ ¬(P↔¬P), and so on
44/44/6868
The Laws of Logic”” ““The Laws of Logic
11
1)1)
2)2)
Double negation law: Double negation law:
3)3)
s laws: De Morgan’’s laws: De Morgan
4)4)
Commutative laws: Commutative laws:
5)5)
laws: Associative laws: Associative andand
Distributive laws: Distributive laws: andand
≡≡ ≡≡ ¬¬¬¬PP PP ≡≡ ¬¬((PP∧∧Q)Q) Q and ¬¬PP∨¬∨¬Q and ≡≡ ¬¬((PP∨∨Q)Q) ¬¬PP∧¬∧¬QQ ≡≡ PP∧∧QQ and QQ∧∧PP ≡≡ and QQ∨∨PP PP∨∨QQ ≡≡ PP∧∧(Q(Q∧∧R)R) ≡≡ PP∨∨(Q(Q∨∨R)R) ≡≡ PP∧∧(Q(Q∨∨R)R) PP∨∨(Q(Q∧∧R)R)
((PP∧∧Q)Q)∧∧RR ((PP∨∨Q)Q)∨∨RR ((PP∧∧Q)Q)∨∨((PP∧∧R)R) ((PP∨∨Q)Q)∧∧((PP∨∨R)R)
Augustus De Morgan (June 27, 1806 – March 18, 1871)
45/45/6868
The Laws of Logic”” ““The Laws of Logic
22
6)6)
Idempotent laws: Idempotent laws: and and
7)7)
≡≡ ≡≡ PP∧∧PP PP∨∨PP
Identity laws: Identity laws: and and
8)8)
PP PP False PP∨∨False PP∧∧TrueTrue ≡≡ ≡≡
Inverse laws: Inverse laws:
9)9)
PP∨¬∨¬PP PP∧¬∧¬PP ≡≡ ≡≡
Domination laws: Domination laws: and and
PP∨∨TrueTrue False PP∧∧False
Absorption laws: 10)10) Absorption laws:
PP∨∨(P(P∧∧Q)Q) PP∧∧(P(P∨∨Q)Q)
PP PP and TrueTrue and False False TrueTrue ≡≡ False ≡≡ False and PP ≡≡ and PP ≡≡
46/46/6868
Proving Equivalences Proving Equivalences
Here is how to prove our ““QQ Here is how to prove our ∧∧ ((¬¬RR→→P)P) ≡≡ (R(R∧∧Q)Q)∨∨(P(P∧∧Q)Q)””
QQ rule] rule] ∧∧ ((¬¬RR→→P)P) ¬¬PP∨∨QQ ≡≡ ≡≡
[[PP→→QQ [double negation] [double negation] ≡≡
[distributive law] [distributive law] ≡≡
[commutative law] [commutative law] ≡≡
[commutative law] [commutative law] QQ∧∧((¬¬¬¬RR∨∨P)P) QQ∧∧(R(R∨∨P)P) (Q(Q∧∧R)R)∨∨(Q(Q∧∧P)P) (R(R∧∧Q)Q)∨∨(Q(Q∧∧P)P) (R(R∧∧Q)Q)∨∨(P(P∧∧Q)Q) ≡≡
47/47/6868
Rules of Inference Rules of Inference
we can make a (valid) argument
In real life when proving mathematical statements often (cid:97)(cid:97) In real life when proving mathematical statements often consequence we do not establish an equivalence but a consequence we do not establish an equivalence but a (cid:86)(cid:86) Theorems (cid:86)(cid:86) Axioms (cid:86)(cid:86) Using the
argument to to
are true/correct mathematical statements Theorems are true/correct mathematical statements theorems evident”” theorems Axioms are are ““selfself--evident Using the rules of inference rules of inference we can make a (valid) derive other theorems from the axioms derive other theorems from the axioms
(cid:86)(cid:86) An An argument
if and only if the validity of the hypotheses argument is is validvalid if and only if the validity of the hypotheses
implies the validity of the conclusion implies the validity of the conclusion
hypotheses or or premises premises toto argument uses hypotheses
(cid:97)(cid:97) How to do this is described by the
Typically, an argument uses (cid:97)(cid:97) Typically, an conclusion reach a conclusion reach a Example: (cid:97)(cid:97) Example: Assuming the hypotheses HH11, H, H22, H, H33 ““Assuming the hypotheses holds”” follows that conclusion C holds itit follows that conclusion C How to do this is described by the rules of inference rules of inference
48/48/6868
Theorem Theorem
(cid:97)(cid:97) Every formula is
logically Every formula is logically equivalent to formula in disjunctive normal equivalent to formula in disjunctive normal formform
Example: (cid:97)(cid:97) Example:
(P (P →→ (R (R →→ Q)Q) Q ) Q ) ∧∧
isis logically equivalent to: logically equivalent to:
((¬¬P P ∧∧ ¬¬R R ∧∧
Q)Q) ((¬¬P P ∧∧ ((¬¬P P ∧∧ R R ∧∧ ¬¬R R ∧∧ Q) Q) ∨∨ ¬¬Q) Q) ∨∨ (P (P ∧∧ Q) Q) ∨∨ R R ∧∧ ¬¬R R ∧∧ Q) Q) ∨∨ (P (P ∧∧
49/49/6868
Shape of an Argument Shape of an Argument
premises or hypotheses
“therefore” symbol
conclusion
H 1 H 2 H 3 ∴ C
The therefore symbol “∴” is a bit old fashioned
50/50/6868
Some Small Arguments Some Small Arguments
∨ QP ∨¬
QP
∴
Q
P → QP → RP ∧∴ RQ
→ QP ¬
P
Valid Arguments
¬∴
Q
QQ ¬∨∴
Invalid Arguments
P Q ∧∴ RP
“inverse fallacy”
51/51/6868
About Arguments About Arguments
tables We can check arguments with the help of truth tables We can check arguments with the help of truth
An argument is valid if for all cases where the hypotheses An argument is valid if for all cases where the hypotheses True, the are are True, the Conclusion is True as wellwell Conclusion is True as
biconditionals are to biconditionals are to ), what Arguments are to conditionals (““→→””), what Arguments are to conditionals ( Equivalences ((““↔↔””)) Equivalences ((““↔↔””))
Arguments are correct or incorrect / valid or invalid; Arguments are correct or incorrect / valid or invalid; False a conditional is True or False a conditional is True or
52/52/6868
About Arguments About Arguments
P, Q, propositions P, Q, (cid:97)(cid:97) ForFor propositions tautology, is a tautology, ifif PP→→QQ is a logically implies QQ then PP logically implies then is denoted by ““P P →→ QQ”” ThisThis is denoted by
Arguments are correct or incorrect / valid or invalid; (cid:97)(cid:97) Arguments are correct or incorrect / valid or invalid; False a conditional is True or False a conditional is True or
are to biconditionals Arguments are to conditionals (““→→””), ), (cid:97)(cid:97) Arguments are to conditionals ( Equivalences ((““↔↔””)) are to whatwhat Equivalences biconditionals ((““↔↔””))
53/53/6868
Checking Arguments Checking Arguments
(cid:97)(cid:97) An argument
(cid:97)(cid:97) We can check arguments with the help of truth
is valid ifif An argument ((HH11∧∧ …… ∧∧HHnn) ) →→ CC is valid all cases where the hypotheses HHjj are are TrueTrue (cid:86)(cid:86) forfor all cases where the hypotheses True as wellwell Conclusion CC isis True as (cid:86)(cid:86) thethe Conclusion
tables We can check arguments with the help of truth tables
But just as with equivalences there are other ways of But just as with equivalences there are other ways of argument proving the validity of an argument proving the validity of an
54/54/6868
Rules of Inference I Rules of Inference I
→ QP → QP
P Syllogism → RQ Rule of Detachment (Modus Ponens)
∴ Q →∴ P R
→ P Q P
¬ Q Q Conjunctio n Modus Tollens
∧∴ ¬∴ QP P
55/55/6868
Rules of Inference II Rules of Inference II
∨ QP
∧ QP
¬ P Rule of Disjunctive Syllogism ∴ P Conjunctive Simplification ∴ Q
P → P False
∨∴ Disjunctive Amplification QP ¬∴ P
1.
2.
3.
Rule of Contradiction Mần reng tui lấy ví ? dụ kiện, Tìm không gian các sự nhân vật thật Tìm các phát biểu tương ứng với các biến trong luật Gán nghĩa cho tứng thành phần của luật Nhận kết quả
4.
56/56/6868
Rules of Inference III Rules of Inference III
→ ∧ QP P R
→→ P )RQ( → RQ Proof by Cases Conditional Proof
∴ r →∨∴ )QP( R
→ QP → QP
→ SR → SR
∨ RP ¬∨¬ Q S Constructive Dilemma Destructive Dilemma
∨∴ SQ ¬∨¬∴ P R
57/57/6868
Proving Validity of Arguments Proving Validity of Arguments
Using basic inference steps and equivalence rules one can Using basic inference steps and equivalence rules one can arguments prove the validity of arguments prove the validity of
→ q ¬→
p
Example: Example: Valid?
p q ¬∴ p
Yes, according to truth tables
But also,
→ p q ¬→ q ¬→∴ p
p p
Syllogism
And because P→¬P ↔ ¬P∨¬P ↔ ¬P we have the validity proven a second time
58/58/6868
Longer Arguments…… Longer Arguments
1)1)
2)2)
3)3)
Tollens]] and Modus Tollens and Modus
4)4)
5)5)
Law] Law]
6)6)
7)7)
8)8)
9)9)
PP ∧∧ ∧∧ →→ ((¬¬T)T) (R(R→→T)T)
10)10)
((((¬¬PP∨¬∨¬QQ))→→(R(R∧∧S))S)) Premise] [[Premise] [Premise] [Premise] [Steps 1, 21, 2 [Steps [Step 3 and Disjunctive Amplification] [Step 3 and Disjunctive Amplification] DeMorgan’’ss [Step 4 and DeMorgan [Step 4 and [Premise] [Premise] [Steps 5, 65, 6 Tollens]] and Modus Tollens [Steps and Modus Law] DeMorgan’’ss [Step 7 and DeMorgan Law] [Step 7 and Step 8 and Double Negation] [[Step 8 and Double Negation]
[Step 9 and Conjunctive Simplification] [Step 9 and Conjunctive Simplification]
Example: Example: RR→→TT ¬¬TT ¬¬RR ¬¬RR∨¬∨¬SS ¬¬(R(R∧∧S)S) ((¬¬PP∨¬∨¬QQ))→→(R(R∧∧S)S) ¬¬((¬¬PP∨¬∨¬QQ)) ¬¬¬¬PP∧¬¬∧¬¬QQ PP∧∧QQ PP
59/59/6868
General Remarks General Remarks
(cid:97)(cid:97) Propositions that only use
(without the implication ““→→””))
(cid:97)(cid:97) This is what you typically have in IF
are the objects in Propositions that only use ∧∧, , ∨∨, , ¬¬, , ((, , )) are the objects in Boolean algebra (without the implication Boolean algebra (cid:86)(cid:86) NoteNote: the Laws of Logic do not use : the Laws of Logic do not use ““→→”” This is what you typically have in IF …… THEN construction THEN construction
(cid:97)(cid:97) ““False
holds that (P(P∧¬∧¬P)P) →→ PP hence
The implication becomes useful when you want to connect (cid:97)(cid:97) The implication becomes useful when you want to connect inference Boolean algebra with the rules of inference Boolean algebra with the rules of
the two cases PP ↔↔ True and
False →→ PP ↔↔ TrueTrue”” follows from proof by (cid:86)(cid:86) ItIt holds that (cid:86)(cid:86) TakeTake the two cases contradiction follows from proof by contradiction hence (P(P∧¬∧¬P)P) →→ PP ↔↔ TrueTrue False True and PP ↔↔ False
60/60/6868
Terminology: 4 Conditionals Terminology: 4 Conditionals
(cid:97)(cid:97) For the propositions
PP
→→
and QQ and the conditional and the conditional PP →→ Q, Q,
inverse: inverse:
O n l y o n e o f
contrapositive: contrapositive:
→→ →→
¬¬QQ ¬¬PP
i s e q u i v a l e n t t h P → Q …
t h e s e w i
For the propositions PP and we have the three other conditionals: we have the three other conditionals: converse: QQ converse: ¬¬PP ¬¬QQ
… 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/61/6868
Example of Inferencing Example of Inferencing
But it can't be Wednesday, since the doctor's office is open 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
Consider the following argument:: (cid:97)(cid:97) Consider the following argument 1.1. Today is Tuesday or Wednesday Today is Tuesday or Wednesday 2.2.
3.3.
Therefore today must be Tuesday Therefore today must be Tuesday
This sequence of reasoning (inferencing) can be (cid:97)(cid:97) This sequence of reasoning (inferencing) can be represented as a series of application of modus ponens to represented as a series of application of modus ponens to the corresponding propositions as follows the corresponding propositions as follows
→ QP
P
∴ Q
63/63/6868
Example of Inferencing (Cont) Example of Inferencing (Cont)
and PP
from P P --> Q> Q and
The modus ponens is an inference rule which deduces (cid:97)(cid:97) The modus ponens is an inference rule which deduces QQ from Today is Tuesday TT Today is Tuesday Today is Wednesday WW Today is Wednesday The doctor's office is open today DD The doctor's office is open today The doctor's office is always closed on Wednesdays CC The doctor's office is always closed on Wednesdays The above reasoning can be represented by propositions as followss (cid:97)(cid:97) The above reasoning can be represented by propositions as follow 1. 1.
V V W W
TT
2. 2.
→ QP
P
∴ Q
3. 3.
D D C C ------------ ------------ ¬¬WW ------------ ------------ TT
64/64/6868
Example of Inferencing (Cont) Example of Inferencing (Cont)
(cid:97)(cid:97) To see if this conclusion
first as the doctor's office is always closed first as the doctor's office is always closed
, we can proceed as follows for CC, we can proceed as follows for
¬¬D)D)
which is correct by modus tollens which is correct by modus tollens
is correct, let us first find the To see if this conclusion TT is correct, let us first find the , and WW relationship among CC, , DD, and relationship among CC and WW can be expressed using DD and can be expressed using That is, restate CC That is, restate if it is Wednesday if it is Wednesday ¬¬D)D) (W →→ Then CC ≡≡ (W Then (W →→ Thus substituting (W Thus substituting DD ¬¬DD W W →→ ------------ ------------ ¬¬WW
65/65/6868
Example of Inferencing (Cont) Example of Inferencing (Cont)
above, combined with TT V V WW of of 1.1. above,
From this ¬¬WW combined with
(cid:97)(cid:97) From this ¬¬WW V V W W TT ------------ ------------ TT
which is correct by disjunctive syllogism which is correct by disjunctive syllogism Thus we can conclude that the given argument is correct Thus we can conclude that the given argument is correct
To save space we also write this process as follows eliminating one of the To save space we also write this process as follows eliminating
's: one of the ¬¬WW's:
DD ¬¬DD W W →→ ------------ ------------ ¬¬WW V V W W TT ------------ ------------ TT
66/66/6868
Limitations of Propositional Logic 1 Limitations of Propositional Logic 1
(cid:97)(cid:97) We could try a variable
, not individuals facts, not individuals
E.g., TallPeople
Propositional Logic : (cid:97)(cid:97) Propositional Logic : is good for facts (cid:86)(cid:86) is good for But hard to identify individuals (terms) But hard to identify individuals (terms) Mary, John, 17, Canada E.g., Mary, John, 17, Canada (cid:86)(cid:86) E.g., We could try a variable JohnIsTall , but suppose we JohnIsTall, but suppose we then want to encode a rule that tall people are good then want to encode a rule that tall people are good at basketball at basketball GoodAtBasketball TallPeople →→ GoodAtBasketball (cid:86)(cid:86) E.g., Given a knowledge base that consists of Given a knowledge base that consists of JohnIsTall (cid:86)(cid:86) JohnIsTall GoodAtBasketball TallPeople →→ GoodAtBasketball (cid:86)(cid:86) TallPeople
67/67/6868
(cid:97)(cid:97) We have no way to conclude that
Limitations of Propositional Logic 2 Limitations of Propositional Logic 2 Can't directly talk about properties of individuals (cid:97)(cid:97) Can't directly talk about properties of individuals or relations between individuals or relations between individuals how to represent the fact that John is tall? E.g., how to represent the fact that John is tall? (cid:86)(cid:86) E.g., John is good at We have no way to conclude that John is good at basketball! ! basketball Generalizations, patterns, regularities can't easily be (cid:97)(cid:97) Generalizations, patterns, regularities can't easily be represented represented (cid:86)(cid:86) E.g.,
all triangles have 3 sides E.g., all triangles have 3 sides
