Produced by Charles Wells Revised 2016-09-28 Introduction to this website website TOC website index blog Back to top of Mathematical Reasoning chapter
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.
If $P$ and $Q$ are assertions, then "$P$ and $Q$" is also an assertion. "$P$ and $Q$" is true precisely when both $P$ and $Q$ are true.
The assertion "$P$ and $Q$" is called a conjunction.
The word "conjunction" in English grammar refers to words such as and and "but". "Conjunction" in abmath, as in most writings on logic, refers to a sentence of the form "$P$ and $Q$", not to the word and. See also name and value.
Let $n$ be an integer variable and let $P(n)$ be the assertion "$n\gt9$ and $n$ is even". Then $P(2)$ is false, $P(3)$ is false, $P(12)$ is true and $P(15)$ is false.
You may have noticed that when I defined $P$ and $Q$ above I used the word "and" in the definition. A more satisfactory way to define connectives is to use truth tables. The truth table for and is displayed below. From this table you can see immediately for example that if $P$ is true and $Q$ is false, then "$P$ and $Q$ " is false.
| $P$ | $Q$ | $P$ and $Q$ |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
In the symbolic language, there is a special way to express conjunction of inequalities.
An expression such
as "$a\le x\le b$"
always means "$a\le x$ and $x\le b$",
never "$a\le x$ or $x\le b$".
In math English, a conjunction is normally expressed with the word and, as you might expect. There are some subtleties in the use of the word and, discussed here. See also Wikipedia.
The word "and" between two assertions $P$ and $Q$ produces the conjunction of $P$ and $Q$.
The assertion "$x$ is positive and $x$ is less than $10$" is true if both these statements are true: $x$ is positive", "$x$ is less than $10$".
The word "and" can also be used between two verb phrases to assert both of them about the same subject.
The assertion" $x$ is positive and less than 10" means the same thing as"$x$ is positive and $x$ is less than 10". This mirrors ordinary English usage.
The word "and" may occur between two noun phrases as well
Other words are also used to denote conjunction. Most of them are familiar and do not cause a problem.
All three of these sentences mean "$10\gt9$ and $10$ is even."
One way of writing conjunctions that may be surprising is to use the word but; for example, "$9$ is odd but $9$ is not a prime". (See the Glossary entry for but for another use in math English.) The word "but" between two assertions means logically exactly the same thing as and. The difference is that "but" communicates that what is coming after it may be surprising.
"Although" (and other words – see Suber’s Translation Tips) performs a similar function.
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. The assertion "$P$ or $Q$" is called a disjunction.
Let $P(n)$ be the assertion "($n>9$ or $n$ is even)". Then $P(2)$, $P(10)$ and $P(11)$ are all true, but $P(7)$ is false.
| $P$ | $Q$ | $P$ or $Q$ |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
So "$P$ or $Q$" if true if at least one of $P$ and $Q$ are true, and it is false only if $P$ and $Q$ are both false.
The usual way to express a disjunction in math English is to use the word or, often with "either".
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.
The assertion
$x>0\text{ or }x<2$
is true for any real number $x$. In particular,
$1>0\text{ or }1<2$
is true.
You may be bothered by this assertion since "$1>0\text{ and }1<2$" is also true. It is not wrong to assert "$P$ or $Q$" even in a situation where you could also assert the stronger statement "$P$ and $Q$" (see unnecessarily weak assertion).
In many assertions in conversational English involving or, both cases cannot happen. Authors in non-mathematical English writing may emphasize inclusiveness when it occurs by using "and/or" or by saying something like "or both".
The meaning of or given by the truth table is called the inclusive or.
In mathematical writing, or is almost always inclusive.
Mathematicians rarely use "and/or" because in math writing or already means "and/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.
Negation has the very simple truth table shown below. The assertion "not $P$" is true exactly when P is false.
| $P$ | not $P$ |
| T | F |
| F | T |
These examples show the kinds of problems you can have in negating a mathematical statement.
As far as I know, few people have problems with proving statements involving these three connectives if they occur one at a time. If they are mixed together, things get more complicated, as in the example below and in the DeMorgan Laws.
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:
Therefore it would not be legitimate to deduce the statement "$n$ is odd" from the statement "$n$ is odd or $n$ is prime". See also the discussion in Wikipedia.
The DeMorgan Laws are:
And and Or are interchanged when they are negated
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
"$x+y=10$ and $x\lt7$"
is
"$x+y\ne 10$ or $x\ge7$"
The negation of
"$n$ is even or $n$ is prime"
is
"$n$ is odd and $n$ is composite."
If you have trouble with these examples, try drawing the corresponding Venn Diagrams.
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.
The unit interval $\mathbb{I}=\left\{ x\,|\,0\le x\le 1 \right\}$, which means that $x\in \mathbb{I} $ if and only if both $0\le x$ and $x\le 1$.
So to prove $x\notin \mathbb{I}$ you have to prove that either $x\lt 0$ or $x\gt1$. You don’t have to prove both. In fact, in this particular case you couldn’t prove both!
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.
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 that is both odd and nonprime, for example $9$.
$P\land Q$or
$P\,\&\, Q$or
$P\,\&\&\, Q$or
$PQ$
$P\lor Q$or
$P||Q$or
$P+Q$.
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 "$0$" and "$1$", by "$T$" and "$F$", or by "$\top$" and "$\bot$". Unfortunately in some texts "true" is "$0$" and in others it is "$1$".
The name for the symbol "$\bot$" is "uptack". Isn't that cute?
This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.