Propositional logic

Maria Tamoor
Agenda
Course policies
Logic

Lecture 1 2
 Course Policies, Schedule,
Syllabus
Quizzes can be online or on compus
There is no such thing as make-up
quiz/test or make-up exam.
There will be one extra quiz
Late assignments will be graded after
50% deduction. Students are
encouraged to submit assignments
before time.
Will drop your lowest score for
Lecture 1 3
 Lectures and Notes
Lectures will be uploaded over the
weekend.
On Tuesday, we can discuss the lecture
in class and offline students can discuss
on whatsapp group

Lecture 1 4
Tentative Grading criteria
Quizzes/Tests 20%
Assignments 10%
Mid Term 30%
Final Examination 40%

Lecture 1 5
Textbook

Discrete Mathematics and Its Applications

by Kenneth H. Rosen

Use lecture notes as study guide.

6
 Quick Overview
Discrete Math is essentially that branch of
mathematics that does not depend on
limits; in this sense, it is the anti-
thesis of Calculus. As computers are
discrete object operating one jumpy,
discontinuous step at a time, Discrete
Math is the right framework for
describing precisely Computer Science
concepts.

Lecture 1 7
 Logic
Foundations of Logic:
Mathematical Logic is a tool for working
with elaborate compound statements. It
includes:
 A formal language for expressing
them.
 A concise notation for writing them.
 A methodology for objectively
reasoning about their truth or falsity.
 1 It is the foundation for expressing8
Lecture
 Section 1.1: Logic
We intuitively know that Truth and Falsehood
are opposites. That statements describe the
world and can be true/false. That the world
is made up of objects and that objects can be
organized to form collections.
.

Lecture 1 9
 False, True, Statements
Axiom: False is the opposite to Truth.
A statement is a description of something.
Examples of statements:
 I have -17 students in dm class.
 You always tell the truth.
Q’s: Which statements are True? False? Both?
Neither?

Lecture 1 10
 False, True, Statements
True: I live in Lahore.
False: We live on MARS

Lecture 1 11
 Propositions
To avoid painful head-aches, we ban silly
non-sense and avoid the most general
type of statements limiting ourselves to
statements with valid truth-values
instead:
DEF: A proposition is a statement that
is true or false.

Lecture 1 12
 Propositions
Propositional Logic is a static discipline of
statements which lack semantic content.
E.G. p = “Clinton was the president.”
q = “The list of U.S. presidents includes
Clinton.”
r = “Lions like to sleep.”
All p and q are no more closely related than q
and r are, in propositional calculus. They are
both equally related as all three statements
are true. Semantically, however, p and q are
the same!
Lecture 1 13
 Propositions
So why waste time on such matters?
Propositional logic is the study of how simple
propositions can come together to make
more complicated propositions. If the simple
propositions get some meaning then the
complicated proposition would have meaning
as well, and then finding out the truth value
is actually important!

Lecture 1 14
 Compound Propositions
In Propositional Logic, we assume a
collection of atomic propositions are
given: p, q, r, s, t, ….
Then we form compound propositions by
using logical connectives (logical
operators) to form propositional
“molecules”.

Lecture 1 15
Examples of proposition
Propositions??

FCC university is in Lahore

Do you like Computer discipline?
There are x students in this class.

FCC is in Lahore Punjab

There is a computer Science Dept in FCC university.
1+1 = 2
What is your name?
2+2= 3
5+x=7

Lecture 1 16
 Logical Connectives
Operator Symbol Usage Java
Negation  not !

Conjunction  and &&

Disjunction  or ||

Exclusive or xor (p||q)&&(!p||!q)


Conditional  if,then p?q:true

Biconditional iff (p&&q)||(!p&&!q)


Lecture 1 17
 Compound Propositions:
Examples
p = “Cruise ships only go on big rivers.”
q = “Cruise ships go on the Hudson.”
r = “The Hudson is a big river.”
r =
“The Hudson is not a big river.”
pq =
“Cruise ships only go on big rivers and go on the
Hudson.”
pq r =
“If cruise ships only go on big rivers and go on the
LectureHudson,
1 then the Hudson is a big river.” 18
 Negation
This just turns a false proposition to true
and the opposite for a true proposition.
EG: p = “23 = 15 +7”
p happens to be false, so p is true.
In Java or C, “!” plays the same role:
!(23 == 15+7)
has the boolean value true whenever
evaluated.

Lecture 1 19
 Find the negation of the proposition
"Today is Friday.'‘
Express this in simple English.
"It is not the case (that today is Friday."
This negation can he more simply
expressed by
"Today is not Friday,"
Or "It is not Friday today."
Lecture 1 20
 Negation – truth table
Logical operators are defined by truth
tables –tables which give the output of
the operator in the right-most column.
Here is the truth table for negation:

p p
F T
T F

Lecture 1 21
 Conjunction
Conjunction is a binary operator in that it
operates on two propositions when
creating compound proposition. On the
other hand, negation is a unary
operator.

Lecture 1 22
 Conjunction
Conjunction is supposed to encapsulate
what happens when we use the word
“and” in English. I.e., for “p and q ” to
be true, it must be the case that BOTH
p is true, as well as q. If one of these
is false, than the compound statement
is false as well.

Lecture 1 23
 Conjunction
EG. p = “Clinton was the president.”
q = “Monica was the president.”
r = “The meaning of is is important.”
Assuming p and r are true, while q false.
Out of pq, pr, qr
which are true??
only pr is true.
Java: x==3 && x!=3
T or F ??
Evaluates to false for any possible value of x.
Lecture 1 24
 Conjunction – truth table

p q p q
T T T
T F F
F T F
F F F

Lecture 1 25
 Disjunction – truth table
Conversely, disjunction is true when at
least one of the components is true:

