# Statements and Truth Values

A statement is a sentence that is either true, or false, but not both. In a logical form statement, p stands for the first variable, and q stands for the second variable. The truth value is whether the statement is true, or false.

The negation of p, denoted ∼p, is the statement "it is not the case that p." ∼p is read as "not p." The conjunction of p and q, denoted p∧q, is read as "p and q." p∧q is only true if both p and q are true. In logical form,  "p but q" means the same as "p and q." The dis-junction of p and q, denoted p∨q, is read as "p or q." p∨q is true if either p is true, q is true, or both are true. p∨q is only false if both p, and q are false. To use the symbol ≡  is to say something is logically equivalent to something else.

An example of ∼ p ∧ q in plain English would be "Bob does not have a watch, and he missed the bus." If there is a negation in the statement, always use the word "not" for the negation.

The symbols and their meanings:

≡ means "logically equivalent"

∧ means "and"

∨ means "or"

∼ means "not"

The following is an example of a truth table. Use truth tables to help you figure out the truth values of statements.

 p q p ∧ q p ∨ q ∼ p ∼ q T T T T F F T F F T F T F T F T T F F F F F T T

Sometimes there is more than two variables. Such as ∼ p ∧ (q ∨ r). This would be read as "not p, and q or r." Use parenthesis the same way as you would a normal mathematical equation. Use parenthesis to separate the variables into groups.

To write a statement, start with the first variable. Then write the relation to the second variable, or variables. Finally, write the last variable.

### Test Yourself

• T
• F

Choose the correct truth value for the missing value.

 p q ∼ p p ∧ q ∼ p ∧ q T T F T T F F F F F T T F T F F T F F

# Conditional Statements

A conditional statement is either an "if-then," or an "if and only if statement." The first element is the hypothesis and the second element is the conclusion.

⇒ ≡ if-then

⇔ ≡ if and only if

To write a conditional statement, simply write the first element, then the matching arrow, then the second element.

In an if-then statement, if the first element is false, then it doesn't matter what the truth value of the second element is. If the truth value of the first statement is false, then the truth value of a if-then statement will always be true by fallacy. In an if and only if statement, both elements must be true for a true truth value.

## Examples:

Tom takes a walk if and only if it is not raining. This can be written as: Tom takes a walk ⇔ it is not raining. So Tom will only take a walk if it is not raining.

Tom does not take a walk if it is raining. This can be written as: Tom does not take a walk ⇒ it is raining. So Tom may not take a walk even if it is not raining, but Tom will not take a walk if it is raining.

 p q p ⇒ q p⇔q T T T T T F F F F T T F F F T F

p ⇒ q

### Converse Statement

q ⇒ p

Simply reverse the order of the two elements to write a converse statement. A converse statement will not have the same truth value of the original statement.

### Contrapositive Statement

∼ q ⇒ ∼ p

Take the negation of both elements, and reverse the order to write a contrapositive statement. A contrapositive statement always has the same truth value as the original statement. Therefore, they are logically equivalent.

Original Statement ≡ Contrapositive Statement

### Inverse Statement

∼ p⇒ ∼ q

Take the negation of both elements to write an inverse statement. An inverse statement will not have the same truth value of the original statement. Since the inverse of the original statement is the contrapositive of the converse of the original statement, the inverse and converse will always have the same truth value. The inverse and converse are logically equivalent.

Converse Statement ≡ Inverse Statement

 p q ∼p ∼q p ⇒ q q ⇒ p ∼q⇒∼p ∼p⇒∼q T T F F T T T T T F F T F T F T F T T F T F T F F F T T T T T T

### Test Yourself

• If Sally cannot buy milk, then she cannot go to the store.
• If Sally cannot go to the store, then she cannot buy milk.
• If Sally can buy milk, then she can go to the store.

Choose the contrapositve of the statement:

If Sally can go to the store, then she can buy milk.

# Universal and Existential Statements

For both universal and existential statements, the first set you use in the statement always affects the second set. Use ∈, and the symbol for whatever set is being used, to denote that the variable is part of a given set.

∈ ≡ is an element of

A universal statement is a statement that says that something is true for everything in the set.

To write a universal statement, you must start out with the symbol ∀, (which looks like an upside-down A). Put a comma after the set, then write the rest of the statement as normal.

∀ ≡ for all

An existential statement is a statement that says that there is at least one thing that exists for which the property is true.

