Propositional

Logic
 Propositional Logic
• A proposition is a declarative sentence (a sentence
that declares a fact) that is either true or false, but not
both.
• Are the following sentences propositions?
– Toronto is the capital of Canada. (Yes)
– Read this carefully. (No)
– 1+2=3 (Yes)
– x+1=2 (No)
– What time is it? (No)
• Propositional Logic – the area of logic that deals with
propositions

2
 Logic
• Logic is a great knowledge representation language
for many AI problems
• Propositional logic is the simple foundation and
fine for some AI problems
• First order logic (FOL) is much more expressive
as a knowledge representation language and more
commonly used in AI
• There are many variations: horn logic, higher order
logic, three-valued logic, probabilistic logics, etc.
 Propositional Variables

• Propositional Variables – variables that represent

propositions: p, q, r, s
– E.g. Proposition p – “Today is Friday.”

• Truth values – T, F
• Literal: atomic sentence or negated atomic sentence P,  P
– E.g.  p – “Today is not Friday.”

4
 Propositional logic
• Logical operators are used to form new propositions from
two or more existing propositions. The logical operators are
also called connectives.
 ...and [conjunction]
 ...or [disjunction]
 ...not [negation]
...implies [implication / conditional]
..is equivalent [biconditional]
 Conditional Statements
⚫ A conditional statement is also called an implication.
⚫ In the conditional statement p → q, p is called the hypothesis
(or antecedent or premise) and q is called the conclusion (or
consequence).
⚫ Example: “If I am elected, then I will lower taxes.”
implication:
elected, lower taxes. T T |T
not elected, lower taxes. F T |T
not elected, not lower taxes. F F |T
elected, not lower taxes. T F |F

6
 Implications
How can both p and q be false, and p→q be true?
•Example: “If you make more than $25,000, then you must file a
tax return.” This says nothing about someone who makes less
than $25,000. So the implication is true no matter what someone
making less than $25,000 does.
•Another example:
p: Bill Gates is poor.
q: Pigs can fly.
p→q is always true because Bill Gates is not poor. Another way
of saying the implication is
“Pigs can fly whenever Bill Gates is poor” which is true since
neither p nor q is true.
 Biconditional Statement
• The biconditional statement p q is the proposition
“p if and only if q.”
•p q has the same truth value as (p → q) Λ (q → p)
• “if and only if” can be expressed by “iff”
• Example:
– Let p be the statement “You can take the flight” and let q be
the statement “You buy a ticket.” Then p q is the
statement
“You can take the flight if and only if you buy a ticket.”
Implication:
If you buy a ticket you can take the flight.
If you don’t buy a ticket you cannot take the flight.

8
 Truth tables
The five logical connectives:

A complex sentence:
Models of complex sentences
 Precedence of Logical Operators
• We can use parentheses to specify the order in which logical operators in a
compound proposition are to be applied.
• To reduce the number of parentheses, the precedence order is defined for
logical operators.

Precedence of Logical Operators.

Operator Precedence
E.g. ¬p Λ q = (¬p ) Λ q
¬ 1
Λ
p Λ q ν r = (p Λ q ) ν r
2
ν 3 p ν q Λ r = p ν (q Λ r)
→ 4
5

11
 Propositional logic (PL)
• A simple language useful for showing key ideas and definitions
• User defines a set of propositional symbols, like P and Q.
• User defines the semantics of each propositional symbol:
– P means “It is hot”
– Q means “It is humid”
– R means “It is raining”
• A sentence (well formed formula) is defined as follows:
– A symbol is a sentence
– If S is a sentence, then S is a sentence
– If S is a sentence, then (S) is a sentence
– If S and T are sentences, then (S  T), (S  T), (S → T), and (S T) are
sentences
– A sentence results from a finite number of applications of the above rules
 Examples of PL sentences
• P means “It is hot.”
• Q means “It is humid.”
• R means “It is raining.”
• (P  Q) → R
“If it is hot and humid, then it is raining”
• Q→P
“If it is humid, then it is hot”
 Some terms

• The meaning or semantics of a sentence determines its

interpretation.
• Given the truth values of all symbols in a sentence, it can be
“evaluated” to determine its truth value (True or False).
• A knowledge base is actually a set of sentences all of which are
true, i.e., a conjunction of sentences or a collection of true facts.
• A model for a knowledge base is a “possible world” (assignment
of truth values to propositional symbols) in which each sentence
is True.
 Model for a KB
• Let the KB be [PQ→R, Q → P]
• Semantics :
P: it’s hot
Q: it’s humid
R: it’s raining
• What are the possible models? Consider all possible
assignments of T|F to P, Q and R and check truth tables.

• If KB is [PQ→R, Q → P, Q], then the only model is TTT

 More terms
• A valid sentence or tautology is a sentence that is True
under all interpretations, no matter what the world is
actually like or how the semantics are defined. Example:
“It’s raining or it’s not raining.”
• An inconsistent sentence or contradiction is a sentence
that is False under all interpretations. The world is never
like what it describes, as in “It’s raining and it’s not
raining.”
 Inference Rules
• There are many patterns that can be formally called rules of
inference for propositional logic.
• These patterns describe how new knowledge can be derived
from existing knowledge, both in the form of propositional logic
sentences.
• When describing an inference rule, the premise specifies the
pattern that must match our knowledge base and the conclusion
is the new knowledge inferred.