p q p q
T T T
T F T
F T T
F F F

Lecture 1 26
 Disjunction
Note: English version of disjunction “or”
does not always satisfy the assumption
that one of p/q being true implies that
“p or q ” is true.
Q: Can someone come up with an
example?

Lecture 1 27
 Disjunction
A: guests are served with soup or salad.
Most restaurants definitely don’t allow
you to get both soup and salad so that
the statement is false when both soup
and salad is served.
To address this situation, exclusive-or is
introduced next.

Lecture 1 28
 Exclusive-Or – truth table
p q p q
T T F
T F T
F T T
F F F

Note: in this course any usage of “or”

will have the logical operator 
as opposed to the exclusive-or.
Lecture 1 29
A simple exercise

“It didn’t rain last night.”

“The lawn was wet this morning, and it
didn’t rain last night.”
“Either the lawn wasn’t wet this
morning, or it rained last night, or the
sprinklers came on last night.”
Lecture 1 30
 p = “I will earn an A in this course,”
q = “I will drop this course,”
I will earn an A or I will drop this
course.
Which is suitable operator?


Lecture 1 31
Lecture 1 32
Lecture 1 33
 Conditional (Implication)
This one is probably the least intuitive.
It’s like English usage of “if,then” or
“implies”.
DEF: p  q is true if q is true, or if p is
false. In the final case (p is true while
q is false) p  q is false.
Semantics: “p implies q ” is true if one
can mathematically derive q from p.

Lecture 1 34
 Conditional -- truth table
p q p q
T T T
T F F
F T T
F F T

IF you get > 90 marks in final exams then your

grade will be A
Only IF you get > 90 marks in final exams then
your
Lecture 1 grade will be A 35
 If Wasim Akram is captain of Pakistani
team then Pakistan will win this match

Only If Wasim Akram is captain of

Pakistani team then Pakistan will win
this match

Lecture 1 36
Examples of Implications
 “If this lecture ever ends, then the sun
will rise tomorrow.” True or False?
 “If Tuesday is a day of the week, then
you are a penguin.” True or False?
. “If 1+1=6, then Obama is still
president.” True or False?
 “If the moon is made of green cheese,
then I am richer than Bill Gates.” True
or False?
Lecture 1 37
Examples of Implications
 “If this lecture ever ends, then the sun
will rise tomorrow.” True or False?
 “If Tuesday is a day of the week, then
you are a penguin.” True or False?
. “If 1+1=6, then Obama is still
president.” True or False?
 “If the moon is made of green cheese,
then I am richer than Bill Gates.” True
or False?
Lecture 1 38
Lecture 1 39
Converse, Inverse,
Contrapositive

contrapositive

Lecture 1 40
Examples
If today is Thursday, then I have a test
today.
Converse:
If I have a test today , then today is
Thursday. q
Contrapositive:
If I don’t have a test today then today
is not Thursday.
Inverse: If today is not Thursday, then
LectureI1 don’t have a test today 41
 Bi-Conditional -- truth table
For p  q to be true, p and q must have
the same truth value. Else, p  q is false:
p q p q
T T T
T F F
F T F
F F T

Q : Which operator is  the opposite of?

Lecture 1 42
Logical Equivalence
p  q and  p  q are logically
equivalent
Truth tables are the simplest way to
prove such facts.
Any conditional and its contrapositive are
logically equivalent and Contrapositive of
p  q is q  p
We will learn other ways later.

43
 . The contrapositive of “If you get
100% in this course, you will get an
A+” is
“If you do not get an A+ in this course,
you did not get 100%”.

Lecture 1 44
 Bi-Conditional
A:  has exactly the opposite truth table
as .

Lecture 1 45
 Bi-Conditional
The biconditional p ↔ q states that p is
true if and only if (IFF) q is true.
p = “You get full score in all exams and
all homework.”
q = “You get an A+ in ICS 141.”
p ↔ q = “If, and only if, you get full
score in all exams and all homework,
you get an A+ in Comp 113.”
Lecture 1 46
 Bit Strings
Electronic computers achieve their calculations
inside semiconducting materials. For
reliability, only two stable voltage states are
used and so the most fundamental operations
are carried out by switching voltages between
these two stable states.
In logic, only two truth values are allowed.
Thus propositional logic is ideal for modeling
computers. High voltage values are modeled
by True, which for brevity we call the number
1, while low voltage values are modeled by
False or 0.
Lecture 1 47
 Bit Strings
Thus voltage memory stored in a computer can
be represented by a sequence of 0’s and 1’s
such as
01 1011 0010 1001
Another portion of the memory might look like
10 0010 1111 1001
Each of the number in the sequence is called a
bit, and the whole sequence of bits is called
a bit string.

Lecture 1 48
 Bit Strings
It turns out that the analogs of the logical
operations can be carried out quite easily
inside the computer, one bit at a time. This
can then be transferred to whole bit strings.
For example, the exclusive-or of the previous
bit strings is:
01 1011 0010 1001
 10 0010 1111 1001
11 1001 1101 0000

Lecture 1 49
Bitwise operations
E.g.:
01 1011 0110
11 0001 1101
11 1011 1111 Bit-wise OR
01 0001 0100 Bit-wise AND
10 1010 1011 Bit-wise XOR

Lecture 1 50
Exercises
q = “You miss the final exam.” r = “You
pass the course.” Express q  r in
English.
1. Construct a truth table for p q.
2. Can one determine relative salaries of F
(Fannie), J (Janice) and M (Maggie) from
the following?
1. If F is not highest paid, then J is.
2. If J is not lowest paid, then M is highest paid.

Lecture 1 51
Exercise question
Q 3,4,5,9,21,24,25 of section 1.1

Lecture 1 52