Design a 2-bit Greater-than Circuit Using Gate-level Logical Operators Only

Truth Table

Fundamentals

John Crowe , Barrie Hayes-Gill , in Introduction to Digital Electronics, 1998

The NOT operator

Since any Boolean variable can only be either 0 or 1 (Boolean algebra is a two- state system) then if it is 0 its complement is 1 and vice versa. The NOT gate performs this operation (of producing the complement of a variable) on a logic signal, so if A is input to the NOT gate then the output is represented by $Y=\overline{A}$ Therefore if A = 0 then Y = 1, or else A = 1 and Y = 0 (there are only two possibilities).

The truth table of a logic system (e.g. digital electronic circuit) describes the output(s) of the system for given input(s). The input(s) and output(s) are used to label the columns of a truth table, with the rows representing all possible inputs to the circuit and the corresponding outputs. For the NOT gate there is only one input (hence one input column, A), which can only have two possible values (0 and 1), so there are only two rows. ³ As there is only one output, Y, there is only one output column. The truth table for the NOT gate in Table 1.2 shows that Y = 1 if A = 0, and Y = 0 if A = 1. So $Y=\overline{A}$ , the complement of A. The NOT gate is also sometimes referred to as an inverter due to the fact that it complements (inverts) its input.

Table 1.2. Truth tables for the three basic logic gates

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780340645703500034

Introduction to Digital Logic Design

Ian Grout , in Digital Systems Design with FPGAs and CPLDs, 2008

5.3.5 Truth Tables

The truth table displays the logical operations on input signals in a table format. Every Boolean expression can be viewed as a truth table. The truth table identifies all possible input combinations and the output for each. It is common to create the table so that the input combinations produce an unsigned binary up-count.

The truth table for the AND gate is shown in Table 5.13. Here, the output Z is a logic 1 only when both inputs A and B are logic 1.

Table 5.13. AND gate truth table

The truth table for the NAND gate is shown in Table 5.14. Here, the output Z is a logic 0 only when both inputs A and B are logic 1. This is the logical inverse of the AND gate.

Table 5.14. NAND gate truth table

The truth table for the OR gate is shown in Table 5.15. Here, the output Z is a logic 1 when either or both inputs A and B are logic 1.

Table 5.15. OR gate truth table

The truth table for the NOR gate is shown in Table 5.16. Here, the output Z is a logic 0 when either or both inputs A and B are logic 1. This is the logical inverse of the OR gate.

Table 5.16. NOR gate truth table

The truth table for the EX-OR gate is shown in Table 5.17. Here, the output Z is a logic 1 when either but not both inputs A and B are logic 1.

Table 5.17. EX-OR gate truth table

The truth table for the EX-NOR gate is shown in Table 5.18. Here, the output Z is a logic 0 when either but not both inputs A and B are logic 1. This is the logical inverse of the EX-OR gate.

Table 5.18. EX-NOR gate truth table

The truth table for the NOT gate (inverter) is shown in Table 5.19. This gate has one input only. The output Z is the logical inverse of the input A.

Table 5.19. NOT gate truth table

The truth table for the BUFFER is shown in Table 5.20. This gate has one input only. The output Z is the same logical value as that of the input A.

Table 5.20. BUFFER truth table

Another way to describe a digital circuit or system is by using a suitable HDL such as VHDL [9, 10]. This describes the operation of the circuit or system at different levels of design abstraction. An example VHDL description for each of the basic logic gates using the built-in logical operators in VHDL is shown in Figure 5.10. The syntax and semantics of the language will be provided in Chapter 6. It is sufficient at this point to note that HDLs exist and for VHDL the basic structure of a VHDL text based description is of the form shown in Figure 5.10.

Figure 5.10. VHDL code examples for the logic gates in Figure 5.8

The EX-OR gate has the Boolean expression:

$\text{Z}=\text{A}\oplus \text{B}$

