Intro To Logic

Section 1.1 Intro To Logic

Objectives: Logic

When we say sentences like "I will have a coffee or a donut" or "If a number is even and divisible by three then it is divisible by six" we want to make sure we all agree on the precise meaning of the sentence. In this section, we will:

🔗

introduce the topic of logical statements

🔗
give precise meaning to common english words like "and", "or", "all", "some" "if", and "then"

🔗
determine exactly when logical statements are true (and when they are false) and how to show this

🔗
introduce various related statements to "if-then" statements.

🔗

As we move forward in our study we will have a common "language" for expressing mathematical ideas.

🔗

Subsection 1.1.1 The Basics

One of the most important aspects of mathematics is communication. As much as it’s important to solve problems and master arithmetic and algebraic skills, it’s just as important to be able to communicate your answers (or questions) to others so that everyone has the same understanding of what is being said mathematically.

🔗

In mathematics we really care about the truth of sentences that we write or say. We introduce the following concepts:

🔗

Definition 1.1.1.

A statement is a sentence that is either always true or always false (but not both).

🔗

Example 1.1.2.

"Ottawa is the capital of Canada" is a true statement.

🔗

"$4^2=10$" is a false statement.

🔗

Example 1.1.3. Non-Examples.

"What time is it?" is a sentence that is not a statement. It is simply a question and cannot be given a truth value of true or false. Similarly, "Go do you homework" is a command, and not a statement.

🔗

Sometimes we want sentences to have a variable in them so that when we fill in the variable with a value it becomes a statement.

🔗

Definition 1.1.4.

An open sentence is a sentence with a variable such that the sentence becomes a statement when you fill in a value into the variable.

🔗

Example 1.1.5.

"$X^2 = 1$" is an open sentence. It is true when $x=1$ or $x=-1$ and false for any other numbers.

🔗

"Winnipeg is the capital city of Canadian province P" is an open sentence. It is true when P = "Manitoba" and false for all other Canadian provinces.

🔗

Notes For a Deeper Understanding.

In open sentences, we usually restrict the allowable inputs for variables. The set of allowable inputs is called the domain. In the first example above, it’s implicit that we only want $X$ to be a number, and not, say, a colour, or telephone, or anything else! If it’s not entirely clear what the domain of an open sentence is, we should tell people what the domain is.
🔗

🔗
We want statements to have exactly one truth value; either True(T) or False(F). If we know a sentence is a statement and it’s not true, it must be false. The easiest way to think about this is by asking yourself "am I being lied to?" If the answer is no, then the statement is true (even if it doesn’t really apply or make sense).
🔗

🔗

🔗

Checkpoint 1.1.6.

Answer the following questions about open sentences. Recall that an open sentence is a mathematical statement containing one or more variables that becomes either true or false when specific values are substituted for the variables.

🔗

Determine whether each of the following is an open sentence:
🔗
1. $\displaystyle x+3=10$
  
  🔗
2. $\displaystyle 7-4=3$
  
  🔗
3. $\displaystyle y^2=25$
  
  🔗
4. $\displaystyle 12 \gt 15$
  
  🔗
🔗
For each open sentence below, state whether it is true or false when the given value is substituted for the variable.
🔗
1. $2x+5=11$ when $x=3$
  
  🔗
2. $n-7 \leq 2$ when $n=10$
  
  🔗
3. $3y=18$ when $y=6$
  
  🔗
🔗
Write an open sentence that describes each situation:
🔗
1. The cost $C$ of $t$ tickets if each ticket costs $12.
  
  🔗
2. The area $A$ of a square with side length $s\text{.}$
  
  🔗
🔗
Suppose $P(x)$ is the open sentence “$x$ is a prime number.” List three values of $x$ that make $P(x)$ true and three that make it false.
🔗

🔗

Solution.

1. Open
  
  🔗
2. Not open(true)
  
  🔗
3. Open
  
  🔗
4. Not open (false)
  
  🔗
🔗
1. True
  
  🔗
2. False
  
  🔗
3. True
  
  🔗
🔗
1. $\displaystyle C = 12t$
  
  🔗
2. $\displaystyle A = s^2$
  
  🔗
🔗
True examples: $x=2,3,5\text{.}$ False examples: $x=1,4,6\text{.}$
🔗

🔗

🔗

Subsection 1.1.2 And, Or, and Not

In the English language, there is a lot of ambiguity in the words that we say. Consider the following two sentences:

