B)' = A' 
B'
and (A B)' = A' B'
Parentheses should be used when combining multiple compound statements together with connectives. If parentheses are omitted, the following order of operation should be assumed: biconditional (highest), conditional, conjunction/disjunction and negation (lowest).
We have already seen in lesson one the relationship between union (disjunction) and or as well as intersection (conjunction) and and. Here we will also introduce various symbols used when drawing logic diagrams, give truth tables in two different forms for a few other common operator, and explore how and and or are similar to switches in series and parallel circuits.
|
|
|
|
(similar to union). | is also often used for or.
Be very careful when programming since conventions vary widely
between programming language!
Languages such as C and C++ introduce additional confusion
by differentiating between bitwise (operating on each bit in a string)
and logical operators (only treating the value as zero or not zero).Augustus DeMorgan's (1806-1871) major contribution to mathematics was his reforming logic and establishing symbolism for algebra. He was the one to define and introduce mathematical induction, which up to that point was still unclear. One major result known as DeMorgan's Law can be summarized as below.
|
DeMorgan's Law
(A B)' = A' B'
and (A B)' = A' B'
|
This is often equivalently stated using ^ and
and overhead lines for nots (instead of primes for the complementary set).
The major author debugged a significant number of COBOL
programs by checking logic of this form.
Around the same time, George Boole (1815-1864) was also establishing logic symbolism. Boolean Algebra, which is a foundation for computers, is an algebra of sets with the operators of union and intersection. Equivalently it is an algebra with the numbers 0 and 1 and operators of and and or. More details are available in lesson 13.
As noted above, truth tables appear in two basic forms: 1) as multiplication or addition style tables; and 2) as an exhaustive list of possible values. Take a moment and compare these truth tables with those obtained in homework 2 regarding the addition and multiplication of even numbers. Then, compare the format below with the earlier format in this lesson.
| p | q | ~p | ~q | p^q | p|q | p eor q | p=>q | p<=>q | p nand q | p nor q | p neor q | p and ~p | p or ~p |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
Often in a truth table the symbol T for true is used for 1 and the symbol F for false is used for 0.
Note how neor and the biconditional are the same.
| Another common name for the biconditional is equivalence. |
|
If a proposition contains only 1's (T's) in the last
column of its truth table, it is a tautology. (See p or ~p in the table above.) |
|
If a proposition contains only 0's (F's) in the last
column of its truth table, it is a contradiction. (See p and ~p in the table above.) |
An argument is valid if it has good logical structure, otherwise it is invalid. An argument is sound if and only if it is valid and has true premises, otherwise it is unsound. One also uses the following terms to identify statement requirements in A implies B: necessary: (B cannot be true unless A is true, or sufficient: A cannot be true unless B is true. A fallacy uses a false premise, invalid reasoning, or vague/ambiguous language. One also calls a set of statements either inconsistent if they lead to a contradiction or consistent if not. A set of statements is complete if one can determine for any combination of statements a result (i.e. prove it) or else incomplete. Kurt Gödel in 1931 showed that no complete system that admits the natural numbers (Peano axioms) can be consistent, which is now known as Gödel Incompleteness Theorem. Thus any useful logical system must either be inconsistent or incomplete. This derailed attempts to axiomize all of mathematics.
| If a proposition contains both 1's and 0's (T's and F's) in the last column of its truth table, it is a contingency. |
Forming truth tables like this is a common way to compare the validity of two different statements. Actually, few of the 16 possible combinations of 0's and 1's are missing in the table above. A former teacher of the major author added a let operator to complete the list—those were his initials!
| 
| 
|
Given below are the corresponding symbols for ands, and ors. An and-gate is equivalent to a series circuit as illustrated in the diagram below right, whereas an or-gate is equivalent to a parallel circuit also illustrated below right.
| 
|
| 
|
|
|
|
| 
|
 |
|
| Basic TTL nor gate | Nand-gate Set-Reset flip-flop |
Today, complex microprocessors utilizing millions even billions of logic gates are routinely etched onto silicon chips. However, these basic logic gates composed of several transistors (invented in 1947) are still an important part of the fundamental design. These logic gates are built up into more complex structures such as flip-flops, memory elements, [shift] registers, counters, decoders, multiplexors, adders, etc. Often many such microprocessors are etched at the same time on one big silicon wafer. The Pentium 4 by INTEL now running at speeds of up to 3.73GHz! demonstrate amazing technological progress.
Some computers of the 1960's and 1970's (SDS/Xerox Sigma) were documented using logic equations. A typical logic equation might read as shown below left. (This can be interpret to say that the negation of the signal representing the family of read/write direct instructions (hexadecimal operation codes .6C or .6D) is generated by the upper nibble being a 6 and the lower nibble being .C (lowest order bit being ignored). Here, hex is indicated by the leading period.) A logic diagram is also shown below right. Note how in diagram form this takes up additional space and uses graphic symbols. The logic equation format is very compact and was easily printed using 60's technology.
| NFARWD=I . OU6.(O4.O5.NO6) |  |
| BACK | HOMEWORK | ACTIVITY | CONTINUE |
|---|