From the truth table for the EX-OR gate, then, a Boolean expression in the first canonical form (the first canonical from is a set of minterms that are AND logical operators on the variables within the expression with the output of the AND logical operators being logically ORed together) can be written as:

$\text{Z}=(\overline{\text{A}}\text{.B})+(\text{A}\text{.}\overline{\text{B}})$

Therefore, the EX-OR gate can be made from AND, OR, and NOT gates as shown in Figure 5.11.

Figure 5.11. EX-OR gate using discrete logic gates

The truth table can be created to identify the input-output relationship for any logic circuit that consists of combinational logic gates and that can be expressed by Boolean logic. It is therefore possible to move between Boolean logic expressions and truth tables. Consider a three-input logic circuit (A, B, and C) with one output (Z), as shown in the truth table in Table 5.21. The inputs are written as a binary count starting at 0₁₀ and incrementing to 7₁₀. The output Z is only a logic 1 when inputs A, B, and C are logic 1. This can be written as a Boolean expression

Table 5.21. Three-input logic circuit truth table: Z = A.B.C

A	B	C	Z
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

$\text{Z}=\text{A}\text{.B}\text{.C}$

Here, where the output Z is a logic 1, the values of inputs A, B, and C are ANDed together. Where a variable is a logic 1, then the variable is used. When the variable is a logic 0, then the inverse (NOT) of the variable is used.

Consider now another three-input logic circuit (inputs A, B, and C) with one output (Z), shown in Table 5.22. The inputs are written as a binary count starting at 0₁₀ and incrementing up to 7₁₀. The output Z is only a logic 1 when inputs A, B, and C are logic 0. This can be written as a Boolean expression

Table 5.22. Three-input logic circuit truth table: Z = NOT (A+B+C)

A	B	C	Z
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

$\text{Z}=\overline{\text{A}}\text{.}\overline{\text{B}}\text{.}\overline{\text{C}}$

Here, where the output Z is a logic 1, the values of inputs A, B, and C are ANDed together. Where a variable is a logic 1, then the variable is used. When the variable is a logic 0, then the inverse (NOT) of the variable is used. The expression identified for the truth table in Table 5.22 can be modified using rules and laws identified in Table 5.12:

$\text{Z}=\overline{\text{A}}\text{.}\overline{\text{B}}\text{.}\overline{\text{C}}$

$\text{Z}=\overline{\overline{\text{A}}\text{.}\overline{\text{B}}\text{.}\overline{\text{C}}}$

$\text{Z}=\overline{\overline{\overline{\text{A}}}\text{.}\overline{\overline{\text{B}}}\text{.}\overline{\overline{\text{C}}}}$

$\text{Z}=\overline{\text{A}+\text{B}+\text{C}}$

The original expression was manipulated by first double-inverting the expression (which logically makes no change), then breaking one of the inversions (the inversion closest in space to the variables) and changing the AND operator to an OR operator (the second De Morgan theorem). This leaves a NOR expression with double-inverted variables. The double-inversion on each input is then dropped.

Now, combining the operations in Table 5.21 and Table 5.22 produces a more complex operation as shown in Table 5.23.

Table 5.23. Three-input logic circuit truth table: complex logic gate

A	B	C	Z
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

The Boolean expression for this is:

$\text{Z}=(\text{A}\text{.B}\text{.C})+(\overline{\text{A}}+\overline{\text{B}}+\overline{\text{C}})$

Each of the ANDed expressions is ORed together. Parentheses group each expression to aid readability of the expression. In this form of expression, the first canonical form, a set of minterms (minimum terms) that are AND logical operators are created (one for each line of the truth table where the output is a logic 1). The outputs for each of the AND logical operators are ORed together. This is also referred to as a sum of products. A circuit schematic for this circuit is shown in Figure 5.12.

Figure 5.12. Circuit schematic for Boolean expression in Table 5.23

