Transcript p q - Cornell University

CS 4700:
Foundations of Artificial Intelligence
Carla P. Gomes
[email protected]
Module:
Propositional Logic:
Syntax and Semantics
(Reading R&N: Chapter 7)
Carla P. Gomes
CS4700
Propositional Logic
Carla P. Gomes
CS4700
Syntax:
Elements of the language
Primitive propositions --- statements like:
Bob loves Alice
Alice loves Bob
P
Q
Propositional Symbols
(atomic propositions)
Compound propositions
Bob loves Alice and Alice loves Bob
PQ
( - stands for and)
Carla P. Gomes
CS4700
Connectives
•
•
•
•
•
¬ - not
 - and
 - or
 - implies
 - equivalent (if and only if)
Carla P. Gomes
CS4700
Syntax
Syntax of Well Formed Formulas (wffs) or sentences
– Atomic sentences are wffs:
Propositional symbol (atom);
Example: P, Q, R, BlockIsRed; SeasonIsWinter;
– Complex or compound wffs.
Given w1 and w2 wffs:
–
–
–
–
–
 w1 (negation)
(w1  w2) (conjunction)
(w1  w2) (disjunction)
(w1  w2) (implication; w1 is the antecedent; w2 is the consequent)
(w1  w2) (biconditional)
Carla P. Gomes
CS4700
Propositional logic:
Examples
Examples of wffs
PQ
(P  Q)  R
PQP
(P  Q)  (Q  P)
 P
P   this is not a wff.
Note1: atoms or negated atoms are called literals; examples p and p are
literals. P  Q is a “compound statement or proposition”.
Note2: parentheses are important to ensure that the syntax is unambiguous.
Quite often parentheses are omitted; The order of precedence in propositional
logic is (from highest to lowest):  ,, , , 
Carla P. Gomes
CS4700
Propositional Logic:
Syntax vs. Semantics
Semantics has to do with “meaning”:
 it associates the elements of a logical language
with the elements of a domain of discourse.
Propositional Logic – we associate atoms with
propositions / assertions about the world (therefore
propositional logic).
Carla P. Gomes
CS4700
Propositional Logic:
Semantics
Interpretation or Truth Assignment
Assignment of truth values (True or False) to every proposition.
So if for n atomic propositions, there are 2n truth assignments or
interpretations. This makes the representation powerful: the
propositions implicitly capture 2n possible states of the world.
Carla P. Gomes
CS4700
Propositional Logic:
Semantics
Truth table for connectives
Given the values of atoms under some interpretation, we can use a truth table to compute the value
for any wff under that same interpretation; the truth table establishes the semantics (meaning) of
the propositional connectives.


