Chapter 16
Notes for the fourth week: symbolic logic

Notes also available as PDF.

16.1 Language of logic

Goals:

We start with definitions:

logical statement
A declaration that is either true or false but not both. For example:

Today is Monday.

Languages contain many statements and declarations that are not logical statements:

Symbolic logic is fun.

While that is a declaration, it is neither true nor false in general. An example of a logical statement from set theory,

x ∈ A.

negation
A logical statement over the same topics that is false if the original statement is true or true if the original is false. The statement

My dog has fleas.

has as its negation

My dog does not have fleas.

However, a statement about my cat(s) cannot be a negation of either of the above regardless of which statements are true or false.

quantifier
When a statement applies to all, some, every of something, the statement is quantified. The word denoting how many is the quantifier. This is where negation becomes tricky. For example, the statement

All dogs have fleas.

has as its negation

Some dogs do not have fleas.

Its negation is not

All dogs do not have fleas.

16.2 Symbolic logic

Expressing logical statements with symbols lets us focus on manipulating the logic itself. We can talk about the dog having fleas without mentioning dogs or fleas.

Variables like p and q can take the values true or false. Like many items, true and false are given different symbols by different authors. Common symbols include

true false
T F
1 0
\mathop{⊤}

I will use 1 and 0.

16.3 Logical operators and truth tables

The first operator is negation. This is a unary operation; it applies to a single operand. Two symbols are commonly used for the negation operator, \mathop{} and ~, as is adding a bar to a variable, \overline{p}. I will stick with the symbol \mathop{} for most cases.

With one operand, listing all possible inputs and outputs is simple. The list is also called a truth table. The truth table for \mathop{} is as follows:

p\mathop{}p
1 0
0 1

Programming languages may represent \mathop{} with operators or functions like !, not(), .NOT., not.

When and joins pieces of a logical statement, we understand that the statement as a whole it true only if both pieces are true. This is the conjunction operator. The conjunction operator is the symbol we use to represent the same idea. The truth table for the operator has four lines and is as follows:

pqp ∧ q
1 1 1
1 0 0
0 1 0
0 0 0

The and operator sometimes is written as multiplication, or just pq. Most often, that is paired with using a bar for negation, so p ∧\mathop{}q is written p\overline{q}. This is common notation in electrical engineering. Occasionally the negation will be written as q'. Programming languages may represent with operators or functions like &&, and(), .AND., and.

The English word or, however, has quite a few different meanings. Sometimes we mean the logical exclusive-or, where one choice rules out the other, and sometimes we mean logical or, where both choices are possible.

In symbolic logic, the disjunction operator, , is the latter type of or. The disjunction is true when either sub-clause is true:

pqp ∨ q
1 1 1
1 0 1
0 1 1
0 0 0

In electrical engineering, or often is represented by +, so p ∨\mathop{}q would be written p + \overline{q}. Programming languages may represent with operators or functions like ||, or(), .OR., or.

The exclusive-or operator, which we will denote , is true whenever exactly one operand is true:

pqp ⊕ q
1 1 0
1 0 1
0 1 1
0 0 0

Mathematically, the symbol for the exclusive-or operator is not particularly standardized. The symbol sometimes appears, as does the operator \mathop{xor}\nolimits . We will expand on the notation once we discuss addition of binary numbers.

Note that often is not considered a core operator. We can write p ⊕ q as (p ∨ q)\mathop{}(p ∧ q).

Programming languages rarely provide logical operators, although they often provide exclusive-or operators on the binary representations of integers. More on those in the next chapter. But if you notice, this is the negation of equality. So programming languages express the logical exclusive-or by negating the equality of two logical expressions.

In symbolic logic, equality of two logical statements is equivalence. When expressed as an operator, equivalence takes the symbols , , or . The reason for the arrow forms will become clear soon.

pqp ≡ q
1 1 1
1 0 0
0 1 0
0 0 1

Again, is not a core operator. p ≡ q is the same statement as (p ∧ q) ∨ (\mathop{}p ∧\mathop{}q).

Programming languages represent equality with ==, =, equal?, and many other forms.

A logical statement that always is true is a tautology. So p ∨\mathop{}p is a tautology:

The sky is periwinkle or the sky is not periwinkle.

Symbolically,

\mathrel{⊧}p ∨\mathop{}p.

