Mathematics for Computer Science

5.4. State Machines 153

Problems for Section 5.2

Practice Problems

Problem 5.17.
Some fundamental principles for reasoning about nonnegative integers are:

1. The Induction Principle,


2. The Strong Induction Principle,


3. The Well Ordering Principle.

Identify which, if any, of the above principles is captured by each of the following
inference rules.

(a)

P.0/; 8 m:. 8 km: P.k//IMPLIESP.mC1/

8 n: P.n/

(b)

P.b/; 8 kb: P.k/IMPLIESP.kC1/

8 kb: P.k/

(c)

9 n: P.n/

9 m: ŒP.m/AND. 8 k: P.k/IMPLIESkm/ç

(d)

P.0/; 8 k > 0: P.k/IMPLIESP.kC1/

8 n: P.n/

(e)

8 m:. 8 k < m: P.k//IMPLIESP.m/

8 n: P.n/

Problem 5.18.
ThenthFibonacci number,F.n/, is defined as follows

F.0/WWD0;

F.1/WWD1;

F.n/WWDF.n1/CF.n2/ forn2:

Which sentences in the proof below contain logical errors?