The second canonical form is an alternative to the first canonical form. In the second, a set of maxterms that are OR logical operators on the variables within the expression are created (one for each line of the truth table where the output is a logic 0). The outputs for each of the OR logical operators are ANDed together. This is also referred to as a product of sums.

Using these approaches, any Boolean logic expression can be described, analyzed, and possibly minimized.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780750683975000052

Combinational logic design principles

B. HOLDSWORTH BSc (Eng), MSc, FIEE , R.C. WOODS MA, DPhil , in Digital Logic Design (Fourth Edition), 2002

4.5 The NOR function

The NOR function is defined by the equation

$f=\overline{A+B}$

which, by using De Morgan's theorem, can be alternatively expressed as

$f=\overline{A}\cdot \overline{B}.$

The truth table is shown in Figure 4.7(a) and the conventional symbol used to represent the gate is shown in Figure 4.7(b). An examination of the truth table shows that if any one, or both, of the inputs are 1 the gate output is 0, while the output is only 1 provided both inputs are 0.

Figure 4.7. (a) Truth table for the NOR function (b) Conventional circuit symbol for a NOR gate (c) and (d) The NOR gate used as an inverter

If the input A of the gate is permanently connected to logic 0 level then clearly the output is given by

$f=\overline{(A+B)}=\overline{(0+B)}=\overline{B}$

so that the NOR gate is now acting as an inverter. This can also be observed directly from the truth table. The only relevant rows in the truth table are those enclosed by the dotted lines in Figure 4.7(a). An examination of these rows shows that if B = 0 then f = 1, and if B = 1 then f = 0. Another way of achieving logic inversion using a NOR gate is by connecting both inputs to the same logic level, whence if A = B then

$f=\overline{(A+B)}=\overline{(B+B)}=\overline{B}$

These two connections are illustrated in Figures 4.7(c) and (d).

As noted above in section 4.2, unused inputs to any gate must never be left 'floating' or unconnected. Unused NOR gate inputs are often connected to logic 0 level, usually achieved in practice simply by connecting the input directly to the ground (0V) of the digital logic circuit. Alternatively, unused inputs in a NOR gate can be connected to one of the used inputs, but again with the risk of reduced performance, as explained above in section 4.2.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780750645829500056

Boolean algebra

B. HOLDSWORTH BSc (Eng), MSc, FIEE , R.C. WOODS MA, DPhil , in Digital Logic Design (Fourth Edition), 2002

2.5 Truth tables

A truth table provides the basic method of describing a Boolean function. It contains a row for every combination of the variables and prescribes the value of the function (0 or 1) for each of these combinations. For the 3-variable function f(A, B, C) whose truth table appears in Figure 2.1, there are 2³ combinations and the value of the function for each of these combinations is listed in the right hand column. The Boolean function described by the truth table is provided by the logical sum of those combinations for which the function has a value of f = 1. Hence

Figure 2.1. Truth table for f = σ m₁,m₂,m₃,m₅

$f(A,B,C)=\overline{A}\overline{B}C+A\overline{B}C+\overline{A}BC+A\overline{B}C$

Each combination of the variables is called a minterm. For example, m ₁ = Ā $\overline{B}$ C and the function tabulated in Figure 2.1 can be described as a sum of minterms so that

$f=\sum m_1{m}_2{m}_3{m}_5$

Alternatively, a minterm can be identified by its subscript and the function can be defined by the following equation

$f=\sum 1,2,3,5$

A Boolean function expressed as a sum of minterms is termed the canonical sum-of-products form of the function.

The inverse function $\overline{f}$ is obtained by taking the logical sum of those combinations for which f = 0. From Figure 2.1

$\overline{f}=\overline{A}\overline{B}\overline{C}+A\overline{B}\overline{C}+AB\overline{C}+ABC$

and by inversion using the principle of duality

$f=(A+B+C)(\overline{A}+B+C)(\overline{A}+\overline{B}+C)(\overline{A}+\overline{B}+\overline{C})$

