Logical Equivalence

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

Problem set 2. In particular, how do you put the things you know by themselves together into a proof, how do you give mathematical reasons for what you know intuitively?

Consider Conjecture 1, that if n is even, then 3n + 2 is also even.

One thought is to start with what Sundstrom calls “backwards questions,” i.e., at the “show” end of one of his know-show tables. My reason for doing this is that, at least in this proof, that’s where the more complicated expression is. In other words, that’s where you have 3n + 2 rather than just n. In this business, a complicated expression can be a good thing, because it has more room to simplify, rewrite, and rearrange into a form you want.

In this case, you need to show that 3n + 2 = 2b, for some integer b, since that’s the definition of an even integer.

A little bit of algebra gives

where the important thing isn’t b, because you don’t know it’s value and don’t really even care what its exact value is, the important thing is that b is an integer. In other words, you need to show that (3n+2)/2 is an integer.

Intuitively, you might know that (3n+2)/2 is an integer because n is even and 3 times an even number is still even, so the whole numerator is even, and therefore divisible by 2. But how do you put this into mathematical terms? The key is to expand n based on knowing that it’s even, i.e., that n = 2a for some integer a. Then

Finally, you can justify why 3a + 1 is an integer by reference to closure properties of integers, namely since a is an integer, closure under multiplication means that 3a is an integer, and then closure under addition means that 3a + 1 is an integer.

As a less detailed example, consider Conjecture 2. Once again the more complicated thing is at the “show” end of things, namely the equation x₁x₂ = c/a. A good way to expand and eventually simplify this would be to replace x₁ and x₂ with their definitions, but all we know about them is that they are solutions to a quadratic equation. But this at least tells us that x₁ and x₂ must have values given by the quadratic formula, i.e.,

So try multiplying these together and simplifying, and see if you eventually get c/a. You might or might not, but doing math sometimes involves exploring ideas without knowing whether they’ll work out, and if they don’t you just back up and try something else.

Misc

Applications for Geneseo Foundation scholarships are now open, until March 14.

Apply online at https://geneseo.academicworks.com/

Go apply — there are lots of scholarships with different criteria for funding, and you might meet someone’s criteria. But not if you don’t apply.

Logical Equivalence

From section 2.2 in the textbook and this logical equivalence discussion.

A Warm-Up Puzzle

Can you rewrite (¬P ∨ Q) ∧ (P ∨ ¬Q) in an equivalent form that uses only “and” and “not” operations?

First idea: is there some way you can move the terms around to get, e.g., both negated terms together? Only via the distributive law, i.e., using the rule that says “and” distributes over “or.” Doing this at first increases the number of “or” connectives in the expression, which is definitely not what we wanted, but eventually we can get rid of some of them when some of their operands turn out to be always false:

(¬P ∨ Q) ∧ (P ∨ ¬Q) ≡ ¬P∧ (P ∨ ¬Q) ∨ Q∧ (P ∨ ¬Q) 

≡ ¬P∧P ∨ ¬P∧¬Q ∨ Q∧P ∨ Q∧¬Q

≡ false ∨ ¬P∧¬Q ∨ Q∧P ∨ false

≡ ¬P∧¬Q ∨ Q∧P

Dropping “false” terms from an “or” is justified by a simple equivalency that I don’t think is presented in the book, namely that false ∨ A ≡ A. The easiest way to prove this is by inspecting a truth table:

Unfortunately, there doesn’t seem to be anywhere to go from ¬P∧¬Q ∨ Q∧P, which still has an “or” in it. This is a good example of exploring an idea that eventually doesn’t work out. So we’ll go back and look for something else to do.

Our next thought was to use De Morgan’s Laws

¬(P∧Q) ≡ ¬P ∨ ¬Q

¬(P∨Q) ≡ ¬P ∧ ¬Q

since they give us a way to replace “or” with “and” or vice versa. And in fact, we can rewrite the first “or” in the original expression in a way that allows application of the first one of these laws:

(¬P ∨ Q) ≡ (¬P ∨ ¬(¬Q)) ≡ ¬(P∧¬Q) .

Now we have gotten rid of one of the “or” connectives. We can do something similar with the other “or,” and the puzzle will be solved.

Next

Continue with logical equivalence.

There’s no new reading, but review section 2.2 of the textbook, and keep trying the exercises in the logical equivalence discussion and posting your results, comments, questions, etc.

Next Lecture