Discrete Mathematics for CS

Discrete Mathematics for

Computer Science

[Link] Rahmani
cenghabib@[Link]
Kandahar University
Discrete Make You Smart

[Link]

Discrete mathematics for CS

Course administrivia
Textbook:
• Kenneth H. Rosen. Discrete Mathematics and Its
Applications, 7th Edition, McGraw Hill, 2012.

Exercises from the book will be given

for homework assignments

1
 Course administrivia
Grading policy

• Midterm: (20%)
• Homework assignments: 10%
• Attendance: 10%
• Final: 60%

Course Web Page: [Link]

Discrete mathematics for CS [Link]

Course administrivia
Weekly homework assignments
• Assigned in class and posted on the course web page
• Due one week later at the beginning of the lecture
• No extension policy

Collaboration policy:
• You may discuss the material covered in the course
with your fellow students in order to understand it better
• However, homework assignments should be worked on
and written up individually

Discrete mathematics for CS [Link]

3
 Course administrivia
Course policies:
• Any un-intellectual behavior and cheating on exams,
homework assignments, quizzes will be dealt with
severely
• If you feel you may have violated the rules speak to us
as soon as possible.
• Please make sure you read, understand and abide by
the Academic Integrity Code for the Faculty and
College of Arts and Sciences.

Discrete mathematics for CS [Link]

Course syllabus
Tentative topics:
• Logic and proofs
• Sets
• Functions
• Integers and modular arithmetic
• Sequences and summations
• Counting
• Probability
• Relations
• Graphs

[Link]
Discrete mathematics for CS

4
 Course administrivia
Questions

Discrete mathematics for CS [Link]

Discrete mathematics
• Discrete mathematics
– study of mathematical structures and objects that are
fundamentally discrete rather than continuous.
• Examples of objects with discrete values are
– integers, graphs, or statements in logic.
• Discrete mathematics and computer science.
– Concepts from discrete mathematics are useful for
describing objects and problems in computer
algorithms and programming languages. These
have applications in cryptography, automated
theorem proving, and software development.

Discrete mathematics for CS [Link]

5
 Course syllabus
Tentative topics:
• Logic and proofs
• Sets
• Functions
• Integers and modular arithmetic
• Sequences and summations
• Counting
• Probability
• Relations
• Graphs

[Link]
Discrete mathematics for CS

Course syllabus
Tentative topics:
• Logic and proofs
• Sets
• Functions
• Integers and modular arithmetic
• Sequences and summations
• Counting
• Probability
• Relations
• Graphs

[Link]
Discrete mathematics for CS

6
 Logic
Logic:
• defines a formal language for representing knowledge and for
making logical inferences
• It helps us to understand how to construct a valid argument

Logic defines:
• Syntax of statements
• The meaning of statements
• The rules of logical inference (manipulation)

Discrete mathematics for CS [Link]

Propositional logic
• The simplest logic

• Definition:
– A proposition is a statement that is either true or false.

• Examples:
– Pitt is located in the Oakland section of Pittsburgh.
• (T)
– 5 + 2 = 8.
• (F)
– It is raining today.
• (either T or F)

Discrete mathematics for CS [Link]

7
 Propositional logic
• Examples (cont.):
– How are you?
• a question is not a proposition
– x+5=3
• since x is not specified, neither true nor false
– 2 is a prime number.
• (T)
– She is very talented.
• since she is not specified, neither true nor false
– There are other life forms on other planets in the universe.
• either T or F

Discrete mathematics for CS [Link]

Composite statements
• More complex propositional statements can be build from
elementary statements using logical connectives.

Example:
• Proposition A: It rains outside
• Proposition B: We will see a movie
• A new (combined) proposition:
If it rains outside then we will see a movie

Discrete mathematics for CS [Link]

8
 Composite statements
• More complex propositional statements can be build from
elementary statements using logical connectives.

• Logical connectives:
– Negation
– Conjunction
– Disjunction
– Exclusive or
– Implication
– Biconditional