Each term in this equation is called a maxterm and the Boolean function is expressed as a product of maxterms. The resulting expression is called the canonical product-of-sums form of the function and it may be written as

$f=\prod M_0{M}_4{M}_6{M}_7$

and in terms of the maxterm subscripts the function may be written

$f=\prod 0,4,6,7$

The truth table representation of a Boolean function has strict limitations. The number of rows in the table for an n-variable function is 2 ⁿ and if n ≥ 5 the construction of the table is tedious, time consuming and prone to error. For this reason this method of representation is of little practical use to the circuit designer.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780750645829500032

A Survey on Zero-Knowledge Proofs

Li Feng , Bruce McMillin , in Advances in Computers, 2014

4.6 ZKP Sketch for SAT

The quadratic residuosity problem is the question of distinguishing by calculating the quadratic residues modulo n, where n is a composite number of two odd primes p and q. Under the assumption of quadratic residuosity that two states are computationally indistinguishable through the calculation of the quadratic residues modulo n, a protocol for satisfiability (SAT) is suggested that directly simulates a circuit that evaluates given instances of SAT [29].

The general technique in Ref. [18] is through the simulation of an arbitrary Boolean circuit without disclosing the inputs or any intermediary results. At the end of the protocol, if the final output of the circuit is 1, then the circuit is satisfiable, but nothing else.

Let u  = b ₁, b ₂,…, b_k be a k bit string of the prover. For each 1   ≤ i  ≤ k, let z_i and z′ _i be the two encryptions of b_i randomly chosen by the prover. It is easy for the prover to convince the verifier that the k bit strings encrypted by z ₁, z ₂,…, z_k and z′₁, z′₂,…, z′ _k are identical without providing the verifier with any additional information by the following string equality protocol.

Definition 2.11 (String Equality Protocol) For each i, 1   ≤ i  ≤ k, the prover gives the verifier some x _i   ∈ ℤ _⋉ ^⁎ (denoting the set of integers relatively prime to n between 1 and n  −   1) so that z _i z _i ^′  ≡ x _i ²(mod   n).

Definition 2.12 (Boolean Computation Protocol) Consider any Boolean function B : {0, 1} ^t   →   {0, 1} agreed upon between the prover and the verifier, and any bits b ₁, b ₂,…, b_t only known to the prover. For 1   ≤ i  ≤ t, let z_i be an encryption of b_i known to the verifier. Let b  = B (b ₁, b ₂,…, b_t ). The prover produces an encryption z for b and convinces the verifier that z encrypts the correct bit without giving the verifier any information on the input bits b ₁, b ₂,…, b_t nor on the result b.

A permuted truth table for the Boolean function B is introduced here, which is a binary string of length (t  +   1)2 ^t formed of 2 ^t blocks of t  +   1 bits. The last bit of each block is the value of B on the other t bits of the block. Let s be the number of permutations agreed upon between the prover and the verifier:

1.

P: The prover randomly chooses s permuted truth tables for B and discloses encryptions for each of them.

2.

V: The verifier selects a random subset X  ⊆   {1, 2,…, s} and sends it to the prover as a challenge.

3.

P: The prover chooses one of the following options based on the request from the verifier:

•

For each j ∈ X, the prover opens the entire encryption of the jth permuted truth table.

•

For each j ∉ X, the prover points to the appropriate block in the encryption of the jth permuted truth table and uses the following string equality protocol to convince the verifier that z ₁, z ₂,…, z_tz encrypts the same bit string as this block.

4.

V: The verifier makes the following verifications:

•

The verifier checks if it is a valid truth table for B.

•

The verifier checks if z ₁, z ₂,…, z_tz encrypts the same bit string.

Figure 2.10 illustrates the ZKP for Boolean computation.

Figure 2.10. ZKP for Boolean computation

