Discrete Structures US-3 Notes for BSCS (Computer Science)

These notes (handout US-3) cover the core topics of Discrete Structures (also called Discrete Mathematics), a compulsory BSCS course. Below is a short study guide to the main ideas in the notes, with examples.

What are discrete structures?

Discrete structures are mathematical objects made of separate, countable elements, such as integers, logical statements, sets, graphs and finite sequences, rather than continuous quantities like the real numbers. Computers store and process information in discrete steps, so this subject gives the mathematical language for programming, algorithms, databases, networks and digital circuits.

Topics in the notes

• Propositional logic, truth tables and logical equivalences
• Predicates and quantifiers
• Rules of inference
• Sets and functions, including floor and ceiling functions
• Algorithms: searching and sorting, with basic analysis
• Integers, congruence and an introduction to cryptography

Propositional logic

A proposition is a statement that is either true (T) or false (F), such as "7 is a prime number". Propositions are combined with connectives: NOT (¬p), AND (p ∧ q), OR (p ∨ q), IF-THEN (p → q) and IF AND ONLY IF (p ↔ q).

An implication is false only when the first part is true and the second is false.

Useful equivalences

• De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Implication: p → q ≡ ¬p ∨ q
• Contrapositive: p → q ≡ ¬q → ¬p

Predicates and quantifiers

A predicate such as P(x): "x > 3" becomes a proposition when x is given a value. The universal quantifier ∀x P(x) means "P(x) is true for every x"; the existential quantifier ∃x P(x) means "there is at least one x for which P(x) is true". To negate them, swap the quantifier and negate the predicate: ¬∀x P(x) ≡ ∃x ¬P(x).

Rules of inference

Sets and functions

A set is a collection of distinct objects, combined with union (∪), intersection (∩) and difference. A function assigns exactly one output to each input. Two functions used often in computing are floor, ⌊x⌋, the greatest integer not more than x, and ceiling, ⌈x⌉, the smallest integer not less than x. For example, ⌊3.7⌋ = 3, ⌈3.2⌉ = 4 and ⌊−2.5⌋ = −3.

Algorithms

• Linear search checks items one by one; in the worst case it looks at all n items, so it takes O(n) steps.
• Binary search works only on a sorted list. It halves the search range each time, so it takes O(log n) steps.
• Bubble sort repeatedly swaps neighbouring items that are out of order; it takes O(n²) steps in the worst case.

Congruence and cryptography

Two integers a and b are congruent modulo m, written a ≡ b (mod m), when m divides a − b. For example, 17 ≡ 5 (mod 12), which is why 17:00 is 5 o'clock on a 12-hour clock. The Caesar cipher uses this idea: each letter number p is encrypted as (p + 3) mod 26, so A becomes D and Z wraps around to C.

Frequently asked questions

Is Discrete Structures the same as Discrete Mathematics?

Yes. Most universities use either name for the same BSCS course covering logic, sets, functions, counting, relations, graphs and basic number theory.

When is an implication p → q false?

Only when p is true and q is false. In every other case p → q is true.

Related Books

• Number System & Boolean Algebra SN-2 Notes
• Discrete Structures US-6 Notes for BSCS (Computer Science)
• Database Management System Overview and Chapter Guide – BSCS University
• Object Oriented Programming Using C++ Overview and Chapter Guide – IT Series BSCS
• Key Book to OOP C++ Programming Exercises Overview and Chapter Guide – IT Series BSCS
• The Concepts of Information Technology Overview and Chapter Guide – IT Series (2nd Edition)