SKEDSOFT

Introduction: “Boolean logic” is a system built with two values TRUE and FALSE. “Boolean values” are represented by values 0 and 1. There are many Boolean operations.

(a) Negation: It means the NOT operation, represents by .

Example: 0 = 1 and 1 = 0.

(b) Conjunction: It means the AND operation, represented by Ù.

(c) Disjunction: It means the OR operation, represented by Ú

The truth tables of the above Boolean operations are shown as below:

(d) Exclusive-OR operation: 1 if either but not both of its operands are 1.

Exclusive-OR is denoted byÅ.

(e) Equality: The equality operation, written with the symbol «, is 1 if both its operands have the same value.

(f) Implication: This operation is designated by the symbol ® and is 0 if its first operand is 1 and its second operand is 0; otherwise ® is 1.

Fundamental Proof Techniques

(a) Principle of Mathematical Induction

Proof of induction is used to show that all elements of an infinite set have a specified property. The proof by induction has two parts,

1. Induction step
2. Basis.

The induction step proves that for each i ³1, if P(i) is true, then so is P(i 1). The basis proves that P(1) is true. When both these parts are proved, then for each i, P(i) is proved.

Let us illustrate the method of writing a proof by induction.

Basis: To prove that P(1) is true.

Induction Step: For each i ³1, assume that P(i) is true and use this assumption to show that P(i 1) is true.

(b) Pigeon-hole Principle

If A and B are finite sets and |A| > |B|, then there is no one-to-one function from A to B. i.e., If an attempt is made to pair off the elements of A (the “pigeons”) with elements of B (the “pigeonholes”), sooner or later we will have to put more than one pigeon in a pigeonhole.

By induction, the pigeonhole principle can be proved.