In this section, we will learn how to construct logical statements. We will later combine our knowledge of sets with what we will learn about constructing logical statements to analyze arguments with logic.

Logic is a systematic way of thinking that allows us to deduce new information from old information and to parse the meanings of sentences. You use logic informally in everyday life and certainly also in doing mathematics. For example, suppose you are working with a certain circle, call it “Circle X,” and you have available the following two pieces of information.

1. Circle X has radius equal to 3.
2. If any circle has radius [latex]r[/latex], then its area is [latex]\pi{r}^{2}[/latex] square units.

You have no trouble putting these two facts together to get:

3. Circle X has area [latex]9\pi[/latex] square units.

You are using logic to combine existing information to produce new information. Since a major objective in mathematics is to deduce new information, logic must play a fundamental role. This chapter is intended to give you a sufficient mastery of logic.

Boolean Logic

Logic is, basically, the study of valid reasoning. When searching the internet, we use Boolean logic – terms like “and” and “or” – to help us find specific web pages that fit in the sets we are interested in. After exploring this form of logic, we will look at logical arguments and how we can determine the validity of a claim.

We can often classify items as belonging to sets. If you went the library to search for a book and they asked you to express your search using unions, intersections, and complements of sets, that would feel a little strange. Instead, we typically using words like “and,” “or,” and “not” to connect our keywords together to form a search. These words, which form the basis of Boolean logic, are directly related to set operations with the same terminology.

Suppose M is the set of all mystery books, and C is the set of all comedy books. If we search for “mystery”, we are looking for all the books that are an element of the set M; the search is true for books that are in the set.

When we search for “mystery and comedy” we are looking for a book that is an element of both sets, in the intersection. If we were to search for “mystery or comedy” we are looking for a book that is a mystery, a comedy, or both, which is the union of the sets. If we searched for “not comedy” we are looking for any book in the library that is not a comedy, the complement of the set C.

Notice here that or is not exclusive. This is a difference between the Boolean logic use of the word and common everyday use. When your significant other asks “do you want to go to the park or the movies?” they usually are proposing an exclusive choice – one option or the other, but not both. In Boolean logic, the or is not exclusive – more like being asked at a restaurant “would you like fries or a drink with that?” Answering “both, please” is an acceptable answer.

In the following video, You will see examples of how Boolean operators are used to denote sets.

In most internet search engines, it is not necessary to include the word and; the search engine assumes that if you provide two keywords you are looking for both. In Google’s search, the keyword or has be capitalized as OR, and a negative sign in front of a word is used to indicate not. Quotes around a phrase indicate that the entire phrase should be looked for. The search from the previous example on Google could be written:

Mexico university -“New Mexico”

Which Comes First?

Sometimes statements made in English can be ambiguous. For this reason, Boolean logic uses parentheses to show precedent, just like in algebraic order of operations.

The English phrase “Go to the store and buy me eggs and bagels or cereal” is ambiguous; it is not clear whether the requestors is asking for eggs always along with either bagels or cereal, or whether they’re asking for either the combination of eggs and bagels, or just cereal.

For this reason, using parentheses clarifies the intent:

Eggs and (bagels or cereal) means	Option 1: Eggs and bagels, Option 2: Eggs and cereal
(Eggs and bagels) or cereal means	Option 1: Eggs and bagels, Option 2: Cereal

Be aware that when a string of conditions is written without grouping symbols, it is often interpreted from the left to right, resulting in the latter interpretation.

Conditionals

Beyond searching, Boolean logic is commonly used in spreadsheet applications like Excel to do conditional calculations. A statement is something that is either true or false.

In common language, an example of a conditional statement would be “If it is raining, then we’ll go to the mall. Otherwise we’ll go for a hike.”
The statement “If it is raining” is the condition—this may be true or false for any given day. If the condition is true, then we will follow the first course of action, and go to the mall. If the condition is false, then we will use the alternative, and go for a hike.

Truth Tables

