5''. A statement is an assertion that can be determined to be true or false. The
truth value of a statement is T if it is true and F if it is false. For example,
the statement ``2 + 3 = 5'' has truth value T. Statements that involve one or more of the connectives
``and'', ``or'', ``not'', ``if ... then'' and `` ... if and only if ... '' are compound
statements (otherwise they are simple statements). For example, ``It is not the case that 2 + 3 = 5'' is the negation
of the statement above. Of course, it is stated more simply as ``2 + 3 5''.
In symbolic logic, we often use letters, such as p, q and r to represent statements and the following symbols to represent the connectives.
Note that the connective ``or'' in logic is used in the inclusive sense (not the exclusive sense as in English). Thus, the logical statement ``It is raining or the sun is shining '' means it is raining, or the sun is shining or it is raining and the sun is shining.
If p is the statement ``The wall is red'' and q is the statement ``The lamp is on'', then 
is the statement
``The wall is red or the lamp is on (or both)'' whereas 
is the statement ``If the lamp is on then the wall is red''. The statement
translates
to ``The wall isn't red and the lamp is on''.
Statements given symbolically have easy translations into English but it should be noted that there are several
ways to write a statement in English. For example, with the examples above, the statement 
directly translates as ``If the wall is red
then the lamp is on''. It can also be stated as ``The wall is red only if the lamp is on'' or ``The lamp is on
if the wall is red''. Similarly, 
directly translates as ``The wall is red and the lamp is not on'' but it would be preferable to say
``The wall is red but the the lamp is off''.
|
|
|
We cannot construct any more than 16 truth tables involving two statements. This is because such a truth table
has 4 rows and the truth value of each row is T or F.
However, we can certainly construct more than 16 statements involving two statements. What happens is that many
(in fact infinitely many) statements have identical truth tables.
 |
 |
 |
 |
Logic gates and logic circuits are associated with mathematical logic, which is the study of the computations that can be done with the logical values true and false and with the logical operators and, or, and not. This association comes about when we think of ON as representing true and OFF as representing false. In that case, AND, OR, and NOT gates do the same computations as the operators and, or, and not.
Mathematical logic uses Boolean algebra, in which the letters A, B, C, and so on, are used to represent logical values. Letters are combined using the logical operators and, or, and not. For example,
(A and C) or (B and (not C))
is an expression of Boolean algebra. As soon as the letters in an expression are assigned values true or false, the value of the entire expression can be computed.
Every expression of boolean algebra corresponds to a logic circuit. The letters used in the expression are represented by the Inputs to the circuit. Each wire in the circuit represents some part of the expression. A gate takes the values from its input wires and combines them with the appropriate word -- and, or, or not -- to produce the label on its output wire. The final output of the whole circuit represents the expression as a whole. For example, consider the sample circuit from the applet. If the inputs are labeled A and B, then the wires in the circuit can be labeled as follows:
The "4-Bit Adder" circuit is an example of a logic circuit that can work with binary numbers. Circuits can work with binary numbers as soon as you think of ON as representing the binary value 1 (one) and OFF as representing the value 0 (zero). The "4-Bit Adder" can add two 4-bit binary numbers to give a five digit result. Here are some examples of adding 4-bit binary numbers:
1011 1111 1111 1010 0111 0001
0110 0001 1111 0101 1010 0011
----- ----- ----- ----- ----- -----
10001 10000 11110 01111 10001 00100
The answer has 5 bits because there can be a carry from the left-most column. Each of the four "Adder" circuits in the "4-Bit Adder" handles one of the columns in the sum. You should test the "4-Bit Adder" to see that it gets the right answers for the above sums. The two four-bit numbers that are to be added are put on the eight Inputs at the top of "4-Bit Adder". The sum appears on the outputs at the bottom, with the fifth bit -- the final carry -- appearing on the output on the right. You should observe that it takes some time after you set the inputs for the circuits to perform its computations.