Prof.

Hany Elnashar
Beni Suef National University
1st. Level, Spring Semester 2024
2 Course

Discrete means ‘unconnected’ or ‘distinct’.

The objective of this course is to study the logical and

algebraic relationships between discrete objects.

Learn how to think mathematically.

This course cultivates clear thinking and creative problem

solving by developing students’ mathematical maturity in
several core areas: logic and proofs, sets, functions, relations,
algorithms and counting techniques.
3
Reference Book
Discrete Mathematics and Its Applications
Kenneth H. Rosen, McGraw Hill, 8th Edition.
4 Course Contents

Week number Title

Week 1
Logic and Proofs
Week 2

Week 3
Basic Structures
Week 4

Week 5 Number Theory and Cryptography

Week 6 Induction and Recursion

Week 7 Mid-Term Exam

5 Course Contents
Week number Title

Week 8
Counting
Week 9

Week 10
Discrete Probability
Week 11

Week 12 Report Discussion

Week 13 Tutorial Exam

Week 14 Final Exam

6 Course Grading
Mid-Term Exam 20

Quizzes (Average) 10

Assignments 10

Tutorial Exam 5

Attendance 5

Bonus (class work & participation) 1-5

Final Exam 50

* Note: Attendance should be more than 75% *

7 Exams

Week Action

3nd Quiz 1

5th Quiz 2

7th Mid-Term

9th Quiz 3

14th Final Exam

8

Any Questions?!
The connection between Discrete Structures and Cybersecurity lies in
the foundational mathematical concepts that underpin both fields.
Discrete structures, particularly areas like logic and graph theory,
provide the theoretical framework for designing algorithms and
protocols used in cybersecurity. For example, graph theory may be
applied to model and analyze network structures, while logic is
fundamental to designing secure cryptographic systems.

Certainly! Discrete structures, particularly concepts from mathematics and computer science, play a crucial role in various aspects of
cybersecurity. Here are some examples:
1. Cryptography:
1. Number Theory: Many cryptographic algorithms, such as RSA (Rivest-Shamir-Adleman), rely on number theory concepts like modular arithmetic
and prime factorization.

2. Boolean Algebra: Cryptographic algorithms often involve logical operations, and Boolean algebra is fundamental in designing secure
cryptographic functions.

2. Network Security:
1. Graph Theory: Network topology and connectivity can be represented and analyzed using graph theory. Detecting anomalies, identifying critical
nodes, and optimizing security measures benefit from graph-based models.

2. Set Theory: Security policies and access control mechanisms often rely on set theory principles to define and manage permissions for users or
devices.

3. Access Control Systems:

1. Set Theory and Logic: Access control systems use sets to represent groups of users and logic to define rules for access permissions. Discrete
structures help formalize and analyze these access control policies.

4. Digital Forensics:
1. Combinatorics: In digital forensics, the analysis of large datasets involves combinatorial methods to identify patterns, anomalies, or correlations
among various data points.

2. Probability and Statistics: Understanding the probability of certain events (e.g., the likelihood of a particular type of cyber attack) is crucial in
assessing risks and making informed decisions.

5. Error Detection and Correction:

1. Coding Theory: Coding theory, a branch of discrete mathematics, is applied in designing error-detecting and error-correcting codes. This is
essential for ensuring the integrity of transmitted data.

6. Secure Protocols:
1. Formal Languages: Formal languages, a topic in discrete structures, are used to define the syntax and semantics of secure communication
protocols. Ensuring a clear and unambiguous communication structure is crucial for preventing security vulnerabilities.

7. Cryptographic Protocols:
10

Chapter 1: Logic and proofs

11 Agenda

Propositional Logic

Logical Operators

Propositional Equivalences

Predicates and Quantifiers

Proofs
12 Propositional Logic
 A proposition is a declarative statement that’s either true (T) or false (F),
but not both.

 Propositions:

 Every cow has 4 legs (T)

 Cairo is the capital of Egypt (T)

 1+1=2 (T)

 2+2=3 (F)

 Not Propositions:

 What time is it?

 X+1=2

 Answer this question

13 Propositional Logic

We use letters to denote propositional variables 𝒑,𝒒,𝒓

,𝒔,…

The truth value of a proposition is true, denoted by T,

if it is a true proposition and false, denoted by F, if it is
a false proposition.
14 Propositional Logic
Logical Operators (Connectives)
15 Propositional Logic
Logical Operators - Negation

Suppose p is a proposition, the negation of p is written as ¬p

and has meaning: “It is not the case that p”.

The proposition ¬p is read “not p”.

Here is the truth table for the negation of proposition ¬p.

p ¬p
F T
T F
16 Propositional Logic
Logical Operators - Negation

“Today is Friday “

The negation could be one of the following:

“It is not the case that today is Friday”.

“Today is not Friday”.

“It is not Friday today”.

17 Propositional Logic
Logical Operators - Conjunction
Suppose p and q are propositions, the conjunction of p
and q is written as pлq.

The proposition pлq is read “p and q”.

Here is the truth table for the conjunction of two

propositions pлq.

p q pлq
F F F
F T F
T F F
T T T
18 Propositional Logic
Logical Operators - Conjunction

p is the proposition “Today is Friday”.

q is the proposition “It is raining today”.

The conjunction of p and q is proposition:

“Today is Friday and it is raining today”.

This proposition is:

True on rainy Fridays

False on any day that is not Friday.

False on Fridays when it does not rain.

 19 Propositional Logic
Logical Operators - Disjunction
Inclusive OR

