## Thursday, March 23, 2006

### A bit of logic

The other day, I was at work, hacking away. Now, most days, I wind up working pretty much without interruptions, because I'm on assignment to a product development group, and I'm the only guy in New York working on this product.

But, once in a while, someone bangs on my door to talk. So I'm chatting away, actually talking about Battlestar Galactica, and the guy I'm talking with responds to something with "But that's not logical". I hate what Star Trek did to the common understanding of "logical".

All of this is a roundabout way of saying that I want to talk about logic.

## What is Logic?

There's no way to look at a statement in isolation and say that it's not logical. In fact, it's pretty darned close to impossible to say whether something is logical at all without first agreeing on just what logic you're talking about!

Logic is not a single set of rules. It's a structure - or more correctly, a way of studying a particular kind of structured system of rules. Logic is a way of building up a structure that lets you decide whether or not a particular set of statements is meaningful; and if they are, what they mean, and what kind of reasoning you can do using them.

What we usually think of as logic is actually one particular logic,
called first order predicate logic (FOPL). It's the logic of basic "and", "or", and "not" statements, with the ability to talk about "all" of some group of objects having a property, or the existence of an item with a property. (I'll define it in more detail later.)

FOPL is far from the only useful logic out there. Just to give a quick idea of a few different logics, here's a couple with brief descriptions.

Intuitionistic Logic
Something close to FOPL, but it's got the very interesting property that "A or (not A)" is not always true.

Temporal Logic
A logic that is focused on reasoning about how things happen as time passes. Quantifiers in temporal logic aren't things like "For all X, P(x) is true", but things like "Eventually there will be an X where P(X) is true", or "For all time, P(x) is true". Temporal logic is widely used in something called model checking, which is a technique use for (among other things) verifying the correctness of operations in a CPU design.

Fuzzy Logic
A logic where statements aren't specifically true or false, but have degrees of truth associated with them. (corrected from "probablity of truth" based on comment -markcc)

Logic is crucial to mathematics, because math is nothing but the formal systems that you can build using logics.

So - what is a logic?

There are three components to a formal logic:

1. Syntax: what does a valid statement in the logic look like?
2. Semantics: what does a valid statement in the logic mean?
3. Inference Rules: how can you use meaningful statements in the logic to
infer other meaningful statements?

## An Example Logic: Basic Propositional Logic

For a simple example, we can look at basic propositional logic. Propositional logic is a very basic logic: it has a set of primitive statements, and just four operators: AND, OR, NOT, and IMPLIES. So it's easy to explain.

### Syntax of Valid Statements in Propositional Logic

In propositional logic, we have a set of basic, atomic propositions. (Atomic means that they can't be subdivided into smaller propositions.) We write those with capital letters. Any single basic proposition is a valid statement in the logic.

We also have the operators: AND, OR, NOT, and IMPLIES. If f and g are valid statements, then not f, not g, f and g, f or g, and f implies g are all valid statements.

Finally, we have parenthesis for grouping: if f is a valid statement, then ( f ) is a valid statement.

So, each of the following is a valid statement:

`        A        B        A or B        A or B         A and B and C or (D and E) or (E implies F)        not A        not A implies (C and D or E)`

That's it for syntax.

### Semantics: The meaning of propositional logic

For semantics, we start by saying _which_ of the basic propositions is true. So, for example, if every upper-case letter were a proposition, we could say that A through M were true, N through Z were false.

Then we define the meanings of the operators:

x AND y x is TRUE x is FALSE
y is TRUE TRUE FALSE
y is FALSE FALSE FALSE

x OR y x is TRUE x is FALSE
y is TRUE TRUE TRUE
y is FALSE TRUE FALSE

x IMPLIES y x is TRUE x is FALSE
y is TRUE TRUE TRUE
y is FALSE FALSE TRUE

NOT x
x is TRUE FALSE
x is FALSE TRUE

Given those tables, and a truth binding for all of the atomic propositions, and we can work out whether a given statement is true or false.

### Inference rules: reasoning using propositional logic

Now, finally, inference rules. Suppose that we aren't given an exhaustive list of all of the atomic propositions and whether they're true or false. We'd like to be able to use statements that we know to decide whether or not other statements are true. There are a set of rules we can use to do this:

• If we know: x is TRUE, and x IMPLIES y is TRUE;
then we can conclude: B is TRUE.
• If we know: y is FALSE and x IMPLIES y is TRUE;
then we can conclude that x is FALSE.
• If we know: x is TRUE and x AND y is TRUE;
then we can conclude that y is TRUE.
• If we know: x is TRUE and NOT (x AND y) is TRUE;
then we can conclude that y is FALSE
• If we know: x is FALSE and x OR y is TRUE;
then we can conclude that y is TRUE
• If we know: x OR y is FALSE;
then we can conclude: X is FALSE and Y is FALSE

And so on. To be complete, we'd need to add some more, but the above are the basics. (We would need a rule for NOT; for AND and OR we would need some rules for commutativity, etc.)

So, finally, let's take an example of propositional logic.

Let's take some basic propositions (note that I'm not yet saying whether any of these are true or false!):

