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$".

- The assertion "$5\leq x\leq 7$" means $5\leq x$
**and**$x\leq 7$. Thus it is true for $5$, $6$, $7$, $5.3$ and $6.999$ but false for $3$, $7.001$ and $42$. - The assertion "$5\le x\le 3$" means $5\le x$
**and**$x\le3$. There are no numbers that satisfy this assertion! Students sometimes write "$5\le x\le 3$" to mean $5\le x$**or**$x\le 3$, but that is wrong.

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

- "$3$ and $5$ are greater than $2$".
- "$2$ is less than $3$ and $5$". This might make someone think this is saying that $2$ is less than $3+5$. I don't think this usage occurs very often.

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."

- $10\gt9$;
**also**$10$ is even. - $10$
is
**both**greater than $9$ and even. - $10$
is greater than 9
**as well as**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 statement "$7$ is even or $7$ is odd" is true, because $7$ is odd and a disjunction requires only that at least one of the assertions be true.
- The statement "every integer $n$ is either even or odd" is true.
- The statement "every integer $n$ is either even or a prime" is false.

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.

- "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 "$3\gt2$", then "not $P$" can be worded as "$3$
is
*not greater than*$2$". It is incorrect to give "$3\lt2$" as the negation of $P$. Of course, "not $P$" can also be*reworded*as "$3\le 2$". - The
statement "$2$ divides every integer" is false. Its negation,
which is true, is "There is some integer that $2$
does
*not*divide". You might want to write the negation as "$2$ does not divide every integer". The trouble with that statement is that it is ambiguous: It might be read as "$2$ does not divide*any*integer", which is*not*the negation of "$2$ divides every integer". See negating quantifiers in Wikipedia.

- The negation of $x<y$ is $x\ge y$ (or of course $y\le x$). The negation is not "$x>y$".
- The negation of $x\le y$ is $y>x$.
- The negation of $x>y$ is $x\le y$.
- The negation of $x\ge y$ is $x<y$.

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 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.
- 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.

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" *from the statement* "$n$ is odd or $n$ is prime". See also the discussion in Wikipedia.

The DeMorgan Laws 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$".

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$.

**And**may be denoted by:$P\land Q$

or$P\,\&\, Q$

or$P\,\&\&\, Q$

or$PQ$

**Or**may be denoted by:$P\lor Q$

or$P||Q$

or$P+Q$

.**Not**may be denoted by:"$\neg P$" or "$\tilde{\ }P$" or "$!P$" or "$\overline{P}$".

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.