abstractmath.org

help with abstract math

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

Last edited 1/31/2008 10:30: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”

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

Text Box: P Q P or Q T T T T F T F T T F F F Text Box: P Q P and Q T T T T F F F T F F F F 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 juxtaposition.  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 are not often seen in math research papers or books except when they concern logic.  Some mathematicians frequently use these symbols in lectures and others never do.  Many regard lectures or notes filled with logical symbols as abhorrent and hard to read.  Others prefer  the symbols, because they don’t then have to translate the mathematical English into the corresponding logical structures.

Conjunction of inequalities

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

Notation such as “  ” means  and .

Expressions like this always denote a conjunction, not 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.

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