A *statement* \( S \) is a sentence that can be *true* or *false*

- For example, the sentence
*"March has 31 days"*is a true statement. - For example, the sentence
*"June has 31 days"*is a false statement.

A *predicate* \( P(x) \) is a sentence that contains a variable \( x \) that can be chosen from some *domain* set \( D \) such that once a value of \( x \) is chosen, \( P(x) \) becomes a statement that is either true or false.

- For example, the sentence
*"\( x \) has 31 days"*is a predicate with domain \( D \) the set of months. This predicate could be denoted \( P(x) \). It is neither true nor false, because we don't know the value of \( x \). Observe that \( P(March) \) is a true statement, while \( P(June) \) is a false statement.

Often, two predicates can look different but actually have same truth value. That is the idea of *logical equivalence*. Here is the definition:

**symbol:**\( P(x) \equiv Q(x) \)**spoken:**\( P(x) \) is*logically equivalent*to \( Q(x) \)**usage:**\( P(x) \) and \( Q(x) \) are predicates with variable \( x \) and domain \( D \)**meaning:**\( P(x) \) and \( Q(x) \) have the same truth value for every particular choice of value for \( x \) from domain \( D \).

**symbol:**\( NOT(S) \)**usage:**\( S \) is some*statement***meaning:**\( NOT(S) \) is a new statement whose truth value is defined to be the opposite of the truth value of \( S \). That is, the truth \( NOT(S) \) is defined by the following*truth table*.truth of \( S \) truth of \( NOT(S) \) *true**false**false**true***generalization:**The symbol \( NOT( P(x) ) \), where \( P(x) \) is a*predicate*, is a*new predicate*that is defined in the obvious way.**symbol:**\( A \; AN\!D \; B \)**alternate symbol:**\( A \wedge B \) (spoken "\( A \)*wedge*\( B \)".)**usage:**\( A \),\( B \) are*statements***meaning:**\( A \; AN\!D \; B \) is a new statement whose truth value is defined by the following truth table. (From now on, the column headings in truth tables will just give the symbol for the statement, rather than saying*truth of statement*.)\( A \) \( B \) \( A \; AN\!D \; B \) *T**T**T**T**F**F**F**T**F**F**F**F***generalization:**The symbol \( A(x) \; AN\!D \; B(x) \), where \( A(x) \) and \( B(x) \) are both*predicates*, is a*new predicate*that is defined in the obvious way.**symbol:**\( A \; OR \; B \)**alternate symbol:**\( A \vee B \) (spoken "\( A \)*vee*\( B \)".)**usage:**\( A \),\( B \) are*statements***meaning:**\( A \; OR \; B \) is a new statement whose truth value is defined by the following truth table.\( A \) \( B \) \( A \; OR \; B \) *T**T**T**T**F**T**F**T**T**F**F**F***Remark:**Notice that the logical*OR*operation is what is sometimes referred to as the*inclusive or*in regular English. That is, \( A \)*OR*\( B \) is true not just when one of \( A \) or \( B \) is true, but also when they are*both*true.**generalization:**The symbol \( A(x) \; OR \; B(x) \), where \( A(x) \) and \( B(x) \) are both*predicates*, is a*new predicate*that is defined in the obvious way.**sentence:**\(I\!f \; A \; then \; B \)**alternate sentence:**\( A \; implies \; B \)**symbol:**\( A \rightarrow B \)**usage:**\( A \),\( B \) are*statements***meaning:**\( A \rightarrow B \) is a new statement whose truth value is defined by the following truth table.\( A \) \( B \) \( A \rightarrow B \) *T**T**T**T**F**F**F**T**T**F**F**T***generalization:**The symbol \( A(x) \rightarrow B(x) \), where \( A(x) \) and \( B(x) \) are both*predicates*, is a*new predicate*that is defined in the obvious way.- Negate
*AND*and*OR*statements using*deMorgan's Laws*- \( NOT ( A \wedge B ) \equiv NOT(A) \vee NOT(B) \)
- \( NOT ( A \vee B ) \equiv NOT(A) \wedge NOT(B) \)

- Negate the
*conditional statement*in this surprising way:- \( NOT ( A \rightarrow B ) \equiv A \wedge NOT(B) \)