Your hamburger combo comes with fries or onion rings.
🔗

🔗
You can check a free bag if you have elite status or you have purchased a business class ticket.
🔗

🔗

In both of these examples, the word "or" has a different meaning. In the first, "or" is used exclusively; you can have fries or onion rings but not both. In the second, it is used inclusively; you would expect that you would get to check a free bag if you had elite status and a business class ticket.

🔗

In mathematics, we aim to be as precise as possible with our language. We want to make sure that everyone understands the exact same ideas when we express ourselves, especially in determining when a statement is true or false. The mathematical community has agreed upon precise meanings for words such as "and", "or", "not", "all", "some", and "if-then" (among others). Let’s learn about them now. In the following definition we use $P$ and $Q$ as variables to mean any two statements:

🔗

Definition 1.1.7.

If $P$ and $Q$ are statements, then:

the statement "$P$ and $Q$" is true exactly when $P$ is true and $Q$ is true. Otherwise it is false.

🔗
the statement "$P$ or $Q$" is false exactly when $P$ is false and $Q$ is false. Otherwise it is true.

🔗

🔗

Checkpoint 1.1.8.

Let $P :=$ "I will have a donair for dinner" and $Q :=$ "I will have pizza for dinner". Determine if the statements "$P$ and $Q$" and "$P$ or $Q$" are true when:

🔗

I had both a donair and pizza for dinner
🔗

🔗
I had a donair for dinner, but not pizza
🔗

🔗
I had pizza for dinner, but not a donair
🔗

🔗
I had neither a donair or pizza for dinner.
🔗

🔗

Solution.

$P$ and $Q\text{:}$

T
🔗

🔗
F
🔗

🔗
F
🔗

🔗
F
🔗

🔗

🔗

$P$ or $Q\text{:}$

T
🔗

🔗
T
🔗

🔗
T
🔗

🔗
F
🔗

🔗

🔗

Definition 1.1.9.

If $P$ is a statement, then the negation of $P\text{,}$ written $\sim P$ is a statement with the opposite truth value of $P$ (but with the same context). If $P$ is an open sentence, then $\sim P$ is an open sentence with the opposite truth value for each variable input.

🔗

Example 1.1.10.

$P:=$$\sim P = $

🔗

Example 1.1.11.

If $P = "x < 5"$ over the domain of counting numbers (which is true when $= 1,2,3,4$ and false otherwise) then $\sim P = "x \geq 5"$ (which is false when $x=1,2,3,4$ and true otherwise). You could also write $\sim P$ as $"x > 4"\text{,}$ or in many other logically equivalent ways.

🔗

Checkpoint 1.1.12.

If $P = "x < 5"$ over the domain of counting numbers, explain why $x > 5$ isn’t the negation of $P\text{.}$

🔗

Solution.

When $x = 5\text{,}$ $P$ is false, since 5 is not less than 5. However $x > 5$ is also false when $x=5$ since 5 is not greater than 5. Since these open sentences do not have opposite truth values for every possible input, one cannot be the negation of the other.

🔗

We can write down more complex expressions using combinations of "and", "or", and "not". To help us determine when these complex statements are true, we can use a truth table to look at these compound statements piece by piece:

🔗

Definition 1.1.13.

If $A$ and $B$ are two (usually compound) statements, we say that they are logically equivalent when their truth values always agree given the truth values of the constituent parts.

🔗

Figure 1.1.14. Supplementary Video

🔗

Subsection 1.1.3 Quantified Statements

Definition 1.1.15.

Universal quantifiers are words that signify every object in our domain (that is, every object under consideration). These are words like "all", "for all", "every", "no", "none", and "each".

🔗

Existential quantifiers are words that signify at least one object in our domain. These are words and phrases like "there is", "some", "at least one", and "there exists".

🔗

Example 1.1.16.

Some universally quantified statements are:

All cats are mammals
🔗

🔗
Each whole number is odd
🔗

🔗
No polygons have exactly two sides
🔗

🔗
Every whole number has a non-negative square
🔗

🔗

🔗

Example 1.1.17.

Some existentially quantified statements are:

There is an odd integer
🔗

🔗
Some cats are grey
🔗

🔗
At least one fraction is equal to 1
🔗

🔗
There exists a prime number with a factor of 6
🔗

🔗

🔗

You may have noticed that these quantified statements are a combination of a quantifier (universal or existential) and an open sentence, thought sometimes when written in English the variable can be hidden. For example, "there is an odd integer" can be reworded to "there is an integer $x$ such that $x$ is odd."