Based on the above discussions, a ZKP sketch has been designed for SAT. f : {0, 1} ^k   →   {0, 1} is the function computed by some satisfiable Boolean formula for which the prover knows that there is an assignment b ₁, b ₂,…, b_k ∈ {0, 1} so that f (b ₁, b ₂,…, b_k )   =   1. Assume that the Boolean formula is given using arbitrary unary and binary Boolean operators. The prover will produce encryptions z ₁, z ₂,…, z_k of b ₁, b ₂,…, b_k . Then, the prover will guide the verifier through the encrypted evaluation of the formula, using the Boolean computation protocol, one Boolean operator at a time. The result will be a z which is the encryption for the value of f (b ₁, b ₂,…, b_k ). Then, the prover opens z and shows the verifier that it encrypts a 1.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128001615000025

Digital Electronic Circuits

David J. Comer , Donald T. Comer , in Encyclopedia of Physical Science and Technology (Third Edition), 2003

III.A.2.a The NOR gate

A truth table is often used to specify the output of a logic gate for all possible combinations of input signals. The truth table for a two-input NOR gate is

$\begin{array}{cccc}\hfill \mathbf{A}& \hfill \mathbf{B}\hfill & \mathbf{X}\hfill & \\ \hfill 0& \hfill 0\hfill & 1\hfill & \\ \hfill 0& \hfill 1\hfill & 1\hfill & \\ \hfill 1& \hfill 0\hfill & 1\hfill & \\ \hfill 1& \hfill 1\hfill & 0\hfill & \end{array}$

When either input is a logic 1, the output will be 0. The only combination of inputs that results in an output of 1 is A  =   0 and B  =   0.

The two-input NOR gate can be implemented in CMOS as shown in Fig. 12. The general logic symbol for the NOR gate is also indicated in this figure. The small circle at the output represents an inversion following the OR gate to create the NOR gate.

FIGURE 12. (a) Two-input CMOS NOR gate. (b) Symbol for the NOR gate.

When both inputs are at 0   V or logic 0, both nMOS devices are off and both pMOS devices are on. This input condition leads to 0-V gate-to-source voltages for both M1 and M2 and -3-V gate-to-source voltages for M3 and M4. The output voltage will be very near 3   V or logic 1. Typical values of on resistance and off resistance are 10   kΩ and 200   MΩ, respectively.

When one or both inputs switch to logic 1 or 3   V, at least one nMOS device turns on while at least one pMOS device turns off. In either case, a very high resistance exists between the power supply voltage and output and a very low resistance exists between output and ground. This forces the output to be at 0   V or logic 0.

The NOR gate can be extended to a higher number of inputs by adding a complementary pair of devices for each additional input. The additional pMOS device is placed in series with the other pMOS devices and the additional nMOS device is placed in parallel with the other nMOS devices.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B0122274105001769

Combinational logic circuits

John Crowe , Barrie Hayes-Gill , in Introduction to Digital Electronics, 1998

4.1.3 Encoders

These are the opposite of decoders in that they convert a single active signal (out of r inputs) into a coded binary, s-bit, output (this would be referred to as an r-line-to-s-line encoder). Often encoders are of a type called priority encoders which means that more than one of the r inputs may be active, in which case the output pattern produced is that for the highest priority input.

Encoders have a less general form than multiplexers and demultiplexers, being specifically designed for the required task. Their usual form is of s combinational circuits (e. g. AND-OR design), with r inputs.

Example 4.5

Write out the truth table for the 4-line-to-2-line encoder that takes a four-line decimal signal and converts it to binary code. Design, and draw, the circuit to implement this encoder.

Solution

The required truth table is shown in Table 4.4. This truth table is incomplete since it has four input columns but only four rows. However, we know that for all of the input combinations not given we need A=0 and B=0. So we can pick out the fundamental sum of product terms for A and B directly from the truth table to give:

Table 4.4. Truth table for a 4-line decimal-to-binary encoder as discussed in Example 4.5

	Decimal				Binary
	0	1	2	3	A	B
0	1	0	0	0	0	0
1	0	1	0	0	0	1
2	0	0	1	0	1	0
3	0	0	0	1	1	1

