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
proof-1
proof-2
|
|
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 one-t-one, 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 k-objects 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 sum-of-product 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
|