17
 Inference rules
• Logical inference is used to create new sentences that
logically follow from a given set of sentences (KB).
• An inference rule is sound if every sentence X produced by
an inference rule operating on a KB logically follows from
the KB. (That is, the inference rule does not create any
contradictions)
• An inference rule is complete if it is able to produce every
expression that logically follows from (is entailed by) the
KB. (Note the analogy to complete search algorithms.)
 Sound rules of inference
• Here are some examples of sound rules of inference
– A rule is sound if its conclusion is true whenever the premises are true.
• Each can be shown to be sound using a truth table

RULE PREMISE CONCLUSION

Modus Ponens A → B, A B
(From an implication and the premise of the implication, you
can infer the conclusion.)
 Soundness of Modus Ponens

A B A→B OK?
True True True

True False False

False True True

False False True

Whenever the premises, i.e. A → B and A are true,
the conclusion B is also true.
 Sound rules of inference
RULE PREMISE CONCLUSION
Modus Ponens A, A → B B
AND Introduction A, B AB
(If a list of facts are true, their conjunct is also true)
AND Elimination AB A
(If the conjunct of a list of facts is true, then each fact is individually true)
Double Negation A A
Unit Resolution A  B, B A
(If B is false, then A must be true for the disjunct of A and B to be true)
Resolution A  B, B  C AC
or equivalently A → B, B → C A→C
 Soundness of the
Resolution inference rule
 Resolution
• A KB is actually a set of sentences all of which are
true, i.e., a conjunction of sentences.
• To use resolution, put KB into conjunctive normal
form (CNF), where each sentence written as a disjunc-
tion of (one or more) literals
Tautologies
Example (A→B) (~AB)
• KB: [P→Q , Q→RS] (A(BC)) (AB)(AC)
• KB in CNF: [~PQ , ~QR , ~QS]
• Resolve KB(1) and KB(2) producing: ~PR (i.e., P→R)
• Resolve KB(1) and KB(3) producing: ~PS (i.e., P→S)
• New KB: [~PQ , ~QR, ~ QS , ~PR , ~PS]
 Proving things
• A proof is a sequence of sentences, where each sentence is either a
premise or a sentence derived from earlier sentences in the proof
by one of the rules of inference.
• The last sentence is the theorem (also called goal or query) that
we want to prove.
• Example for the “weather problem” given above.
1 Humid Premise “It is humid”

2 Humid→Hot Premise “If it is humid, it is hot”

3 Hot Modus Ponens(1,2) “It is hot”

4 (HotHumid)→Rain Premise “If it’s hot & humid, it’s raining”

5 HotHumid And Introduction(1,2) “It is hot and humid”

6 Rain Modus Ponens(4,5) “It is raining”

 Horn sentences
• A Horn sentence or Horn clause has the form:
P1  P2  P3 ...  Pn → Q
or alternatively (P → Q) = (P  Q)
P1   P2   P3 ...   Pn  Q
where Ps and Q are non-negated atoms
• To get a proof for Horn sentences, apply Modus
Ponens repeatedly until nothing can be done
 Propositional logic: pro and con
• Advantages
– Simple KR language sufficient for some problems
– Lays the foundation for higher logics (e.g., FOL)
– Reasoning is decidable, though NP complete, and efficient
techniques exist for many problems
• Disadvantages
– The expressive power of propositional logic is limited. The
assumption is that everything can be expressed by simple
facts. Not expressive enough for most problems
– Even when it is, it can very “un-concise”
 Propositional logic is a weak language
• Hard to identify “individuals” (e.g., Mary, 3)
• Can’t directly talk about properties of individuals or relations between
individuals (e.g., “Bill is tall”)
• Generalizations, patterns, regularities can’t easily be represented (e.g., “all
triangles have 3 sides”)
• First-Order Logic (abbreviated FOL or FOPC) is expressive enough to
concisely represent this kind of information. It is much easier to model real
world objects using properties and relations.

FOL adds relations, variables, and quantifiers, e.g.,

•“Every elephant is gray”:  x (elephant(x) → gray(x))
•“There is a white alligator”:  x (alligator(X) ^ white(X))
 Example
• Consider the problem of representing the following
information:
– Every person is mortal.
– Confucius is a person.
– Confucius is mortal.
• How can these sentences be represented so that we can infer
the third sentence from the first two?
 Example II
• In PL we have to create propositional symbols to stand for all or
part of each sentence. For example, we might have:
P = “person”; Q = “mortal”; R = “Confucius”
• so the above 3 sentences are represented as:
P → Q; R → P; R → Q
• Although the third sentence is entailed by the first two, we needed
an explicit symbol, R, to represent an individual, Confucius, who
is a member of the classes “person” and “mortal”
• To represent other individuals we must introduce separate
symbols for each one, with some way to represent the fact that all
individuals who are “people” are also “mortal”
 Summary
• The process of deriving new sentences from old one is called inference.
– Sound inference processes derives true conclusions given true premises
– Complete inference processes derive all true conclusions from a set of premises
• A valid sentence is true in all worlds under all interpretations
• If an implication sentence can be shown to be valid, then—given its
premise—its consequent can be derived
• Propositional logic commits only to the existence of facts that may or may
not be the case in the world being represented
– It has a simple syntax and simple semantics. It suffices to illustrate the process
of inference
– Propositional logic quickly becomes impractical, even for very small worlds