Last edited 2/24/2009 10:27:00 AM
And, or, not
Let n be an integer variable and let P(n) be the assertion “( andnis)”. Then
Let P(n) be the assertion “( or n is even)”.
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.
The connective "and" may be denoted by " " or "&", or by 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 ( , ) and in Boolean Algebra ( , ). (Boolean algebra is an of the Propositional Calculus.)
In computer science and logic, “True” and “False” may be
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.
In thespecial way to express conjunction of inequalities.there is a
The statement means and . There are no numbers that satisfy this statement! Students sometimes write to mean or , but that is wrong.
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.
One way of writing conjunctions that may be surprising is to
use the word “but” as in “
The usual way to express disjunction is to use the word “or”, often with “either”.
The statement “every integer n is either even or odd” is true.
The statement “
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.
See also the discussion in Wikipedia.
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.)
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”.
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.
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.
¨ 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”.
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 has the very simple truth table shown on the right. The assertion “not P” is true exactly when P is false.
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.
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 "
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.
¨ The negation of is (or of course ). The negation is not “ ”.
¨ The negation of is .
¨ The negation of is .
¨ The negation of is .
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.
The negation of “ ” is “ ”, which is the same as “ ”.
This is one of the two DeMorgan Laws. They are:
The unit interval , which means that 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!
You may be tempted to prove that only one of P and Q is false. But then you have not done everything required.
Consider the statement, "A positive integer is either even or it is prime". (See ). This statement is false. To show it is false, you must find a positive integer which is both odd and nonprime, for example 9.
For how many x are both x > 0 and x < 2 true?
Nevertheless a careful writer would have written, “For how many real numbers x …” Back.