Logic

Abigail Huettig

10 Logic

We use logic every day in many areas of our lives. Logic is what enables us to determine whether an idea, belief, statement, etc. is true or false. As with any area of life, it is impossible for one idea to be true and at the same time false. This is known as the Law of Excluded Middle [23]. In mathematics, logic functions the same way. A mathematical statement is either true or false, and logic enables us to determine whether it is true or false. There are also different types of logical statements, which we will discuss below.

Disjunctions
In English, a disjunction can be identified by the word “or.” In math, we use the symbol $\vee$ to mean “or.” Suppose we have the following statements:

$\text{Statement A: Seven is odd.}$

$\text{Statement B: Seven is even.}$

If we want to combine these two statements to form a disjunction, then we have the following:

$\text{Seven is odd, or seven is even.}$

Using mathematical symbols, this statement is $A\vee B$ . Finding and creating disjunctions is not difficult. But we also need to determine whether a disjunction is true or false. This is where we use truth tables. The following is the truth table for disjunctions.

What this table is saying is that if $A$ , $B$ , or $A$ and $B$ are true, then the disjunction is true. The only way a disjunction can be false is if both $A$ and $B$ are false.

By definition, an even number is one that is divisible by 2, and an odd number is one that is not. Because

$7=3(2)+1,$

7 is not divisible by two. Thus, seven is odd, but not even. So, our statement “seven is odd, or seven is even” is true because it is true that seven is odd even though it is not true that seven is even.

Conjunctions
In English, a conjunction can be identified by the word “and.” Sometimes “and” will actually be stated in the sentence while other times it will be implied. In math, we use the symbol $\wedge$ to mean “and.” Suppose we have the following statements:

$\text{Statement A: Six is divisible by two.}$

$\text{Statement B: Six is divisible by five.}$

If we want to combine these two statements to form a conjunction, then we have the following:

$\text{Six is divisible by two, and six is divisible by five.}$

Using mathematical symbols, this statement is $A\wedge B$ . The truth table is

If $A$ , $B$ , or $A$ and $B$ are false, then the conjunction is false. The only way a conjunction can be true is if both $A$ and $B$ are true. Because

$6=2(3)\text{ and } 6=5(1)+1,$

6 is divisible by two but not five. Thus, our statement “six is divisible by two, and six is divisible by five” is false because it is false that six is divisible by five even though it is true that six is divisible by two.

Implications
In English, an implication can be identified by the word “if.” Suppose we have the following statements:

$\begin{align*} \text{Statement A}&: \text{There exists an integer $x$ that is divisible by 14.}\\ \text{Statement B}&: \text{There exists an integer $x$ that is divisible by 7.} \end{align*}$

If we want to combine these two statements to form an implication, then we have the following: If there exists an integer $x$ that is divisible by 14, there exists an integer $x$ that is divisible by 7. Using mathematical symbols, this statement is $A\Rightarrow B$ . The truth table is

An implication $A \Rightarrow B$ means that if $A$ is true then $B$ must be true. Thus, the only way an implication could be false is if $A$ is true but $B$ is not.

For an integer $x$ that is divisible by 14, we have

$\begin{align*} x&=14y \\ &=2(7)y\\ &=7(2y), \end{align*}$

where $y$ is an integer.

Thus, if an integer is divisible by 14, it follows that this integer is also divisible by 7. Therefore, our statement “if there exists an integer $x$ that is divisible by 14, there exists an integer $x$ that is divisible by 7″ is true.

One additional symbol is $\neg$ , meaning “not,” which we will see in the following homework problem from Smith et al. that I completed for this paper [23].

Example 20
Determine the truth value for each of the following.

Although 51 divides 153, it is neither prime nor a divisor of 409.
It is not the case that both -5 and 13 are elements of $\mathbb{N}$ , but 4 is in the set of rational numbers.

Solution

