6.1 Logical Statements and Operations

To begin our study of logic, we must first define our most basic unit, the statement; we'll consider whether specific statements are true or not, and we'll combine statements to form compound statements and ultimately arguments.

The following sentences are statements:

Notice that it doesn't matter for the definition whether we know if a statement is true or false; it simply has to be one or the other.

What, then, is not a statement? The following are a few examples:

The first is a command and the second is a question, neither of which have any claim to being true or false. It doesn't make sense to talk about truth values with them.

The third is an interesting one. At first, it looks like a statement, because it makes a claim; however, upon closer inspection, we see that it isn't either true or false. This is known as the liar's paradox: if it were true, it would be false, which would mean it is true, which would mean...

In this chapter, we will commonly represent statements with letters to shorten the amount we have to write. For instance, we might define $p$ We typically start with $p$ for proposition, another name for a statement and $q$ as

That way, if we want to combine these statements, we don't have to write them out over and over again; we can simply write $p$ and $q$ and save a lot of trouble.

In the coming sections, we'll spend a lot of time combining statements in various ways, and it can be easy to get lost in the notation and think of logic as some sort of abstract study of notation. Resist this temptation. Instead, always remember that the letters and symbols we use and manipulate are tied to simple statements like these examples. With every new operation we investigate, our goal is to not just focus on memorizing a list of symbols, but rather to understand why this operation makes sense.

Every time you use Google to search the Internet, the search engine turns to Boolean logic to narrow down the search results to give you what you're looking for, using key terms like "and," "or," and "not." Three basic Boolean operators:
1. And
2. Or
3. Not

For instance, if you searched for "Frederick," the search engine would pull up results that contain that word (like the city tourism website, the Wikipedia article on the city, maybe the article for Frederick Douglass, etc.). If you searched for "Frederick Community College," the search engine would look for pages that contain those three words; it would search for "Frederick" AND "Community" AND "College."

If instead you search for "Frederick Community $-$College," the search engine will search for pages that contain "Frederick" AND "Community" but NOT "College," so the FCC website will not be listed.

We can think of objects as belonging to sets; in this case, performing a search means looking for objects that belong to a specific list of sets. For instance, if you went to library and searched "History" AND "Fiction," you would find all the books that belong both to the History set and to the Fiction set (i.e. historical fiction).

As it turns out, we can deal with logic using either statements or sets. When working with statements, Boolean logic combines multiple statements that are either true or false into a compound statement that is either true or false. When working with sets, Boolean logic combines sets, and a search is considered "true" when it returns an object in that combination of sets.

We can draw similar diagrams for the other two basic Boolean operations. For instance, if we searched for "History" OR "Fiction," the search would return any books that are either historical or fiction, or both.