Discrete mathematics for CS [Link]

Negation
Definition: Let p be a proposition. The statement "It is not the
case that p." is another proposition, called the negation of p. The
negation of p is denoted by ¬ p and read as "not p."
Example:
• Pitt is located in the Oakland section of Pittsburgh.

• It is not the case that Pitt is located in the Oakland section of
Pittsburgh.
Other examples:
– 5 + 2  8.
– 10 is not a prime number.
– It is not the case that buses stop running at 9:00pm.
Discrete mathematics for CS [Link]

9
 Negation
• Negate the following propositions:
– It is raining today.
• It is not raining today.
– 2 is a prime number.
• 2 is not a prime number
– There are other life forms on other planets in the universe.
• It is not the case that there are other life forms on other
planets in the universe.

Discrete mathematics for CS [Link]

Negation
• A truth table displays the relationships between truth
values (T or F) of different propositions.

p ¬p
T F
F T
Rows: all possible
values of elementary
propositions:

Discrete mathematics for CS [Link]

10
 Conjunction
• Definition: Let p and q be propositions. The proposition "p
and q" denoted by p  q, is true when both p and q are true
and is false otherwise. The proposition p  q is called the
conjunction of p and q.

• Examples:
– Pitt is located in the Oakland section of Pittsburgh and 5 +
2=8
– It is raining today and 2 is a prime number.
– 2 is a prime number and 5 + 2  8.
– 13 is a perfect square and 9 is a prime.

Discrete mathematics for CS [Link]

Disjunction
• Definition: Let p and q be propositions. The proposition "p
or q" denoted by p  q, is false when both p and q are false
and is true otherwise. The proposition p  q is called the
disjunction of p and q.

• Examples:
– Pitt is located in the Oakland section of Pittsburgh or 5 + 2
= 8.
– It is raining today or 2 is a prime number.
– 2 is a prime number or 5 + 2  8.
– 13 is a perfect square or 9 is a prime.

Discrete mathematics for CS [Link]

11
 Truth tables
• Conjunction and disjunction
• Four different combinations of values for p and q

p q pq pq
T T

T F

F T
Rows: all possible combinations of values for
F F
elementary propositions: 2n values

Discrete mathematics for CS [Link]

Truth tables
• Conjunction and disjunction
• Four different combinations of values for p and q

p q pq pq
T T T

T F F

F T F

• NB: p  q (theFor is used inclusively,

F F p  q is true when
i.e.,
either p or q or both are true).
Discrete mathematics for CS [Link]

12
 Truth tables
• Conjunction and disjunction
• Four different combinations of values for p and q

p q pq pq
T T T T
T F F T
F T F T
F F F F
• NB: p  q (the or is used inclusively, i.e., p  q is true when
either p or q or both are true).
Discrete mathematics for CS [Link]

Exclusive or
• Definition: Let p and q be propositions. The proposition "p
exclusive or q" denoted by p  q, is true when exactly one of p
and q is true and it is false otherwise.

p q pq
T T F
T F T
F T T
F F F

Discrete mathematics for CS [Link]

13
 Implication
• Definition: Let p and q be propositions. The proposition "p
implies q" denoted by p  q is called implication. It is false
when p is true and q is false and is true otherwise.

• In p  q, p is called the hypothesis and q is called the

conclusion.

p q pq
T T T
T F F
F T T
F F T
Discrete mathematics for CS [Link]

Implication
• p  q is read in a variety of equivalent ways:
• if p then q
• p only if q
• p is sufficient for q
• q whenever p

• Examples:
– if Steelers win the Super Bowl in 2013 then 2 is a prime.
• If F then T ?

Discrete mathematics for CS [Link]

14
 Implication
• p  q is read in a variety of equivalent ways:
• if p then q
• p only if q
• p is sufficient for q
• q whenever p

