Discrete Mathematics: Sets, Logic, Relations and Graphs

I prepared my discrete-mathematics notes during undergraduate Computer Engineering courses in the 2013-2014 period. This revision preserves the original progression from sets, counting, and propositional logic through relations, functions, graph theory, and elementary algorithms, while reviewing terminology and examples with later sources.

Unit 1: Introduction to Set Theory

Set concept

A set is a well-defined collection of distinct objects called elements. Membership is written as

x ∈ A
x ∉ A.

A set can be described by listing its elements or by specifying a property that characterizes membership.

Venn diagrams

Venn diagrams represent sets as regions and make operations such as union, intersection, difference, and complement visually explicit. They are useful for reasoning but do not replace formal set definitions.

Finite and infinite sets

A finite set has a finite cardinality. Infinite sets contain no finite list of all elements. Different infinite sets can nevertheless be compared through one-to-one correspondences.

Empty set

The empty set ∅ contains no elements. It is a subset of every set and is not the same object as a set that contains the empty set.

Subset and proper subset

A ⊆ B

means every element of A belongs to B. A proper subset is a subset that is not equal to the containing set.

Equality of sets

Two sets are equal exactly when they contain the same elements:

A = B  ⇔  A ⊆ B and B ⊆ A.

Order and repeated listing do not change a set.

Universal set

The universal set U specifies the reference domain in a particular discussion. Complements are always interpreted relative to this universe.

Union

A ∪ B = {x | x∈A or x∈B}.

Intersection

A ∩ B = {x | x∈A and x∈B}.

Disjoint sets have empty intersection.

Complement and difference

A^c = U \ A
A \ B = {x | x∈A and x∉B}.

Symmetric difference

The symmetric difference contains elements that belong to exactly one of the two sets:

A △ B = (A\B) ∪ (B\A).

Ordered pairs and Cartesian product

An ordered pair (a,b) distinguishes first and second components. The Cartesian product is

A x B = {(a,b) | a∈A, b∈B}.

In general A x B and B x A are not the same set.

Boolean algebra of sets

Set operations obey commutative, associative, distributive, identity, absorption, complement, and De Morgan laws. These laws parallel Boolean logic and digital-circuit algebra.

Number sets

The common hierarchy includes natural numbers, integers, rational numbers, real numbers, and complex numbers. Inclusion relations depend on the chosen convention for natural numbers but the structural containment is otherwise standard.

Intervals

Intervals describe subsets of the real line. Parentheses indicate excluded endpoints and brackets included endpoints, with infinity always written as an open boundary.

Absolute value

|x| = x       if x ≥ 0
|x| = -x      if x < 0.

Geometrically, |x-a| is the distance between x and a on the real line.

Integer part

The floor function ⌊x⌋ is the greatest integer less than or equal to x. It is a step function and must not be confused with ordinary rounding.

Unit 2: Permutations and Combinations

Factorial

For a positive integer n,

n! = n(n-1)...2·1,

with 0! = 1 by convention and combinatorial consistency.

Counting principles

The addition rule handles mutually exclusive alternatives. The multiplication rule handles sequential choices. Many combinatorial formulas are direct consequences of these two principles.

Permutation

When order matters, the number of arrangements of r distinct objects chosen from n is

P(n,r) = n!/(n-r)!.

For all n objects, the count is n!.

Permutations with repetition

If a multiset of n objects contains groups of identical elements with multiplicities n1,...,nk, the number of distinct arrangements is

n!/(n1! n2! ... nk!).

Permutation group

All permutations of n objects form the symmetric group S_n under composition. The identity permutation, inverses, closure, and associativity give the group structure.

Combination

When order does not matter,

C(n,r) = n!/[r!(n-r)!].

Properties of combinations

Important identities include

C(n,r) = C(n,n-r)
C(n,r) + C(n,r-1) = C(n+1,r).

These connect combinations with Pascal's triangle and the binomial theorem.

Combinations with repetition

The number of ways to select r items from n types when repetition is allowed is

C(n+r-1,r).

Unit 3: Propositional Logic

Proposition

A proposition is a declarative statement that has a definite truth value, true or false. Questions, commands, and open expressions containing unspecified variables are not propositions until interpreted appropriately.

Compound proposition and truth table

Logical connectives combine propositions into compound propositions. A truth table lists all possible truth-value assignments and the resulting value of the compound expression.

Negation

If p is a proposition, ¬p reverses its truth value.

Conjunction

p ∧ q

is true only when both propositions are true.

Disjunction

The inclusive OR

p ∨ q

is true when at least one operand is true. Exclusive OR is a different operation and is true when exactly one is true.

Conditional proposition

p → q

is false only when p is true and q is false. It is logically equivalent to

¬p ∨ q.