$\begin{array}{l}A=\overline{0}\overline{1}2\overline{3}+\overline{0}\overline{1}\overline{2}3\\ B=\overline{0}1\overline{2}\overline{3}+\overline{0}\overline{1}\overline{2}3\end{array}$

The circuit is shown in Fig. 4.10.

Fig. 4.10. Circuit that implements the truth table shown in Table 4.4, discussed in Example 4.5

As with decoders, encoders are often used in an active-LOW input and/or output form.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978034064570350006X

Boolean algebra

Mary Attenborough , in Mathematics for Electrical Engineering and Computing, 2003

Example 4.4

Show, using truth tables, that for any propositions p, q, r

$(p\wedge q)\wedge r=p\wedge (q\wedge r)$

Solution The truth tables are given in Table 4.2. Note that there are eight lines in the truth table in order to represent all the possible states (T, F) for the three variables p, q, and r. As each can be either TRUE or FALSE, in total there are 2³ = 8 possibilities. To find (p ∧ q) ∧ r, p ∧ q is performed first and the result of that is ANDed with r. To find p ∧ (q ∧ r) then q ∧ r is performed first and p is ANDed with the result. As the resulting columns are equal we can conclude that

Table 4.2. A truth table to show (p ⋀ q) ⋀ r ⇔ p ⋀ (q ⋀ r). The fifth column gives the truth values of (p ⋀ q) ⋀ r and the seventh column gives the truth value of p ⋀ (q ⋀ r). As the two columns are the same we can conclude that (p ⋀ q) ⋀ r ⇔ p ⋀ (q ⋀ r)

p	q	r	p ⋀ q	(p ⋀ q)⋀ r	q ⋀ r	p ⋀ (q⋀ r)
T	T	T	T	T	T	T
T	T	F	T	F	F	F
T	F	T	F	F	F	F
T	F	F	F	F	F	F
F	T	T	F	F	T	F
F	T	F	F	F	F	F
F	F	T	F	F	F	F
F	F	F	F	F	F	F

$(p\wedge q)\wedge r\iff p\wedge (q\wedge r)$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780750658553500309

Circuit Complexity

Raymond Greenlaw , H. James Hoover , in Fundamentals of the Theory of Computation: Principles and Practice, 1998

9.2 The Boolean Circuit Model of Computation

An example of a Boolean circuit is provided in Figure 9.1. Circuit inputs are placed in boxes, and gates (excluding inputs) are represented by circles. A Boolean circuit is an acyclic, directed graph in which the edges carry unidirectional logical signals and the vertices compute elementary logical functions. The entire graph computes a Boolean function from the inputs to the outputs in the expected way (described formally below).

Figure 9.1. A sample boolean circuit.

The Boolean circuit shown in Figure 9.1 has five types of gates: id (i), and (∧), or (∨), not (¬), and implies (⇒). Let's examine the properties of these types of gates with the aid of truth tables . The most straightforward gate is the id gate. We show its truth table in Table 9.1 with input x ₁. An id gate can be thought of as simply passing on its input unchanged.

Table 9.1. The truth table for the id gate with input x ₁.

The truth table for a not gate with input x ₁ is depicted in Table 9.2. A not gate simply negates its input value.

Table 9.2. The truth table for a not gate with input x ₁.

The truth table for an or gate with inputs x ₁ and x ₂ is depicted in Table 9.3. An or gate evaluates to true ² if and only if at least one of its inputs is true.

Table 9.3. The truth table for an or gate with inputs x ₁ and x ₂.

The truth table for an and gate with inputs x ₁ and x ₂ is depicted in Table 9.4. An and gate evaluates to true if and only if both of its inputs are true.

Table 9.4. The truth table for an and gate with inputs x ₁ and x ₂.

x 1	x 2	x 1 and x 2
0	0	0
0	1	0
1	0	0
1	1	1

