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

So, let's start with syntax.

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)."