Artificial Intelligence: Rabiya Tahir Ratahir@ssuet - Edu.pk

Artificial
Intelligence
Lecturer
Rabiya Tahir
[email protected]
Lecture # 10
Propositional Logic
Logic in General (1)
Logics are formal languages for representing

information such that conclusions can be drawn
When people talk about logic they often mean
propositional or first-order predicate logic.
3
Logic in General (2)
A logic usually has a well defined syntax,

semantics and proof theory.
The syntax of a logic defines the syntactically
acceptable objects of the logic, or well-formed
formulae.
The semantics of a logic associate each
formula with a meaning.
The proof theory is concerned with
manipulating formulae according to certain
rules. 4
Propositional Logic
The syntax of propositional logic is
constructed from propositions and
connectives.
A proposition is a statement that is either
true or false but not both
5
Propositions???
Najib is Prime Minister
What is the time?
2 + 3 = 5
„Phone‟ has five letters.
2 + 3 = 6
Oh dear!
„Work‟ has five letters.
the reactor is on
2+3
All elephants have 4 legs
I like AI class
6
How to determine Propositions??
It is possible to determine whether any given

statement is a proposition by prefixing it with
It is true that . . .
and seeing whether the result makes grammatical
sense.
Propositions are often abbreviated using
propositional variables eg p, q, r.
Thus we must associate the propositional variable
with its meaning i.e.
Let p be Najib is Prime Minister.
7
connectives
 Propositions may be combined with other propositions to

form compound propositions. These in turn may be
combined into further propositions.
 The connectives that may be used are
and conjunction (& or .)
or disjunction (| or +)
Not negation (~)
if …..then implication ( )
if and only if equivalence ( )
 Some books use notations. Some of these are
different
given in parentheses. 8
Propositional Logic: Syntax
 The proposition symbols P1, P2 etc are sentences
 If S is a sentence, S is a sentence (negation)
 If S and S are sentences, S
1 2 1 S is a sentence (conjunction)
2

1 2 1
S is a sentence (disjunction)
2

1 2
1 S is a sentence (implication)
2

1 2
1 S is a sentence (equivalence)
2
9
Propositional Logic: Semantic
Each model species true/false for each

proposition symbol
E.g. P Q R Why 8?
true true false
(With these symbols, 8 possible models, can be
enumerated automatically.)
Rules for evaluating truth with respect to a
model m are determined by truth tables
10
And (also called conjunction)
The conjunction ‘p AND q’, written p q, of two

propositions is true when both p and q are true, false
otherwise.
We can summarise the operation of using a truth
table. Rows in the table give all possible setting of the
propositions to true (T) or false (F).
p q
11
Natural Language Meaning (1)
p Its Monday.
q Its raining.
p ^ q Its Monday and its raining.
Its Monday but its raining.
Its Monday. Its raining.
12
Natural Language Meaning
Caution: semantics?
p I took a shower
q I woke up
p^q “I took a shower and I woke up”
q^p “I woke up and I took a shower”.
Logically the same! WE may see a difference.
The word both is often useful eg. I both took a shower

and I woke up.
13
Or
Also called disjunction.
The disjunction „p OR q‟, written p q, of two
propositions is true when p or q (or both) are true, false
otherwise.
Sometimes called inclusive or.
p q
14
p It‟s Monday.
q It‟s raining.
p q It‟s Monday or it is
raining.
The word either is often useful eg. either it’s Monday
or it is raining.
It also includes the case of rain on a Monday!
15
Not
Also known as negation

The negation „NOT p‟ of a proposition (or p) is true when p is
false and is false otherwise. p may be read that it is
false that p.
Negation is a unary connective. It only takes one argument.

Conjunction and disjunction were both binary connectives.
16
p Logic is easy.
p It is false that logic is easy.
It is not the case that logic is easy.
Logic is not easy.
17
If . . . then
Also known as implication
The implication „p IMPLIES q‟, written p q, of two
propositions is true when either p is false or q is true, and
false otherwise.
p q
18
p I study hard.
q I get rich.
p q If I study hard then I get rich.
Whenever I study hard, I get rich.
That I study hard implies I get rich.
I get rich, if I study hard.
19
More About Implication
20
Biconditional
Also known as iff or the biconditional.
The biconditional, written as p q, of two
propositions is true when both p and q are true or
when both p and q are false, and false otherwise.
21
Biconditional
22
Recap: Truth Tables
23
Truth Tables for Compound Propositions
 Truth tables may be used to show interpretations of

compound propositions.
 To draw up a truth table, construct a column for each
proposition involved.
 You need 2n rows for n propositions for all possible ways of
setting the propositions to T and F.
 If we have 3 propositions, p; q; r, i.e. we need 23 = 8 rows.
 Next, construct a column for each connective, the most deeply
nested first.
 Evaluate each column using values for propositions or
previous columns.
24
Exercise
p.. (my breakfast is) eggs.
q.. (my breakfast is) cereal.
r.. (my breakfast is) toast.
The statement „my breakfast is

either eggs or cereal, and toast‟
may be written in symbolic form
as ???
WHAT DOES THE TABLE

