2.1: Propositions

Last updated
Save as PDF

Page ID: 23235

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

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 statement, or an assertion) to be a sentence that is either true or false, but not both.

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¹. 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 $\sim p$ or $\neg p$, both of which are pronounced as “not $p$.” The similarity between the notations $\sim 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.

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$, $\sim 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.

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$.

Answer: Only (a), (c), and (e) are propositions.

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.

Answer: (a) false (b) false (c) false (d) true

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

Determine the truth values of these statements:

$\pi\in\mathbb{Z}$.
$1^3+2^3+3^3 = 3^2\cdot4^2/4$.
$u$ is a vowel.

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

Negate these statements:

$\pi\in\mathbb{Z}$.
$1^3+2^3+3^3 = 3^2\cdot4^2/4$.
$u$ is a vowel.

Answer: (a) $\pi\notin\mathbb{Z}$ (b) $1^3+2^3+3^3 \neq 3^2\cdot4^2/4$ (c) $u$ is not a vowel

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

Negate the following statements about the real number $x$:

$x>0$
$x\leq-5$
$7\leq x$

Search

Text Color

Text Size

Margin Size

Font Type

\(p\)	\(\overline{p}\)
T	F
F	T