Proposition A = I am an annoying person.
Proposition B = I am talking to you.
Proposition C = You are annoyed at me.

We assert that the following two things are TRUE:

1. (A AND B) IMPLIES C (In English, "IF I am an annoying person and AND I am talking to you THEN you are annoyed.")
2. NOT C. (In English, "You are not annoyed at me. Remember, this is just for illustrations sake, by now, you may well be annoyed at me in reality!)

Now, what can we figure out by knowing that those two statements are true?

By one the inference rules we gave above, "If we know: y is FALSE and x IMPLIES y is TRUE; then we can conclude that x is FALSE.". We can use this rule, by using (A AND B) for x, and C for y: If we know that C is false, and (A and B) implies C, then we know that (A AND B) is false. So we can conclude NOT (A AND B), which means "It is not the case that I am annoyed and I am talking to you"; which actually can be switched (through a sequence of changes) to "Either I am not annoying, or I am not talking to you (or both)."

• A great post overall! A good intro to logic.I have only a very small quible. The definition of fuzzy logic is not quite right. Fuzzy logic attaches degree of truth to proposition not probability of truth. For example in fuzzy logic one could say it is "somewhat true that 70 degrees is warm" Of course one can jump up one level of abstraction and say "the previous statement is quite true"

Keep up the good work, I enjoy reading this blog!

By  RandomDNA, at 3:11 PM

• Thanks for the correction. I haven't studied fuzzy logic, just read a couple of references to it in other texts; I misinterpreted what they said about it. I've corrected it in the post.

By  MarkCC, at 3:37 PM

• A couple of nits:
"If we know: x is TRUE, and x IMPLIES y is TRUE;
then we can conclude: B is TRUE."

I think you mean: "then we can conclude: y is TRUE"

"If we know: x is TRUE and x AND y is TRUE;
then we can conclude that y is TRUE."

Actually, "x AND y is TRUE" is sufficient to conclude that y is true.

By  bcarson, at 4:12 PM

• Don't forget the pioneers, Boole and DeMorgan.

• quick correction on the bullet list

If we know: x is TRUE, and x IMPLIES y is TRUE;
then we can conclude: B is TRUE.

I think you meant "y is TRUE", not "B".

By  Joe Shelby, at 5:31 PM

• oh, oops, someone got it already.

gotta remember to refresh before posting. :)

By  Joe Shelby, at 5:32 PM

• The most enlightening moment while learning to program is the absolute comprehension that everything is really one's and zero's. The average user never realizes this underlying fact and in my experience believes that programming is some form of black magic brewed from a witches cauldron. Once a journeyman programmer comprehends the digital nature of all code, it is a transcendant event from ignorance to reality.

It really is a shame that more people cannot fathom how computers work. Abstraction has the downside of creating mystery where there is none. The real mystery is how a complicated list of logical statements can ever work. Of course, this is the cultural question society is haggeling over right now.

I actually disagree; to me, the specific reduction of programming to "It's all zero and ones" is pretty uninteresting - and for many people, I think it's actually misleading. I remember a conversation with my brother when I was in college, where he said something along the lines of "can you imagine computers could do if they hand *three* values instead of two? (The answer is, of course, absolutely nothing that they can't do right now.)

