Example 1: Inputs: $A$ , $B$ , $C$ . Output: To agree with the majority of $A$ , $B$ , and $C$ . Devices available: two-input OR, two-input AND. One solution is $((A\wedge B)\vee(A\wedge C))\vee(B\wedge C)$ , which uses five devices and has a delay of 3. But a better solution is $(A\wedge(B\vee C))\vee(B\wedge C)$ , which uses four devices and has the same delay.

If all three devices are $\wedge$ then, regardless of their inputs and positions, the result is $T$ iff all inputs are $T$ . Hence, this does not work. Similarly, using $\vee$ only results in $T$ iff at least one input is $T$ , which still does not work. Now, the tree of the circuit has three vertices corresponding to devices. The top vertex has to be one of them. It has two child vertices. There are two possible cases.

First case is where both child vertices are devices themselves. Now, similar to the text, consider the table of $T,F$ -values corresponding to the requirements ($F$ ’s are omitted):

	$A$	$\neg A$
$B$	$T$		$\neg C$
$B$	$T$	$T$	$C$
$\neg B$	$T$		$C$
$\neg B$			$\neg C$

Note that each child device can take as its inputs sentence symbols only, as we are trying to use three devices only. Depending on whether it is a $\wedge$ or $\vee$ device, it can return $T$ either in two cells corresponding to the truth values of both of its parameters (e.g. $A\wedge B$ returns $T$ in the top two cells of the first column), or in six cells corresponding to the truth values of at least one of its parameters.

$A\wedge B$	$A$	$\neg A$			$A\vee B$	$A$	$\neg A$
$B$	$T$		$\neg C$		$B$	$T$	$\times$	$\neg C$
$B$	$T$	$\cdot$	$C$		$B$	$T$	$T$	$C$
$\neg B$	$\cdot$		$C$		$\neg B$	$T$		$C$
$\neg B$			$\neg C$		$\neg B$	$\times$		$\neg C$

$A\wedge C$	$A$	$\neg A$			$A\vee C$	$A$	$\neg A$
$B$	$\cdot$		$\neg C$		$B$	$T$		$\neg C$
$B$	$T$	$\cdot$	$C$		$B$	$T$	$T$	$C$
$\neg B$	$T$		$C$		$\neg B$	$T$	$\times$	$C$
$\neg B$			$\neg C$		$\neg B$	$\times$		$\neg C$

$B\wedge C$	$A$	$\neg A$			$B\vee C$	$A$	$\neg A$
$B$	$\cdot$		$\neg C$		$B$	$T$	$\times$	$\neg C$
$B$	$T$	$T$	$C$		$B$	$T$	$T$	$C$
$\neg B$	$\cdot$		$C$		$\neg B$	$T$	$\times$	$C$
$\neg B$			$\neg C$		$\neg B$			$\neg C$

By $\cdot$ we marked those cells that need to be added in each case (they have value $F$ , while the pattern we need has $T$ ), and by $\times$ those that need to be removed (vice versa). The top device takes either intersection or union of two of these patterns. Looking at these patterns we conclude that there is no way to combine two of them, so that their intersection or union is what we need. For example, if one child device is $\wedge$ , wlog $A\wedge B$ , then the pattern misses two cells, so that the top device should be $\vee$ , but there is no other pattern having both missing cells that would not have anything extra that we do not need. Similarly, if a child device is $\vee$ , wlog $A\vee B$ , then the pattern has two extra cells, meaning that the top device should be $\wedge$ , but then the other child device should be $\vee$ as well, but the intersection of any two $\vee$ -patterns has five cells.

The second case is where the top device has one child vertex being a device and the other being an input. Here are patterns for sentence symbols and their negations.

$A$

$A$

$\neg A$

$B$

$A$

$\neg A$

$C$

$A$

$\neg A$

$B$

$T$

$\neg C$

$B$

$T$

$\times$

$\neg C$

$B$

$\cdot$

$\neg C$

$B$

$T$

$\cdot$

$C$

$B$

$T$

$T$

$C$

$B$

$T$

$T$

$C$

$\neg B$

$T$

$C$

$\neg B$

$\cdot$

$C$

$\neg B$

$T$

$\times$

$C$

$\neg B$

$\times$

$\neg C$

$\neg B$

$\neg C$

$\neg B$

$\neg C$

$\neg A$

$A$

$\neg A$

$\neg B$

$A$

$\neg A$

$\neg C$

$A$

$\neg A$

$B$

$\cdot$

$\times$

$\neg C$

$B$

$\cdot$

$\neg C$

$B$

$T$

$\times$

$\neg C$

$B$

$\cdot$

$T$

$C$

$B$

$\cdot$

$\cdot$

$C$

$B$

$\cdot$

$\cdot$

$C$

$\neg B$

$\cdot$

$\times$

$C$

$\neg B$

$T$

$\times$

$C$

$\neg B$

$\cdot$

$C$

$\neg B$

$\times$

$\neg C$

$\neg B$

$\times$

$\times$

$\neg C$

$\neg B$

$\times$

$\times$

$\neg C$

Since each pattern has one or more extra cells, the top device should be $\wedge$ . At the same time, there is at least one missing cell in each pattern, so that the top device should be $\vee$ . In other words, it is not enough to just apply $\wedge$ or $\vee$ to a sentence symbol or its negation and some other formula to obtain what we need. For example, $A\vee\alpha$ implies $T$ whenever $A$ is true, regardless of the values assigned to $B$ and $C$ (we have the extra cell corresponding to $A\wedge\neg B\wedge\neg C$ ). Similarly, $A\wedge\alpha$ requires $A$ to be true, regardless of the values assigned to $B$ and $C$ (we have the missing cell corresponding to $\neg A\wedge B\wedge C$ ).