59. Sketch the Ex-OR truth table.
A
B
C A B
= ⊕
0
0
0
0
1
1
1
0
1
1
1
0
Con junc tion
60. What is the principle of Mathematical Induction?
There are two parts to the method of proof by induction (used to
show that all elements of an infinite set have a specified property):
(i) Induction step (ii) 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.
61. State Pigeon-hole Principle.
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.
62. Define a Grammar of a Language.
A Grammar (G) is defined as a quadruple
G V T S P
= ( , , , )
where
V = finite set of objects called Variables
T = finite set of objects called Terminal symbols.
S V
∈
= start symbol
P = finite set of productions.
Introduction
57
A
B
C A B
= ⊕
0
0
0
0
1
1
1
0
1
1
1
0
Con junc tion
60. What is the principle of Mathematical Induction?
There are two parts to the method of proof by induction (used to
show that all elements of an infinite set have a specified property):
(i) Induction step (ii) 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.
61. State Pigeon-hole Principle.
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.
62. Define a Grammar of a Language.
A Grammar (G) is defined as a quadruple
G V T S P
= ( , , , )
where
V = finite set of objects called Variables
T = finite set of objects called Terminal symbols.
S V
∈
= start symbol
P = finite set of productions.
Introduction
57