A statement that always is false is a contradiction. Here p ∧\mathop{}p is an example:

The sky is blue and the sky is not blue.

A statement that is neither always true nor always false is logically contingent. So pq is contingent on the values of p and q.

We use the symbol for tautology, \mathrel{⊧}, to make certain equivalence statements unambiguous. Because we defined as an operator above, the plain statement

p ∨ q ≡ q ∨ p

appears contingent on its values. By adding \mathrel{⊧}, we make it clear that we are asserting that the statement is always true. To state that p ∨ q is the same as q ∨ p, we say

\mathrel{⊧}p ∨ q ≡ q ∨ p.

16.4 Properties of logical operators

Three properties from arithmetic also hold for the core logical operators and :

commutative
In language, and and or are commutative, or p and q is the same as q and p. Symbolically, \mathrel{⊧}p ∧ q ≡ q ∧ p and \mathrel{⊧}p ∨ q ≡ q ∨ p.
associative
Again, linguistically we don’t use parenthesis. Run-on statements are just as true or false as well-structured ones, so we expect and and or to be associative. We could build a large truth table to verify this, but for now let us just state that \mathrel{⊧}(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) and \mathrel{⊧}(p ∨ q) ∨ r ≡ p ∨ (q ∨ r).
distributive
As with sets, both operations distribute over the other. So p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).

As a demonstration of using a truth table to show equivalence,

pqrq ∨ rp ∧ (q ∨ r)p ∧ qp ∧ r(p ∧ q) ∨ (p ∧ r)
1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1
1 0 1 1 1 0 1 1
1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0

Which of these hold for and ? Over which operations may each be distributed?

16.5 Truth tables and logical expressions

16.5.1 De Morgan’s laws

As an example of truth tables and a demonstration of some very useful logical laws, we examine De Morgan’s laws.

In arithmetic, we know that - (1 + 2) = -1 + -2. Logical operations are similar to arithmetic, but not that similar.

We could reason about the two rules, but they serve as succinct examples of truth tables.

16.5.2 Logical expressions from truth tables

Say we are provided with a truth table showing all possible values for an unknown logical statement f(p,q). From that truth table, we can construct a logical statement equivalent to f(p,q).

Take:

pqf(p,q)
1 1 0
1 0 1
0 1 0
0 0 1

To construct f, we can combine all the true outputs with . The terms to be combined are the of all the variables. In each expression, each variable is negated to make its value true.

So in the above table, there are two true entries. One has p ≡ 1 and q ≡ 0, while the other has p ≡ 0 and q ≡ 0. The two corresponding -statements are p ∧\mathop{}q and \mathop{}p ∧\mathop{}q. So an equivalent statement is

\mathrel{⊧}f(p,q) ≡ (p ∧\mathop{}q) ∨ (\mathop{}p ∧\mathop{}q).

Alternately, we can list the false entries and combine their negations. This provides another equivalent statement,

\mathrel{⊧}f(p,q) ≡\mathop{}\left ((p ∧ q) ∨ (\mathop{}p ∧\mathop{}q)\right ).

We can use De Morgan’s laws to show these are the same:

\eqalignno{ \mathrel{⊧}\mathop{}((p ∧ q) ∨ (\mathop{}p ∧\mathop{}q)) & ≡\mathop{}(p ∧ q) ∧\mathop{}(\mathop{}p ∧\mathop{}q) & & \cr & ≡ (\mathop{}p ∨\mathop{}q) ∧ (p ∨ q) & & }

Neither of these are the simplest possible expression, but each is equivalent to f(p,q) and is constructed by a straight-forward recipe.

To simplify this expression, we use the distributive property and the fact that \mathrel{⊧}p ∨\mathop{}p,

\eqalignno{ \mathrel{⊧}f(p,q) & ≡ (p ∧\mathop{}q) ∨ (\mathop{}p ∧\mathop{}q) & & \cr & ≡ (p ∨\mathop{}p) ∧\mathop{}q & & \cr & ≡ 1 ∧\mathop{}q & & \cr & ≡\mathop{}q. & & }

There is another method for simplifying expressions which we will not cover. If you are interested in a more visual method for simplifying expressions over a few variables, look up Veitch charts or Karnaugh maps from electrical engineering. With those forms, you draw a 2-d truth table and cover the true values with boxes of area {2}^{k}. This mechanism is particularly useful when you have don’t care values, places where the output value does not matter.