The truth table for an implies gate with inputs x ₁ and x ₂ is depicted in Table 9.5. implies is true if and only if its antecedent is true or its consequent is false.

Table 9.5. The truth table for an implies gate with inputs x ₁ and x ₂.

x 1	x 2	x 1 implies x 2
0	0	1
0	1	1
1	0	0
1	1	1

In the Boolean circuit shown in Figure 9.1, suppose x ₁ = 0, x ₂ = 1, and x ₃ = 1. Under these conditions, the implies gate evaluates to 1 (see Table 9.5). The value 1computed by the implies gate is passed on to the and gate having label y ₁. The other input of this and gate is x ₂ = 1. Therefore, the and gate evaluates to true. The or gate has two 1-inputs and so evaluates to true. The not gate receives a 1 as input and so outputs a 0. The id gate labeled y ₂ just passes on its input so it outputs a 0. The basic ideas of how a Boolean circuit computes should now be clear.

We have defined a number of gate types. In general, gates can be arbitrary Boolean functions of their inputs. If a gate has k inputs, it belongs to the set of k-ary Boolean functions B_k = {ƒ | ƒ: {0, l} ^k → {0,1}}. As is common practice (and in agreement with the presentation thus far), we refer informally to such functions by symbols like "1," "0," "¬," "∧," and "∨," among others. For the sake of readability and to expose you to a variety of common notations, we will also use "not," "and," "or," and other descriptive words (again as above). A list of some common gates and their corresponding symbols is provided in Table 9.6.

Table 9.6. Some common gates and their symbolic representations.

Name of Gate	Symbol
and	∧
id	i
implies	⇒
nand	¬∧
nor	¬∨
not	¬
input	x i
or	∨

Let's explain how the or function fits into the Boolean function terminology just presented. It is easy to see that or ∈ B ₂, since or : {0, l}² → {0,1} is defined by or((0, 0)) = 0, or((0, 1)) = 1, or((1, 0)) = 1, and or((1, 1)) = 1, as is shown in Table 9.3. Other gate types fit into this scheme in an analogous manner. This notation helps us simplify the formal definition of a Boolean circuit.

Conceptually, a Boolean circuit is simply a collection of interconnected gates, whose input values propagate towards the outputs, computing according to the functions of the gates. More precisely, we have the following definition.

Definition 9.2.1

A Boolean circuit α is a labeled finite oriented directed acyclic graph Each vertex v has a type τ, ³ where

$\tau (v)\in \left\{\text{INPUT}\right\}\cup B_0\cup B_1\cup B_2$

The indegree (or outdegree) of a vertex is the number of incoming (or, respectively, outgoing) edges. A vertex v with τ(v) = input has indegree 0 and is called an input. The inputs of α are given by a tuple (x ₁, …, x_n ) of distinct vertices. A vertex v with outdegree 0 is called an output. The outputs of α are given by a tuple (y ₁, …, y_m ) of distinct venices. A vertex v with τ (v) ∈ B_i must have indegree i. Each vertex is called a gate.

Note that fanin, which is defined as the indegree of a gate, is less than or equal to two, but fanout, which is defined as the outdegree of a gate, is unrestricted. We say the fanout is unbounded in this case. Circuit inputs, elements of type input, are also considered gates. Inputs can also be outputs, as shown in Figure 9.1. The circuit depicted there has inputs x ₁, x ₂, and x ₃, and outputs y ₁, y ₂, and y ₃, where x ₃ = y ₃. Input x ₂ has outdegree four and thus fanout four. Gate y ₂ has indegree one and thus fanin one.

Each circuit computes a function of its input bits as follows:

Definition 9.2.2