Let statement be “51 divides 153,” be “51 is prime,” and be “51 is a divisor of 409.” We will use a table to organize the information and help us reach the answer. Note that this is not a truth table as a truth table looks at all possible combinations of true and false. This table only looks at one combination, but it is all we need to solve the problem.
Therefore, the statement “although 51 divides 153, it is neither prime nor a divisor of 409″ is true.
Let statement be “-5 is an element of ,” be “13 is an element of , and be “4 is in the set of rational numbers.”
Therefore, the statement “it is not the case that both -5 and 13 are elements of $\mathbb{N}$ , but 4 is in the set of rational numbers” is true.

Next, we are going to take a quick look at a few logically equivalent statements, known as DeMorgan’s Laws.

DeMorgan’s Laws

DeMorgan’s Laws are simple, intuitive statements that give a couple rules of logic. They are stated as follows:

Theorem II.1 (DeMorgan’s Laws of Logic)

Let $A$ and $B$ be statements.

$\neg (A \wedge B) = \neg A \vee \neg B$
$\neg (A \vee B) = \neg A \wedge \neg B$

One way of understanding what these laws are saying is to think of a multiple choice test. Suppose a question has options $A$ , $B$ , $C$ , and $AB$ . Now, suppose that we have eliminated option $AB$ , we are saying that the answer is not $A$ and $B$ ( $\neg (A \wedge B)$ ). Because of this, we know that $A$ is not correct or $B$ is not correct ( $\neg A \vee \neg B$ ). That is the first law, and the second can be thought of in a similar way. Suppose we know that the answer is not $A$ or $B$ ( $\neg (A \vee B)$ ). This leaves us with option $C$ because it makes sense that when we say the answer is not $A$ or $B$ we mean that the answer is not $A$ and not $B$ ( $\neg A \wedge \neg B$ ).

The following example is one I wrote for this paper.

Example 21
Write a statement that is equivalent to “Find an integer $x$ that is not an even number that is a perfect square and is not less than 50 or greater than 100.”

Solution
Let $A$ , $B$ , $C$ , $D$ be the following statements respectively:

$\begin{align*} &\text{Find an integer $x$ that is an even number.}\\ &\text{Find an integer $x$ that is a perfect square.}\\ &\text{Find an integer $x$ that is less than 50.}\\ &\text{Find an integer $x$ that is greater than 100.} \end{align*}$

This means that the statement “find an integer $x$ that is an even number that is a perfect square” is $A\wedge B$ . It then follows that the statement “Find an integer $x$ that is not an even number that is a perfect square” is $\neg(A\wedge B).$ By the first of DeMorgan’s Laws, $\neg(A\wedge B)=\neg A \vee \neg B$ . Thus, an equivalent statement to “find an integer $x$ is not an even number that is a perfect square” would be “find an integer $x$ that is either not an even number or not a perfect square.”

The statement “find an integer $x$ that is less than 50 or greater than 100″ is $C\vee D$ . It then follows that the statement “find an integer $x$ that is not less than 50 or greater than 100″ is $\neg (C\vee D).$

By the second of DeMorgan’s Laws, $\neg (C\vee D)=\neg C\wedge \neg D$ . Thus, an equivalent statement to “find an integer $x$ that is not less than 50 or greater than 100″ is “find an integer $x$ that is not less than 50 and not greater than 100.”

Therefore, an equivalent statement to “find an integer $x$ that is not an even number that is a perfect square and is not less than 50 or greater than 100″ is “find an integer $x$ that is either not an even number or is not a perfect square and is not less than 50 and not greater than 100.”

We have seen how DeMorgan’s laws can be applied to logic, but they are also used in set theory with slightly different notation. (See DeMorgan’s Laws in Part III: Chapter 13.) Additionally, these laws appear in other mathematical areas, such as discrete math and real analysis, and come in handy when constructing proofs, which we will now discuss.

10 Logic

DeMorgan’s Laws

License

Share This Book