Discrete! #1: Discrete Mathematics and Its Applications 1.1A

HOO DOGGIE! I’ve been wanting to dig into this for a while, but I wanted to take calc all the way to derivatives before I did so. Logically, discrete should probably be prior to calc, but I wanted to get through enough calc that I could do physics at the same time. The question of whether physics is prior to mathematics shall be left for philosophers…

I admit, I only have some knowledge of discrete. I’m a bit better on physics and calc. So, this part of my textblogging stuff is going to be a little less of me teaching, and a little more of you and I holding hands and galivanting through the fields of math. Huzzah!

From what I have learned, discrete is awesome. More and more I’m convinced it should be taught in high school. Why? Because it’s fucking fundamental – aka, fuckdamental. It’s the basic logical steps that you need in math. When we go over a proof in Calc, it’ll be a shitload clearer if you’ve learned some discrete. Here is where you learn all the legal moves in logic. It’s glorious.

I remember reading the autobiograph of Malcolm X (perhaps the best biography ever written), and reading him discuss why, despite being a learning addict, he wasn’t big on math. He said that he liked to argue too much, and that math left no room for argument. Ahh, if only he’d learned discrete! It’s the fundamental underpinning of all argument, and that’s what makes it fun. Most of the math you’ve learned  up till now is probably about HOW to do things. Discrete is all about WHY you can do things.

So, let’s dig in, shall we?

Since we’re just starting, there’s going to be a lot of new terminology. Fortunately, I have a glossary I started a while back. Because it’s a personal glossary, it mostly deals with terms I found difficult initially. So, not everything is in there.

First up: propositions. You know what a proposition is. As the book says “a proposition is a declarative sentence.” That is, a proposition is some claim about reality, like “cats are birds” or “redheads are virile.” The defining feature of a proposition is that it can be assigned a truth value of True or False. It doesn’t have to be true to be a proposition. It just has to have a truth value. So, of the above two statements, the first is false, and the second is true.

Like in algebra, for convenience, we denote everything with symbols. Propositions get “proposition variables” aka “statement variables” usually starting with p then working down the alphabet. So, if the above two statements are proposition p and proposition q, we could say p is false and q is true. Or, better still, p is F and q is T.

Every proposition has a negated version. There are several ways to express this, but I’m going to be using this symbol: ¬. Usually it’s just pronounced “not.” So, “¬p” is pronounced “not p.”

So, if p is “cats are birds,” “¬p” is “it is not true that cats are birds” or “cats are not birds.”

We also introduce a concept here called a “truth table.” It’ll seem simple at first, but in fact these are extremely useful. A truth table is a great way to lay out all possibilities. So, here’s a simple one for our statement p:

[table id=1 /]

Each column represents a proposition, the truth values it may hold, and how those truth values affect other propositions in the table. So, you see, if p is F, ¬p is T. If p is T, ¬p is F. That is, if it’s false that “cats are birds,” then it must be true that “cats are not birds.” And, if it’s true that “cats are birds,” then “cats aren’t birds” must be false.

So, you’ve already learned a new symbol, the negation operator: ¬. Let’s learn a few more:

There are three common operators called connectives, given by ∧, ∨, and ⊕. The first is the conjunction symbol, more commonly known as “and.” The second is the disjunction symbol, more commonly known as “or.” The third is the somewhat less common exclusive disjunction symbol, called xor, which I pronounce “zore,” though wikipedia says “exore” is also acceptable. I’ll get to the difference between or and xor shortly.

First, let’s make up some new propositions.

p: “Zach Weinersmith is sexy.”

q: “Pigs can fly.”

p∧q is pretty straightforward. It means  ”Zach Weinersmith is sexy, and pigs can fly.” So, the statement p∧q is true whenever p AND q are both true.

p∨q is a little more tricky, only because it differs from the common usage. Said aloud, it’s “Zach is sexy, or pigs can fly.” In terms of logic, it might be said “Either Zach is sexy or pigs can fly or both.”

p⊕q is like p∨q, but without the possibility that BOTH are true. That is, if I say “you can read my comics xor you can be said” I mean that there are two possibilities: 1) You read my comics. 2) You are sad. If I had said “you can read my comics or you can be sad” I’d be leaving open the possibility that you could read my comics AND be sad, which is of course impossible.

If you’ve ever wondered the purpose of the word “either” in English, it’s to separate OR from XOR. For example, consider these phrases: “Would you like either cream or sugar with your tea?” “Would you like cream or sugar in your tea?” The first indicates you can only have one or the other. The second indicates you can have one or both.

Here are the truth tables for each of these connectives:

[table id=2 /]

[table id=3 /]

[table id=4 /]

You should notice some patterns here. For example, AND is only true under one circumstance, while OR is only false under one circumstance. XOR is true only when you mix a true and a false.

As you can imagine, there are other simple operators. For example, there’s NXOR, which is usually denoted by a XOR sign with a line over it, since  in logic a line overhead indicates negation. NXOR is only true if both statements are false or both statements are true.

So, now you know how to make a few logical statements. You can say something’s true, something’s not true, two things are true, one of two things is true, and one or both of two things is true.

Next, we get into conditional statements. That’s “if this, then that” statements. Wooh!

This entry was posted in Autodidaction. Bookmark the permalink.

9 Responses to Discrete! #1: Discrete Mathematics and Its Applications 1.1A

  1. david says:

    the OR truth table is actually a NAND table.
    the last column should be T T T F.

  2. mjec says:

    “There are two common operators called connectives, given by ∧, ∨, and ⊕.”

    That sort of two we generally call three.

  3. V2Blast says:

    You misspelled “sad” three times (out of the four times you meant to use it).

    That *said*, I feel smarter already! :P

  4. Zacmanman says:

    I feel like I learned that last symbol differently (of course with the same result)

  5. Benjamin says:

    Wow just wait until you get into abstract algebra…you will have your MIND BLOWN by the beauty and elegance of math and the power of proofs.

  6. Harold says:

    Do they list it in the book as NXOR? I’d never seen that before, either in math or computer science. I think you’ll find XNOR much more common.

  7. Jeremy says:

    I’m taking discrete math this semester, actually, so this is going to be AWESOME.

  8. Bill says:

    If you like this stuff, you’ll probably like “automata theory”. It uses these this “boolean logic” stuff to create abstract models for computers:
    http://en.wikipedia.org/wiki/Automata_theory

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>