The simplest way to build a new statement from an old one is by using the *negation*

A common way of building a new statement from *two* old ones is by using the *conjunction*, which is also known as the *AND* operation.

Another common way of building a new statement from two old ones is by using the *disjunction*, which is also known as the *OR* operation.

Our third way of building a new statement from two old ones is by building a *conditional statement*, which is also known as an *IF-THEN* statement.

Recall the truth table for the conditional statement \( I\!f \; A \; then \; B \):

\( A \) | \( B \) | \( A \rightarrow B \) |
---|---|---|

T |
T |
T |

T |
F |
F |

F |
T |
T |

F |
F |
T |

We let \( S \) stand for the original conditional statement \( I\!f \; A \; then \; B \). There are three conditional statements that are related to \( S \):

- The
*converse of \( S \)*is the statement \( I\!f \; B \; then \; A \). - The
*inverse of \( S \)*is the statement \( I\!f \; NOT(A) \; then \; NOT(B) \). - The
*contrapositive of \( S \)*is the statement \( I\!f \; NOT(B) \; then \; NOT(A) \).

For an original statement \( S \) of the form \( I\!f \; A \; then \; B \), the truth of the related conditional statements can be determined by making truth tables for them.

Truth table for the *converse of *\( S\):

\( A \) | \( B \) | \( A \) | \( B \rightarrow A \) |
---|---|---|---|

T |
T |
T |
T |

T |
F |
T |
T |

F |
T |
F |
F |

F |
F |
F |
T |

Observe that the *converse of* \( S\) is *not* logically equivalent to \( S \) because \( S\) and the *converse of* \( S\) have different truth tables.

Truth table for the *inverse of *\( S\):

\( A \) | \( B \) | \( NOT(A) \) | \( NOT(B) \) | \( NOT(A) \rightarrow NOT(B) \) |
---|---|---|---|---|

T |
T |
F |
F |
T |

T |
F |
F |
T |
T |

F |
T |
T |
F |
F |

F |
F |
T |
T |
T |

Observe that the *inverse of* \( S\) is *not* logically equivalent to \( S \) because they have different truth tables.

But notice that the *inverse of* \( S\) *is* logically equivalent to the *converse of* \( S\) because they have the same truth tables.

Truth table for the *contrapositive of *\( S\):

\( A \) | \( B \) | \( NOT(B) \) | \( NOT(A) \) | \( NOT(B) \rightarrow NOT(B) \) |
---|---|---|---|---|

T |
T |
F |
F |
T |

T |
F |
T |
F |
F |

F |
T |
F |
T |
T |

F |
F |
T |
T |
T |

Observe that the *contrapositive of* \( S\) *is* logically equivalent to \( S \) because they have the same truth tables. Knowing how to exploit this fact will be incredibly useful in this course and in all future math that you do.

Definition of the *existential quantifier*

**symbol:**\( \exists x \in D \left( P(x) \right) \)**usage:**\( P(x) \) is some*predicate*containing the variable*x*with domain*D***meaning:**There exists some \( x \) in \( D \) such that \( P(x) \) is true.**more terminology:**The symbol \( \exists \) is called the*existential quantifier*; The whole sentence "\( \exists x \in D \left( P(x) \right) \)" is called an*existentially quantified statement***example:**- Let \( D \) be the set of cars in the Morton Hall parking lot.
- Let \( x \) be a variable with domain \( D \).
- Let \( Silver(x) \) be a the predicate
*"\( x \) is silver."* - Let \( A \) be the statement \( \exists x \in D \left( Silver(x) \right) \)
- Then Statement \( A \) means
*"There exists a car in the Morton Hall lot that is silver."*

Definition of the *universal quantifier*

**symbol:**\( \forall x \in D \left( P(x) \right) \)**usage:**\( P(x) \) is some*predicate*containing the variable*x*with domain*D***meaning:**For every \( x \) in \( D \), \( P(x) \) is true.**more terminology:**The symbol \( \forall \) is called the*universal quantifier*; The whole sentence "\( \forall x \in D \left( P(x) \right) \)" is called a*universally quantified statement***example:**- Same domain \( D \), variable \( x \) and predicate \( Silver(x) \) as in the previous example
- Let \( B \) be the statement \( \forall x \in D \left( Silver(x) \right) \)
- Then Statement \( B \) means
*"Every car in the Morton Hall lot is silver."*

