The circuit representation in the chapter is more detailed than necessary if we care only about circuit functionality. A simpler formulation describes any m-input, n-output gate or circuit using a predicate with m + n arguments, such that the predicate is true exactly when the inputs and outputs are consistent. For example, NOT-gates are described by the binary predicate NOT (i, o), for which NOT (0,l) and NOT (1,O) are known. Compositions of gates are defined by conjunctions of gate predicates in which shared variables indicate direct connections. For example, a NAND circuit can be cornposed from ANDs and NOTs:

Using this representation, define the one-bit adder in Figure

Transcribed Image Text:

Vi1,2,0,0 NAND (11, 12.0) AND (11, 12, 0a) A NOT (0, 0).