Discrete Structures

(Discrete Mathematics)

Lecture-1

Introduction to
Propositional Logic
Instructor: Mr. Obaid ur Rehman
Email : ourehman@[Link]
Course Objectives
• Deep understanding of discrete structures used in
Computer Science
• Developing problem solving and analytical skills
• Developing algorithmic and computational skills

• Ability to understand mathematical arguments and their design

• Understanding of logic
• Proofing techniques
Course Outline
• Formal Logic
• Quantifiers and Predicates
• Proof Techniques
• Number Theory
• Sequence and Summations
• Induction and Recursion
• Basic Set Theory
• Relations
• Functions
• Graphs
• Trees
Text Books

• Discrete Mathematics and its Applications 7th Ed. by

Kenneth H. Rosen, McGraw Hill Publisher.

• Discrete Mathematics with Applications 4th Ed. by

Susanna S., Thomson Learning, Inc.
Reasons to Study Discrete
Structures
• Proof
Ability to understand and create mathematical
argument

• Gateway to more advanced CS courses

Data structures, algorithms, automata theory, formal
languages, Database, networks, operating system,
security etc.
Reasons to Study Discrete
Structures
• It is the mathematics underlying almost all of
computer science:
• Program verification
• Analyzing algorithms for correctness and efficiency
• Finding efficient algorithms
• (for sorting, searching, etc.)
• Formalizing security requirements
• Designing cryptographic protocols for enhanced
security
• Graph Theory (Networks – both physical & social)
Problems solved using Discrete Math's
• How many secure passwords (using a specific number of
characters or digits)?
• Probability of winning a lottery?
• How can I encrypt a message?
• Shortest paths between two cities using public
transportation?
• How many steps required to sort 10,000 numbers? Is this
algorithm correct?
• How to design a circuit that multiply two integers?
Logic

Logic is the study of the principles and methods that

distinguishes between a valid and an invalid argument.

Logic deals with general reasoning laws, which you can

trust.
Applications
• Applied in proving program correctness and verification
• Databases (Relational Algebra and calculus)
• Artificial Intelligence
Propositional Logic
• Proposition
• A proposition is a declarative statement that is either TRUE or FALSE, but not
both.

• Example 1
• 2 + 2 = 4.
• Lahore is the capital of Pakistan.
• It is Sunday today.
• Ali is student of this class.

• Example 2
• What time is it?
• X + 1 = 2.
• Close the door.
• Read this carefully.
Propositional Logic

• Letter are used to denote propositional variables, to

symbolically represent propositions.
• Letters used for this purpose are p, q, r, s,………
• A propositional can have one of two values: true (T) or false (F).

• Example
• p = “Islamabad is the capital of Pakistan”
• q = “17 is divisible by 3”
Propositional Logic
• The area of logic that deals with propositions is called the
Propositional Calculus or Propositional Logic.

• Compound Propositions are constructed by combining

one or more propositions using logical operators
(connectives).

• Examples
• “3 + 2 = 5” and “Lahore is a city in Pakistan”
• “The grass is green” or “ It is hot today”
Symbols for Logical Operators

Symbol Meaning
Negation
And, Conjunction
Or, Disjunction
→ Implication
↔ Bi-Conditional
Logical Operators (Logical connectives)
•
Logical Operator - Negation
• 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
T F
P
F T
Logical Operator - Negation
•
Logical Operator - Conjunction
•
Logical Operator - Conjunction
• Truth Table

p q
T T T
T F F
F T F
F F F
Logical Operator - Conjunction
•
Logical Operator - Conjunction
• Hamza’s PC has more than 16 GB free hard disk space,
and the processor in Hamza’s PC runs faster than 1 GHz.

• It is cold and sunny.

Logical Operator - Disjunction
•
Logical Operator - Disjunction
• Truth Table

p q
T T T
T F T
F T T
F F F
Logical Operator - Disjunction
•
Example
•
Logical Operator – Exclusive Or
•

p q
T T F
T F T
F T T
F F F
Logical Operator – Exclusive Or
•
Exclusive or Versus Inclusive or
(Disjunction)

• Coffee or tea comes with dinner. Exclusive or

• A password must have at least three digits or be at least

five characters long. Inclusive or

• Lunch includes soup or salad. Exclusive or

• Experience with C++ or Java is required. Inclusive or

