Transcript Logic

Inference Methods
Propositional and Predicate
Calculus
Propositional Logic
• A declarative statement such as “Bill is a CS student”
has a truth value of T or F and is denoted by P (a truth
variable)
• Propositions may be combined with logical operators
and the composite statement has value as shown below.
P  Q is true if either P or Q are true and false if both are false
P  Q is true if both P and Q are true and false if either is false.
¬ P is true if P is false and false if P is true
P  Q is true if P and Q have the same truth value and false if
their values differ
– P  Q is false if P is true and Q is false and true otherwise.
–
–
–
–
• A tautology is always true.
– P  Q  ¬ P  Q is a tautology.
– P  (Q  R)  (P  Q)  (P  R) is a tautology.
Terminology
•  is negation,  is conjunction,  is disjunction,  is
conditional,  is equivalence
• Atomic expression is P,Q,etc representing a declarative
statement having value of True or False, or True or False
• A fully parenthesized expression fpe is a well-formed
formula and is constructed according to following rules
– Any atomic expression
– If A is a fpe, so is A
– If A,B are fpe’s, so are (AB), (AB), (AB) and (AB)
Precedence Relations and Truth Tables
 has highest precedence, then , , , and  .
Every logical operatior is left associative.
A truth table gives the values of an logical expression for every
combination of truth values of the atomic statements. It can be
used to prove a tautology:
•
•
•
P  (Q  R)  (P  Q)  (P  R)
–
P
Q
R
F
F
F
F
F
T
F
T
F
F
T
T
T
F
F
T
F
T
T
T
F
T
T
T
QR
P Q
PR
P  (Q  R)
(P  Q)  (P  R)

Proof by Truth Table
P  (Q  R)  (P  Q)  (P  R)
P
Q
R
QR
P Q
PR
P  (Q  R)
(P  Q)  (P  R)

F
F
F
F
F
F
F
F
T
F
F
T
F
F
T
F
F
T
F
T
F
F
T
F
F
F
T
F
T
T
T
T
T
T
T
T
T
F
F
F
T
T
T
T
T
T
F
T
F
T
T
T
T
T
T
T
F
F
T
T
T
T
T
T
T
T
T
T
T
T
T
T
Contradiction & Proof by Contradiction
• A contradiction is always false
• Suppose A are axioms assumed to be true.
– Want to show A  T
– If T  A  False is a tautology, then
• T  A must be false
• So, since A is true, T must be false and so T is true.
Rules of Inference
• P , P  Q then Q - modus ponens
• ¬ Q, P  Q then ¬ P - modus tollens