Because complex Boolean statements can get tricky to think about, we can create a truth table to break the complex statement into simple statements, and determine whether they are true or false. A table will help keep track of all the truth values of the simple statements that make up a complex statement, leading to an analysis of the full statement.

Some symbols that are commonly used for and, or, and not make using a truth table easier.

You can remember the first two symbols by relating them to the shapes for the union and intersection. [latex]A\wedge{B}[/latex] would be the elements that exist in both sets, in [latex]A\cap{B}[/latex]. Likewise, [latex]A\vee{B}[/latex] would be the elements that exist in either set, in [latex]A\cup{B}[/latex].
In the previous example, the truth table was really just summarizing what we already know about how the or statement work. The truth tables for the basic and, or, and not statements are shown below.

Truth tables really become useful when analyzing more complex Boolean statements.

 

When we discussed conditions earlier, we discussed the type where we take an action based on the value of the condition. We are now going to talk about a more general version of a conditional, sometimes called an implication.

Implications are similar to the conditional statements we looked at earlier; [latex]p\rightarrow{q}[/latex] is typically written as “if p then q,” or “p therefore q.” The difference between implications and conditionals is that conditionals we discussed earlier suggest an action—if the condition is true, then we take some action as a result. Implications are a logical statement that suggest that the consequence must logically follow if the antecedent is true.

Notice that the statement tells us nothing of what to expect if it is not raining. If the antecedent is false, then the implication becomes irrelevant.

In traditional logic, an implication is considered valid (true) as long as there are no cases in which the antecedent is true and the consequence is false. It is important to keep in mind that symbolic logic cannot capture all the intricacies of the English language.

 

For any implication, there are three related statements, the converse, the inverse, and the contrapositive.

Looking at truth tables, we can see that the original conditional and the contrapositive are logically equivalent, and that the converse and inverse are logically equivalent.

		Implication	Converse	Inverse	Contrapositive
p	q	[latex]p\rightarrow{q}[/latex]	[latex]q{\rightarrow}p[/latex]	[latex]\sim{p}\rightarrow\sim{q}[/latex]	[latex]\sim{q}\rightarrow\sim{p}[/latex]
T	T	T	T	T	T
T	F	F	T	T	F
F	T	T	F	F	T
F	F	T	T	T	T

DeMorgan’s Laws

There are two pairs of logically equivalent statements that come up again and again in logic. They are prevalent enough to be dignified by a special name: DeMorgan’s laws.

The laws are named after Augustus De Morgan (1806–1871), who introduced a formal version of the laws to classical propositional logic. De Morgan’s formulation was influenced by algebraization of logic undertaken by George Boole, which later cemented De Morgan’s claim to the find. Nevertheless, a similar observation was made by Aristotle, and was known to Greek and Medieval logicians. For example, in the 14th century, William of Ockham wrote down the words that would result by reading the laws out. Jean Buridan, in his Summulae de Dialectica, also describes rules of conversion that follow the lines of De Morgan’s laws. Still, De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into the language of logic. De Morgan’s laws can be proved easily, and may even seem trivial. Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments.

The first of DeMorgan’s laws is verified by the following table. You are asked to verify the second in an exercise.

[latex]P[/latex]	[latex]Q[/latex]	[latex]\sim{P}[/latex]	[latex]\sim{Q}[/latex]	[latex]P\wedge{Q}[/latex]	[latex]\sim\left(P\wedge{Q}\right)[/latex]	[latex]\left(\sim{P}\right)\vee\left(\sim{Q}\right)[/latex]
T	T	F	F	T	F	F
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	F	T	T	F	T	T

DeMorgan’s laws are actually very natural and intuitive. Consider the statement [latex]\sim\left(P\wedge{Q}\right)[/latex], which we can interpret as meaning that it is not the case that both P and Q are true. If it is not the case that both P and Q are true, then at least one of P or Q is false, in which case [latex]\left(\sim{P}\right)\vee\left(\sim{Q}\right)[/latex] is true. Thus [latex]\sim\left(P\wedge{Q}\right)[/latex] means the same thing as [latex]\left(\sim{P}\right)\vee\left(\sim{Q}\right)[/latex].