TELL U?
25
... So
The truth table gives results for all possible
interpretations of p, q and r. The compound
proposition is true if
I eat cereal, eggs and toast; or
I eat cereal and toast; or
I eat eggs and toast.
Interpretation - A line in the truth table.
26
Try this..
Complete the truth table for
. 27
Satisfiable and Valid
• A formula is valid if it is true for all values of its

terms. Valid if all values it returns in the truth table
are true .
• A proposition is satisfiable if there is at least one
true result in its truth table.
28
DIY
29
•Example 1: Formalize in propositional logic:
•a = ‘It is early in the morning’

•b = ‘It is late at night’
•c = ‘I take a taxi’
•d = ‘I use the train’
•e = ‘I am abroad’
DIY When it is early in the morning or late at night and I

am abroad I take a taxi.
(Avb)^(ec)
If it is early in the morning and I am not abroad I
always use the train.
(a^~e)-d
I use either the train or the taxi if it is late at night
and I am not abroad.
30
(Dvc)-(b^~e)
•Example 1: Formalize in propositional logic:
•a = ‘It is early in the morning’

•b = ‘It is late at night’
•c = ‘I take a taxi’
•d = ‘I use the train’
•e = ‘I am abroad’
DIY When it is early in the morning or late at night and I am abroad I take a
taxi.
(a v b) ^ (e  c)
If it is early in the morning and I am not abroad I always use the train.
(a ^ ~e) <---> d
I use either the train or the taxi if it is late at night and I am not abroad.
(d v c) -> (b ^ ~e)
31
Logical Equivalence of Conditional and
Contrapositive
The easiest way to check for logical equivalence is
to see if the truth tables of both variants have
identical last columns:
p q p q p q ¬q ¬p ¬q¬p
T T T T T F F T
T F F T F T F F
F T T F T F T T
F F T F F T T T
32
Table of Logical Equivalences
33
Tautology and contradiction
• Tautology is a proposition which is always true. It is also valid.
• Contradiction is a proposition which is always false. It is

unsatisfiable.
• Contingency is a proposition which is neither a tautology nor a
contradiction
( p ^ q) →p
P →(p V q)
~p → (p V q) 34
Converse, Contrapositive and
Inverse
• We start with the conditional statement “If P then Q.”

• The converse of the conditional statement is “If Q then P.”
• The contrapositive of the conditional statement is “If not Q then not
P.”
• The inverse of the conditional statement is “If not P then not Q
35
Converse, Contrapositive and
Inverse
p: If it is raining
q: grass is wet
Given an implication p → q
If it is raining then grass is wet
• The converse is: q → p
If Grass is wet then it is raining
• The contrapositive is: ¬q → ¬p
• The inverse is: ¬p → ¬q 36

Converse, Contrapositive and Inverse
• The contrapositive of a conditional statement of the form

"If p then q" is "If ~q then ~p". Symbolically,
the contrapositive of p q is ~q ~p.
•A conditional statement is logically equivalent to

its contrapositive. A conditional statement is not logically
equivalent to its inverse.
For example, the contrapositive of "If it is raining then the
grass is wet" is "If the grass is not wet then it is not raining."
37
Exercise
• Construct a truth table for

• (p<---> q) <---> (r<---> s)
• ((p---> q) --->r) ---> s
• (p V q)^ ~r
38
Exercise
• Let p be the “ the election is decided” and
• Q= the votes have been counted.
Translate the following proposition into Propositional
logic
~p
PV q
~p ^ q
~q ~p
P< ---> q
39
Exercise
• Convert the following sentence into PL
• You will get an A in this class if and if you either do
every exercise in this book or you get an A in the final
• Berries are ripe along the trail, but grizzly bears have
not been seen in the area.
• It is below freezing but not snowing.
• Swimming at the new jersey shore is not allowed and
either swimming at the new jersey shore is allowed or
shark have not been spotted near the shore.
40

Artificial Intelligence: Rabiya Tahir Ratahir@ssuet - Edu.pk

Uploaded by

Copyright:

Available Formats

Artificial Intelligence: Rabiya Tahir Ratahir@ssuet - Edu.pk

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Artificial Intelligence: Rabiya Tahir Ratahir@ssuet - Edu.pk

Uploaded by

Copyright:

Available Formats

Artificial

Logics are formal languages for representing

A logic usually has a well defined syntax,

It is possible to determine whether any given

 Propositions may be combined with other propositions to

 If S and S are sentences, S

 If S and S are sentences, S

 If S and S are sentences, S

Each model species true/false for each

The conjunction ‘p AND q’, written p q, of two

The word both is often useful eg. I both took a shower

It also includes the case of rain on a Monday!

Also known as negation

Negation is a unary connective. It only takes one argument.

 Truth tables may be used to show interpretations of

The statement „my breakfast is

WHAT DOES THE TABLE

Complete the truth table for

• A formula is valid if it is true for all values of its

•a = ‘It is early in the morning’

DIY When it is early in the morning or late at night and I

•a = ‘It is early in the morning’

• Contradiction is a proposition which is always false. It is

• We start with the conditional statement “If P then Q.”

• The converse is: q → p

If Grass is wet then it is raining

• The contrapositive is: ¬q → ¬p

• The inverse is: ¬p → ¬q 36

• The contrapositive of a conditional statement of the form

•A conditional statement is logically equivalent to

• Construct a truth table for

You might also like