Essential Logic for Computer Science by Rex Page & Ruben Gamboa

Author:Rex Page & Ruben Gamboa [Page, Rex & Gamboa, Ruben]
Language: eng
Format: epub
Tags: Computers, Computer Science, Mathematics, Logic
ISBN: 9780262039185
Google: 0oCADwAAQBAJ
Publisher: MIT Press
Published: 2019-01-08T00:36:23.792020+00:00

Figure 6.5

Definitions of operators bits and numb.

A theorem about numb concerning the interpretation of binary numerals as numbers and a theorem about numb being the inverse of the bits operator are true, and the proofs are similar to the proofs of the corresponding theorems about decimal numerals presented earlier in this chapter. Constructing those proofs can clarify your understanding of both decimal numerals and binary numerals.

Box 6.6

Representation Trick: Any List Is a Binary Numeral

A difference between the definition of numb (figure 6.5) and the definition of nmb10 (page 130) is that numb treats bits as symbols, whereas nmb10 assumes that digits are numbers. A 1 in our representation of binary numerals stands for a one-bit. Anything else stands for a zero-bit. That’s why the definition of numb has two equations ({2numb+1} and {2numb}) for nonempty numerals, whereas the definition of nmb10 has only one equation ({n10.1}).

There are two motivations for this design decision. One is that it makes binary numerals entirely symbolic, with no ephemeral entities like mathematical numbers. Circuits represent bits symbolically by electronic signals, and so the definition of numb is more closely related to a circuit than it would be if it treated bits as numbers.

The other motivation is to reduce the number of constraints in theorems about ACL2 models of circuits. Bits don’t have to be lists of zeros and ones. Any list is a numeral. That numeral has one-bits where the elements of the list are ones and zero-bits where its elements are anything other than ones. In fact, numerals are entirely unconstrained. The empty list represents the number zero, but so does any ACL2 entity x such that (consp x) is false. Many picayune details in theorems about binary numerals are avoided by this elimination of constraints.

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.