Consider the predicate *"\( x \) is red."* Clearly the predicate is a sentence about car \( x \). In general, *a predicate is a sentence about the variable \( x \).* Once an actual value for \( x \), an actual car, is chosen and substituted into \( Red(x) \), the predicate becomes a *statement* about that particular car, a statement that is either true or false. For exampe. The symbol \( Red( \) *Mark's car* \( ) \) denotes the statement *"Mark's car is red*. This is a statement about Mark's car. (It is a false statement.)

Now consider two sets:

- Let \( V \) be the set of cars in the Village Bakery parking lot.
- Let \( C \) be the set of cars in the Columbus Airport parking lots (all of the lots).

- Let \( A \) be the statement \( \exists x \in V \left( Red(x) \right) \). Statement \( A \) means
*"There exists a car in the Village Bakery parking lot that is red."* - Let \( B \) be the statement \( \exists x \in C \left( Red(x) \right) \). Statement \( B \) means
*"There exists a car in the Columbus Airport parking lots that is red."*

Return to an earlier example of a universal statement \( B \):

The negation of this statement would be the following

Notice that the original statement \( B \) is a *false* statement, while its negation is a *true* statement. That makes sense.

Expressinging our observations about statement \( B \) in symbols, we have

Generalizing to other universal statements, we would write

Notice that the *negation of a universal statement* will be an *existential statement*.

Return to an earlier example of an existential statement \( a \):

The negation of this statement would be the following

Notice that the original statement \( A \) is a *true* statement, while its negation is a *false* statement. That makes sense.

Expressing our observations about statement \( A \) in symbols, we have

Generalizing to other existential statements, we would write

Notice that the *negation of an existential statement* will be a *universal statement*.

An *existentially quantified conditional statement* would be just what it sounds like: a statement of the following form:

- \( \exists x \in D \left( I\!f \; A(x) \; then \; B(x) \right) \)
- \( \exists x \in D \left( A(x) \; implies \; B(x) \right) \)
- \( \exists x \in D \left( A(x) \rightarrow B(x) \right) \)

A *universally quantified conditional statement* would be just what it sounds like: a statement of the following form:

- \( \forall x \in D \left( I\!f \; A(x) \; then \; B(x) \right) \)
- \( \forall x \in D \left( A(x) \; implies \; B(x) \right) \)
- \( \forall x \in D \left( A(x) \rightarrow B(x) \right) \)

The simplest way to negate a statement or a predicate is to simply put the statement or predicate in parentheses and put the word \( NOT \) in front. The resulting sentence could be read as *"Not statement"*, or *"It is not true that statement."* This applies, in particular to *quantified conditional statements*.

For example

- Let \( C \) be the set of cars in the Columbus Airport parking lots (all of the lots).
- Let \( x \) be a variable with domain \( C \).
- Let \( Toyota(x) \) be the predicate
*" \( x \) is a Toyota."* - Let \( blue(x) \) be the predicate
*" \( x \) is blue."* - Let \( S \) be the statement \( \forall x \in C \left( I\!f \; A(x) \; then \; B(x) \right) \). Statement \( S \) means
*"For every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."* - The simplest way to negate \( S \) would be to write
- \( NOT(S) \)
- \( NOT \left( \forall x \in C \left( I\!f \; A(x) \; then \; B(x) \right) \right) \)
*"It is not true that for every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."*

But while that long sentence is technically the the negation of \( S \), the long sentence is rather confusing. What does it really mean to say that that all of that stuff is not true? What does the phrase *it is not true that* do to all of the stuff that follows to its right in the sentence?

When writing sentences using the word *not*, or the phrase *it is not true that*, clarity is often improved if the sentence can be rewritten with word *not* moved as far to the right in the sentence as possible. The reason is that then there are not many words to the right of the word *not* in the sentence, so it won't be as hard to figure out what the word *not* does to all the stuff that follows to its right in the sentence.

So our goal in writing sentences containing the word *not* will be to figure out how to rewrite them so that the *not* is as far to the right as possible while retaining the same meaning as the original sentence. This goal can be easier to achieve if we convert our sentences to logical notation, and then do the rewriting in logical notation, and then convert the final logical notation to a sentence.

Here is an example of that process at work, using the above example.

**Original Sentence: ** We start with the statement \( NOT(S) \)

**in symbols:**\( NOT \left( \forall x \in C \left( I\!f \; A(x) \; then \; B(x) \right) \right) \)**in words:***"***It is not true that**for every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."

**Move the NOT one place to the right**: This moves the

**in symbols:**\( \exists x \in C \left( NOT \left( I\!f \; A(x) \; then \; B(x) \right) \right) \)**in words:***"There exists a car in the Columbus Airport parking lots such that***it is not true that**if the car is a Toyota, then the car is blue."

**Move the NOT further to the right**: This can only be done by negating the conditional statement. Note that the result will be an

**in symbols:**\( \exists x \in C \left( A(x) \; AND \; NOT(B(x)) \right) \)**in words:***"There exists a car in the Columbus Airport parking lots such that the car is a Toyota and the car is***not**blue."

Realize that we have now written three sentences in words that all mean the same thing. They are all \( NOT(S) \). Most people would find the third version to be the easiest to understand.

There is a *practical reason* for wanting to rewrite our sentences in the way just described, so that they are easier to understand. Remember the original statement \( S \)

- \( S \) is the statement:
*"For every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."*

*"***It is not true that**for every car in the Columbus Airport parking lots, if the car is a Toyota, then the car is blue."*"There exists a car in the Columbus Airport parking lots such that***it is not true that**if the car is a Toyota, then the car is blue."*"There exists a car in the Columbus Airport parking lots such that the car is a Toyota and the car is***not**blue."

This same sort of thing will happen in our course. That is, it will happen that we will need to prove a statement that contains the word *not*. It will be be much simpler to figure out how to prove the statement if the statement is written in a form that has the word *not* appearing as far to the right as possible. That is the *practical reason* referred to above.

In summary, when writing the negation of a logical statement, whether in words or in symbols, we will always strive to rewrite the negation in an equivalent form that has the word *NOT* appearing as far to the right as possible.

To prove a statement of the form \( I\!f \; A \; then \; B \), one builds a proof frame as follows:

**Proof that \( A \rightarrow B \)**

- Suppose that \( A \) is true.
*Some statement (with some justification)**Some statement (with some justification)**Some statement (with some justification)**Some statement (with some justification)*- Therefore, \( B \) is true
*(with some justification)*

**End of proof**

To *disprove* a conditional statement, one must prove that the *negation* of the conditional statement is *true*. Remember that the negation of the conditional statement \( I\!f \; A \; then \; B \) is not another conditional statement. Rather, the negation is an \( AND \) Statement: \( NOT ( I\!f \; A \; then \; B ) \equiv A \; AND \; NOT(B) \)

**Proof that \( NOT(A \rightarrow B) \). That is, Proof that \( A \; AND \; NOT(B) \)**

*Some statement (with some justification)**Some statement (with some justification)**Some statement (with some justification)*- \( A \) is true.
*(with some justification)* *Some statement (with some justification)**Some statement (with some justification)**Some statement (with some justification)*- \( B \) is false.
*(with some justification)*

**End of proof**

Prove an *existential* statement by giving an example of an element \( x \) in the domain \( D \) that makes \( P(x) \) true.

- If domain is a \( D \) finite set, then one can check all of the \( x \) in the domain \( D \) to find their corresponding values of \( P(x) \). This is called the
*method of exhaustion*. For example, consider the universally-quantified statement \( W \):*"Every car in the Morton Lot has all its windows up."*To prove this statement, one would have to go through the parking lot and check every car. - If domain is a \( D \) an infinite set, then one can't possibly do the method of exhaustion. Must do a
*general proof*.- Suppose \( x \) is a generic (unkown) particular element of the domain \( D \).
- Show that \( P(x) \) is true.
- By the
*principle of generalizing from generic particular example (GFGPE)*, conclude that \( P(x) \) is true for all \( x \) in \( D \).

(page maintained by Mark Barsamian, last updated Jan, 2022)