Logic Review

Section 1.2 Logic Review

In basic proof logic, we will usually be proving a statement of the form

🔗

If \(P\) is true, then \(Q\) is also true.
🔗

🔗

Example 1.

Prove that if \(x\) is an even integer, then \(x^2\) is an even integer.

🔗

However, there are more interesting examples of how to prove things. Recall the converse of the generic statement:

🔗

If \(Q\) is true, then \(P\) is true
🔗

🔗

and the contrapositive thereof,

🔗

If \(Q\) is not true, then \(P\) is not true.
🔗

🔗

Example 2.

State the converse of Example 1, and then its contrapositive. Prove that final statement.

🔗

In normal mathematical logic, we say that the contrapositive and the original statement are logically equivalent. So you should use whichever you find useful in proving theorems!

🔗

However, that isn’t the case with the converse and the original statement.

🔗

Example 3.

Take the statement “If \(n\) is a prime number, then \(n\) is a positive integer” and give a reason why it is true, but its converse is false.

🔗

In Example 1 and Example 2, we have the highly unusual situation where both \(P \Rightarrow Q\) and \(Q \Rightarrow P\) are both true. We say this is a biconditional statement and write \(P\Leftrightarrow Q\text{,}\) saying

🔗

\(P\) is true if and only if \(Q\) is true,
🔗

🔗

or “\(P\) is necessary and sufficient for \(Q\)”, or some variation thereon.

🔗

There are a few other tricky logic issues that we should definitely practice.

🔗

Or is a word that means many things. In most of math (and here), “\(A\) or \(B\)” means “\(A\) or \(B\) or both”. This is important in statements like
🔗

If \(x\) or \(y\) is even, then \(xy\) is also even.
🔗

🔗

🔗

Example 4.

Come up with a theorem which is not true with this meaning of “or” but is true with the so-called exclusive or.

🔗

The other remaining tricky issue is that of quantifiers—things like “for all” and “there exists”. This is best tackled by trying it.

🔗

Example 5.

Restate the statements below as accurately as possible in terms of logic, and then do all of the following with as few double negatives as you can, using natural negations where possible:

🔗

Negate the statement, “All professors at my university who live in my town are tall and blond.”

🔗
Negate the statement, “There exists a student at my university who does not live in my town,” in the most natural way possible (i.e., without double negatives).

🔗
Give the contrapositive of the statement, “If there exists a professor at my university who is neither tall nor blond, then all students at my university are young and short.”

🔗

🔗

Problem 6.

Formally negate the statement, “For every positive number \(p\text{,}\) there is a positive integer \(N\) such that if an integer \(I\) is greater than \(N\text{,}\) then the reciprocal of \(I\) is less than \(p\text{,}\)” with as few negatives and as naturally as possible. (But please don’t try to prove it!)

🔗

Prev Top Next