abstractmath.org

help with abstract math

`Produced by Charles Wells.  Home    Website TOC    Website Index   Blog   `
` Back to Math Reasoning`

Last edited 2/24/2009 10:27:00 AM

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

# “And” and “or”

 The word “conjunction” in English grammar refers to words such as “and”, “or” and “but”.  “Conjunction” here, as in most writings on logic, refers to a sentence of the form “P and Q”, not to the word “and”.  See name and value.

## Conjunction

If P and Q are assertions, then "P and Q" is also an assertion, and it is true precisely when both P and Q are true.   P and Q” is called the conjunction of P and Q.

#### Example

Let n be an integer variable and let P(n) be the assertion “(  andniseven)”. Then P(2) is false, P(12) is true and P(15) is false.

## 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.  P or Q” is called the disjunction of P and Q.

#### Example

Let P(n) be the assertion “(  or n  is even)”.  Then P(2) , P(10) and P(11)  are true, but P(7) is false.

## Truth tables

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.

## Symbolic notation for connectives

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 (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; unfortunately in some texts “true” is 0 and in others it is 1!

### Usage

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.

## Conjunction of inequalities

In the there is a special way to express conjunction of inequalities.

Notation such as “  ” means  and .

Expressions such as  always denote a conjunction,

never a disjunction.

#### Example

The statement  means  and .  There are no numbers that satisfy this statement! Students sometimes write  to mean  or , but that is wrong.

## Conjunction in math English

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.

#### Examples

¨ 10 > 9; 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” as in “9 is odd but 9 is not a prime”.  (See 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 in math English

The usual way to express disjunction is to use the word “or”, often with “either”.

#### Examples

The statement “every integer n is either even or odd” is true.  The statement “7 is even or 7 is odd” is also true, because 7 is odd.

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

### Inclusive or

 If P and Q are both true, then not only is “P or Q”  true but “P and Q”  is also true.    It is not wrong to assert “P or Q”  even though you could assert a stronger statement  “P and Q”  (see unnecessarily weak assertion).

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

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

#### Exercise

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.

In mathematical writing, “or” is almost always inclusive.

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.

### Other words

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

## Methods of proof for “and” and “or”.

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

Negation has the very simple truth table shown on the right.  The assertion “not P” is true exactly when P is false.

 P not P T F F T

## Expressing negation

### In the symbolic language

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.

### In mathematical English

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

¨ The statement “2 divides every integer” is false.  Its negation, which is true, is “There is some integer that 2 does not divide”.  It would be wrong to write the negation as “All integers are not divisible by 2”.  See negating quantifiers.

¨ “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 "3 is not greater than 2".It is incorrect to give “  ” as the negation. Of course, “not P” can be reworded as “  ”.  (See below).

## Methods of proof for negation

The rules for negation are simple and obvious:

 Math uses classical logic, which means among other things that “not not P” has the same truth value as P  This fails in intuitionistic logic (MW, Wik), which has uses in math and elsewhere.

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

### Negating inequalities

¨  The negation of  is  (or of course  ).  The negation is not  .

¨  The negation of  is .

¨  The negation of  is .

¨  The negation of  is  .

# The DeMorgan Laws

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 “  ” is   ”, which is the same as “  ”.

This is one of the two DeMorgan Laws.  They 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”.

Speaking loosely,

## 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 , which means that  if and only if 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!

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

# Appendix

#### Exercise

For how many  x are both x > 0 and x < 2 true?