Suppose p and q are propositions, the disjunction of p and q

is written as pνq.

 The proposition pνq is read “p or q”.

Here is the truth table for the disjunction (Inclusive OR of two

propositions pνq. p q pνq
F F F
F T T
T F T
T T T
20 Propositional Logic
Logical Operators - Disjunction
p is the proposition “Today is Friday”.

q is the proposition “It is raining today”.

The disjunction of p and q is proposition:

“Today is Friday or it is raining today”.

This proposition is:

True on any day that is either a Friday or a rainy day

(including rainy Fridays)

False on days that are not Fridays when it also does not
rain.
 Propositional Logic
21
Logical Operators - Disjunction
Exclusive OR

 Suppose p and q are propositions, the Exclusive OR of p and q is

written as p⊕q.

 The proposition p⊕q is read “p or q but not both”, “p XOR q”.

 Here is the truth table for the Exclusive OR of two propositions

p⊕q.
p q p⊕q
 Ex. “Tonight I will
F F F
stay home or go F T T
out to a movie but T F T

not both”. T T F
 22 Propositional Logic
Logical Operators - Implication
 Suppose p and q are propositions, the conditional statement
(implication) of p and q is written as p q.

p q is read “if p, then q” or “p implies q” or “p only if q” or “q when p”.

 p hypothesis – antecedent – premise, q conclusion – consequence.

 Here is the truth table for the Implication of two propositions p q.

p q p q
F F T
F T T
T F F
T T T
23 Propositional Logic
Logical Operators - Implication

p is the proposition “Ahmed gets 100%”.

q is the proposition “Ahmed will get an A+”.

The implication of p and q is proposition:

“if Ahmed gets 100% , then he will get an A+ ”.

This proposition is false when p is true, and q is false.

Otherwise, it is true.
 24 Propositional Logic
Logical Operators: BI-Implication
 Suppose p and q are propositions, the biconditional statement (bi-
implication) of p and q is written as p q.

 The proposition p q is read “p if and only if q”.

 Here is the truth table for the Bi-implication of two propositions p q.

p q p q
F F T
F T F
T F F
T T T
25 Propositional Logic
Logical Operators: BI-Implication

p is the proposition “You can take the flight”.

q is the proposition “You buy a ticket”.

The p q is proposition:

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

This proposition is true if p and q are either both true or

both false.
 26 Propositional Logic
Logical Operators: BI-Implication
 The proposition p q has the same truth value as p qлq p

p q p q q p p qлq p p q

F F T T T T

F T T F F F

T F F T F F

T T T T T T
27 Propositional Logic
Truth Table of Compound Propositions

Class Work

 Construct the truth table of compound propositions (p ν ¬q) (pлq)

28 Propositional Logic
Truth Table of Compound Propositions

Sol.

p q ¬q p ν ¬q pлq (p ν ¬q) (pлq)

F F T T F F

F T F F F T

T F T T F F

T T F T T T
 29 Propositional Logic
Truth table of compound propositions
Precedence of logical operators
 Order of precedence of Logical Operators , , , , 

Precedence of logical operators

Operator Precedence

¬ 1

л 2
ν 3
4
5
30 Propositional Logic
Truth Table of Compound Propositions

 The statements ¬(pлq) and (¬p) ν (¬q) are logically equivalent.

p q ¬p ¬q pлq ¬(pлq) (¬p) ν (¬q)

F F T T F T T

F T T F F T T

T F F T F T T

T T F F T F F
31 Translating English Sentence into a Logical
Expression

“You can access the internet from campus if you are a

computer science major or you are not a student”.
32 Translating English Sentence into a Logical
Expression

Sol.

p: “you can access the internet from campus“

q: “you are a computer science major”

r: “you are a student”

Where p, q, r are propositional variables.

(q ν ¬r) p
33 Propositional Logic
Exercises

When you buy a new car from Ace Motor Company, you
get $2000 back in cash or a 2% car loan but not both.
34 Propositional Logic
Exercises

SOL.

p: buy a new car from Ace Motor Company

q: get $2000 cash back

r: get a 2% car loan

p q⊕r
35 Propositional Logic
Exercises

If more than 2 feet of snow falls or if the wind chill is below
-100, then school will be closed
36 Propositional Logic
Exercises

SOL.

p: more than 2 feet of snow falls

q: the wind chill is below -100

r: school will be closed

pνq r
37 Example Application
Boolean searches

logical connectives are used extensively is searches of

large collections of information: Indexes of Web pages, these
searches employ techniques from propositional logic.

The connective

AND: is used to match records that contain both of the two

search items.

OR: is used to match one or both of two search items.

NOT: is used to exclude a particular search item (- is used in

Google).
 38 Propositional Logic
Example of Use on Bit String
 Table for the Bit Operators OR, AND, and XOR.

x y xνy xлy x⊕y

0 0 0 0 0

0 1 1 0 1

1 0 1 0 1

1 1 1 1 0
 39 Propositional Logic
Example of Use on Bit String
 Logic and Bit operations

A bit string is a sequence of zero or more bits. The length of this string is
the number of bits in the string.

 110110110 is a bit string of length nine.

 Bitwise OR (ν), Bitwise AND (л), Bitwise XOR (⊕)

 1100011101 is a bit string of length ten.

 Bitwise OR (ν), Bitwise AND (л), Bitwise XOR (⊕)

0110110110
1100011101
Bitwise (OR) 1110111111
Bitwise (AND) 0100010100
Bitwise XOR 1010101011
40

Thank You