# 2.1: Propositions

- Page ID
- 8386

The rules of logic allow us to distinguish between valid and invalid arguments. Besides mathematics, logic has numerous applications in computer science, including the design of computer circuits and the construction of computer programs. To analyze whether a certain argument is valid, we first extract its syntax.

Example \(\PageIndex{1}\label{eg:prop-01}\)

These two arguments:

- If \(x+1=5\), then \(x=4\). Therefore, if \(x\neq4\), then \(x+1\neq5\).
- If I watch Monday night football, then I will miss the following Tuesday 8 a.m. class. Therefore, if I do not miss my Tuesday 8 a.m. class, then I did not watch football the previous Monday night.

use the same format:

If *p *then *q. *Therefore if \(q\) is false then \(p\) is false.

If we can establish the validity of this type of argument, then we have proved *at once* that both arguments are legitimate. In fact, we have also proved that any argument using the same format is also credible.

Hands-on Exercise \(\PageIndex{1}\label{he:prop-01}\)

Can you give another argument that uses the same format in the last example?

In mathematics, we are interested in statements that can be proved or disproved. We define a ** proposition** (sometimes called a

**, or an**

*statement***) to be a sentence that is either true or false, but not both.**

*assertion*Example \(\PageIndex{2}\label{eg:prop-02}\)

The following sentences:

- Barack Obama is the president of the United States.
- \(2+3=6\).

are propositions, because each of them is either true or false (but not both).

Example \(\PageIndex{3}\label{eg:prop-03}\)

These two sentences:

- Ouch!
- What time is it?

are not propositions because they do not proclaim anything; they are exclamation and question, respectively.

Example \(\PageIndex{4}\label{eg:prop-04}\)

Explain why the following sentences are *not* propositions:

- \(x+1 = 2\).
- \(x-y = y-x\).
- \(A^2 = 0\) implies \(A = 0\).

**Solution**-
- This equation is not a statement because we cannot tell whether it is true or false unless we know the value of \(x\). It is true when \(x=1\); it is false for other \(x\)-values. Since the sentence is sometimes true and sometimes false, it cannot be a statement.
- For the same reason, since \(x-y=y-x\) is sometimes true and sometimes false, it cannot be a statement.
- This looks like a statement because it appears to be true all the time. Yet, this is
*not*a statement, because we never say what \(A\) represents. The claim is true if \(A\) is a real number, but it is not always true if \(A\) is a matrix^{1}. Thus, it is not a proposition.

Hands-on Exercise \(\PageIndex{2}\label{he:prop-02}\)

Explain why these sentences are not propositions:

- He is the quarterback of our football team.
- \(x+y=17\).
- \(AB=BA\).

Example \(\PageIndex{5}\label{eg:prop-05}\)

Although the sentence “\(x+1=2\)” is not a statement, we can change it into a statement by adding some condition on \(x\). For instance, the following is a true statement:

For some real number \(x\), we have \(x+1=2\).

and the statement

For all real numbers \(x\), we have \(x+1=2\).

is false. The parts of these two statements that say “for some real number \(x\)” and “for all real numbers \(x\)” are called quantifiers. We shall study them in Section 6.