This is what is called the inclusive OR; it includes all values in the first set, plus all values in the second set, plus all values in the overlap. There is also an exclusive OR operation (that we won't consider) that includes all values in the first set and all values in the second set, but not the values in the overlap. It is equivalent to saying "Either history or fiction, but not both."

The inclusive OR is like the following question at a restaurant: "Would you like fries or a drink with that?" It is perfectly acceptable to respond "Both, please."

Finally, if we searched for NOT "Fiction," the search would return everything in the database except for those labeled "Fiction." For obvious reasons, Google gives an error if you only search for NOT something

Diagrams like these will helpful to visualize combining statements using these three operations.

We can use these same three operators with statements; instead of thinking of objects belonging to sets, we'll think about whether statements are true or false.

For instance, consider the following two statements.

Clearly, $p$ is true and $q$ is false. What about $p$ AND $q$? In words, this would be the compound statement "Greece belongs to the European Union, and Tokyo is in Iran."

In this example, the fact that $q$ is false makes the compound statement break down; just because the first half is true isn't enough.

On the other hand, what if we wrote "Greece belongs to the European Union or Tokyo is in Iran"? In this case, the fact that the first half is true is enough to satisfy the compound statement.

Therefore, $p$ OR $q$ is true, simply because $p$ is true.

Finally, what about NOT, the last of the three basic Boolean operators? What if we wrote "Greece does not belong to the European Union"? This statement would be false, because it is the opposite of a true statement. Conversely, "Tokyo is not in Iran" would be true, because it is the opposite of a false statement.

Although the notation can be a bit intimidating at first, it will soon become familiar. Just remember that the ideas are the same as the ones we've already seen; the notation is simply a shorthand that we can use to write compound statements more concisely.

To remember the difference between $\wedge$ (AND) and $\vee$ (OR), you can think of the $\wedge$ as looking like the "A" in AND. As we do examples, you'll quickly grow more comfortable with these symbols.

Let's summarize what we know about these three operators. We'll begin with the AND operator, and after we've seen how to handle it, we'll use a similar approach with the OR and NOT operators.

AND: The combination of two statements using AND is true when both statements are true; otherwise it is false.

1. If $p$ is true and $q$ is true, then $p \wedge q$ is true:

$p$	$q$	$p \wedge q$
T	T	T

1. If $p$ is true and $q$ is false, then $p \wedge q$ is false:

$p$	$q$	$p \wedge q$
T	F	F

1. If $p$ is false and $q$ is true, then $p \wedge q$ is false:

$p$	$q$	$p \wedge q$
F	T	F

1. If $p$ is false and $q$ is false, then $p \wedge q$ is false:

$p$	$q$	$p \wedge q$
F	F	F

These are the only four possible combinations of truth values for $p$ and $q$. We can summarize these four possibilities in a single table; this is called a truth table, as shown below.

A computer scientist might write this table using 1 and 0 instead of T and F:

$p$	$q$	$p \wedge q$
1	1	1
1	0	0
0	1	0
0	0	0

A truth table handles all the possibilities at once; it lists every combination of whether $p$ and $q$ are true or false, and for each of them, it lists whether the compound statement is true or false. Notice that once we have this table, if we know the truth values of $p$ and $q$, we can look up the appropriate row in the table to find whether $p \wedge q$ is true or false.

For instance, if $p$ is "All fish are purple" and $q$ is "North America is in the Western Hemisphere," we would look at the row where $p$ is false and $q$ is true--the third row--and note that the compound statement "All fish are purple and North America is in the Western Hemisphere" is therefore false.

Truth tables will be especially useful once we begin to look at more complicated compound statements. If the compound statement is some combination of two statements $p$ and $q$, the first two columns will be the same as the first two columns shown here, and we'll slowly build up to the final compound statement by systematically adding columns. That's all we'll say for now; it'll make more sense later when we see actual examples.

When building a truth table with one statement, there will only be two rows:

$p$	$\ldots$
T	$\ldots$
F	$\ldots$

If we work with two statements, there are four possible combinations of true and false:

$p$	$q$	$\ldots$
T	T	$\ldots$
T	F	$\ldots$
F	T	$\ldots$
F	F	$\ldots$

If we have three statements, we'll have to double the number of rows; we'll need to include the four rows above when $r$ is true, and include them again when $r$ is false. In general, if we're working with $n$ statements, we'll need $2^n$ rows

$p$	$q$	$r$	$\ldots$
T	T	T	$\ldots$
T	F	T	$\ldots$
F	T	T	$\ldots$
F	F	T	$\ldots$
T	T	F	$\ldots$
T	F	F	$\ldots$
F	T	F	$\ldots$
F	F	F	$\ldots$

No matter how we order the rows, we need to account for these eight possibilities.

Now let's look at the truth tables for the other two operations.

OR: The combination of two statements using OR is true if at least one of the statements is true; it is only false if both of them are false. The truth table below summarizes this.

NOT: The negation of a statement is true if the original statement is false; it is false if the original statement is true.

As you may imagine, we can describe longer compound statements by using multiple operations. For instance, a university might advertise a scholarship by saying that "students are eligible if they have completed at least two years of college-level work and they have at least a 3.0 GPA or they have worked full-time for at least five years."

Let's take a look at this statement; first, define $p$, $q$, and $r$ to represent the simple pieces that are connected by the operations:

Next, try to write the compound statement using the notation we've introduced so far: $$p \wedge q \vee r$$

There's a problem with this, though; there is some ambiguity in the way the statement is phrased. Does it mean that a student is eligible after completing two years of college with a 3.0 GPA or after working for five years (with no GPA requirement)? Or does it mean that the student is eligible after completing two years of college, as long as they EITHER have a 3.0 GPA OR have worked at least five years?

To handle this ambiguity, we can use parentheses to group statements together. This works like the order of operations in algebra; the parentheses tell us in what order to combine the simple statements.

In this example, if we wanted to make it clear that the first option is the correct one (a student is eligible after completing two years of college with a 3.0 GPA or after working for five years (with no GPA requirement)) we would group the first two statements together: $$(p \wedge q) \vee r$$

Evaluating Statements with Multiple Operations

Suppose we want to take the compound statement above and consider a specific case, whether a specific student meets the minimum requirements for the scholarship. All we have to know is whether $p$, $q$, and $r$ are true for this student. Then, if we substitute these values into the compound statement and get a true result, the student meets the requirements; if not, the student does not meet the requirements.

For instance, suppose a student applies who has completed two years of college and has five years of work experience, but only had a 2.5 GPA. For this student, $p$ is true, $q$ is false, and $r$ is true. If we substitute these values into the compound statement, we have $$(T \wedge F) \vee T$$ Now we can simplify this statement: the parentheses define the order in which we do so. Note: F $\wedge$ T $=$ F
and F $\vee$ T $=$ T

$$\begin{align*} (T \wedge F) &\vee T\ F &\vee T\ T \end{align*}$$ For this student, the compound statement simplifies to T, so they meet the requirements.

Truth Tables for Statements with Multiple Operations

We could repeat the substitution and simplification process shown above every time we encounter a new student applying for the scholarship, but it will be more efficient in the long run to simply account for all the possibilities for the students that could apply; this is precisely what a truth table does for us.

Let's practice with the same example, using the compound statement $$(p \wedge q) \vee r$$ Since we have three simple statements ($p$, $q$, and $r$) we'll need eight rows to account for all possible combinations of truth values.

$p$	$q$	$r$	$\ldots$
T	T	T	$\ldots$
T	F	T	$\ldots$
F	T	T	$\ldots$
F	F	T	$\ldots$
T	T	F	$\ldots$
T	F	F	$\ldots$
F	T	F	$\ldots$
F	F	F	$\ldots$

Now, to build up to $(p \wedge q) \vee r$, we'll start by including a column for $p \wedge q$, using the rule for AND to create this column. Then we'll add another column that combines this new column with $r$ using the rule for OR. That final column will be the one we're interested in.

$p$	$q$	$r$	$p \wedge q$	$(p \wedge q) \vee r$
T	T	T	T	T
T	F	T	F	T
F	T	T	F	T
F	F	T	F	T
T	T	F	T	T
T	F	F	F	F
F	T	F	F	F
F	F	F	F	F

This table lists every possible combination of $p$, $q$, and $r$, and the result for $(p \wedge q) \vee r$ in that case. If we were sorting applications for this scholarship, we could look at every student and see which row of this truth table they fit into; if it is one of the first five, they are eligible, but if it is one of the last three, they are ineligible. In practice, we'd probably write a computer program to do the sorting for us, and we'd consider this logic in order to write that program.

Notice that we could have built the truth table in the last example without using the intermediate rows for $\sim p$ and $\sim q$; to do so, we could substitute each combination of $p$ and $q$ into the final statement $\sim p\ \wedge \sim q$ to jump straight from the first two columns to the final column:

If $p$ is true and $q$ is true: $$\begin{align*} \sim T\ &\wedge \sim T\ F\ &\wedge F\ F \end{align*}$$ Therefore, in the row where $p$ is T and $q$ is T, the compound statement $\sim p\ \wedge \sim q$ is F. The other rows can be done similarly.

The reason we tend to build truth tables as shown in the example above—by slowly adding columns and only performing one operation per column—is that this systematic approach tends to be simpler and avoid errors.

Notice that the column for $\sim (p\ \vee q)$ here is identical to the column for $\sim p\ \wedge \sim q$ in the previous example. Again, this is no accident; this is another representation of one of De Morgan's laws (which we'll encounter later in this chapter).

Some statements only make a claim about a specific category. For instance, one might say that "all politicians are dishonest." In this case, only those who fall into the category of politician are considered. This is an example of a quantified statement.

The words "all" or "some" (similarly "none" or "not all") are called quantifiers, since they refer to quantities, limiting the scope of a statement to a given category.

We can draw diagrams to represent quantified statements, like the following examples. We'll use circles to represent categories, but the size of the circles is not relevant; we're only interested in the location and interaction of the circles.

Negating a quantified statement is not initially an intuitive process. For instance, suppose we have a false statement like "all clouds are white." If we negate it, we should get a true statement.

You may be tempted to write the negation as "all clouds are not white." However, this too is a false statement, so it cannot be the negation of the first false statement.

The correct negation would be "NOT all clouds are white," which can also be written "some clouds are not white" or "there is at least one cloud that is not white."