🔗

Checkpoint 1.1.18.

In the two examples above, write the quantified statement using a combination of a quantifier (use only "For All" or "There is") and an open sentence. Make sure to include a variable. Then, determine the truth value of the quantified statement.

🔗

Solution 1.

You may have a different wording, but one choice would be:

For all cats $C\text{,}$ $C$ is a mammal (T)
🔗

🔗
For all whole numbers $n\text{,}$ $n$ is odd (F)
🔗

🔗
For all polygons $p\text{,}$ $p$ does not have exactly two sides (T) , ,
🔗

🔗
For all whole numbers $n\text{,}$ $n^2 \geq 0$ (T)
🔗

🔗

Note that, for 3, we changed "No $p$ are $Q$", where $Q$ was an open sentence, to "All $p$ are $\sim Q$".

🔗

Solution 2.

You may have a slightly different wording, but one choice would be:

There is an integer $n$ such that $n$ is odd. (T)
🔗

🔗
There is a cat $C$ such that $C$ is grey. (T)
🔗

🔗
There is a fraction $\frac{a}{b}$ such that $\frac{a}{b} =1$ (T)
🔗

🔗
There is a prime number $p$ such that $p$ is divisible by 6 (F)
🔗

🔗

Later in this chapter we will learn how to write "is an odd number" and "is divisible by 6" more mathematically, using algebra.

🔗

Notes for a Deeper Understanding.

A universally quantified statement can be vacuously true if there are no objects that apply to the statement. For example, "all unicorns are named George" is not lying to you since you can’t find a unicorn not named George, so we consider statements like this true.
🔗

🔗
Other than vacuously true statements, if a universally quantified statement is true so is the "existentially" quantified version. For example, "all polygons have at least three sides" is true, so "some polygons have at least three sides" is true too! Remember, existential quantifiers only care of an object exists, not how many.
🔗

🔗

🔗

We can negate quantified statements as well. We do this regularly in our daily lives, but let’s try and pinpoint what is going on:

🔗

Checkpoint 1.1.19.

A friend tells you that all cats are blue. This is obviously a false statement! Suppose you wanted to reply to your friend with the correct negated (true) statement. Which of the following could you reply with?

🔗

Some cats are blue
🔗

🔗
Some cats are not blue
🔗

🔗
All cats are not blue
🔗

🔗
There is a cat that isn’t blue
🔗

🔗
No cats are blue
🔗

🔗

Solution.

Statements 2 and 4 are correct. Be careful with statements 3 and 5; the reason we know not all cats are blue is that we’ve seen cats that are not blue. There may be a cat out there that is blue that we’ve never seen, so we can’t say for sure that no cats are blue.

🔗

Checkpoint 1.1.20.

A friend tells you that some cats have wings. This, like the exercise above, is obviously a false statement! Suppose you wanted to reply to your friend with the correct negated (true) statement. Which of the following could you reply with?

🔗

All cats have wings
🔗

🔗
No cats have wings
🔗

🔗
Some cats do not have wings
🔗

🔗
All cats do not have wings
🔗

🔗

Solution.

Statements 2 and 4 are correct. Note the form of these two statements: statement 2 is "No P are Q" and statement 4 is "All P are not Q". As mentioned above, these are logically equivalent.

🔗

Note that in the previous two exercises, there was a pattern to negating a quantified statement. In general, this holds for negating any quantified statement.

🔗

To negate a quantified statement of the type "All P are Q" or "Some P are Q":

Switch the type of quantifier to the other
🔗

🔗
Negate the open sentence part of the quantified statement.
🔗

🔗

🔗

Remember that you can rewrite "No P are Q" as "All P are not Q". Using this, you can negate "No P are Q" to "Some P are Q" (and vice versa).

🔗

Notes for a Deeper Understanding.

It might be clear, but it should be noted that for any statement or open sentence $P$ it’s true that $\sim (\sim P)$ is logically equivalent to $P\text{.}$ So, much like negatives, two negations cancel each other out. Since quantified statements are indeed statements, this holds for them as well.

🔗

Subsection 1.1.4 Viewing Quantified Statements as a Diagram

It’s quite helpful to view these quantified statements as a diagram. Since most students are familiar with the idea of a Venn diagram (which are circles representing groups of objects), this is the tool we will use to help us visualize these statements.

🔗

