Discrete! #9: Discrete Mathematics and Its Applications 1.2D

Wooh! We’re getting toward more fun stuff.

Constructing New Logical Equivalences

If you know how the “basic 4″ arithmetic operations work, you can make pretty much any rule about numbers you like.

For example, you can show that -(-(x+1)) = x+1. Okay, so it’s not the most useful rule. But, you’ll note that you can make it as big and complex as you like by adding other operations. Or, you can simplify a big ugly operation by knowing certain things (like how the negative of a negative is a positive).

Well, with discrete, you can do the same stuff. Using the arrows and bars and carats you’ve recently learned, you can make up your own rules by finding new logical equivalences. The basic idea is this: if you can show that one statement reduces to another, then you’ve shown that the two statements are logically equivalent.

The book gives a couple examples of these, and they’re worth a try. They’re really quite a lot like puzzles. You have two things that don’t look the same, which you must show to be the same. By knowing the basic rules we learned recently, you manipulate one side to equal the other.

This is where rules like de Morgan’s laws, and the law for converting a conditional to a disjunction are awesome. They can provide clever little insights, along the lines of “well… I don’t know how this’ll work out, but I know this side needs to have no conditionals.”

There’s not too much beyond that to see here. However, you’ll note that problem set here contains 61 problems in a little over a page. Why? Because the way you’re gonna get good at finding logical equivalences is via a shit-ton of practice. There isn’t always an obvious way to figure these things out, so you need to develop some intuition.

Since there are some cool facts in some of these problems, and because I haven’t gone over this stuff in a while, in the next section I’ll work some problems from the final set here.

Next stop: Problem set for 1.2. WOOP!

This entry was posted in Autodidaction, Discrete Math. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>