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, 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. 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)=|x|, the statement becomes false. We will deal with this issue in Chapter 4.
<Prev^TopNext>