30-11-2012, 01:43 PM
A Boolean Circuit
A Boolean.docx (Size: 13.49 KB / Downloads: 24)
ABSTRACT:
The main aim was to write a denition for the predicate V alue that
allows computing the value of the output of the whole circuit given the structure
Of the circuit as well as values of its inputs.
DESCRIPTION:
A Boolean circuit consists of a set of gates that connect the inputs of the circuit
to the outputs. Three types of gates are considered here: and-gates, or-gates
and inverters. These gates implement the respective logical connectives (i.e.
conjunction, disjunction and negation), but gates handle Boolean values 0 and
1 rather than truth values
Predicate V alue(p; v): the value of a point p in the circuit is v.
Predicate And(x; y; z): there is an and-gate in the circuit that connects
inputs x and y to an output z. It should be clear that the value of z is 1
only when both x and y have the value 1.
Predicate Or(x; y; z): there is an or-gate in the circuit that connects inputs
x and y to an output z.
Predicate Inv(x; y): there is an inverter in the circuit that connects an
input x to an output y.
We had to use a language based only on the symbols mentioned above. Suppose that the structure of this circuitis the following:
The and-gate connects inputs a and b to output d, the or-gate connects inputs d and e to output f, and the inverter connects input c to output e. In terms of the given predicates, this is expressed as
And(a; b; d), Or(d; e; f) and Inv(c; e).
suppose that the input values a is 0 and the points b and c are 1. This is expressed
as V alue(a; 0), V alue(b; 1) and V alue(c; 1) Then, the denitions of the value
predicate should allow us to infer that e.g. the value of the point d is 0, which is expressed as
V alue(d; 0).