GE-161
Discrete Structures
Unit 1:
Propositional Logic
Dr. Asif Sohail
University of the Punjab
Department of Information Technology, FCIT
Text & Reference Books / Material
Discrete Mathematics and Its Applications Kenneth
H. Rosen (13th Ed.)
Discrete Mathematics with Applications Sausanna
S.Epp (4th Ed.)
Discrete Mathematics Schaums’ Outlines (3rd Ed.)
Some of the slides are adapted from Fahad Hussain
https://www.youtube.com/c/FahadHussaintutorial/
playlists
https://fahadhussaincs.blogspot.com/
Introduction
"Discrete Math" OR "Discrete Structure" is not the name of a branch of
mathematics, like number theory, algebra, calculus, etc. Rather, it's a
description of a set of branches of math that all have in common the feature
that they are "discrete" rather than "continuous".
Logic: Logic is the study of reasoning. It is the basic on which all the
sentence are build. OR Correct and Incorrect reasoning.
A proposition is a declarative sentence (that is, a sentence that
declares a fact) that is either true or false, but not both.
Declarative Sentences
1.The semester Spr 25 started on Feb 3,25.
2. 5 > 3
3. I am in Class.
4. Lahore is capital of Punjab.
Non-Declarative Sentences
5. Read this carefully. (Imperative)
6. What time is it? (Interrogative)
7. x + 1 = 2.
8. x + y = z
Propositional Variables
• Propositional (or sentential) variables are used to represent
propositions.
• The conventional letters used for propositional variables are p,
q, r, s,… .
• The area of logic that deals with propositions is called
Propositional Logic or Propositional Calculus.
• It was first developed systematically by the Greek philosopher
Aristotle.
• The methods for producing new propositions from the given
propositions were discussed by the English mathematician
George Boole in 1854 in his book "The Laws of Thought".
Compound Propositions
Logical Connectives
Logical operators are used to form new propositions also called
compound propositions from two or more existing propositions.
A truth table is a tabular representation of all the combinations of
values for inputs and their corresponding outputs
Negatio
n
• I am in class.
• Cat cannot fly.
• Today is Sunday.
Conjunct
ion
Let p and q be propositions. The conjunction of p
and q, denoted by p Λ q, is the proposition “p and
q”. The conjunction p Λ q is true when both p and q
are true and is false otherwise.
Today is Friday AND it is raining today.
I'd like pizza AND a salad for lunch.
Disjunction
• Let p and q be propositions. The disjunction of p and q, denoted
by p ν q, is the proposition “p or q”. The disjunction p ν q is false
when both p and q are false and is true otherwise (Inclusive OR).
• “Students who have taken calculus or computer science can take
this class.”
• Exclusive OR: The disjunction is true only when one of the
proposition is true.
• “Ice cream or pudding will be served after lunch.”
CONDITIONAL STATEMENT / IMPLICATION:
• Let p and q be propositions. The conditional statement p → q, is
the proposition “if p, then q” which is false when p is true and q is
false, and true otherwise.
• p is called the hypothesis (or antecedent or premise)
• q is called the conclusion (or consequence).
CONDITIONAL STATEMENT / Bi-
MPLICATION:
• Let p and q be propositions. The biconditional statement p ↔ q
is the proposition “p if and only if q.”
• The biconditional statement p ↔ q is true when p and q have
the same truth values, and is false otherwise.
• Biconditional statements are also called bi-implications
• “You can take the flight if and only if you buy a ticket.”
• Show that p ↔ q is equivalent to (p->q) Λ (q->p).
Different Ways of Expressing p →q
CONDITIONAL STATEMENT:
Necessary and Sufficient conditions
If r and s are statements:
• r is a sufficient condition for s means “if r then s.”
• r is a necessary condition for s means “if not r then not s.”
Necessary and Sufficient Conditions
If r and s are statements:
• r is a sufficient condition for s means “if r then s.”
• r is a necessary condition for s means
• “if not r then not s.”
• “if s then r.” (Contrapositive)
• r is a necessary and sufficient condition for s means
• “r if and only if s.”
OTHER CONDITIONAL STATEMENTS
• We can form the following conditional statements starting from
p → q.
1) Converse: q → p
2) Inverse: ¬p → ¬q
3) Contrapositive: ¬q → ¬p
• Conditional: If you are working hard, then you are a topper.
• Converse: If you are a topper, then you are working hard.
• Inverse: If you are not working hard, then you are not a topper.
• Contrapositive: If you are not topper, then you are not working
hard.
• Conditional: If your parents are rich, then you are rich.
• Converse: If you are rich, then your parents are rich.
• Inverse: If your parents are not rich, then you are not rich.
• Contrapositive: If you are not rich, then your parents are not rich.
OTHER CONDITIONAL STATEMENTS
• An implication is equivalent to the contrapositive.
p q ¬p ¬q p->q ¬q->¬p
T T F F T T
T F F T F F
F T T F T T
F F T T T T
• Neither the converse nor inverse of an implication are not
equivalent to the implication. However, converse and inverse of a
conditional statement are equivalent.
p q ¬p ¬q p->q ¬p->¬q q->p
T T F F T T T
T F F T F T T
F T T F T F F
F F T T T T T
Truth Tables of Compound Propositions
• (P ν ¬q) -> (p^q)
p q ¬q p v ¬q p^q (p v ¬q) -> (p^q)
T T F T T T
T F T T F F
F T F F F T
F F T T F F
(p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r
∨ ¬p)
1.2.6 Logic Circuits –
Logic Gate
1.2.6 Logic Circuits –
Logic Gate
(p ∧ ¬q) ∨ ¬r
(p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r)).
Propositional Equivalences
Introduction
• 5 is greater than 2 , 2 is lesser than 5.
• Replacement of a statement with another statement with the
• Two logical logically equivalent propositions are written as p⇔q
same truth value.
or as p≡q where p and q are compound propositions.
• Two compound propositions p and q are equivalent if and only if
the columns in a truth table giving their truth values agree.
• Express implication () and bi-implication (↔) using ∧, ∨, ¬
p q p→q ¬p v q p v ¬q P↔q (¬p v q) ^ (p v ¬q)
T T T T T T T
T F F F T F F
F T T T F F F
F F T T T T T
Propositional Equivalences
• A tautology is a proposition which is always true. p ∨¬p
Introduction
• A contradiction is a proposition which is always false. p ∧¬p
• A contingency is a proposition which is neither a tautology nor a
contradiction, such as p
• Two compound propositions p and q are logically equivalent if
• is Conditional Disjunction Equivalence.
p↔q is a tautology.
Propositional Equivalences, Law of Logic
Propositional Equivalences, Law of Logic
Proof of Distributive Law
Propositional Equivalences, Law of Logic
Propositional Equivalences, Law of Logic
• Show that is a Tautology.
• Prove the following equivalences
Propositional Satisfiability
• A compound proposition is satisfiable if there is an assignment of truth
values to its variables that makes it true. When no such assignments exists,
that is, when the compound proposition is false for all assignments of truth
values to its variables, the compound proposition is unsatisfiable.
• Note that a compound proposition is unsatisfiable if and only if its negation is
true for all assignments of truth values to the variables, that is, if and only if
its negation is a tautology
Satisfibale: A compound proposition is satisfiable if there is an assignment of truth
values to its variables that makes it output true.
UnSatisfiable: If no such assignments exists i.e. compound proposition is equivalent to
CONTRADICTION, then compound proposition is unsatisfiable .
Solution: Such assignment of truth value which makes a compound proposition
satisfiable is called a solution of proposition.
A TRUTH TABLE can be used to determine whether a compound propositions is
satisfiable .
Notation
The n-Queens Problem Sudoku
Practice Time
Write each of these statements in the form “if p, then q” in English.
[Hint: Refer to the list of common ways to express conditional statements provided in this section.]
a) You send me an e-mail message only if I will remember to send you the address.
b) To be a citizen of this country, it is sufficient that you were born in the United States.
c) If you keep your textbook, it will be a useful reference in your future courses.
d) The Red Wings will win the Stanley Cup if their goalie plays well.
e) That you get the job implies that you had the best credentials.
f) The beach erodes whenever there is a storm.
g) It is necessary to have a valid password to log on to the server.
h) You will reach the summit unless you begin your climb too late.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Practice Time
Let p, q, and r be the propositions
p: You have the flu.
q: You miss the final examination.
r: You pass the course.
Express each of these propositions as an English sentence.
a) p→q
b) ¬q ↔ r
c) q →¬r
d) p∨q∨r
e) (p →¬r) ∨ (q →¬r)
f) (p ∧ q) ∨ (¬q ∧ r)
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Practice Time
Let p, q, and r be the propositions
p: You get an A on the final exam.
q: You do every exercise in this book.
r: You get an A in this class.
Write these propositions using p, q, and r and logical connectives.
a) You get an A in this class, but you do not do every exercise in this book.
b) You get an A on the final, you do every exercise in this book, and you get an A in this class.
c) To get an A in this class, it is necessary for you to get an A on the final.
d) You get an A on the final, but you don’t do every exercise in this book; nevertheless, you get an A in this class.
e) Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.
f) You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