Converse, inverse, and contrapositive

For p→q:

• converse: q→p,
• inverse: ¬p→¬q,
• contrapositive: ¬q→¬p.

The original conditional is logically equivalent to its contrapositive, not generally to its converse or inverse.

Biconditional

p ↔ q

is true when p and q have the same truth value. It represents two implications together.

Equivalent propositions and standard forms

Two formulas are logically equivalent if they have identical truth values under every assignment. Conjunctive and disjunctive normal forms provide systematic representations built from literals.

Tautology and contradiction

A tautology is true under every truth assignment; a contradiction is false under every assignment. A contingency is true for some assignments and false for others.

Laws of logic

Commutative, associative, distributive, identity, idempotent, absorption, double-negation, and De Morgan laws allow expressions to be transformed without changing their truth functions.

Quine method

The Quine-style tabular approach systematically manipulates truth assignments or implicants to simplify Boolean expressions. In digital-logic applications, systematic minimization reduces redundant terms.

Logical circuits

Boolean expressions map naturally to logic gates. AND, OR, and NOT correspond to fundamental gates, while more complex circuits implement compound propositions. Logical equivalence can therefore be used to simplify circuit structure.

Unit 4: Relations

Relation concept

A binary relation from A to B is any subset of the Cartesian product:

R ⊆ A x B.

A relation on A is a subset of A x A.

Forms of representation

Relations can be represented as sets of ordered pairs, tables, directed graphs, or zero-one matrices. Each representation emphasizes different operations.

Inverse relation

The inverse relation reverses every ordered pair:

R^-1 = {(b,a) | (a,b)∈R}.

Reflexive relation

A relation on A is reflexive if

(a,a) ∈ R

for every a∈A.

Symmetric relation

It is symmetric if

(a,b)∈R ⇒ (b,a)∈R.

Antisymmetric relation

It is antisymmetric if

(a,b)∈R and (b,a)∈R ⇒ a=b.

Antisymmetry does not mean "not symmetric"; the two properties address different conditions.

Transitive relation

It is transitive if

(a,b)∈R and (b,c)∈R ⇒ (a,c)∈R.

Equivalence relation

An equivalence relation is reflexive, symmetric, and transitive. It divides a set into disjoint equivalence classes.

Equivalence classes and partitions

For an equivalence relation, the class of a is

[a] = {x∈A | xRa}.

Distinct classes are disjoint, and their union is the entire set. Conversely, every partition defines an equivalence relation.

Order relations

A partial order is reflexive, antisymmetric, and transitive. A total order additionally makes every pair comparable. Hasse diagrams provide a compact representation of finite partially ordered sets by omitting implied transitive edges.

Relation matrix

For a finite relation, a zero-one matrix records whether each ordered pair belongs to the relation. Reflexivity, symmetry, and other properties can often be checked from matrix structure.

Closures

A closure adds the minimum information needed to give a relation a desired property, such as reflexive, symmetric, or transitive closure.

Warshall algorithm

Warshall's algorithm computes transitive closure from an adjacency/relation matrix. At stage k, paths are allowed to use the first k vertices as intermediate points. The Boolean recurrence is

r_ij^(k) = r_ij^(k-1) OR
           (r_ik^(k-1) AND r_kj^(k-1)).

Unit 5: Functions and Operations

Function

A function f:A→B assigns exactly one element of B to every element of A. A function is a special kind of relation with a uniqueness and totality requirement on the domain.

Types of functions

• injective: distinct inputs have distinct outputs;
• surjective: every element of the codomain is reached;
• bijective: both injective and surjective.

A bijection establishes a one-to-one correspondence between the sets.

Inverse function

A function has an inverse function exactly when it is bijective. The inverse reverses input and output roles:

f^-1(f(x)) = x.

Composition

For compatible functions,

(g∘f)(x) = g(f(x)).

Composition is associative but generally not commutative.

Binary operation

A binary operation on A is a function

*: A x A → A.

Closure is therefore built into the definition.

Properties of an operation

Associativity, commutativity, identity elements, and inverses are central properties. Different combinations lead to algebraic structures such as semigroups, monoids, and groups.

Unit 6: Graph Theory

Königsberg bridge problem

Euler's analysis of the Königsberg bridge problem abstracted land regions as vertices and bridges as edges. The problem became a foundational example of graph theory because connectivity, not geometric distance, determined the answer.

Fundamental terminology

A graph consists of vertices and edges. Edges can be undirected or directed, simple or multiple depending on the graph model. Vertex degree counts incident edges in an undirected graph, while directed graphs distinguish indegree and outdegree.

Walk, trail, path, and circuit

A walk is a sequence of adjacent vertices/edges. A trail does not repeat edges; a path usually does not repeat vertices. A closed trail/circuit returns to its starting point. Terminology varies slightly among texts, so the structural restriction should be stated explicitly.

