Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 1.1 Statements

statement
a sentence that is either true or false

Example 1.1.1. Logical statements.

  1. All prime numbers are odd.
  2. Some trees have leaves and some trees have needles.
  3. If you pay attention in class and work through all the homework problems, then you will do well in this course.
substatement
part of a logical statement that could be considered a statement on its own
simple statement
does not contain any proper substatements
compound statement
contains two or more substatements
connective
a connecting word between substatements in a compound statement

Example 1.1.3. Simple and compound statements.

Reconsidering the statements in Example 1.1.1:
  1. statement 1 is simple;
  2. statement 2 is a compound statement made up of two (simple) substatements linked by the connective “and”; and
  3. statement 3 is a compound statement made up of two substatements linked by the connective “if … then …”, where the substatement that constitutes the “if” part is itself a compound statement.
The substatements in a compound statement can be related to each other by connectives in various ways.

Definition 1.1.4. Five basic connectives.

negation
“not”
conjuction
“and”
disjunction
“or”
conditional
“if … then …”
biconditional
“if and only if”
Given statements \(A\) and \(B\text{,}\) we use these connectives to construct new statements:
negation of \(A\)
not \(A\)
conjuction of \(A\) and \(B\)
\(A\) and \(B\)
disjunction of \(A\) and \(B\)
\(A\) or \(B\)
conditional where \(A\) implies \(B\)
if \(A\) then \(B\)
biconditional involving \(A\) and \(B\)
\(A\) if and only if \(B\)

Remark 1.1.5.

  1. All statements we will consider can be constructed starting from a finite number of simple statements and modifying/joining them using connectives as above.
  2. Always take “\(A\) or \(B\)” to mean “\(A\) or \(B\) or both” (known as inclusive or). However, in everyday language it may be reasonable to take “either \(A\) or \(B\)” to mean “(\(A\) or \(B\)) and not (\(A\) and \(B\))” (known as exclusive or).
  3. The conditional and biconditional connectives are actually superfluous — they can be constructed from the first three. (See Worked Example 2.1.2 and Exercise 2.5.5.) But they occur frequently, and such constructions from other connectives obscure their meaning, so it is more convenient to include these two connectives in our list of of basic connectives.

Example 1.1.6. Translating everyday English into logical statements.

A conversation.
Alice
It is raining.
Bob
No, it isn’t.
Alice
Either it’s raining or it isn’t.
Bob
How can we decide?
Alice
If we go outside and we get wet, then it’s raining.
Bob
We’d get wet outside if the sprinklers are on, too.
Alice
Don’t be silly!
Alice (continuing…)
We’ll get wet if it’s raining, and this is the only way we’ll get wet.
Let us rewrite the above conversation to clearly identify the substatements and connectives.
Alice
it is raining
Bob
not (it is raining)
Alice
(it is raining) or (not (it is raining))
Bob
[not a statement!]
Alice
if ((we are outside) and (we get wet)) then (it is raining)
Bob
if ((we are outside) and (the sprinklers are on)) then (we get wet)
Alice
[not a statement!]
Alice
if (we are outside) then ((we get wet) if and only if (it is raining))
Strictly speaking, many mathematical statements are not logical statements, for a different reason then the one used in the test above.

Example 1.1.8. An ambiguous mathematical statement.

The phrase “\(f\) is a differentiable function” is not a logical statement, since whether it is true or false depends on the free variable \(f\text{.}\) For example, if we substitute the function \(f(x) = x\) into this statement, the statement becomes true. However, if we substitute the function \(f(x) = \abs{x}\text{,}\) the statement becomes false. We will deal with this issue in Chapter 4.
<Prev^TopNext>