We want to be able to represent both universally- and existentially quantified statements. For both types, we first need to draw a box representing the domain of all possible objects under consideration:

🔗

🔗

For universally quantified statements (e.g., "All A are B" or as a concrete example "All cats are mammals") we want a circle representing all objects that satisfy condition A (all cats in our example).
🔗

🔗

Now, we want a circle to represent all objects that satisfy B (in our example, all mammals). Note that since we wish to show all A are B, we want to draw this circle so that all of the A objects are also included in the B circle:
🔗

🔗

🔗
For existentially quantified statements (e.g., "Some A are B" or as a concrete example "Some cats are grey") we want a circle representing all objects that satisfy condition A (all cats in our example).
🔗

🔗

Now, we want a circle to represent all objects that satisfy B (in out example, things that are grey). Note that there could be cats that are not grey, and grey things that are not cats, so we need to draw the diagram so that they only partially overlap. We also know that there is definitely at least one A that is B (cat that is grey) since the statement tells us so, therefore we can put a little dot in the intersection to represent that object (the grey cat).
🔗

🔗

🔗

There is an alternate way of representing a universally quantified statement with overlapping circles. We will hatch out the area where we know is empty (the area that is A but not B, or in our example the area that is cats that are not mammals):

🔗

Checkpoint 1.1.21.

Using the ideas above, draw a diagram representing the statement "No A are B".

🔗

Solution.

We could represent this in (at least) two ways. One way is as two non-overlapping circles:

🔗

🔗

Or as intersecting circles with the intersection hatch out to indicate it is empty.

🔗

🔗

Subsection 1.1.5 Expressing Even and Odd Numbers Algebraically

In the coming sections, we will be using even and odd numbers as examples of quantified and conditional statements. For example, we can say "All pairs of whole numbers $a,b$ that are both odd have a sum $a+b$ that is even and a product $a \times b$ that is odd".

🔗

To determine the truth values of these statements, it’s not enough to only look at some examples, as we’ll see in the upcoming section Subsection 1.2.4. So we will have to learn to express the idea of even and odd numbers it terms of the property that makes them even and odd.

🔗

Checkpoint 1.1.22.

How would you explain or show to someone that the number 12 is even? How about that 15 is odd? Can you extend these ideas to any even or odd number?

🔗

Solution.

Of course, there are many ways of doing this, but one way is to draw a picture. There is a very good chance that you would do the same thing! Let’s start by showing 12 is even:

🔗

🔗

Here we took 12 dots and organized them as 6 rows of 2. Since 12 can be grouped evenly into rows of 2, we know that 12 is even. Hence, we can write $12=2 \times 6.$

🔗

In general, the number of rows of 2 isn’t particularly important to say that a number is even; it’s the fact that we can group the number into *some amount* of rows of 2. Usually we’ll express this as $k$ rows of 2. So for an even whole number $n\text{,}$ we know $n=2k$ for some whole number $k\text{.}$

🔗

🔗

To show 15 is odd, you probably drew a picture similar to this:

🔗

🔗

Here we took the 15 dots and organized them into 7 rows of 2, but we had 1 dot remaining where we were unable to complete a full row of two. Hence, we can write $15=2 \times 7 + 1.$

🔗

Like for even numbers, the number of rows of 2 isn’t particularly important to say that a number is odd; it’s the fact that we can group the number into as many rows of 2 as possible, we always have 1 left over. Usually we’ll express this as $k$ rows of 2 + 1 remaining. So for a odd whole number $n\text{,}$ we know $n=2k+1$ for some whole number $k\text{.}$

🔗

In picture form:

🔗

To summarize: let $n$ be a whole number.

If $n$ is an even number then $n=2k$ for some whole number $k\text{.}$
🔗

🔗
If $n$ is an odd number then $n=2k+1$ for some whole number $k$
🔗

🔗

🔗

Notes for a Deeper Understanding.

The number 0 is even since $0=2 \times 0\text{.}$
🔗

🔗
Even really just means "divisible by 2". We can (and will in subsequent chapters) extend this idea to express a number $n$ being divisible by some other number $c$ meaning $n=c \times k$ for some whole number $k\text{.}$ The idea of "odd" extends similarly, though you can have more than one part remaining. This is basically the idea of remainders when doing division.
🔗

🔗
We can also extend these ideas to integers as well (that is, positive and negative counting numbers, including 0).
🔗

🔗

🔗

Figure 1.1.24. Supplementary Video: Even and Odd Numbers

🔗

Prev Top Next