Math 170 lecture notes for January 23, 2003

Mathematics and politics
Lecture notes, 1/23/03

Current assignments:
Homework will be due Tuesday, Feb. 4. It will be posted on the web site tomorrow.

Introduction to mathematical logic:

Coalition of the willing (group activity)

Statements -- true and false

Logical operators (NOT, AND, OR)

Truth tables

"Coalition of the willing"

The handout

Don't assume anything other than what is given.
If you have questions, ask!
We will soon study a more systematic way of doing this.

Symbolic logic

In mathematical logic, statements are declarative sentences which are either true or false.
Symbolically we often denote them by a capital letter.
Examples:

"Nadia Masri is the teaching assistant for this course"
This is a statement. It is true, and everyone agrees.
- "Shopping is fun"
  This is not a statement, since it is an opinion.
- "Jerry thinks shopping is fun"
  This is not a statement, since "fun" has not been clearly defined.
- "Jerry goes shopping every weekend"
  This is a statement.
"George W. Bush used cocaine in 1972"
This is a statement. It is unambiguous, and it is either true or false. Most people don't know for sure and two people may violently disagree about its validity.
- "Bill Clinton did not have sexual relations with that woman"
  This is not a statement until the terms "that woman" and "sexual relations" are defined.
- "Bill Clinton did not have oral sex with Monica Lewinsky"
  This is a statement, even though it is false.
"x=3"
This is not a statement since x has not been defined. (We will come back to this, though.)

Suppose P is a statement, which may be true or false. The negation of P is a new statement which may be denoted by either NOT P
¬P. If P is true, then ¬P is false. If P is false, then ¬P is true.

Example:
Suppose P="Dick Cheney is a registered Democrat." Then ¬P="Dick Cheney is not a registered Democrat," or "It is not the case that Dick Cheney is a registered Democrat." P is false, so ¬P is true.
Notice that ¬P is not equivalent to "Dick Cheney is a registered Republican," since P could be false for other reasons.

Suppose P and Q are both statements, each of which may be either true or false. The "and" operator is denoted by either P AND Q,
P/\Q, and it is defined so that it is true if P is true and Q is also true. It is false if P is false, if Q is false, or if both are false.

Examples:
Suppose P="Philadelphia is in Pennsylvania," and Q="Fred Flintstone was our nation's first President."

P/\Q = "Philadelphia is in Pennsylvania, and Fred Flintstone was our nation's first President." is false since the second part is false.
P/\¬Q = "Philadelphia is in Pennsylvania, but Fred Flintstone was not our nation's first President." is true since both parts are true.
¬P/\¬Q = "Philadelphia is not in Pennsylvania, nor was Fred Flintstone our nation's first President." is false since the first part is false.
¬P/\Q = "Philadelphia is not in Pennsylvania, but Fred Flintstone was our nation's first President." is false since both parts are false.

Again suppose P and Q are both statements, each of which may be either true or false. The "or" operator is denoted by either P OR Q,
P\/Q, and it is defined so that it is true if P is true, if Q is true, or if both P and Q are true. It is false only when P is false and Q is false.

Important:This is the "inclusive or," which is sometimes how we use "or" in English. e.g. "He must be crazy, or stupid!" (the target could be both crazy and stupid).

Sometimes in English we use the "exclusive or," which means one or the other is true, but not both. e.g. "You will do what I say or I will bomb your country" (if you do what I say, I won't bomb your country, at least one would hope).

To avoid ambiguity, in mathematics we always use "or" in the inclusive sense.

Examples:
Suppose P="Today is January 23rd," and Q="Today is Wednesday." Then:

P\/Q = "Today is January 23rd, or it's a Wednesday." is true, since the first part is true.
P\/¬Q = "Today is January 23rd, or it's not Wednesday." is true, since both parts are true.
¬P\/¬Q = "Today is not January 23rd, or it's not Wednesday." is true, since the second part is true.
¬P\/Q = "Today is not January 23rd, or it's Wednesday." is false, since both parts are false.

The reason we use "or" in the inclusive sense is to make it the opposite of "and."