abstractmath.org 2.0
help with abstract math


Produced by Charles Wells   Revised 2017-02-09   
Introduction to this website
website TOC    website index    blog   
Back to top of Mathematical Reasoning chapter

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.  

Conjunction

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.

Example

Let $n$ be an integer variable and let $P(n)$ be the assertion "$n\gt9$" and $Q(n)$ the assertion "$n \text{ is even}$". Then "$P(2)\text{ and }Q(2)$" is false and "$P(12)\text{ and }Q(12)$" is true.

Truth table for conjunctions

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

Conjunction of inequalities

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

Examples

Conjunction in math English

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.

"And" between assertions

The word "and" between two assertions $P$ and $Q$ produces the conjunction of $P$ and $Q$.

Example

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

"And" between verb phrases

The word "and" can also be used between two verb phrases to assert both of them about the same subject.

Example

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.

"And" between noun phrases

The word "and" may occur between two noun phrases as well

Example

Other words for conjunction

Other words are also used to denote conjunction.  Most of them are familiar and do not cause a problem. 

Example

All three of these sentences mean "$10\gt9$ and $10$ is even."

But

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.

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.  The assertion "$P$ or $Q$" is called a disjunction.

Example

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.

Truth table for disjunction

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

Disjunction in math English

The usual way to express a disjunction in math English is to use the word or, often with "either".

Examples

Inclusive or

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

                                             $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 inclusive­ness 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

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

Example

Negation in math English

These examples show the kinds of problems you can have in negating a mathematical statement.

Negating inequalities

Methods of proof for and, or and not.

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.

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:

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

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. 

Example

The negation of

"$x+y=10$ and $x\lt7$"

is

 

"$x+y\ne 10$ or $x\ge7$"

Example

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.

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 $\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!

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 that is both odd and nonprime, for example $9$.

And, or and not in the symbolic language of math

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

True and false

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?



Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.