DISCRETE MATHEMATICS (Unit 3)

Unit 3: Relations and Finite State Machines

Binary Relation

A subset of a Cartesian product A × B. If A = B, it is a relation on set A.

Reflexive Relation

Every element relates to itself. In its Boolean matrix MR, the main diagonal is entirely 1s.

Symmetric Relation

If aRb, then bRa. In its matrix, MR equals its transpose (MR = M T/R ).

Inverse Relation (R−1 )

Formed by reversing all ordered pairs. Given MR, the inverse matrix is strictly the Transpose of the matrix: MR−1 = (MR) T .

Complement Relation (R complement)

Formed by flipping all logic states. Given MR, the complement matrix is the Bitwise NOT of the matrix (0s become 1s, 1s become 0s).

Equivalence Relation

A relation that is simultaneously Reflexive, Symmetric, and Transitive

Partial Order (PoSet)

A relation that is simultaneously Reflexive, Antisymmetric, and Transitive.

Mealy Machine

A Finite State Machine where the output depends on BOTH the present state and the current input. (Transitions are labeled Input/Output).

Moore Machine

A Finite State Machine where the output depends ONLY on the present state

Overlapping Sequence Detector

An FSM that allows the terminal bits of one detected pattern to serve as the starting bits of the next pattern.