Transcript 7. Propositional and Predicate Logic

Chapter 7.
Propositional and
Predicate Logic
Fall 2013
Comp3710 Artificial Intelligence
Computing Science
Thompson Rivers University
Course Outline


Part I – Introduction to Artificial Intelligence
Part II – Classical Artificial Intelligence



Knowledge Representation
Searching
Knowledge Represenation and Automated Reasoning





Propositinoal and Predicate Logic
Inference and Resolution for Problem Solving
Rules and Expert Systems
Part III – Machine Learning
Part IV – Advanced Topics

Genetic Algorithms
TRU-COMP3710
Propositional/Predicate Logic
2
Chapter Objectives
TRU-COMP3710
Propositional/Predicate Logic
3
Chapter Outline

Propositional logic
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Introduction
What is logic? Why is logic used in Artificial Intelligence?
How to use logical operators
How to translate an English statement with logic notations
Let’s recall complex truth tables
Let’s recall tautology and contradictory
How to use equivalent propositions
How to logically use propositions – propositional logic
Introduction to predicate calculus
Summary
TRU-COMP3710
Propositional/Predicate Logic
4
1. Introduction

[Q] What is reasoning?



[Wikipedia] Reason is the capacity for consciously making sense of things,
applying logic, for establishing and verifying facts, and changing or
justifying practices, institutions, and beliefs based on new or existing
information.
To form conclusions, inferences, or judgments
[Q] How to automate reasoning?

Need to know how to represent information, knowledge, facts and beliefs, and
how to apply logic, …
5





[Q] How to formalize/validate our arguments?
Argument = premises (proposition or statement) + conclusion
To have confidence in the conclusion in your argument, the premises
should be acceptable on their own merits or follow from other statements
that are known to be true.
[Q] Any logical forms for valid arguments?
Examples




Argument 1: If the program syntax is faulty or if program execution results
in division by zero, then the computer will generate an error message.
Therefore, if the computer does not generate, then the program syntax is
correct and program execution does not result in division by zero.
Argument 2: If x is a real number such that x < -2 or x > 2, then x2 > 4.
Therefore, if x2 /> 4, then x /< -2 and x /> 2.
The common logical form of both of the above arguments:
If p or q, then r. Therefore, if not r, then not p and not q.
Is this logical form valid?
6
Topics

You may recall “Logic and Truth Tables” in COMP 1380.

In this unit,




Boolean logic
Propositional logic
Introduction to predicate calculus – first-order predicate logic
Propositional logic will be used in the following unit to solve some
problems.


Based on rules, knowledge, and facts,
Decide if a given query is valid.
TRU-COMP3710
Propositional/Predicate Logic
7
2. What is Logic?


Logic: reasoning about the validity of arguments.
An argument is valid if its conclusions follow logically from its
premises (proposition or statement) – even if the argument doesn’t
actually reflect the real world:





Topics
Mary is a lemon.
All lemons are blue.
Therefore, Mary is blue.
Logic is widely used as a representation method of AI, and allows us
to easily reason about negatives (i.e., “NOT”) and disjunctions (,i.e.,
“OR”)
One of the main weaknesses of traditional logic (i.e., Boolean logic) is
its inability to deal with uncertainty.

Later probabilistic method and fuzzy logic will be discussed to deal with
uncertainty.
TRU-COMP3710
Propositional/Predicate Logic
8
3. How to Use Logical Operators

Definition of statement


A statement (or proposition) is a sentence that is true or false but not
both.
Examples

Two plus two equals four.
2+2=4
I am a TRU student.

x+y>0


TRU-COMP3710
???
Propositional/Predicate Logic
9

Compound Statements

Symbols used in complicated logical statements:





~



not
and
or
exclusive or
~p
pq
pq
pq
negation of p
conjunction of p and q
disjunction of p and q
Order of operations: ( ) and ~ have the higher precedence.


TRU-COMP3710
~p  q = (~p)  q
~(p  q)
Propositional/Predicate Logic
10
Topics

And (conjunction)
Or (disjunction)
Not (negation)
Implies (conditional)
Iff (biconditional)

Exclusive OR?




TRU-COMP3710





or
~
(if… then…)
(if and only if)
Propositional/Predicate Logic
11
4. Translating between English and Logic


Facts and rules need to be translated into logical notation.
For example:



It is Raining and it is Thursday:
R  T, where
R represents “It is Raining”, T represents “it is Thursday”.
TRU-COMP3710
Propositional/Predicate Logic
12


More complex sentences need predicates. That part of a proposition
that is affirmed or denied about the subject. For example, in the
proposition We are mortal, mortal is the predicate.
E.g.,





It is raining in New York:
R(N)
Could also be written N(R), or even just R.
[Q] How to express “It is not raining in New York”???
It is important to select the correct level of detail for the concepts you
want to reason about.
TRU-COMP3710
Propositional/Predicate Logic
13
Topics

Example
It is not hot but it is sunny.
It is neither hot nor sunny.
-> It is not hot, and it is sunny.
It is not hot, and it is not sunny.

Let h = “it is hot” and s = “it is sunny.” Then the above statements can be
translated as

~h  s
~h  ~s


Example

Suppose x is a particular real number. Let p, q, and r symbolize
“0 < x,” “x < 3,” and “x = 3.” respectively.
Then the following inequalities

x3
0<x<3
0<x3
pq
p  (q  r)
can be translated as

TRU-COMP3710
qr
Propositional/Predicate Logic
14
5. Truth Tables