A Boolean circuit α with inputs (x ₁, …, x_n ) and outputs (y ₁, …, y_m ) computes a function ƒ : {0, 1} ⁿ → {0, l} ^m in the following way: input x_i , 1 ≤ i ≤ n, is assigned a value v(x_i ) from {0,1} representing the ith bit of the argument to the function. ⁴ Every other vertex v is assigned a value v(v) ∈ {0,1} obtained by applying τ(v) to the value(s) of the vertices incoming to v. The value of the function is the tuple (v(y ₁), …, v(y_m )), in which output y_j , 1 ≤ j ≤ m, contributes the jth bit of the output.

Let's apply this definition to the Boolean circuit shown in Figure 9.1. Suppose v (x ₁) = 0, v(x ₂) = 1, and v(x ₃) = 0. Then v(y ₁) = 1, v(y ₂) = 0, and v(y ₃) = 0. For example, using Tables 9.5 and 9.4, 0 ⇒ 1 = 1 and 1 ∧ 1 = 1, so v(y ₁) = 1. Sometimes we will be less precise (as we were originally) and drop the v. That is, we simply say that the inputs are x ₁ = 0, x ₂ = 1, and x ₃ = 0. If ƒ is the function computed by the circuit of Figure 9.1, then ƒ((0, 1, 0)) = (1, 0, 0). In this example n = m = 3.

Unlike the computational models we have considered so far, individual circuits have a fixed number of input bits and so cannot handle arbitrary-length inputs (a capability even posessed by DFAs). So we need a circuit for each given length of input that we want to process. For this reason, we have to produce, communicate, and manipulate circuit descriptions. Although there are different ways of describing circuits, there are a handful of common representations, of which the most common is called the standard encoding.

Definition 9.2.3

The standard encoding $\tilde{\alpha }$ of a circuit α is a string from {0,1}* grouped into a sequence of four tuples (v, g, l, r), one tuple for each vertex of α, followed by two sequences of vertex numbers 〈〈x ₁, …, x _n 〉〉 and 〈〈y ₁, …, y _m 〉〉. Within the encoding, the vertices of α are uniquely (but arbitrarily) numbered in the range from one up to the number of gates in the circuit. The tuple (v, g, l, r) describes a vertex, numbered v, and its oriented connections to other vertices as follows. Vertex number v has gate type g, where

$g\in \left\{\text{INPUT}\right\}\cup B_0\cup B_1\cup B_2$

The left (or right) input to v, if any, is numbered l (or, respectively, r). The vertex number of the ith input, 1 ≤ i ≤ n,is given byx _i, and that of the jth output, 1 ≤ j ≤ m, is given by y_j .

The main points of this definition are that circuit descriptions are simple objects to generate and manipulate, and they are compact. Figure 10.7 in Chapter 10 shows a circuit where the gates of the circuit have been arbitrarily numbered from one to six. A standard encoding of the circuit based on this numbering at a high level is

Note that this description can be converted to a binary string using the techniques of Section 2.5, although for ease of presentation we have described it as a string over the alphabet consisting of parentheses, comma, decimal digits, and the like. As is customary we state all encodings at a high level. You can convert them into bit strings using the methods described in Section 2.5. We ask for such conversions in the exercises.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9781558605473500133

PCAP Extractor and OS Fingerprinting

Chet Hosmer , in Python Passive Network Mapping, 2015

Truth Table Python Class

To handle the processing of the truth table, I create a simple class that will perform three basic functions:

1.

Load the truth table and process the range values

2.

Accept a known set (TTL, TOS, DF and Window Size) as input and return the first matching OS Fingerprint from the loaded truth table.

3.

Print the truth table for convenience and verification

Now that we can load and process the truth table, all that is left to do is build a menu driven script that can:

1.

Load a previously generated .osDict file

2.

Load and process and user defined truth table

3.

Generate the OS fingerprint results

In addition, I have provided similar support functions as with the P2NMAP-Analyze script to allow directing the output to a file, along with the ability to print the contents of the .osDict observations and the truth table contents.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128027219000053

Design a 2-bit Greater-than Circuit Using Gate-level Logical Operators Only

Source: https://www.sciencedirect.com/topics/computer-science/truth-table

Share this post