TOPIC

DESCRIPTION

Logic 

Statements
and logical connectives; truth tables.

Predicates
logic and Quantifiers

Proof
techniques, the nature of mathematical theorems and proofs; direct
proof, proof by contraposition, by contradiction; use of
counterexamples; the principle of mathematical induction
proof1
proof2

Sets 

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

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

Relations & Functions


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

Functions;
definition and examples; properties of functions onetone, onto,
bijective; function composition, inverse function

Combinatorics


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

Sampling
and selecting

Permutations
and combinations; formulas for counting the number of permutations and
combinations of kobjects from n distinct objects

Graphs


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

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

Boolean
Algebra & Computer Logic 

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

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 sumofproduct Boolean expressions
using Karnaugh map or Boolean
algebra properties

Algebraic Structures


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

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


Definition
of FSM; state tables and state graphs

FSM
as transducers and recognizers

Discussion of limitations of FSMs; introduction to
formal languages

Final Examination
