Knowing and the Mystique of Logic and Rules by Peter Naur

Author:Peter Naur
Language: eng
Format: epub
Publisher: Springer Netherlands, Dordrecht

Define M * by the following construction: 1 0. Set M* = M.

1. Set i = 1.

2.

3. Increment i by 1.

4. If go to step 2; otherwise, stop.

We assert M * = M’.

PROOF. Trivially, For, either m *[i, j] was unity initially (m[i, j] = 1)—in which case m ’[i, j] is surely unity—or m *[i, j] was set to unity in step two. That is, there were, at the L 0th application of step two, m *[i, L 0] = m *[L 0, j] = 1. Each of these, similarly, either came directly from M or from a previous application of step two. Since there are exactly d applications of step two, this procedure is finite and leads to m *[i, L A] = m *[L A, L A-1] = … = m *[L 2, L 1] = m *[L 1, L 0] = m *[L 0, R 1] = … = m *[R B , j] = 1, where all the corresponding entries in M were unity. This is exactly the sequence required in the definition of M’ (to within redundant elements which may simply be struck out) to imply that m’[i, j] = 1.

We have yet to prove that Assume this is false. Then there is a sequence of integers such that m[i, k 1] = m[k 1, k 2] = … = m [k n , j] = 1, but m *[i, j] =0. Let L = . Let λ be the largest element of L. Surely m *[i, k λ] must have been changed from zero to unity by an application of step two (for if m[i, k λ] = 1, since m[k λ, k λ+1] = 1, m *[i, k λ+1] = 1 by the k λth step 2, which would contradict the definition of λ), the γth, say. This γ must be less than k λ, for immediately after the k λth iteration of step two, . Any p 0 such that m *[p 0, k λ] is set to one after this will result from the p 1th iteration of step two when m *[p 1, k λ] = m *[p 0, p 1] = 1 leads to m *[p 0, k λ] = 1. But if m *[p 1, k λ] = 1 at this time, then either m *[p 1, k λ] = 1 at the time of the k λth iteration (in which case m *[p 1, k λ+1] =1 also), or m *[p1, k λ] is set to one at the p 2th iteration where k λ < p 2 < p 1. We thus generate a finite ordered set p 1 > p 2 > … > p q > k », where m *(p q, k λ] = 1 at the time of the k λth iteration, whence m *[p q, k λ+1] = 1 immediately after that iteration. Then the sequence of iterations designated by the p’s will surely result in m *[p 0,k λ+1] = 1 after the p 1th iteration.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.