DeMorgan’s laws can be very useful. Suppose we happen to know that some statement having form [latex]\sim\left(P\vee{Q}\right)[/latex] is true. The second of DeMorgan’s laws tells us that [latex]\left(\sim{Q}\right)\wedge\left(\sim{P}\right)[/latex] is also true, hence [latex]\sim{P}[/latex] and [latex]\sim{Q}[/latex] are both true as well. Being able to quickly obtain such additional pieces of information can be extremely useful.

Here is a summary of some significant logical equivalences. Those that are not immediately obvious can be verified with a truth table.

[latex]\text{Contrapositive law}\begin{array}{c}P\rightarrow{Q}=(\sim{Q})\rightarrow(\sim{P})\end{array}[/latex]

[latex]\text{DeMorgan's laws}\begin{array}{c}{\sim(P\land{Q})=\sim{P}\lor\sim{Q}}\\{\sim(P\lor{Q})=\sim{P}\land\sim{Q}}\end{array}[/latex]

[latex]\text{Commutative laws}\begin{array}{c}{(P\land{Q})={P}\land{Q}}\\{(P\lor{Q})={P}\lor{Q}}\end{array}[/latex]

[latex]\text{Distributive laws}\begin{array}{c}{{P}\land(Q\lor{R})=({P}\land{Q})\lor(P\land{R})}\\{P\lor(Q\land{R})=({P}\lor{Q})\land(P\lor{R})}\end{array}[/latex]

[latex]\text{Associative laws}\begin{array}{c}{P\land(Q\land{R})=(P\land{Q})\land{R}}\\{P\lor(Q\lor{R})=(P\lor{Q})\lor{R}}\end{array}[/latex]

Notice how the distributive law [latex]P\wedge\left(Q\vee{R}\right)=\left(P\wedge{Q}\right)\vee\left(P\wedge{Q}\right)\vee\left(P\wedge{R}\right)[/latex] has the same structure as the distributive law [latex]p\left(q+r\right)=p\cdot{q}+p\cdot{r}[/latex] from algebra. Concerning the associative laws, the fact that [latex]P\wedge\left(Q\wedge{R}\right)=\left(P\wedge{Q}\right)\wedge{R}[/latex] means that the position of the parentheses is irrelevant, and we can write this as [latex]P\wedge{Q}\wedge{R}[/latex] without ambiguity. Similarly, we may drop the parentheses in an expression such as [latex]P\vee\left(Q\vee{R}\right)[/latex].

But parentheses are essential when there is a mix of [latex]\wedge[/latex] and [latex]\vee[/latex], as in [latex]P\vee\left(Q\wedge{R}\right)[/latex]. Indeed, [latex]P\vee\left(Q\wedge{R}\right)[/latex] and [latex]P\vee\left(Q\wedge{R}\right)[/latex] and [latex]P\vee\left({Q}\right)\wedge{R}[/latex] are not logically equivalent.

Negating Statements

Given a statement R, the statement [latex]\sim{R}[/latex] is called the negation of R. If R is a complex statement, then it is often the case that its negation [latex]\sim{R}[/latex] can be written in a simpler or more useful form. The process of finding this form is called negating R. In proving theorems it is often necessary to negate certain statements. We now investigate how to do this.

We have already examined part of this topic. DeMorgan’s laws

[latex]\sim\left(P\wedge{Q}\right)=\left(\sim{P}\right)\vee\left(\sim{Q}\right)\\\sim\left(P\vee{Q}\right)=\left(\sim{P}\right)\wedge\left(\sim{Q}\right)[/latex]

(from “Logical Equivalence”) can be viewed as rules that tell us how to negate the statements [latex]P\wedge{Q}[/latex] and [latex]P\vee{Q}[/latex]. Here are some examples that illustrate how DeMorgan’s laws are used to negate statements involving “and” or “or.”