16.6 Conditionals

16.6.1 English and the operator

One (compound) operator we have not mentioned so far is the conditional, the symbolic form of an if-then rule. A statement like

If the sky is blue, then it is not raining.

is translated to

\text{the sky is blue} →\text{it is not raining},

or p → q using only symbols. Here p is the antecedent and q is the consequent.

Many English statements are forms of conditionals. For example,

Many forms:

The two in bold are very important in mathematics and science because they are very, very common and often read incorrectly. Sufficient follows the arrow in p → q, and necessary works backward. We will see why when we examine the appropriate truth table.

Colloquially, we can refer to p as a premise or hypothesis and q as a conclusion. However, we will stop using those terms when we discuss logical deduction. Identifying p as a premise is useful for reasoning about p → q, but it introduces ambiguity when we consider as an operator. Just like with \mathrel{⊧} and , additional symbols provide the appropriate context.

16.6.2 Defining p → q

The truth table defining the conditional is slightly surprising:

pqp → q
1 1 1
1 0 0
0 1 1
0 0 1

The first and last lines are expected. When truth implies truth or falsity implies falsity, the statement as a whole is true.

The second line also is expected. A true premise implying a false conclusion renders the statement false.

Now comes the surprise. A false hypothesis implying a true conclusion renders the statement as a whole true! This is only surprising because we are looking at one line at a time. Consider the general case where the premise is false. If you start reasoning from a false hypothesis, what is the result? Anything. So any time p is false, the statement as a whole is true.

We can break the conditional operator into core operators by listing the single negated output and applying De Morgan’s laws:

\eqalignno{ \mathrel{⊧}p → q & ≡\mathop{}(p ∧\mathop{}q) & & \cr & ≡\mathop{}p ∨ q. & & }

So p → q is a true statement whenever the conclusion q is true or when we start from a false premise and \mathrel{≠}p is true.

16.6.3 Converse, inverse, and contrapositive

Considering a few rules from arithmetic, we see that is not commutative! The form q → p is the converse of p → q, but the two statements are not equivalent. Similarly, we cannot simply negate terms to obtain the negation, so \mathop{}(p → q) is not the same as the inverse \mathop{}p →\mathop{}q. There is one other form here that is equivalent. The contrapositive \mathop{}q →\mathop{}q is equivalent to p → q.

converse: inverse: contrapositive
pqp → qq → p\mathop{}p →\mathop{}q\mathop{}q →\mathop{}p
1 1 1 1 1 1
1 0 0 1 1 1
0 1 1 0 0 0
0 0 1 1 1 1

16.6.4 If and only if, or

One more form of the conditional is important because it is so frequently used, the phrase if and only if .

p if and only if q is a double conditional or biconditional. It means p → q ∧ q → p and is written symbolically as p ↔ q. In text, if and only if often is abbreviated as iff.

Looking at its truth table, we see that is the same as equivalence:

pqp → qq → pp ↔ q
1 1 1 1 1
1 0 0 1 0
0 1 1 0 0
0 0 1 1 1

Which symbol you use is a matter of preference and emphasis.

16.7 Quantifiers

We are interested in two quantifiers for logical statements: for all and there exists. These are universal and existential quantifiers, respectively. To demonstrate these, I’m going to switch to predicate logic. Here properties have parameters, and the quantifiers describe possible values for those parameters. There is a third common quantifier, the uniqueness quantifier, but we will not explore it.

Say Dexter has fleas (which he doesn’t). So far, we would simply associate this statement with a single variable. But to examine quantifiers, we need a bit more.

Let P(p) be the property of having fleas. This P(\text{Dexter}) is a (false) statement that Dexter has fleas. We can generalize this to state that \mathop{∃}p ∈ D : P(p) where D is the set of dogs. If p is Dexter, then P(p) would be stating that Dexter has fleas, so there does exist such a p. The colon ( :) is read as “such that” or “satisfies” and sometimes is replaced by a vertical bar | or the backwards epsilon-ish symbol .

But Dexter does not have fleas, so in reality \mathop{∃}p ∈ D : \mathop{}P(p). Because Dexter is a dog, we know not all dogs have fleas. So \mathop{∃}p ∈ D : \mathop{}P(p) is the same as \mathop{}\mathop{∀}p ∈ D : P(p).

