Exclusive-OR: 1 if either but not both of its operands are 1.
Mathematical Induction: Has two parts (a) Induction step (b) Basis.
Pigen-hole principle: If an attempt is made to pair off the elements of A (“the
pigeons”) with elements of B (the “pigeon holes”), sooner or later we
will have to put more than one pigeon in a pigeon hole.
REVIEW QUESTIONS
1. Define the following terms:
(a) Set (b) Union (c) Intersection
2. Define the following terms:
(a) set difference (b) Complement
Explain with examples.
3. What have you understood by the following:
(a) Idempotency
(b) Commutativity
(c) Associativity in respect of sets.
4. Define the following w.r.t. sets:
(a) Distributivity (b) Absorption (c) DeMorgan’s laws
5. Stand prove DeMorgan’s Laws.
6. Define the following terms w.r.t. sets:
(a) Disjoint sets
(b) Cardinality
(c) Powerset
(d) Cartesian product.
7. Define a relation. Explain with an example.
8. What is an equivalence relation? Give an example.
9. Explain the terms:
(a) Partial ordered set/Poset (b) Partition of a relation
10. What do you mean by equivalence class?
11. Define function as a relation.
12. What are the kinds of functions?
13. Explain the following with an example for each:
(a) one-to-one function
(b) onto function
(c) one-to-one onto function
(d) invertible function.
14. Differentiate between Injection, Surjection and bijection with
examples.
15. Define a graph with an example.
44
Theory of Automata, Formal Languages and Computation