abstractmath.org
help with abstract math
Produced by Charles Wells. Home Website TOC Website Index Blog
Back to Math Reasoning
Last
edited 2/24/2009 10:27:00 AM
|
|
And,
or, not
Assertions
can be combined into logical
constructions (compound assertions) using combining operators called logical connectives. This chapter is
concerned with the connectives "and", "or" and "not".
“And” and “or”
|
The word “conjunction” in English
grammar refers to words such as “and”, “or” and “but”. “Conjunction” here, as in most writings on
logic,
refers to a sentence of the form “P and Q”, not to
the word “and”. See name and
value. |
Conjunction
If
P and Q are assertions, then "P
and Q" is also an assertion,
and it is true precisely when both P and Q are true. “P and Q” is called the conjunction
of P and Q.
Example
Let n be an integer variable and let P(n) be the assertion “( and
n
is
even)”. Then
P(
Disjunction
If P and Q are assertions, then "P or Q" is also an assertion, and it is true precisely when at least one of P and Q are true. “P or Q” is called the disjunction of P and Q.
Example
Let P(n) be the assertion “( or n is even)”.
Then P(
Truth tables
You may have noticed that when I defined
“and” above I used the word “and” in the definition. A more satisfactory way to define connectives is to use truth tables. The truth tables for “and” and “or” are
displayed here. From these tables you
can see immediately for example that if P
is true and Q is false, then “P and Q” is false but “P or Q” is true.
Symbolic notation for connectives
The connective "and" may be denoted by " "
or "&", or by juxtaposition.
For example if P and Q are assertions, “P and Q” could be written
,
P&Q or PQ.
“Or” may be denoted by “ ” or “+”.
This notation makes “and” and “or” look like algebraic operations. In fact they are operations in the Propositional Calculus (MW, Wik) and in Boolean Algebra (MW, Wik). (Boolean algebra is an abstraction of the Propositional Calculus.)
In computer science and logic, “True” and “False” may be
denoted by
Usage
These symbols (and the quantifier symbols) are not often seen in math research papers or books except when the books concern logic. Some mathematicians frequently use these symbols in lectures and others never do. Mathematicians differ sharply on using these symbols, taking one of two attitudes:
¨ Lectures or notes filled with logical symbols as abhorrent and hard to read.
¨ It
is best to use the symbols,
because we don’t then have to translate the mathematical
English into the corresponding logical structures.
Conjunction of inequalities
In the symbolic language, there is a special way to express conjunction of inequalities.
Notation such as “ ” means
and
.
Expressions such
as always denote a conjunction,
never
a disjunction.
Example
The statement means
and
. There are no numbers that satisfy this
statement! Students sometimes write
to mean
or
,
but that is wrong.
Conjunction in math English
The statement “P and Q” is normally expressed with the word “and”, as you might expect. There are many subtleties in the use of the word “and” which are discussed under that heading. See also Wikipedia.
Other words are used, too. Most of them are familiar and do not cause a problem.
Examples
¨
10 >
¨
¨
But
One way of writing conjunctions that may be surprising is to
use the word “but” as in “ see Suber’s
Translation Tips) performs a similar function.
Disjunction in math English
The usual way to express disjunction is to use the word “or”, often with “either”.
Examples
The statement “every integer n is either even or odd” is true.
The statement “
Example
If all you know
about n is given by the statement “n is odd or n is prime”, the you
know from the truth table only that one of the following three possibilities is correct:
¨ n is odd but not prime
¨ n
is prime but not odd
¨ n
is both prime and odd.
Therefore it would
not be
legitimate to deduce the statement “n is odd”.
See also the
discussion in Wikipedia.
Inclusive or
|
If
P and Q are both true, then not only is “P or Q” true but “P and Q” is also true. It is not wrong
to assert “P or Q” even though you
could assert a stronger statement “P
and Q” (see unnecessarily weak assertion). |
The truth table for “or” says that if P and Q are both true, then “P or Q” is true. This is because the definition of “P or Q” says that “P or Q” is true “precisely when at least one of P and Q are true. (This is an excellent example of the literal nature of mathematical language.)
Example
The assertion
is true for any real number x.
You may be bothered by this assertion, perhaps because in
many assertions in conversational English involving "or", both cases cannot happen. Authors may emphasize
the inclusiveness by saying something like "or both"; for example, “ or both”.
Exercise
For how many numbers x
are both x > 0 and
x < 2
true? Answer.
The meaning of “or” given by the truth table is called the inclusive or.
In mathematical writing, “or” is almost always inclusive.
If
mathematicians want to insist that exactly one of P and Q is true they
would say “Either P or Q but not both” or something similar.
Other words
¨ The phrase “and/or” may be used to emphasize the inclusiveness of the “or”. It is rarely seen in mathematical writing.
¨ “Neither
P nor Q” means “not P and
not Q”.
Methods of proof for “and” and “or”.
As far as I know, few
people have problems with proving statements involving “and” and “or”. Here they are, summed up:
¨ If you know P
is true then you know “P or Q” is true.
¨ If you know Q
is true then you know “P or Q” is true.
¨ If you know “P or Q” then you know
that one or both of P and Q are true.
¨ If you know “P and Q” is true then you
know P is true.
¨ If you know “P and Q” is true then you
know Q is true.
¨ If you know P
is true and you know Q is true then
you know “P and Q” is true.
Negation
Negation has the
very simple truth
table shown on
the right. The assertion “not P” is true exactly when P is false.
|
P |
not
P |
|
T |
F |
|
F |
T |
Expressing negation
In the symbolic language
In the symbolic language, the negation of P may be denoted
¨
“ ”, used in logic and Boolean algebra.
¨
“ ”, used in logic.
¨ “!P”, used in many computer languages.
¨
“ ”, used in Boolean algebra.
In mathematical English
These examples show the kinds of problems you can have in negating a mathematical statement.
¨
The statement “
¨ “Neither
P nor Q” is not
the negation of “P or
Q”.
It is the negation of “P and Q”. See the Demorgan
Laws.
¨
Negating an assertion
is not necessarily the same thing as stating its opposite. If P
is the proposition “ ”, then “not P” is "
” as the negation. Of course, “not P” can be reworded as “
”. (See
below).
Methods of proof for negation
The rules for negation are simple and obvious:
¨ If you know P is true then you know “not P” is false.
¨
If you know P
is false then you know “not P” is
true.
¨
If you know “not P” is true then you know P
is false.
¨
If you know “not P” is false then you know P
is true.
It follows from those rules that negation cancels: “not not P” has the same truth value as P.
Negating
inequalities
¨ The negation of is
(or of course
). The negation is not “
”.
¨ The negation of is
.
¨ The negation of is
.
¨ The negation of is
.
The
DeMorgan Laws
Consider what happens when you negate a conjunction. The statement “not (P and Q)” means that “P and Q” is false. Look at the truth table for “and”: this means that one of P
and Q is false;
it does
not require both of them to be false.
Example
The negation of “ ” is “
”, which is the same as “
”.
This is one of the two DeMorgan Laws. They are:
“not (P and Q)” has the same truth value as “not P or not Q”.
“not (P or Q)” has the same truth value as “not P and not Q”.
Speaking
loosely,
Using the DeMorgan Laws in proofs
Proving conjunctions false
To
prove that “P and Q” is false you have to prove that either P is false or that
Q is false. You don’t have to prove that
both are false.
Example+
The unit
interval , which means that
if and only if both
and
. So to prove
you have to
prove that either
or
. You don’t have to prove both. In fact, in this particular case you couldn’t prove both!
Proving
disjunctions false
To
prove that “P or Q” is false you have to prove that both P
is false and Q is false.
You may be tempted to prove that
only one of P and Q is false. But then you have not done everything required.
Example
Consider the statement, "A positive integer is either even or it is prime". (See indefinite article). This statement is false. To show it is false, you must find a positive integer which is both odd and nonprime, for example 9.
Appendix
Exercise
For how many x
are both x > 0 and
x < 2
true?
Answer
By convention, x is a real number, so there are infinitely many such x. If you said “Only the number 1” you may have been making the every number is an integer mistake.
Nevertheless a careful writer would have written, “For how many real numbers x …” Back.