Example \(\PageIndex{6}\label{eg:prop-06\)

Saying that

“A statement is not a proposition if we *cannot* decide whether it is true or false.”

is different from saying that

“A statement is not a proposition if we do not know

*how* to verify whether it is true or false.”

The more important issue is whether the truth value of the statement can be determined in theory. Consider the sentence

Every even integer greater than 2 can be written as the sum of two primes.

Nobody has ever proved or disproved this claim, so we do not know whether it is true or false, even though computational data suggest it is true. Nevertheless, it *is* a proposition because it is either true or false but not both. It is impossible for this sentence to be true sometimes, and false at other times. With the advancement of mathematics, someone may be able to either prove or disprove it in the future. The example above is the famous ** Goldbach Conjecture**, which dates back to 1742.

We usually use the lowercase letters \(p\), \(q\) and \(r\) to represent propositions. This can be compared to using variables \(x\), \(y\) and \(z\) to denote real numbers. Since the truth values of \(p\), \(q\), and \(r\) vary, they are called ** propositional variables**. A proposition has only two possible values: it is either true or false. We often abbreviate these values as T and F, respectively.

Given a proposition \(p\), we form another proposition by changing its truth value. The result is called the ** negation** of \(p\), and is denoted \(\neg p\) or \(\altneg p\), both of which are pronounced as “not \(p\).” The similarity between the notations \(\neg p\) and \(-x\) is obvious.

We can also write the negation of \(p\) as \(\overline{p}\), which is pronounced as “\(p\) bar.” The truth value of \(\overline{p}\) is opposite of that of \(p\). Hence, if \(p\) is true, then \(\overline{p}\) would be false; and if \(p\) is false, then \(\overline{p}\) would be true. We summarize these results in a ** truth table**:

\(p\) | \(\overline{p}\) |
---|---|

T | F |

F | T |

Example \(\PageIndex{7}\label{eg:prop-07}\)

Find the negation of the following statements:

- George W. Bush is the president of the United States.
- It is not true that New York is the largest state in the United States.
- \(x\) is a real number such that \(x=4\).
- \(x\) is a real number such that \(x<4\).

If necessary, you may rephrase the negated statements, and change a mathematical notation to a more appropriate one.

**Answer**-
- George W. Bush is not the president of the United States.
- It is true that New York is the largest state in the United States.
- The phrase “\(x\) is a real number” describes what kinds of numbers we are considering. The main part of the proposition is the proclamation that \(x=4\). Hence, we only need to negate “\(x=4\)”. The answer is: \[\mbox{$x$ is a real number such that $x\neq4$}.\]
- \(x\) is a real number such that \(x\geq4\).

Hands-on Exercise \(\PageIndex{3}\label{he:prop-03}\)

- \(x\) is an integer greater than 7. 0.4in
- We can factor 144 into a product of prime numbers. 0.4in
- The number 64 is a perfect square.

Since we will be studying numbers throughout this course, it is convenient to introduce some notations to facilitate our discussion. Let

\[\begin{aligned} \mathbb{N} &=& \mbox{the set of natural numbers (positive integers),} \\ \mathbb{Z} &=& \mbox{the set of integers,} \\ \mathbb{R} &=& \mbox{the set of real numbers, and} \\ \mathbb{Q} &=& \mbox{the set of rational numbers.} \end{aligned}\]

Recall that a rational number is a number that can be expressed as a ratio of two integers. Hence, a rational number can be written as \(\frac{m}{n}\) for some integers \(m\) and \(n\), where \(n\neq0\). If you use a word processor, and cannot find, for example, the symbol \(\mathbb{N}\), you may use bold face **N** as a replacement.

We usually use uppercase letters such as \(A\), \(B\), \(C\), \(S\) and \(T\) to represent sets, and denote their elements by the corresponding lowercase letters \(a\), \(b\), \(c\), \(s\), and \(t\), respectively. To indicate that \(b\) is an element of the set \(B\), we adopt the notation

\[b \in B \qquad\mbox{[pronounced as ``$b$ belongs to $B$'']}.\]

Occasionally, we also use the notation

\[B \ni b \qquad\mbox{[pronounced as ``$B$ contains $b$'']}.\]

Consequently, saying \(x\in\R\) is another way of saying \(x\) is a real number.

Denote the set of positive real numbers, the set of negative real numbers, and the set of nonzero real numbers, by inserting the appropriate sign in the superscript:

\[\begin{aligned} \mathbb{R}^+ &=& \mbox{the set of all positive real numbers}, \\ \mathbb{R}^- &=& \mbox{the set of all negative real numbers}, \\ \mathbb{R}^* &=& \mbox{the set of all nonzero real numbers}. \end{aligned}\]

The same convention applies to \(\mathbb{Z}\) and \(\mathbb{Q}\). Notice that \(\mathbb{Z}^+\) is same as \(\N\).

In addition, if \(S\) is a set of numbers, and \(k\) is a number, we sometimes use the notation \(kS\) to indicate the set of numbers obtained by multiplying \(k\) to every number in \(S\).

Example \(\PageIndex{8}\label{eg:kS}\)

The notation \(2\Z\) denotes the set of all even integers. Take note that an even integer can be positive, negative, or even zero.

## Summary and Review

- A proposition (statement or assertion) is a sentence which is either always true or always false.
- The negation of the statement \(p\) is denoted \(\neg p\), \(\altneg p\), or \(\overline{p}\).
- We can describe the effect of a logical operation by displaying a truth table which covers all possibilities (in terms of truth values) involved in the operation.
- The notations \(\mathbb{R}\), \(\mathbb{Q}\), \(\mathbb{Z}\), and \(\mathbb{N}\) represent the set of real numbers, rational numbers, integers, and natural numbers (positive integers), respectively.
- If \(S\) denotes a set of numbers, \(S^+\) means the set of positive numbers in \(S\), \(S^-\) means the set of negative numbers in \(S\), and \(S^*\) means the set of nonzero numbers in \(S\).
- If \(S\) denotes a set of numbers, and \(k\) is a real number, then \(kS\) means the set of numbers obtained by multiplying \(k\) to every number in \(S\).

## Exercises \(\PageIndex{}\)

Exercise \(\PageIndex{1}\label{ex:prop-01}\)

Indicate which of the following are propositions (assume that \(x\) and \(y\) are real numbers).

- The integer 36 is even.
- Is the integer \(3^{15}-8\) even?
- The product of 3 and 4 is 11.
- The sum of \(x\) and \(y\) is 12.
- If \(x>2\), then \(x^2\geq3\).
- \(5^2-5+3\).

Exercise \(\PageIndex{2}\label{ex:prop-02}\)

Which of the following are propositions (assume that \(x\) is a real number)?

- \(2\pi+5\pi = 7\pi\).
- The product of \(x^2\) and \(x^3\) is \(x^6\).
- It is not possible for \(3^{15}-7\) to be both even and odd.
- If the integer \(x\) is odd, is \(x^2\) odd?
- The integer \(2^{524287}-1\) is prime.
- \(1.7+.2 = 4.0\).

Exercise \(\PageIndex{3}\label{ex:prop-03}\)

Determine the truth values of these statements:

- The product of \(x^2\) and \(x^3\) is \(x^6\) for any real number \(x\).
- \(x^2>0\) for any real number \(x\).
- The number \(3^{15}-8\) is even.
- The sum of two odd integers is even.

Exercise \(\PageIndex{4}\label{ex:prop-04}\)

Determine the truth values of these statements:

- \(\pi\in\Z\).
- \(1^3+2^3+3^3 = 3^2\cdot4^2/4\).
- \(u\) is a vowel.
- This statement is both true and false.

Exercise \(\PageIndex{5}\label{ex:prop-05}\)

Negate the statements in Problem [ex:prop-04].

Exercise \(\PageIndex{6}\label{ex:prop-06}\)

Determine the truth values of these statements:

- \(\sqrt{2}\in\Z\)
- \(-1\notin\Z^+\)
- \(0\in\N\)
- \(\pi\in\R\)
- \(\frac{4}{2}\in\Q\)
- \(1.5\in\Q\)

Exercise \(\PageIndex{7}\label{ex:prop-07}\)

Determine whether these statements are true or false:

- \(0\in\Q\)
- \(0\in\Z\)
- \(-4\in\Z\)
- \(-4\in\N\)
- \(2\in3\Z\)
- \(-18\in3\Z\)

Exercise \(\PageIndex{8}\label{ex:prop-08}\)

Negate the following statements about the real number \(x\):

- \(x>0\)
- \(x\leq-5\)
- \(7\leq x\)

Exercise \(\PageIndex{9}\label{ex:prop-09}\)

Explain why \(7\Q=\Q\). Is it still true that \(0\Q = \Q\)?

Exercise \(\PageIndex{10}\label{ex:prop-10}\)

Find the number(s) \(k\) such that \(k\Z=\Z\).