Translating to and from English needs attention to detail. The word always does not always translate into \mathop{∀}. Some translations:

P(p) is always true. \mathop{∀}p : P(p).
P(p) is almost always true. \mathop{∃}p : \mathop{}P(p).
There always is some way for P(p) to be true.\mathop{∃}p : P(p)
Sometimes P(p). \mathop{∃}p : P(p).

And here are the reasons why we care about formalizing quantifiers in this class: Negation is tricky, and composing or nesting quantifiers is tricky.

16.7.1 Negating quantifiers

Symbolically, two rules apply:

Reading the first aloud,

Stating that not all p satisfy P(p) is the same as saying there exists some p that satisfies \mathop{}P(p).

And the second,

Stating that there does not exist a p such that P(p) is the same as saying that all p satisfy \mathop{}P(p).

16.7.2 Nesting quantifiers

One other item to note: Different quantifiers are not operators, hence you cannot assume they commute! Quantifiers nest. As an example, consider two statements:

All homework questions have been answered by at least one student.
Some student has answered all homework problems.

Translating the first (true) statement into a symbolic form gives

\mathop{∀}q ∈\text{questions}\kern 1.66702pt \mathop{∃}s ∈\text{students} : s\text{ answered }q.

The second (false) statement becomes

\mathop{∃}s ∈\text{students}\kern 1.66702pt \mathop{∀}q ∈\text{questions} : s\text{ answered }q.

The symbolic versions appear similar. The only difference is the order of the quantifiers. But the statements obviously have very different meanings.

The text gives a nice visual interpretation in Section 3.5 using diagrams akin to Venn diagrams from set theory. Here we consider a more syntactic approach.

Given the English and logic statements:

All homework questions have been answered by at least one student.
\mathop{∀}q ∈\text{questions}\kern 1.66702pt \mathop{∃}s ∈\text{students} : s\text{ answered }q.

You can read the latter as the former, or as

For all questions, there is some student who has answered that question.

Which student is meant depends on which question is considered.

Now consider the other statement:

Some student has answered all homework problems.
\mathop{∃}s ∈\text{students}\kern 1.66702pt \mathop{∀}q ∈\text{questions} : s\text{ answered }q.

Here the questions answered depends on which student is considered. And this statement says that one student has answered all questions.

For a more formal example, you read \mathop{∀}p ∈ {J}^{+}\mathop{∃}q ∈ {J}^{+} : p < q as

For all positive integers p there exists a positive integer q such that p > q.

The particular q depends on the p. There is not be a single q that works for all positive integers p. This statement is true over the integers.

Swapping the quantified statements produces a false statement. The translation of \mathop{∃}q ∈ {J}^{+}\mathop{∀}p ∈ {J}^{+} : p < q is

There exists a positive integer q such that for all positive integers p, p < q.

There is no such integer, as q = q and thus q≮q.

So we cannot simply swap quantifiers.

16.7.3 Combining nesting with negation

How do we negate the following true and equivalent English and logic statements?

All homework questions have been answered by at least one person.
\mathop{∀}q ∈\text{questions}\kern 1.66702pt \mathop{∃}s ∈\text{students} : s\text{ answered }q.

Consider working symbolically with the rules we already established:

\eqalignno{ \mathop{}(\mathop{∀}q ∈ &\text{questions}\kern 1.66702pt \mathop{∃}s ∈\text{students} : s\text{ answered }q) & & \cr & ≡\mathop{∃}q ∈\text{questions}\kern 1.66702pt \mathop{}(\mathop{∃}s ∈\text{students} : s\text{ answered }q) & & \cr & ≡\mathop{∃}q ∈\text{questions}\kern 1.66702pt \mathop{∀}s ∈\text{students} : \mathop{}(s\text{ answered }q) & & \cr & ≡\mathop{∃}q ∈\text{questions}\kern 1.66702pt \mathop{∀}s ∈\text{students} : s\text{ has not answered }q. & & }

So the negation is

There exists a question such that for all students the student has not answered the question.

Equivalently,

There is some question where no student has answered that question.

Is this the same as just sticking a not in front of the original sentence?

Not all homework questions have been answered by at least one person.

In this case, yes. But the other statement is not as simple.

Now consider the other statement:

Some student has answered all homework problems.
\mathop{∃}s ∈\text{students}\kern 1.66702pt \mathop{∀}q ∈\text{questions} : s\text{ answered }q.

