abstractmath.org 2.0
help with abstract math


Produced by Charles Wells   Revised 2016-09-28

Introduction to this website

website TOC    website index    blog



# 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 $n$ is even". Then $P(2)$ is false, $P(3)$ is false, $P(12)$ is true and $P(15)$ is false.

### Truth table for conjunction

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

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

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

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

• $10\gt9$; also $10$ is even.
• $10$ is both greater than $9$ and even.
• $10$ is greater than 9 as well as 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
• 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.

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

### Negation in math English

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.

### Negating inequalities

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

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

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

## The DeMorgan Laws

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.

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

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

#### 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?