Home ] Up ]





  1. Statements and logical connectives; truth tables.

  2. Predicates logic and Quantifiers

  3. Proof techniques, the nature of mathematical theorems and proofs; direct proof, proof by contraposition, by contradiction; use of counterexamples; the principle of mathematical induction   proof-1  proof-2


  1. The notation of set theory - Subsets and the power set; binary and unary operations on a set; set operations of union, intersection, complementation, difference, and Cartesian product

  2. Demonstration of the denumerability of some sets and the use of Cantor  diagonalization method to prove the uncountability; partition of a set

Relations & Functions

  1. Binary relations as ordered pairs and verbal description; the reflexive, symmetric, transitive and antisymmetric properties of binary relations; the definition and terminology about partial orderings; graphs of partially ordered finite sets; the definition of equivalence relation and equivalence class

  2. Functions; definition and examples; properties of functions one-t-one, onto, bijective; function composition, inverse function


  1.  Counting; fundamental counting principles, including the multiplication and addition principles

  2.  Sampling and selecting

  3. Permutations and combinations; formulas for counting the number of permutations and combinations of k-objects from n distinct objects


  1. Graph terminology; undirected graphs, simple, complete, path, cycle, adjacency matrix, connectivity; Euler’s path and Hamiltonian circuit; graph representation, trees

  2. Digraphs and connectivity problems - Reachability matrix analysis; Warshall’s algorithm

Boolean Algebra & Computer Logic

  1. Discussion and Definition; similarities between propositional logic and set theory; mathematical structures as models or abstractions incorporating common properties found in different contexts

  2. Logic circuits; basic logic elements of AND gate, OR gate and inverter;  representation of a Boolean expression as a combinational network and vice versa; procedure to find a canonical sum-of-product Boolean expressions using Karnaugh map or  Boolean algebra properties

Algebraic Structures

  1. Definition of binary operation and structure; discussion of the associative, commutative, identity and inverse properties; definition of semigroup, monoid, and a substructure

  2. Group structure; elementary group theorems, uniqueness of identity and inverse; cancellation laws; definition and properties of a subgroup; application to error correcting codes

Finite State Machines

  1. Definition of FSM; state tables and state graphs

  2. FSM as transducers and recognizers

  3. Discussion of limitations of FSMs; introduction to formal languages

Final Examination