Does the statement

Not some student has answered all homework problems.

mean anything? Not really. So how can we negate this statement correctly?

Work with the symbolic form. Then

\eqalignno{ \mathrel{⊧}\mathop{}(\mathop{∃}s ∈ &\text{students}\kern 1.66702pt \mathop{∀}q ∈\text{questions} : s\text{ answered }q) & & \cr & ≡\mathop{∀}s ∈\text{students}\kern 1.66702pt \mathop{}(\mathop{∀}q ∈\text{questions} : s\text{ answered }q) & & \cr & ≡\mathop{∀}s ∈\text{students}\kern 1.66702pt \mathop{∃}q ∈\text{questions} : \mathop{}(s\text{ answered }q) & & \cr & ≡\mathop{∀}s ∈\text{students}\kern 1.66702pt \mathop{∃}q ∈\text{questions} : s\text{ has not answered }q. & & }

So a correct negation is

For all students, there is some question that student did not answer.

16.8 Logical deduction: Delayed until after the test

Now that we have if-then statements, we can speak more about logical deduction. And the simplest level, we can chain operators to show deduction. But then we end up with statements like \left ((p → q) ∧ (q → r) ∧\mathop{}r\right ) →\left ((p → r) ∧\mathop{}r\right ) → p. These become unreadable quickly.

Instead, we introduce new symbols. The above could be written as p → q,q → r,\mathop{}r ⊢ p → r,\mathop{}r ⊢ p. Taking up more room but being more clear, we can write the logical argument or logical deduction as

p → q
q → r
\mathop{}r
⊢ p → r
\mathop{}r
⊢\mathop{}p

The general form in one line: Premise 1, premise 2 conclusion. In table form,

Premise 1
Premise 2
Conclusion.

Both are read as assuming premise one and premise two, infer the conclusion or premise one and premise two entail the conclusion.

The symbol is syntactic sugar meant to place emphasis where important. p ⊢ q is the same as ⊢ p → q or just p → q, but the former implies a deduction while the latter appears to be just a statement.

Sometimes three dots, , is used instead of . And sometimes (as in the text) neither appears in the tabular form. However, symbolic logic is about removing ambiguity that comes from language. Using the symbol helps disambiguate valid logical arguments from examples of invalid arguments or fallacies.

When reasoning about reasoning itself, the set of premises in a rule often are represented by Γ, so Γ ⊢ q is a rule with a set of premises Γ leading to a single result q.

Some forms or structures of logical arguments have classical names. These names came long before the symbolic form.

Modus ponens
p → q,p ⊢ q, or

p → q
p
⊢ q
Modus tollens
p → q,\mathop{}q ⊢\mathop{}p, or

p → q
\mathop{}q
⊢\mathop{}p
Disjunctive syllogism
p ∨ q,\mathop{}p ⊢ q, or

p ∨ q
\mathop{}p
⊢ q
Hypothetical syllogism
(also called transitivity) p → q,q → r ⊢ p → r, or

p → q
q → r
⊢ p → r

We also can write De Morgan’s laws as laws of deduction, for example \mathop{}(p ∨ q) ⊢\mathop{}p ∧\mathop{}q, or

\mathop{}(p ∨ q)
⊢\mathop{}p ∧\mathop{}q .

Much of the reason why we care about the correct rules of deduction is to highlight incorrect rules, or logical fallacies. A list of a few common fallacies follows. Note that we include a symbol after the line in the tabular form; the negation of implication, , lets you know we are talking about fallacies. The text does not use any symbol, so you may end up seeing these fallacies as valid.

Fallacy of the converse
Given p → q and q, we cannot deduce p. Symbolically, p → q,q ⊬ p or

p → q
q
⊬ p .
Fallacy of the inverse
Given p → q and \mathop{}p, we cannot deduce \mathop{}q. Symbolically, p → q,\mathop{}p ⊬ \mathop{}q or

p → q
\mathop{}p
⊬ \mathop{}q .
Fallacy of the alternative disjunct
Given p ∨ q and p, we cannot deduce \mathop{}q. Symbolically, p ∨ q,p ⊬ \mathop{}q or

p ∨ q
p
⊬ \mathop{}q .

With the exclusive-or operator , we can conclude that only one disjunct is chosen. But the or operator allows both to occur at once.