What I think is interesting is that you can reduce almost any problem down to a really small set of symbols. They could be zero and one, or they could be on and off, or they could be -1, 0, and 1, or they could be "a", "b", "c", and "d".

The way that I think about it, the fact that it's binary under the covers doesn't affect a lot of normal day to day programming (if you think about it, the only places where the underlying binary nature come into play are at numeric overflow points, and in floating point numbers, where there's a distinctive binary floating point roundoff.) But the reduction to discrete symbolic values - that's *everything* we do as a programmers.

I don't mean to say that you're wrong - there is something profound about the whole thing, the way that we can encode almost anything we want in a program. I mean, there's a reason that I'm a computer scientist, not a pure mathematician: there's something so deeply cool about how you can solve problems with programs, once I saw my first computer, I knew that that's what I was going to do.

By  MarkCC, at 7:26 PM

• The transcendant part for me was breaking through the mystery and realizing that all computational programming is simply the use of a cipher much like the magic decoder ring. Beyond that initial realization is the additional wonder that these abstract concepts are essentially translated into human language for human consumption. A user working in a program designed in a 4GL language has no concept that the underlying layers of logic end up translating into the humble one and zero. This is why the uninitiated computer user sees magic. I see only binary, yet remain amazed in the complexity of the whole assemblage and thankful for the intelligence and creativity of others.

• Think of the Class. The power comes from the ability to turn it into a representation of anything. Almost no one writes in binary, instead we use a human compatible language. Once the Class is compiled, it is translated into another language, binary, and resides as a lump of ones and zeros in a bank of transistors with the same properties as the conceptual object.

Humanity engineers technologies capable of comprehending, responding and interacting with these binary languages and our real world. Entire universes are simulated consisting entirely out of ones and zeros. And we bridge between the real universe and these virtual universes. That to me is absolutely amazing and has taught me the adage "the truth is stranger than fiction" is sage advice.

This internet we use to communicate is really ones and zeros. You and I are communicating in binary. Just under this veneer of English words is the seedy binary underbelly doing all the grunt work.

Yes, I do I know that I am weird.

• markcc said:
"But the reduction to discrete symbolic values - that's *everything* we do as a programmers."

You are absolutely correct, but it is easy to lose sight of the underlying logic driving it all. Programmers are users too. We become dependant on the languages we code in. Each of these languages is speaking some form of binary. Whenever I need to peek at unknown data, I use an ascii/hex editor.

• Good post. I think there needs to be more logic blogging. As a guy who has TA'd more than his fair share of intro logic classes, I can safely say that people are far too ignorant regarding formal deductive systems.

By  CK, at 12:59 AM

• nice webpage! i'm going to do my dissertation soon and my field consist of programming and fuzzy maths. do you have any suggestions what i can do with these 2 subjects for my dissertation?:) thanks!!

p/s:you can contact me at haw_alexis@yahoo.com!

By  Anonymous, at 7:42 AM

• actually, all these logics are just different aspects of the same logic...... either some thing is true or false (0 or 1) I also hate it when people equal "logical" with not taking feelings into consideration, emotions exsist, therefore, they can be logical, if my boyfriend is flirting with some hot cocktail waitress at my department's Christmas party, then logically I'm going to be jealous because I'm insecure.

By  Anonymous, at 8:59 AM

• I'm really enjoying this blog a great deal (and just sent the URL to my two mathmatician uncles).

You did omit the simpler version of the definition:
Logic is little tweeting bird, chirpping in meadow.
Logic is a bunch of pretty flowers that smell bad...
[/trek_geek]

Sorry, but that was one I couldn't let pass.

By  usagi, at 2:28 PM

• Doesn't the fact that such complex and adaptive systems composed entirely of ones and zeros, make the theories underlying genetics, chemistry and quantum mechanics entirely plausible in your mind? Sure the details are hard to comprehend without the appropriate educational background, but conceptually, dna, atomic composition and quarks are analogs to the binary language. It is entirely reasonable to agree that our complex universe is composed enitrely out of simple bits.