Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic
  1. Propositions
  2. Modeling Logic with Truth Tables
  3. Logical Equivalence
  4. The Laws of Logic
  5. Application: Switching Networks
  6. Logical Implications
  7. Propositions with Variables
  8. Quantifiers
  9. Logic with Quantified Statements
  10. Nested Quantifiers
  11. Application: Logic Puzzles
  12. A Primer on Fuzzy Logic
  1. Mathematical Logic with Maple
  2. Defining Propositions with Maple
Arguments and Proof
  1. The Structure of Basic Arguments
  2. Rules of Inference
  3. Using the Rules of Inference
  4. Logically Equivalent Arguments
  5. Invalid Arguments
  6. Universal Specification
  7. Universal Generalization
  8. Axioms, Definitions, Theorems, and Proofs
  9. Proof Technique: Direct Proofs
  10. Proof Technique: Indirect Proofs
  11. Proof Technique: Contradiction
  12. Mistakes in Proofs
  13. Proof Technique: Equivalence
  1. Verifying Mathematical Arguments in Maple
Set Theory
  1. Sets
  2. Subsets
  3. Proof Technique: Element Arguments
  4. A Set of Operations on Sets
  5. The Laws of Set Theory
  6. Proof Technique: Exhaustion
  1. Set Theory in Maple

Modeling Logic with Truth Tables

As can be seen on the previous page, having to write out all logical expressions in English and keeping track of truth values can be tedious and burdensome. It also makes it difficult to evaluate the truth value of compound statements involving many propositions and logical connectives.

In analyzing a compound statement’s truth value, we need to be able to evaluate it for all combinations of truth values for it’s constituent parts. Without any organization, this can be quite error-prone. For example, in analyzing the relatively simple compound statement p ∧ q, we have four cases to check: p is false and q is false, p is false and q is true, p is true and q is false, and finally p is true and q is true. Without any systematic way of dealing with each case, mistakes are easy to make.

Organizing Logical Expressions

The first thing we can do to make things easy on ourselves is to simplify logical values. Up to now, propositions were evaluated as “true” or “false”. We can save ourselves a bit of writing by making the following substitutions:

0 can be used in place of “false”
1 can be used in place of “true”

What this allows us to do is express propositions (either primitive or compound) using numerical values. For example, if proposition p evaluates to “true”, we can also say that p evaluates to 1. Therefore, we can say that ¬p evaluates to “false”, or equivalently, we can say that ¬p evaluates to 0. Of course, the equals sign = can also be used. Thus, if we know that p = 1, then we’d have that ¬p = 0.

Next, we can organize groups of propositions into tables, and record the truth value of each proposition in a cell of that table. Such tables are called truth tables. In these types of tables, the first row is used to label each column with a proposition. Each row of these tables is used to record the numerical value of the propositions used in their respective columns.

Example 1.2.1

Suppose we want to evaluate the truth value for the proposition ¬p ∨ q when p is true and q is false, and when p is false and q is true. Note that this is a compound proposition made up of propositions ¬p and q connected by a conjunction. Furthermore, ¬p is the negation of proposition p.

We want to keep track of the values of p, q, ¬p, and ¬p ∨ q, so our table needs four columns. Next, we only want to evaluate these propositions at two sets of values: one where p is true and q is false, and one where p is false and q is true. So our table needs three rows (one row for recording the propositions being tracked in the table.) We’ll throw in two more rows just so we can capture all possible assignments of p and q.

We start by constructing our table as follows, where only the values of p and q are given initially. Remember, we can use 0 in place of “false”, and 1 in place of “true”.

pq¬p¬p ∨ q
00
01
10
11

Next, let’s examine the cell colored green in the next table.

pq¬p¬p ∨ q
00
01
10
11

The green cell is in the ¬p column, so that’s the expression being evaluated by the green cell. The given values for p and q in this row are p = 1 and q = 0. Based on how negation is defined that means that ¬p = 0. So, we fill in a 0 for the green cell.

pq¬p¬p ∨ q
00
01
100
11

Next, let’s focus on the next cell marked in green.

pq¬p¬p ∨ q
00
01
100
11

This cell is in the ¬p ∨ q column, so that is the expression being evaluated by this cell. In this row, the value of ¬p is 0, and the value of q is 0 as well. By definition of disjunction, we have that ¬p ∨ q = 0. We fill in this green cell with the number 0.

pq¬p¬p ∨ q
00
01
1000
11

We can fill out the second row of this truth table following the same basic procedure. In the second row of the ¬p column, since p = 0, we have that ¬p = 1. In the second row of the ¬p ∨ q column, since ¬p = 1 and q = 1, we have that ¬p ∨ q = 1.

pq¬p¬p ∨ q
00
0111
1000
11

We take the same approach for filling out the first and fourth row to complete the truth table.

pq¬p¬p ∨ q
0011
0111
1000
1101

Revisiting the Logical Connectives

We can use truth tables to evaluate the logical connectives talked about previously.

Negation is a very simple logical operation that depends on only one proposition.

p¬p
01
10

Conjunction and disjunction (and and inclusive-or) act on two propositions, so we’ll need four rows to examine all possible combinations of truth values.

pqp ∧ q
000
010
100
111
pqp ∨ q
000
011
101
111

