Logic in the ordinary sense of the word deals with reasoning and Lewis Carroll took great delight in playing with the reasoning process of his characters in the Alice books. Interestingly this reasoning process has been formalized in a mathematical system and is the basis for the circuits of a computer.
The idea of building computer circuits based on logic was one of major importance in the development of computers; it helped expand the computer from a machine that could only do arithmetic and process numbers to one that can meaningfully process any type of information. The two state nature of formal logic was a natural match for the two state electronic circuitry of a computer. The mathematicians and philosophers who first sought to formalize logic had no idea it would find such a practical use in computers. In fact, when logic is studied in philosophy and mathematics courses most of the time is spent on symbolic forms of arguments and on valid forms of reasoning. In a computer science course the goal is to apply logic to the design of computer circuits although logical reasoning is also an important aspect of writing algorithms and programs.
The idea of formalizing reasoning and casting the reasoning process in mathematical and symbolic terms has fascinated many thinkers throughout the ages. Aristotle, in around 400 B.C., was one of the first to try. Aristotle's main contribution was to notice, and categorize, a few correct patterns of argumentation. He dealt primarily with syllogisms -- arguments consisting of a major premise, a minor premise, and a conclusion. One of the most famous of his syllogisms is:
The following are examples of sentences that are not statements according to our definition. What is wrong with each? (The last one is tricky!)
The operators in Boolean algebra correspond to the words we use in English to connect simple sentences to form more complex ones. We call these operators logical connectives. The logical connectives that we will use as logic operators in our study of logic are and, or, and not; however there are many more in English (such as but, neither...nor, if...then, only if).
Mathematics tends to express all ideas using some symbol system and logic is no different. We will use lowercase letters such as p, q, and r to denote statements. We will use the letter T to denote true and the letter F to denote false. The symbol ∼ (or ¬) denotes not (the negation operator), the symbol ∧ denotes and (the conjunction operator), and the symbol ∨ denotes or (the disjunction operator). A script T (T) will denote a tautology and a script F (F) will denote a contradiction. Parentheses (and other forms of brackets such as square brackets) are used to group symbols when needed.
Example Suppose we let p denote the statement "Logic is interesting" and let q denote the statement "Logic is easy." Then, we can write each of the following compound statements symbolically using the logic operators.
| Statement | Symbolic Form | |
| Logic is not interesting. | ∼p | |
| Logic is interesting and easy. | p ∧ q | |
| Logic is easy or interesting. | p ∨ q | |
| Logic is interesting but not easy | p ∧ ∼q | |
| It is not true that logic is interesting and easy | ∼(p ∧ q) | |
| Logic is not interesting and it is not easy | ∼p ∧ ∼q | |
| Logic is neither interesting nor easy | ∼p ∨ ∼q | |
| Logic is not interesting or easy | ∼(p ∨ q) |
Logic in Java
Java has a primitive data type named boolean with values of true or false and has operators for and, or, and not.
| Boolean (Logical) Operator | Math Symbol | Java Operator |
| AND | ∧ | && |
| OR | ∨ | || |
| NOT | ∼ | ! |
The logic statements in Java are conditions (Boolean expressions) that appear in conditional statements (such as if statements) and loops (such as while statements).
Examples:
1. if (age >= 65 || age < 12)
ticketPrice = 10;
else
ticketPrice = 15;
2. while (keepGoing && guesss != answer) // keepGoing is a boolean variable
{
... do whatever
}
When we combine statements with logical connectives we are interested in determining the truth value of the combined statement in terms of the truth value of the simpler statements that form it. A truth table is a way of tabulating these truth values.
Truth Tables for the Basic Connectives NEGATION (Not): The negation ∼p (not p) is true when p is false and it is false when p is true. In a truth table we show this by listing on the left side the simple statement p with one row for each of its possible truth values (there are only two -- T and F). On the right side, in each row we list the corresponding truth value for ∼p.
| p | ∼p |
| T | F |
| F | T |
CONJUNCTION (And): If p and q are statements, then the conjunction of p and q, denoted p ∧ q (read "p and q"), is true when p and q are both true. Otherwise it is false. To show this in a truth table we make a column for each of the simple statements (one for p and one for q) on the left and a column for the conjunction on the right. The table must then have one row for each of the possible combinations of truth values of p and q (there are four possible combinations: both p and q could be true, p could be true and q false, p could be false and q true, or both could be false). For each row we list the corresponding truth value for the conjunction (there is only one case in which the conjunction is true -- when both p and q are true).
| p | q | p ∧ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
DISJUNCTION (Or): If p and q are two statements, then the disjunction of p and q, denoted p ∨ q (read "p or q"), is true when either p is true or q is true or both are true. Hence, the truth table for p q has four rows, one for each of the four possible combinations of truth values for the statements p and q, with the resulting truth value for "p or q" being true in every case except when both p and q are false.
| p | q | p ∨ q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
A note on the truth values of the disjunction p ∨ q: The truth value of a sentence with the English word "or" is ambiguous in the case that the two statements being combined are both true. Sometimes when we use the word or we mean an "exclusive or" -- one or the other of our statements is true, but not both. For example, "the meal comes with a baked potato or french fries" means you can choose a baked potato or french fries, but not both. Sometimes we mean an "inclusive or" --- the statement will be true when both of the simple statements are true. For example, "to pass this course you must have at least a 60 average or pass the final exam" means you will pass the course under either of these circumstances and clearly you would also pass if both circumstances were met. Neither mathematics nor computer science tolerates ambiguity well so we must make sure our definition of or is clear. In this course we will only use the inclusive or (denoted ∨) which gives a true whenever one or both of the statements being combined is true. There is also an exclusive or (denoted ∨) which is defined to be true when exactly one of the statements being combined is true (but false when both are true).
Truth Tables for Compound Statements Compound statements can be formed by combining statements with more than one connective. In earlier examples we had statements of the form: p ∧ ∼q, ∼(p ∨ q), etc. A truth table for a compound statement lists the simple statements in columns on the left with one row for each of the possible combinations of truth values of these statements. The final result is a column containing the truth value of the compound statement for each row (for each combination of truth values of the simple statements). There will usually be several other columns in which we "calculate" intermediate truth values using the basic truth values for not, and, and or. When there are several operators and statements to be combined we apply rules similar to those in algebra for combining statements (evaluate expressions in parentheses first; "not" is evaluated before "and" and "or" if there are no parentheses).
Example To construct a truth table for the statement p ∧ ∼q, we first set up a table containing the columns for p and q with the rows for their possible truth values. Next we compute the truth values for ∼q (because not is evaluated before and) and place them in a column (in row 1, q is T so ∼q is F, in row 2, q is F so ∼q is T, and so on). Now we combine the truth values of p with those of ∼q using the ∧ operator (in row 1, p is T and ∼q is F so p ∧ ∼q is F; in row 2, p is T and ∼q is T so p ∧ ∼q is T, ...). The result is as follows:
| p | q | ∼q | p ∧ ∼q |
| T | T | F | F |
| T | F | T | T |
| F | T | F | F |
| F | F | T | F |
The final column gives us the truth values for p ∧ ∼q for each possible combination of truth values of p and q (in row 1 where p and q are both T, p ∧ ∼q is F; in row 2 where p is T and q is F, p ∧ ∼q is T, ...).
Example To construct a truth table for the statement ∼(∼p ∨ q) we first compute the truth value of the statement inside the parentheses. To do this we need to compute ∼p, then combine the ∼p column with the q column using the ∨ (or) operator (note: we get F only when both ∼p and q are F). Finally we apply the negation operator to the column for ∼p ∨ q.
| p | q | ∼q | ∼p ∨ q | ∼(∼p ∨ q) |
| T | T | F | T | F |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | T | F |
Example To construct the truth table for the statement (p ∨ q) ∧ (p ∨ r) we need more rows because there are eight possible combinations of the truth values of the three simple statements p, q, and r (the cases are listed in the table below). In computing the truth values each of the expressions in parentheses must be computed first and then the results combined with "and" to get the final column.
| p | q | r | p ∨ q | p ∨ r | (p ∨ q) ∧ (p ∨ r) |
| T | T | T | T | T | T |
| T | T | F | T | T | T |
| T | F | T | T | T | T |
| T | F | F | T | T | T |
| F | T | T | T | T | T |
| F | T | F | T | F | F |
| F | F | T | F | T | F |
| F | F | F | F | F | F |
Example The following is the truth table for ∼(p ∧ ∼r) ∨ (q ∨ r). Note the order of calculation (the column for computing ∼r is omitted since it can be done in your head as you go): The parenthesized statement p ∧ ∼q is computed then it is negated then the other parenthesized statement is computed. The final step is to use "or" to connect ∼(p ∧ ∼r) with (q ∨ r).
| p | q | r | p ∧ ∼r | ∼(p ∧ ∼r) | q ∨ r | ∼(p ∧ ∼r) ∨ (q ∨ r) |
| T | T | T | F | T | T | T |
| T | T | F | T | F | T | T |
| T | F | T | F | T | T | T |
| T | F | F | T | F | F | F |
| F | T | T | F | T | T | T |
| F | T | F | F | T | T | T |
| F | F | T | F | T | T | T |
| F | F | F | F | T | F | T |
Logical Equivalences, Tautologies, and Contradictions Two statements are said to be logically equivalent if they have the same truth values; that is, in each possible case in the truth table (each row) the truth values of the two statements are the same. The symbol ≡ is used to denote equivalence.
Example Show that ∼(p ∨ q) ≡ ∼p ∧ ∼q.
We show this equivalence holds by constructing truth tables for each statement and observe that the truth values are the same. The following table shows the computations (to save space we can use the same table for both statements). Note that the columns for ∼(p ∨ q) and for ∼p ∧ ∼q are identical, hence the two statements are equivalent.
| p | q | p ∨ q | ∼(p ∨ q) | ∼p | ∼q | ∼p ∧ ∼q |
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Examples Show that the following equivalences hold.
| p | ∼p | ∼(∼p) | p ∧ ∼p |
| T | F | T | F |
| F | T | F | F |
Note that the columns for p and for ∼(∼p) are identical, hence the two statements are equivalent, and that the column for p ∧ ∼p has F in every position hence p ∧ ∼p is a contradiction (equivalent to F).
Constructing tables for parts c. and d. is left for the reader. For part c. you should get that both statements have truth values TTFT hence are equivalent. In part d. you should get that both statements have truth values TTTTTFFF (in fact the second statement was an example above).
Exercise Show that the following pairs of statements are not equivalent. (To do this you need to construct tables for each statement and show that they differ in at least one row.)
The laws of Boolean Algebra are the basic equivalences such as the equivalence p ∨ q ≡ q ∨ p. These laws can be used to verify more complicated equivalences similar to the way one uses laws of ordinary algebra to simplify equations. The following table shows the equivalences that constitute Boolean algebra. These are called the laws of logic. They can be proved by constructing truth tables.
| Law | Law Name | Intuitive Understanding |
| p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p |
Commutative | When combining two statements with either "and" or "or" the order of the statements doesn't matter -- "p or q" is the same as "q or p" |
| p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r |
Associative | When combining three statements with same operator (all "ands" or all "ors") the order in which the statements are combined doesn't matter (the first two can be combined first then combine the result with the last statement or the last two can be combined first and the result combined with the first statement) |
| p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
Distributive | This one applies when you have a statement with one "and" and one "or." Think of it as "multiplying through" in algebra -- a(b + c) = ab + ac. |
| p ∨ T ≡ T p ∧ T ≡ p |
Identity for T | A tautology combined with any other statement using an "or" always results in a tautology (is always true); a tautology combined with any other statement using an "and" will always have the same truth value as the other statement -- ie will be equivalent to the other statement. |
| p ∨ F ≡ p p ∧ F ≡ F |
Identity for F | A contradiction combined with any other statement using an "or" will have the same truth values as the other statement -- i.e. will be equivalent to the other statement; a contradiction combined with any other statement using an "and" will always be false, i.e. will be a contradiction. |
| p ∧ p ≡ p p ∨ p ≡ p |
Idempotence | A statement combined with itself with either "and" or "or" is equivalent to the statement -- "p and p" is the same as p; "p or p" is the same as p |
| p ∧ ∼p ≡ F p ∨ ∼p ≡ T | Negations | "p and not p" is a contradiction; "p or not p" is a tautology |
| ∼ T ≡ F ∼ F ≡ T |
Negations of T and F | The negation of a tautology is a contradiction; the negation of a contradiction is a tautology. |
| ∼(p ∧ q) ≡ ∼p ∨ ∼q ∼(p ∨ q) ≡ ∼p ∧ ∼q |
DeMorgan's Laws | The negation of an "and" statement is equivalent to negating each of the original statements and combining the result with an "or"; the negation of an "or" is equivalent to negating each of the two original statements and combining the result with an "and." |
| p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p |
Absorption | "p or (p and q)" is the same as p; that is, if you know p is true or you know p and q is true then you know p is true. "p and (p or q)" is the same as p; that is, if you know p is true and you know "p or q" is true then you know p is true. |
| ∼(∼p) ≡ p | Involution (Double Negative) | Two negations "cancel" each other. |
Using the Laws of Logic to Simplify Statements Laws of logic can be used to simplify logic statements in the same way that the laws of algebra are used to simplify algebraic expressions. The laws are used (preferably, one at a time so you can keep things straight!) to transform the original statement into an equivalent statement.
Examples
1. ∼(p ∨ ∼q) ≡ ∼p ∧ ∼(∼q) |
(DeMorgan's law is used first because this statement is a negation of an or statement) | ≡ ∼p ∧ q |
(Apply the double negative law) |
2. p ∧ (∼p ∨ q) ≡ (p ∧ ∼p) ∨ (p ∧ q) |
(The distributive property is applied because this statement has an "and" connected to an "or") |
≡ F ∨ (p ∧ q) |
(p and not p is always false -- negation law) |
≡ p ∧ q |
(a contradiction "or" another statement is equivalent to the other statement -- Identity for F) |
3. ∼(p ∨ ∼(p ∧ ∼q)) ≡ ∼p ∧ (p ∧ ∼q)) |
(Apply DeMorgan's law -- this is the negation of an or statement hence we negate each part -- the p and the ∼(p ∧ ∼q) --- and change the or to and. Note that the double negative law was also used on "not not (p ∧ ∼q)" to get p ∧ ∼q) |
≡ (∼p ∧ p) ∧ ∼q |
(Apply the associative law to regroup since both operators are and) |
≡ F ∧ ∼q |
(not p and p is always false-- Negation law) |
≡ F |
(a contradiction combined using and with another statement is always false -- Identity for F) |
(NOTE: Often there are several different orders in which the laws may be used. In example 3 we could start by applying DeMorgan's law to the expression ∼(p ∧ ∼q) inside the parentheses and work from there. The end result should be the same but the number of steps it takes to get there will differ.)
Exercises