We can use the truth table to compute the value of any wff given the values of the constituent atom
in the wff. Note: In table, P and Q can be compound propositions themselves. Note: implication
Carla P. Gomes
not necessarily aligned with English usage.
CS4700
Implication (p  q)
This is only False (violated) when q is False and p is True.
Related implications:
– Converse: q  p;
– Contra-positive: q   p;
– Inverse  p   q;
Important: only the contra-positive of p  q is equivalent to p  q (i.e., has the same
truth values in all models); the converse and the inverse are equivalent;
Carla P. Gomes
CS4700
Implication (p  q)
Implication plays an important role in reasoning a variety of terminology
is used to refer to implication:
•conditional statement
•if p then q
•if p, q
•p is sufficient for q
•q if p
•q when p
•a necessary condition for p is q (*)
•p implies q
•p only if q (*)
•a sufficient condition for q is p
•q whenever p
•q is necessary for p (*)
•q follows from p
Note: the mathematical concept of implication is independent of a cause and effect
relationship between the hypothesis (p) and the conclusion (q), that is normally
present when we use implication in English.
Note: Focus on the case, when is the statement False. I.e., p is True and q is False, should
be the only case that makes the statement false.
(*) assuming the statement true, for p to be true, q has to
be
true
Carla
P. Gomes
CS4700
Propositional Logic:
Semantics
Notes: Bi-conditionals (p  q)
Variety of terminology :
•p is necessary and sufficient for q
•if p then q, and conversely
•p if and only if q
•p iff q
p  q is equivalent to (pq)  (q p)
Note: the if and only if construction used in biconditionals is rarely used in
common language;
Example: “if you finish your meal, then you can play;” what is really meant
is: “If you finish your meal, then you can play” and ”You can play, only if
you finish your meal”.
Carla P. Gomes
CS4700
Exclusive Or
Truth Table
P Q
PQ
_____________
T T
F
T F
T
F T
T
F F
F
P  Q is equivalent to (P ¬Q)  (¬PQ)
and also equivalent to ¬ (P  Q)
Use a truth table to check these equivalences.
Carla P. Gomes
CS4700
Propositional Logic:
Satisfiability and Models
Satisfiability and Models
An interpretation or truth assignment satisfies a wff, if the wff is assigned the
value True, under that interpretation. An interpretation that satisfies a wff is
called a model of that wff.
Given an interpretation (i.e., the truth values for the n atoms) the one can use
the truth table to find the value of any wff.
Carla P. Gomes
CS4700
The truth table method
(Propositional) logic has a “truth compositional semantics”:
Meaning is built up from the meaning of its primitive parts (just like English
text).
Carla P. Gomes
CS4700
Propositional Logic:
Inconsistency (Unsatisfiability) and Validity
•Inconsistent or Unsatisfiable set of Wffs
It is possible that no interpretation satisifies a set of wffs 
In that case we say that the set of wffs is inconsistent or unsatisfiable or a
contradiction
Examples:
1 – {P  P}
2 – { P  Q, P Q, P  Q, P Q}
(use the truth table to confirm that this set of wffs is inconsistent)
•Validity (Tautology) of a set of Wffs
If a wff is True under all the interpretations of its constituents atoms, we say that
the wff is valid or it is a tautology.
Examples:
1- P  P; 2 - (P  P); 3 - [P  (Q  P)]; 4- [(P  Q) P) P]
Carla P. Gomes
CS4700
Logical equivalence
Two sentences p an q are logically equivalent ( or ) iff p  q is a tautology
(and therefore p and q have the same truth value for all truth assignments)