Next up, we also have the exclusive-or. Not quite as common as other logical connectives, but still simple enough.

pqp ⊻ q
000
011
101
110

Finally, we have the logical implications.

pqp → q
001
011
100
111
pqp ↔ q
001
010
100
111

We can also collect all of this information in one larger truth table.

pq¬pp ∧ qp ∨ qp ⊻ qp → qp ↔ q
00100011
01101110
10001100
11011011

Tautologies and Contradictions

Using the previous logical connectives, let’s examine an interesting example.

Example 1.2.2

Consider the following truth table.

pqp ∨ qp → (p ∨ q)
00
01
10
11

We start by filling out the p ∨ q column:

pqp ∨ qp → (p ∨ q)
000
011
101
111

Now, based on how logical implication → works, we fill out the last column:

pqp ∨ qp → (p ∨ q)
0001
0111
1011
1111

The last column consists entirely of 1s. So, no matter, what p and q evaluate to, whether they are simple or compound, it appears that p → (p ∨ q) is always true.

If we translate this to English, we get

“If p, then p or q”.

Of course if we start with p, then we always get p regardless if q is true or false. Thus, this statement should always evaluate to true, which is what we just observed.

Keep in mind that, in our example, we evaluated the associated proposition for every possible combination of values for p and q. In other words, no matter what p and q are, the expression always evaluates to 1.

We could run into the opposite situation where every value in a column evaluates to 0.

Example 1.2.3

Consider the following truth table:

pq¬p¬p ∧ qp ∧ (¬p ∧ q)
00
01
10
11

The third and fourth columns are relatively easy to evaluate. The last column doesn’t require too much work either. The complete table looks like the following:

pq¬p¬p ∧ qp ∧ (¬p ∧ q)
00100
01110
10000
11000

Notice that in the last column, every value is 0, meaning for all possible values of p and q, the expression p ∧ (¬p ∧ q) always evaluates to 0.

This should make sense. How can we have both p and ¬p? Suppose p represents the statement “The sun is shining”. Then ¬p represents the statement “The sun is not shining”. This means that ¬p ∧ p represents the statement “The sun is not shining, and the sun is shining” or perhaps equivalently “The sun is simultaneously not shining and shining”.

Such a statement is nonsensical. As such, any compound proposition that is made up of p and ¬p in a conjunction is probably impossible to be true. Depending on how complicated a logical expression is, the overall proposition may still evaluate to true, but care should be taken, especially when parts of that large proposition contains these kinds of constituent propositions.

For example, the proposition

q ∨ (p ∧ ¬p)

will evaluate to 1 when q = 1, even though the proposition (p ∧ ¬p) is contained within the larger proposition q ∨ (p ∧ ¬p).

We have special names for these kinds of situations.

Tautology, Contradiction

A compound statement is called a tautology if it is true for all possible truth value assignments for its component statements. The symbol T0 is commonly used to represent tautological statements.

A compound statement is called a contradiction if it is false for all possible truth value assignments for its component statements. The symbol F0 is commonly used to represent contradictory statements.

Satisfiability

Truth tables allow us to quickly determine whether or not for a given compound proposition, there are values for its constituent propositions that yield a value of 1 or 0.

Satisfiable, Unsatisfiable

A compound proposition is called satisfiable if there exists values of its constituent propositions that result in the compound proposition having a truth value of 1.

Otherwise, that compound statement is called unsatisfiable.

In order to be satisfiable, a compound statement has to have a truth value of 1 for at least one combination of truth values for its constituent parts. This means that in its truth table, there is at least one 1 in its column.

Notice that if a compound statement is a contradiction, then there will be no 1s in its column in a truth table. This means it is unsatisfiable. Otherwise, if a compound statement is not a contradiction, then there is at least one 1 in its column in a truth table.

In effect, this means that contradictions are unsatisfiable, while non-contradictions are satisfiable.

Notice that this definition says nothing about primitive propositions. That’s because either that primitive proposition is true or false. It doesn’t depend on other propositions, and so trying to test combinations of truth value assignments for those non-existent propositions would be meaningless.

Example 1.2.4

We can construct truth tables for compound propositions made up of three smaller propositions. These truth tables will require 8 rows for each value assignment.

Consider the following truth table:

pqrp ∨ q(p ∨ q) ∧ r
000
001
010
011
100
101
110
111

The last two columns are relatively simple, so completing this table won’t be too much of a hassle.

pqrp ∨ q(p ∨ q) ∧ r
00000
00100
01010
01111
10010
10111
11010
11111

Here, there are only three cases where (p ∨ q) ∧ r can be made true. One such case is when p = 1, q = 0, and r = 1. Thus, the expression (p ∨ q) ∧ r is satisfiable.

Example 1.2.5

Let’s take another look at the truth table from Example 1.2.2:

pqp ∨ qp → (p ∨ q)
0001
0111
1011
1111

In this case, we have that p → (p ∨ q) is a tautology. Every combination of values for p and q yield a truth value of 1. The expression p → (p ∨ q) is thus satisfiable.

Example 1.2.6

Let’s take another look at a slightly different truth table than what is presented in Example 1.2.3:

pq¬pp ∧ q¬p ∧ (p ∧ q)
00100
01100
10000
11010

Here, we have that ¬p ∧ (p ∧ q) = F0. This compound statement is not satisfiable.