Logic

0.1 - Introduction

"Contrariwise," continued Tweedledee, "if it was so, it might be; and if it were so, it would be; but as it isn't, it ain't. That's logic." from Alice Through the Looking Glass by Lewis Carroll

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:

In the 17th century Gottfried Leibniz, at the age of 20, worked on devising "a general method in which all the truths of reason would be reduced to a kind calculation." Leibniz' grand scheme became a bit complicated when he tried to reduce everything to numbers. Significant progress was not made until the mid-1800's when George Boole expressed logic as an algebra system which today we call Boolean algebra. In an algebra system, there are two components of interest --- objects and operations on those objects. In the ordinary algebra one studies in high school, the objects of interest are numbers that have values (such as 5 or 1.4) and the operations on those numbers are addition, multiplication, and negation (and a few others). In Boolean algebra the objects of interest are statements that have values of either true or false and the operations on those statements are and (conjunction), or (disjunction), and not (negation). Formally, a statement (or proposition) is a declarative sentence that is either true or false (but not both simultaneously). The following are examples of statements:
  1. John von Neumann wrote an important paper describing the main ideas in the design of a computer.
  2. Charles Babbage was born in 1962.
  3. The temperature is 85 degrees at the Roanoke Airport.
  4. There is a quiz in CPSC 101 today.
  5. There exists a real number x such that x + 2 = x.
  6. There exists a real number x such that x + 2 = 5.
Note that in the above the first statement is true (always) and the second statement is false (always). The third and fourth statements are sometimes true and sometimes false, depending on the day (and time). Similarly the last statement is always true (x = 3 works), yet statement #5 is always false (no matter what x is, x + 2 does not equal x). Statements that are always true are called tautologies and statements that are always false are called contradictions.

The following are examples of sentences that are not statements according to our definition. What is wrong with each? (The last one is tricky!)

0.2 - Logical Connectives (Operators in Boolean Algebra)

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).

Logic Symbols

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)

0.2.1 - Logic in Python

Python has a primitive data type named boolean with values of True or False and has operators and, or, and not.

Boolean (Logical) Operator Math Symbol Python Operator
AND
and
OR
or
NOT
not

The logic statements in Python are conditions (Boolean expressions) that appear in conditional statements (such as if statements).

Examples:

1.  if (age >= 65 or age < 12):
	ticketPrice = 10;
     else:
	ticketPrice = 15;

2. if (keepGoing and guesss != answer):        # keepGoing is a boolean variable
          ... do whatever

0.3 Truth Tables

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

0.3.1 - 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.

  1. p ≡ ∼(∼p)
  2. p ∧ ∼p ≡ F
  3. ∼(∼p ∧ q) ≡ p ∨ ∼q
  4. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
In each case construct the truth table for each statement. In parts a. and b. there is only one simple statement p so the table needs only two rows.

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.)

  1. ∼(p ∨ q) ; ∼p ∨ ∼q
  2. p ∧ (q ∨ r) ; (p ∧ q) ∨ r

0.4 - Laws of Logic (Boolean Algebra)

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 ∨ TT

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 ∧ FF

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
TF

FT

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.

0.4.1 - 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

  1. Let p represent the statement "Jack went up the hill" and q represent "Jill went up the hill." Write each of the following statements in symbolic form.
    1. Jack and Jill went up the hill.
    2. Jack went up the hill but Jill didn't.
    3. Neither Jack nor Jill went up the hill.
    4. Jack went up the hill or Jill went up the hill (or both).
    5. It is not true that Jack and Jill went up the hill.
    6. If Jack went up the hill, then Jill did not go up the hill.

  2. Construct a truth table for each of the following statements. Identify any tautologies or contradictions.
    1. ∼(p ∨ ∼q)
    2. (∼p ∧ q) ∨ ∼q
    3. ∼(∼p ∧ q) ∨ (∼q ∨ q)
    4. ∼p ∧ (q ∨ ∼r)
    5. (p ∧ ∼r) ∧ (∼q ∨ r)
    6. ∼[(∼p ∧ ∼r) ∧ (∼q ∨ r)]

  3. Construct truth tables to show that...
    1. DeMorgan's laws hold.
    2. the distributive laws hold.
    3. the adsorption laws hold.

  4. Determine which of the following pairs of statements are logically equivalent.
    1. (p ∨ q) ∧ r; p ∨ (q ∧ r)
    2. ∼(∼p ∧ ∼q); p ∨ q
    3. ∼(∼p ∧ ∼q); p ∧ q (use some of your work from part b.)
    4. ∼(∼(p ∧ q) ∨ p); ∼p ∨ q
    5. ∼(∼(p ∧ q) ∨ p); F (use your work from part d.)
    6. p ∧ ( ∼(∼p ∨ q) ∨ (∼p ∧ q)); p ∧ ∼q

  5. Use the laws of logic to simplify each of the following statements.
    1. ∼ (∼p ∧ q)
    2. p ∨ (∼p ∧ q)
    3. ∼ [ ∼p ∧ (∼p ∧ q) ]
    4. p ∨ ∼(q ∧ ∼r)
    5. (p ∧ q ∧ ∼r) ∨ (p ∧ q ∧ r)

  6. Use the laws of logic to verify the equivalences you found in #5.

  7. Suppose age is a variable of type int, answer is a String variable, and discountCard is a Boolean variable. Write each of the following statements in correct Java syntax.
    1. age is between 18 and 21 (inclusive)
    2. age is less than 18 but greater than 10
    3. age is greater than 40 or less than 20
    4. answer is neither "Yes" nor "No
    5. discountCard is true or age is greater than 25 and answer is "Yes"
    6. age is greater than 21 and either discountCard is true or answer is "No"

  8. Write the negation of each of the Java Boolean expressions in #7 (using Java syntax and NOT just putting a ! in front of the expression).