Connectivity and subgraphs

A graph is connected when a path exists between every pair of vertices. A subgraph uses subsets of the original vertices and edges. Connected components are maximal connected subgraphs.

Trees

A tree is a connected undirected graph with no cycles. For a finite tree with n vertices,

number of edges = n - 1.

Between any two vertices of a tree there is a unique simple path.

Directed graphs

Directed edges have orientation. Reachability, paths, and strongly/weakly connected components reflect this direction information.

Weighted graphs and minimum spanning trees

A weighted graph associates costs or lengths with edges. A minimum spanning tree connects all vertices with no cycles and minimum total edge weight. Classical greedy methods include Kruskal and Prim algorithms.

Matrices and graphs

An adjacency matrix records direct edges. Powers of an adjacency matrix encode information about walks of given length, while Boolean matrix operations support reachability computations.

Gantt charts and activity networks

Project activities can be represented by time-oriented Gantt charts or dependency networks. Graph-based scheduling makes precedence relations and critical dependencies explicit; it is conceptually distinct from merely drawing a calendar bar.

Unit 7: Algorithms

Algorithm concept

An algorithm is a finite, unambiguous sequence of effective steps that transforms input into output. Correctness and termination are separate from efficiency.

Pseudocode

Pseudocode expresses control flow independently of a particular programming language. It should be precise enough that the intended algorithm is unambiguous.

Decision structure

Conditional execution selects different steps according to a Boolean condition:

if condition
    action A
else
    action B

Loop structures

Loops repeat computation while a condition holds or over a finite collection. for, while, and repeat-until styles differ in how repetition is controlled.

Subprogram and function

A subprogram encapsulates a reusable computation. Functions additionally emphasize returning a value, although programming-language terminology varies.

Finding the maximum value

A linear scan can find the maximum of n elements by keeping the largest value seen so far. The algorithm requires n-1 comparisons in the ordinary sequential model.

Computer representation of sets

Finite sets over a known universe can be represented by bit vectors. Membership becomes a bit test; union and intersection correspond naturally to bitwise OR and AND.

Computer representation of relations and graphs

Adjacency matrices provide constant-time edge lookup but use quadratic space. Adjacency lists use space proportional to vertices plus edges and are often better for sparse graphs.

Transitive-closure algorithm

Warshall's dynamic-programming recurrence computes reachability for all vertex pairs in O(n^3) time for an n x n relation matrix.

General Conceptual Framework

Discrete mathematics supplies structural language for computer science:

Sets
  ↓
Counting and logic
  ↓
Relations and functions
  ↓
Graphs and algebraic structure
  ↓
Algorithms and representations

Sets define collections and domains. Logic defines valid propositions and transformations. Relations model pairwise structure; functions impose deterministic mapping. Graphs model connectivity and dependency. Algorithms convert these mathematical structures into finite computational procedures.

Conceptual Distinctions

Element ≠ subset. x∈A is membership; B⊆A compares two sets.

Empty set ≠ set containing the empty set. ∅ has zero elements, while {∅} has one element.

Union ≠ intersection. Union uses logical OR; intersection uses logical AND.

Permutation ≠ combination. Permutations distinguish order; combinations do not.

Implication ≠ converse. p→q is equivalent to its contrapositive ¬q→¬p, not generally to q→p.

Tautology ≠ satisfiable formula. A tautology is true under every assignment; a satisfiable formula only needs at least one true assignment.

Symmetric ≠ antisymmetric. Antisymmetry is not the negation of symmetry; a relation can satisfy both in appropriate cases.

Equivalence relation ≠ order relation. Equivalence uses symmetry; partial order uses antisymmetry.

Relation ≠ function. A function must assign exactly one output to each domain element.

Injective ≠ surjective. Injectivity constrains repeated outputs; surjectivity requires the entire codomain to be reached.

Graph ≠ tree. Every tree is a graph, but a tree must be connected and acyclic.

Walk ≠ path. A path imposes stronger nonrepetition conditions than a general walk.

Algorithm ≠ program. An algorithm is an abstract procedure; a program is an implementation in a computational environment.

Correctness ≠ efficiency. A correct algorithm can still be impractical because of time or space complexity.

References

• Ahmet Yesevi Üniversitesi Bilgisayar Mühendisliği Bölümü. Ayrık Matematik (TBIL108) ders materyalleri.
• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th Edition. McGraw-Hill, 2019.
• Susanna S. Epp. Discrete Mathematics with Applications, 5th Edition. Cengage, 2019.
• Ralph P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction, 5th Edition. Pearson, 2003.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022.
• Reinhard Diestel. Graph Theory, 5th Edition. Springer, 2017.