Tables that show truth values for all possible inputs to a logical
operator.
For example:

[Q] Truth table for implies () ???





A  B:
A is the antecedent, and B is the consequent.
A  B  A  B
[Q] Can you prove it? How?
A  B  B  A
[Q] Can you prove it? How?
[Q] Truth table for iff () ???
TRU-COMP3710
Propositional/Predicate Logic
15
Topics

We can produce truth tables for complex logical expressions, which
show the overall value of the expression for all possible combinations
of variables:
TRU-COMP3710
Propositional/Predicate Logic
16
6. Tautology and Contradictory




Topics
A tautology is true under any interpretation.
The expression A ˅ ¬A is a tautology.
This means it is always true, regardless of the value of A.
P is a tautology: this is written
╞P

An expression which is false under any interpretation is contradictory
(or unsatisfiable).


A  ¬A
Some expressions are satisfiable, but not valid. This means that they
are true under some interpretation, but not under all interpretations.

AB
TRU-COMP3710
Propositional/Predicate Logic
17
7. How to Use Equivalent Propositions

Two expressions are equivalent if they always have the same logical
value under any interpretation:


[Q] How to prove the above equivalence?


A˄BB˄A
Equivalences can be proven by examining truth tables.
[Q] Are there more equivalences?
TRU-COMP3710
Propositional/Predicate Logic
18

A ˅ A  ???
A ˄ A  ???
A ˄ (B ˄ C)  (A ˄ B) ˄ C
A ˅ (B ˅ C)  (A ˅ B) ˅ C
A ˄ (B ˅ C)  (A ˄ B) ˅(A ˄ C)
A ˅ (B ˄ C)  (A ˅ B) ˄ (A ˅ C)
A ˄ (A ˅ B)  ???
A ˅(A ˄ B)  ???
A ˄ true  ???
A ˄ false  ???
A ˅ true  ???
A ˅ false  ???
[Q] DeMorgans’ Laws ???

[Q] Why do we need these equivalences?










By using the above and other equivalences, logical expressions can be
simplified.
TRU-COMP3710
Propositional/Predicate Logic
19
Topics

Some more
TRU-COMP3710
Propositional/Predicate Logic
20
8. How to Use Propositions




Propositional logic in this chapter is a logical system.
It deals with propositions.
Propositional calculus is the language we use to reason about
propositional logic.
A sentence in propositional logic is called a well-formed formula
(wff) (or sentence).
TRU-COMP3710
Propositional/Predicate Logic
21

Propositional calculus:

BNF (Backus-Naur Form) – The following are wff’s:










P, Q, R…
propositional symbols
true, false
(A)
¬A
A˄B
A˅B
A→B
A↔B
Any combination of wff’s is a wff.
[Q] Is P  Q  (B  C)  A  B  D  (E) a wff ???
TRU-COMP3710
Propositional/Predicate Logic
22





Deduction: the process of deriving a conclusion from a set of
assumptions.
Will be discussed in the following unit again to solve some problems.
If we deduce a conclusion C from a set of assumptions, we write:
{A1, A2, …, An} ├ C
If C can be concluded without any assumption
├ C
The inference rule A ├ B is expressed as
A
B Given A, B is deduced (or concluded).
It is like if A is true, then B is true.
TRU-COMP3710
Propositional/Predicate Logic
23

 introduction


Given A and B, we can deduce A  B.
A, B
{A, B} ├ A ˄ B
A˄B
 introduction
A_
A B

 elimination
AB
A

Some valid inference rules
AB
B
 elimination (called Modus Ponens)
A, A  B
B

[Q] Can you prove?
  elimination
A
A
TRU-COMP3710
Propositional/Predicate Logic
24

Reduction to absurdity: Reductio Ad Absurdum (proof by
contradiction)
A
.
.
_
A

Contradiction, i.e., false
 Induction (called deduction theorem)
A
.
.
C__
AC
TRU-COMP3710
Propositional/Predicate Logic
25
Topics

 Introduction
A__
BA

Modus Tollens
~B, A  B
~A
TRU-COMP3710
Propositional/Predicate Logic
26
9. Introduction to Predicate Calculus

Predicate Calculus extends the syntax of propositional calculus with
predicates and quantifiers:

P(X) – P is a predicate.

First Order Predicate Calculus (FOPC) allows predicates to apply to
objects or terms, but not functions or predicates.

Just introduction in this unit.
Predicate calculus is used in solving more complex problems.

TRU-COMP3710
Propositional/Predicate Logic
27

Quantifiers  and 

 - For all:



 - There Exists:



x P(x) is read “For all x’es, P (x) is true”.
E.g., for all pine TRU COMP students, they are smart.
x P(x) is read “there exists an x such that P(x) is true”.
E.g., there is a TRU COMP student who is not smart.
Relationship between the quantifiers:


TRU-COMP3710
x P(x)  ¬ (x)¬P(x)
“If There exists an x for which P holds, then it is not true that for all x P does
not hold”.
Propositional/Predicate Logic
28
Topics

Properties of Logical Systems

Four factors to consider of:




TRU-COMP3710
Soundness: Is every theorem valid?
Completeness: Is every tautology a theorem?
Decidability: Does an algorithm exist that will determine if a wff is valid?
Monotonicity: Can a valid logical proof be made invalid by adding additional
premises or assumptions?
Propositional/Predicate Logic
29
10. Summary

Topics
Propositional logic



Propositions
Boolean logic
Deduction; inference rules
TRU-COMP3710
Propositional/Predicate Logic
30