SKEDSOFT

Logic Puzzles
Puzzles that can be solved using logical reasoning are known as logic puzzles. Solving logic puzzles is an excellent way to practice working with the rules of logic. Also, computer programs designed to carry out logical reasoning often use well-known logic puzzles to illustrate their capabilities. Many people enjoy solving logic puzzles, published in periodicals, books, and on theWeb, as a recreational activity.

Logic Circuits: Propositional logic can be applied to the design of computer hardware. This was first observed in 1938 by Claude Shannon in his MIT master’s thesis. In Chapter 12 we will study this topic in depth. (See that chapter for a biography of Shannon.) We give a brief introduction to this application here.
A logic circuit (or digital circuit) receives input signals p1, p2, . . . , pn, each a bit [either 0 (off) or 1 (on)], and produces output signals s1, s2, . . . , sn, each a bit. In this section we will restrict our attention to logic circuits with a single output signal; in general, digital circuits may have multiple outputs.

Complicated digital circuits can be constructed from three basic circuits, called gates, shown in Figure 1. The inverter, or NOT gate, takes an input bit p, and produces as output ¬p. The OR gate takes two input signals p and q, each a bit, and produces as output the signal p ∨ q. Finally, the AND gate takes two input signals p and q, each a bit, and produces as output the signal p ∧ q.We use combinations of these three basic gates to build more complicated circuits, such as that shown in Figure 2.