6.5.1. Circuit Satisfiability¶

1 / 32 Settings

<<<>>>

Introduction to Circuit Satisfiability

This slideshow introduces and explains the "Circuit Satisfiability" Problem.


We start with some definitions and background.

A boolean value is a value drawn from the set {T, F},
where $F$ represents FALSE and $T$ represents TRUE.

A boolean combinational element is any circuit element that has a constant number of boolean inputs
and outputs and that performs a well-defined function.

The boolean combinational elements used in Circuit Satisfiability Problem are known as Logic Gates.

The Logic Gates used for Circuit Satisfibiality problem are AND (represented by the symbol '$.$'),
OR (represented by the symbol '$+$'), and NOT (represented by a bar '$\overline{\ \ \ }$' over some variable).

The Truth Table for Logic Gates

The NOT gate

1. $x$
2. $\overline{x}$

1. T
2. F

1. F
2. T

The AND gate

1. $x$
2. $y$
3. $x.y$

1. T
2. T
3. T

1. T
2. F
3. F

1. F
2. T
3. F

1. F
2. F
3. F

The OR gate

1. $x$
2. $y$
3. $x$+$y$

1. T
2. T
3. T

1. T
2. F
3. T

1. F
2. T
3. T

1. F
2. F
3. F

A boolean combinational circuit consists of one or more boolean combinational elements
interconnected by wires.

A wire can connect the output of one element to the input of another, thereby providing the output
value of the first element as an input value of the second.

If a wire is not connected as input to any element, it is called the circuit output.

For defining a circuit satisfiability problem, the number of circuit outputs is limited to 1.

x1

x2

x3

A

B

C

D

E

F

G

We number the input and output wires to be able to refer to them in the later slides.

1

2

3

4

5

6

7

8

9

10

We also present an alternate representation of the circuit in
tabular form which will be used to explain propagation of signals.

2. $\overline{A}$
3. $B+$
4. $\overline{C}$
5. $D\ .$
6. $E+$
7. $F+$
8. $G\ .$

1. 1

1. 2

1. 3

1. 4

1. 5

1. 6

1. 7

1. 8

1. 9

The table has a row for each input wire and a column for each gate.

Each item in the column header contains the name
and the type of the gate.

For example '$A^{\overline{\ \ \ \ }}$' indicates that
the gate labelled as 'A' is of type 'NOT'.

We now show how to populate the table starting with Gate A.

As input signal 3 passes through Gate A, wire 4 carries the output.
Hence the cell under input wire 3 and gate A is assigned the value 4.

Populating the table for Gate B.

Populating the table for Gate C.

Populating the table for Gate D.

Populating the table for Gate E.

Populating the table for Gate F.

Populating the table for Gate G.

This is the complete tabular representation of the circuit.

We show the propagation of signals by assuming a particular
assignment of input signals to the circuit.

Let the assignment be { $x1 = T , x2 = F , x3 = F $ }.

As signal x3 passes through Gate A, wire 4 gets value $F$.

As signals x1 and x2 pass through Gate B, wire 5 gets value $T$.

As signal 4 passes through Gate C, wire 6 gets value $T$.

As signals x1, x2 and 4 passes through Gate D, wire 7 gets value $F$.

As signals 5 and 6 pass through Gate E, wire 8 gets value $T$.

As signals 6 and 7 pass through Gate F, wire 9 gets value $T$.

As signals 8 and 9 pass through Gate G, wire 10 gets value $T$.

The above circuit yields a value $T$ for the assignment
{ $x1 = T, x2 = F, x3 = T $}.

The set of boolean input values for a boolean combinatorial circuit is called a Truth Assignment.

If a truth assignment causes the output of a circuit to be True, it is called a satisfying assigment.

A one-output boolean combinational circuit is satisfiable if it has a satisfying assignment.

Given a boolean combinatorial circuit composed of AND , OR and NOT gates , is the circuit satisfiable?

This circuit is satisfied for the assignment {$x1 = T, x2 = F, x3 = T$}.

As seen form the table above, possible assigment for x1, x2 and x3 satisfies the above circuit.
Hence the circuit is not satisfiable.

1. x1
2. x2
3. x3
4. x0

1. T
2. T
3. T
4. F

1. T
2. T
3. F
4. F

1. T
2. F
3. T
4. F

1. T
2. F
3. F
4. F

1. F
2. T
3. T
4. F

1. F
2. T
3. F
4. F

1. F
2. F
3. T
4. F

1. F
2. F
3. F
4. F

Saving...
Server Error
Resubmit

While it is easy to check whether a given truth assignment satisfies a given circuit, we have no easy way of knowing whether an arbitrary cirucit has some satisfying assignment.