• Examples:
– if Steelers win the Super Bowl in 2013 then 2 is a prime.
•T
– if today is Tuesday then 2 * 3 = 8.
• What is the truth value ?

Discrete mathematics for CS [Link]

Implication
• p  q is read in a variety of equivalent ways:
• if p then q
• p only if q
• p is sufficient for q
• q whenever p

• Examples:
– if Steelers win the Super Bowl in 2013 then 2 is a prime.
•T
– if today is Tuesday then 2 * 3 = 8.
• If T then F

Discrete mathematics for CS [Link]

15
 Implication
• p  q is read in a variety of equivalent ways:
• if p then q
• p only if q
• p is sufficient for q
• q whenever p

• Examples:
– if Steelers win the Super Bowl in 2013 then 2 is a prime.
•T
– if today is Tuesday then 2 * 3 = 8.
•F

Discrete mathematics for CS [Link]

Implication
• The converse of p  q is q  p.
• The contrapositive of p  q is ¬q  ¬p
• The inverse of p  q is ¬p  ¬q

• Examples:
• If it snows, the traffic moves slowly.
• p: it snows q: traffic moves slowly.
• pq
– The converse:
If the traffic moves slowly then it snows.
• qp

[Link]
Discrete mathematics for CS

16
 Implication
• The contrapositive of p  q is ¬q  ¬p
• The inverse of p  q is ¬p  ¬q

• Examples:
• If it snows, the traffic moves slowly.
– The contrapositive:
• If the traffic does not move slowly then it does not
snow.
• ¬q  ¬p
– The inverse:
• If it does not snow the traffic moves quickly.
• ¬p  ¬q

Discrete mathematics for CS [Link]

Biconditional
• Definition: Let p and q be propositions. The biconditional p
 q (read p if and only if q), is true when p and q have the
same truth values and is false otherwise.

p q pq
T T T
T F F
F T F
F F T
• Note: two truth values always agree.

Discrete mathematics for CS [Link]

17
 Constructing the truth table
• Example: Construct a truth table for
(p  q)  (¬p  q)
• Simpler if we decompose the sentence to elementary and
intermediate propositions

p q ¬p pq ¬pq (pq)


(¬pq)
T T

T F

F T
Discrete mathematics for CS [Link]
F F

Constructing the truth table

• Example: Construct the truth table for
(p  q)  (¬p  q)

Rows: all possible

p q ¬p ofvalue
pq s (pq)
forelem ¬pq 
e (¬pq)

T T n
2values
T F
Discrete mathematics for CS [Link]
F T

F F

18
 Constructing the truth table
• Example: Construct the truth table for
(p  q)  (¬p  q) Typically the target
(unknown) compound
proposition and its
values
p q ¬p pq ¬pq (pq)

(¬pq)
T T

T F
values
F T iaryco
Auxil ound
mp
Discrete mathematics for CS [Link]

F F propo sitionsa their

nd

Constructing the truth table

• Examples: Construct a truth table for
(p  q)  (¬p  q)

p q ¬p pq ¬pq (pq)


(¬pq)
T T F

T F F

F T T
Discrete mathematics for CS [Link]
F F T

19
 Constructing the truth table
• Examples: Construct a truth table for
(p  q)  (¬p  q)

p q ¬p pq ¬pq (pq)


(¬pq)
T T F T

T F F F

F T T T
Discrete mathematics for CS [Link]
F F T T

Constructing the truth table

• Examples: Construct a truth table for
(p  q)  (¬p  q)

p q ¬p pq ¬pq (pq)


(¬pq)
T T F T F

T F F F T

F T T T T
Discrete mathematics for CS [Link]
F F T T F

20
 Constructing the truth table
• Examples: Construct a truth table for
(p  q)  (¬p  q)
Simpler if we decompose the sentence to elementary and
intermediate propositions

p q ¬p pq ¬pq (pq)


(¬pq)
T T F T F F
T F F F T F
F T T T T T
F F T T F F
Discrete mathematics for CS [Link]

21