Note: logical equivalence (or iff) allows us to make statements about PL, pretty much
Carla P. Gomes
like we use = in in ordinary mathematics.
CS4700
Inference
Carla P. Gomes
CS4700
Entailment in the wumpus world
Knowledge Base in the Wumpus World 
Rules of the wumpus world + new percepts
Situation after detecting nothing in [1,1], moving right, breeze
in [2,1]
Consider possible models for KB with respect to the cells (1,2),
(2,2) and (3,1), with respect to the existence or non
existence of pits
3 Boolean choices 
8 possible models (enumerate all the models)
Carla P. Gomes
CS4700
Wumpus world sentences
Let Pi,j be true if there is a pit in [i, j].
Let Bi,j be true if there is a breeze in [i, j].
Sentence 1 (R1):  P1,1
Sentence 2 (R2): B1,1
Sentence 3 (R3): B2,1
"Pits cause breezes in adjacent squares"
Sentence 4 (R4): B1,1 
(P1,2  P2,1)
Sentence 5 (R5): B2,1  (P1,1  P2,2  P3,1)
Carla P. Gomes
CS4700
Inference by enumeration
•
The goal of logical inference is to decide whether KB╞ α, for some
sentence .
• For example, given the rules of the Wumpus World is P22
entailed?
Relevant propositional symbols:
R1:  P1,1
R2: B1,1
R3: B2,1
"Pits cause breezes in adjacent squares"
R4: B1,1 
R5: B2,1 
(P1,2  P2,1)
(P1,1  P2,2  P3,1)
Inference by enumeration  we have 7 symbols therefore
27 interpretations – check if P22 is true in all the KB models;
Carla P. Gomes
CS4700
Propositional logic:
Wumpus World
Each model specifies true/false for each proposition symbol
E.g.
false
P1,2
true
P2,2
false
P3,1
With these symbols, 8 interpretations, can be enumerated
automatically. P12  P22  P31
P12  P22  P31
P12  P22  P31
etc
Carla P. Gomes
CS4700
Is P12 Entailed from KB?
Is P22 Entailed from KB?
Given R1, R2, R3, R4, R5
P11
P12
P21
P22
P31
B11
B21
R1:P11
R2:B11
R3:B21
False
False
False
True
True
True
True
False
False
False
True
True
True
True
False
False
False
True
True
True
True
False
False
False
True
True
True
True
False
False
False
True
True
True
True
False
False
False
True
True
True
True
False
False
False
True
True
True
True
False
False
False
True
True
True
True
R4:B11
(P12 
P21)
R5:B21
P11 
P22P31
KB
Consider all possible truth assignments to P12, P22, P31, and check which assignments
lead to models for the KB; then check if P12 and P22 is true in all the models
Carla P. Gomes
CS4700
Is P12 Entailed from KB?
Is P22 Entailed from KB?
Given R1, R2, R3, R4, R5
What does the KB entail wrt P12?
What does the KB entail wrt P22?
P11
P12
P21
P22
P31
B11
B21
R1:P11
R2:B11
R3:B21
R4:B11
(P12 
P21)
R5:B21
P11 
P22P31
KB
False
False
False
False
False
False
True
True
True
True
True
False
False
False
False
False
False
True
False
True
True
True
True
True
True
True
False
False
False
True
False
False
True
True
True
True
True
True
True
False
True
False
False
False
False
True
True
True
True
False
False
False
False
False
False
True
True
False
True
True
True
True
True
True
True
False
True
False
True
False
False
True
True
True
True
False
False
False
False
True
False
False
True
False
True
True
True
True
False
True
False
False
True
False
True
True
False
True
True
True
True
False
True
False
There are only 3 models for the KB: i.e., for which R1, R2, R3, R4, R5 are True;
In all of them P12 is false, so there is not pit in [1,2] – the KB entails P12; on the other
hand P22 is true in two of the three models and false in the other one – so at this point
we cannot tell whether P22 is true or not.
Carla P. Gomes
CS4700
Inference by enumeration
TT-Entails – Truth Table enumeration algorithm for
deciding propositional entailment;
This is a recursive enumeration of a finite space of assignments to variables;
depth-first algorithm: it enumerates all models and checks if the sentence is true in all the
models;
 sound
 complete;
For n symbols, time complexity is O(2n), space complexity is O(n).
Worst-case complexity is exponential for any algorithm. But in practice we can do better.
More later…
Carla P. Gomes
CS4700
Inference by enumeration
TT-Entails – Truth Table enumeration algorithm for
deciding propositional entailment;
Processed all symbols
We only care about models
For which KB is True
Depth-first enumeration of all models is sound and complete
TT – Truth Table; PL-True returns true if a sentence holds within a model;
Model – represents a partial model – an assignment to some of the variables;
Carla P. Gomes
CS4700
Models
KB ╞ α iff M(KB)  M(α)
Note:
The empty set or null set ( Ø )
is a subset of every set.
An inconsistent KB entails every possible sentence.
Carla P. Gomes
CS4700
Validity and Satisfiability
A sentence is valid (or is a tautology) if it is true in all interpretations,
e.g., True,
A A,
A  A,
(A  (A  B))  B
Validity is connected to inference via the Deduction Theorem:
KB ╞ α iff (KB  α) is valid
A sentence is satisfiable if it is true in some model
e.g., A B, C
A sentence is unsatisfiable if it is true in no models
e.g., AA
Satisfiability is connected to inference via the following:
KB ╞ α iff (KB α) is unsatisfiable (Reductio ad absurdum;
Carla P. Gomes
CS4700