To write an existential statement, you must start out with the symbol ∃, (which looks like a backward E). You then must write "such that," "so that," or use an abbreviation such as "s.t." Then you write the rest of the statement as normal.

∃ ≡ there exists, there is at least one, there is a

## Universal Statement:

∀ r ∈ P, ∃ q ∈ P such that r loves q

In plain English:

Everyone loves someone.

## Existential Statement:

∃ x ∈ P such that ∀ y ∈ P, x loves y

In plain English:

There is someone who loves everyone.

### Test Yourself

• ∀ p ∈ Q, ∃ r ∈ Q such that p⇒r
• ∃ p ∈ Q, ∀ r ∈ Q, p ∧ r
• ∃ p ∈ Q such that ∃ r ∈ Q such that p ∧ r
• ∃ p ∈ Q such that ∃ r ∈ Q, p ⇔ r
Choose the correct format for writing an existential statement.

# How to Write a Proper Proof

There are steps to writing a proper proof.

1. Statement you are proving
2. Basis Step
3. Induction Step (if writing an induction or strong induction proof)
4. Induction Hypothesis (if writing an induction or strong induction proof)
5. Concluding Statement
6. Q.E.D. or equivalent

You first start out by writing the statement you are going to prove. If you are writing an indirect proof, you should put the negation, or contrapostive statement after the original statement. Make sure you label that it is a negation or contrapositive statement, because the negation or contrapostive statement is what you are using in the proof.

Then you start your basis step. This is the where you prove a statement in direct and indirect proofs. The basis step shows the statement is true for one or more values in induction and strong induction proofs.

 A handy tip is to first work on your proof on a scratch piece of paper. Sometimes a proof is easier to figure out by working backwards. When you are finished, you can copy the correct information in the correct order onto the actual proof.

If you are writing a direct, or indirect proof,  you can skip the induction step and induction hypothesis.

The induction step is where you prove the statement for induction, and strong induction proofs. The proof for "k+1," which shows that the statement is true, or false, for the value after k. The induction hypothesis goes in the beginning of induction step.

Next you write the concluding statement. This states whether the statement is true or false, and by what means it is true or false.

The final step is to show that you are finished with the proof. You put this at the very bottom of the proof, under the concluding statement. Q.E.D. is an abbreviation for the Latin phrase "quod erat demonstrandum," which translates as "that which was to be demonstrated." Q.E.D. is one of the most common ways to show you are finished with a proof. Another common way is to draw a little box, and shade the box in.

### Test Yourself

• Statement
• Basis Step
• Induction Step (If writing an induction or strong induction proof)
• Induction Hypothesis (if writing an induction or strong induction proof)
• Concluding Statement
• Q.E.D.
Place the steps to writing a proof in the correct order.

## Direct Proofs

### Test Yourself

Prove there is an integer the sum of two odd integers is even.

Let n,m ∈ Ζ  be odd.

So ∃ r,k ∈ Ζ such that n=2k+1 and m=

n+m=(2k+1)+(2r+1)==2(k+r+1)

which is even by definition.

Q.E.D.

### Test Yourself

∀ n ∈ Ζ, 2n^2+1 is odd.

### Proof:

Case One: n is even

So ∃ k ∈ Ζ such that n=

Then 2n^2+1=2(2k)^2+1=2(4k^2)+1

which is  by definition.

Case Two: n is

So ∃ k ∈ Ζ such that n=2k+1

Then 2n^2+1==2(4k^2+4k+1)+1

which is odd by definition.

Q.E.D.

### Test Yourself

Every even integer n greater than 2 and less than 16 can be expressed as the sum of two prime numbers.

Let n=4

Let n=6

6=3+3

8=5+3

Let n=10

12=7+5

Let n=14

14=7+7

Q.E.D.

## Indirect Proofs

### Test Yourself

There is no greatest even integer.

### Proof by contradiction:

Assume there is a greatest integer n.

So So ∀ a ∈ Ζ, .

Now suppose there is a m so that m=n+2, so m is even. So  because n+2>n and m=n+2.

Therefore m≤ n<m

which gives a , so there is no greatest even integer.

Q.E.D.

### Test Yourself

Prove ∀ n ∈ Z, if n^2 is even then n is even.

Contrapositive:

Proof:

Let n ∈ Z be

So ∃  k ∈ Z such that n=2k+1

n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1

which is by definition.

Q.E.D.

## Induction Proofs

### Test Yourself

Choose the correct induction proof.

## Strong Induction Proofs

### Test Yourself

Choose the correct proof.