Logical Operator – Implication
• p → q corresponds to English “if p then q,” or “p implies
q.”
• Symbol: →
• The implication p → q is the proposition that is false when
p is true and q is false, and true otherwise.
p→q

• Examples
• If it is raining then it is cloudy. Hypothesis Conclusion
• If you get 100% on the final, then you will get an A.
• If p then 2+2 = 4.
Logical Operator – Implication
• Truth Table

p q p→q
T T T
T F F
F T T
F F T
Logical Operator – Implication

• Alternate ways of stating an implication

• p implies q
• If p, q
• p only if q
• p is sufficient for q
• q if p
• q whenever p
• q is necessary for p
Implication - Example
p: you get 100% on the final
q: you will get an A
• p implies that q.
you get 100% on the final implies that you will get an A.
• If p, then q.
If you get 100% on the final, then that you will get an A.
• If p, q.
If you get 100% on the final, that you will get an A.
• p is sufficient for q.
Get 100% on the final is sufficient for getting an A.
• q if p.
you will get an A if you get 100% on the final.
• q unless ￢ p.
you will get an A unless you don’t get 100% on final.
Logical Operator – Implication

• Converse
The proposition q → p is converse of p → q.

• Contrapositive
The contrapositive of p → q is the proposition ￢q →￢p.

• Inverse
The proposition ￢p →￢q is called the inverse of p → q.
Logical Operator – Implication
• Example

“The home team wins whenever it is raining?”

Because “q whenever p”, so p → q, the original statement
can be rewritten as “If it is raining, then the home team wins.”

• Contrapositive
“If the home team does not win, then it is not raining.”
• Converse
“If the home team wins, then it is raining.”
• Inverse
“If it is not raining, then the home team does not win.”
Logical Operator – Bi-conditional
• p ↔ q corresponds to English “p if and only if q.”
• Symbol: ↔
• The bi-conditional statement p ↔ q is true when p and q
have the same truth values, and is false otherwise.
• Bi-conditional statements are also called bi-implications.
• Alternatively, it means “(if p then q) and (if q then p)”

• Example
• “You can take the flight if and only if you buy a ticket.”
Logical Operator – Bi-conditional
• Truth Table

p q p↔q
T T T
T F F
F T F
F F T
Logical Operator – Bi-conditional
•
Logical Operator – Bi-conditional

• Other English equivalents:

• “p if and only if q”
• “p is equivalent to q”
• “p is necessary and sufficient for q”
• “p iff q”
• “If p then q, and conversely”
Bi-conditional -Example
p: “You can take the flight”
q: “You buy a ticket”
p ↔ q:

You can take the flight if and only if you buy a ticket

You can take the flight iff you buy a ticket

The fact that you can take the flight is necessary and
sufficient for buying a ticket
Logical Operators Summary

Not Not And Or Xor Implication Bi-conditional

p q ¬p ¬q p∨q p⊕q p→q p ↔q
T T F F T T F T T
T F F T F T T F F
F T T F F T T T F
F F T T F F F T T
Truth Table of Compound Propositions
• Construction of a truth table:
• Rows
• Need a row for every possible combination of values for the every
propositions.
• Columns
• Need a column for the compound proposition (usually at far right)
• Need a column for the truth value of each expression that occurs in
the compound proposition as it is built up.
• This includes the atomic propositions
Truth Table of Compound Propositions
• (p ∨￢q) → (p ∧ q)

p
p q ￢q p∧q (p ∨￢q) → (p ∧ q)
∨￢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
Truth Table of Compound Propositions
• p → (￢q ∧ r )

p q r ￢q ￢q ∧ r p → (￢q ∧ r )

T T T F F F
T T F F F F
T F T T T T
T F F T F F
F T T F F T
F T F F F T
F F T T T T
F F F T F T
Precedence of Logical Operators
• Just as in algebra, operators have precedence

4+3*2 = 4+(3*2), not (4+3)*2

• Example Operator Precedence

¬ 1
This means that
∧ 2
p ∨ q ∧ ¬r → s ↔ t
∨ 3
yields: (p ∨ (q ∧ (¬r)) → s) ↔ (t)
→ 4

↔ 5
Truth Tables
• Construct the truth table of following compound
propositions
• p →￢p
•p⊕p
• (q →￢p) ↔ (p ↔ q)
Chapter Reading
• Chapter 1, Kenneth H. Rosen, Discrete Mathematics and
Its Applications