Logic tutorial - Propositional (boolean) logic

[Complexity]

Due to the interest and discussions on logic, I've decided to put together some tutorials on logic. I'm starting with propositional logic, also known as boolean logic.

I have a background in boolean expressions and automated reasoning, which is also known as automated theorem proving.

My doctoral dissertation was written on research that I did on boolean expressions (determining satisfiability, simplification), which I'll discuss later on in this thread.

I'll be drawing on a variety of resources, including my dissertation and other writings. Dr Kitten has kindly lent me some work that is being prepared for publication, which I shall happily mine for ideas. I'll also search the internet and my library for ideas, explanations, and metaphors that may help.

My goal in these tutorials is to offer a comfortable path into mathematical logic for anyone who wants to go along for the ride.

I will try to post material in a fairly reasonable order, but I'm sure I'll revisit topics often, either to offer a different slant, or in response to questions.

Even though I will post often, there is a lot of material to cover, and I'm determined to make it friendly and approachable. This will take a while.

I'll avoid formal logical notation at first and then introduce it once many ideas have been become familiar.

I've got my own way of looking at things and have come to use some ideas and terms that are not standard (e.g. non-model, partial interpretation). I'll try to identify these as I introduce them. I will, of course, try to use standard terminology and notation when I can.

Please feel free to post any questions that you have, as well as any topics you'd like to see covered or revisited. I'll keep notes on what has been asked and suggested and address them as soon as I can without disrupting the flow of the tutorial.

Enjoy.

[cyborg]

Perhaps we could get some interactive programs together for people to run? I think seeing some of these processes enacted in a visual way would be an assistance to those who may find it harder to visualise this sort of thing in their heads.

[Fnord]

Can you reduce the following table to common minterms for A, B, C, and D?

# = D C B A = g f e d c b a
0 = 0 0 0 0 = 0 1 1 1 1 1 1
1 = 0 0 0 1 = 0 1 1 0 0 0 0
1 = 0 0 0 1 = 0 0 0 0 1 1 0
2 = 0 0 1 0 = 1 0 1 1 0 1 1
3 = 0 0 1 1 = 1 0 0 1 1 1 1
4 = 0 1 0 0 = 1 1 0 0 1 1 0
5 = 0 1 0 1 = 1 1 0 1 1 0 1
6 = 0 1 1 0 = 1 1 1 1 1 0 x
7 = 0 1 1 1 = 0 0 0 0 1 1 1
8 = 1 0 0 0 = 1 1 1 1 1 1 1
9 = 1 0 0 1 = 1 1 0 x 1 1 1

0 = Low or False
1 = High or True
x = Don't Care

This is based on the functioning of the 74915 type 7-segment to binary-coded decimal decoder chip. All of the data sheets I have do not show the internal logic as implemented by the manufacturers, in spite of the fact that this chip is no longer in production.

I've come up with several solutions on my own, and I use this very question to test candidates for employment. Needless to say, most haven't a clue where to even begin.

("Gosh, I should know this! We covered it in my sophomore year!" -- A graduate of University of California at Irvine.)

[Complexity]

Propositional logic is all about propositions.

A proposition is a statement about things. For example,

It is raining.

John has a birthmark on his right hand.

Every proposition is either true or false, though its truth value may depend upon time and context.

What can we do with propositions?

We can negate a proposition: not ( It is raining ). This is just a way of saying that it is not raining.

We can put two propositions together in a variety of ways, for example,

It is raining and John has a birthmark on his right hand.

It is raining or John has a birthmark on his right hand.

As interesting as John's birthmark may be, we are often more interested in the forms or structures that logical representation and argument can take.

We may, for example, may want to think about a statements like:

A and B

B or not C

not ( not C or ( not A and B ) )

A and not A

A or not A

in which the variables A, B, and C can each represent any proposition.

When a variable, such as A, is used more than once in a statement, each occurrence of the variable represents the same proposition and must take on the same truth value.

There are standard symbols available for not, and, or, and so forth, but we'll use words for now.

[Complexity]

I'll keep my eye out for interactive programs.

Minterms are definitely a later topic. I'll remember.

[Complexity]

Boolean expressions are named in honor of George Boole, an influential English logician and author of the breakthrough An Investigation on the Laws of Thought, On Which are Founded the Mathematical Theories of Logic and Probabilities (1854).

Boolean expressions are what we work with in propositional logic.

There are only two boolean values: true and false.

A boolean variable may only take on or be assigned a boolean value. We'll use upper-case English letters for boolean variables (e.g. A, B, C).

Any boolean expression can be negated by preceding it with not.

Any two boolean expressions can be joined by a placing a binary operator, known as a junctor, between them. While there are 16 different junctors, we'll only be concerned with these for now: and, or, xor, implies, is-equivalent-to. More on these soon.

We're going to build up which statements are boolean expressions using the following rules:

1. A boolean variable is a boolean expression.
2. A boolean expression surrounded by a pair of parentheses is a boolean expression.
3. A boolean expression preceded by a not is a boolean expression.
4. Two boolean expressions joined by a junctor is a boolean expression.

The following are examples of boolean expressions:

A

( A )

not ( A )

A and B

A and not ( B or not C )

and is also known as a conjunctor.

or is also known as a disjunctor.

Each occurrence of a variable in an expression is known as a literal.

The number of variables in an expression is the number of distinct variables, excluding duplicates.

The number of literals in an expression is the number of occurrences of variables, including duplicates.

The vocabulary of an expression is the set of variables that occur in the expression.


For example, the expression

( A or not B ) or ( ( not A and C ) and ( not D or ( B and not C ) ) ) )

has 7 literals, four of which are negated, which are drawn from the vocabulary { A, B, C, D }, which contains 4 variables.

[Complexity]

Two boolean expressions can be joined together by putting a junctor between them.

Five of the most familiar junctors are and, or, xor, implies, and is-equivalent-to. The symbols that are used for these and other junctors will be introduced later.

Note: We'll be using iff as an abbreviation for 'if and only if'.

and has same meaning that 'and' does in English. 'A and B' is true iff both A and B are true.

The English word 'or' has two different meanings - it can be an 'inclusive or' (including the possibility that both can be true) or an 'exclusive or' (excluding the possibility that both can be true, i.e. 'either..or').

or will be used for the 'inclusive or'. 'A or B' is true iff A is true, or B is true, or both A and B are true.

xor will be used for the 'exclusive or'. 'A xor B' is true iff A is true or B is true, but is false if both A and B and true.

implies will have the roughly the same meaning that it has in English. 'A implies B' will be true iff A is false or B is true. This often causes some confusion.

'A implies B' is equivalent to '( not A ) or B'.

Consider 'It is raining on my lawn implies that my lawn is wet'. If it is not raining on your lawn, your lawn may be dry or it may be wet. Either way, the statement is wrong only if it is raining on your lawn and your lawn is not wet.

is-equivalent-to means what it says. 'A is-equivalent-to B' is true iff A is true whenever B is true, and A is false whenever B is false.

Truth tables are often used to define junctors. I'll introduce them soon.

[GodMark2]

Originally Posted by Fnord

Can you reduce the following table to common minterms for A, B, C, and D?

# = D C B A = g f e d c b a
0 = 0 0 0 0 = 0 1 1 1 1 1 1
1 = 0 0 0 1 = 0 1 1 0 0 0 0
1 = 0 0 0 1 = 0 0 0 0 1 1 0
2 = 0 0 1 0 = 1 0 1 1 0 1 1
3 = 0 0 1 1 = 1 0 0 1 1 1 1
4 = 0 1 0 0 = 1 1 0 0 1 1 0
5 = 0 1 0 1 = 1 1 0 1 1 0 1
6 = 0 1 1 0 = 1 1 1 1 1 0 x
7 = 0 1 1 1 = 0 0 0 0 1 1 1
8 = 1 0 0 0 = 1 1 1 1 1 1 1
9 = 1 0 0 1 = 1 1 0 x 1 1 1

0 = Low or False
1 = High or True
x = Don't Care

The way it's presented, it's not possible, but that's only because I think you forgot an "or" between the two {0,0,0,1} input lines. The same inputs can't lead to two mutually exclusive outputs for a simple logic device.

[phildonnia]

Originally Posted by Fnord

Can you reduce the following table to common minterms for A, B, C, and D?

I've come up with several solutions on my own, and I use this very question to test candidates for employment. Needless to say, most haven't a clue where to even begin.

Wikipedia is your friend.

http://en.wikipedia.org/wiki/Karnaugh_map

[becomingagodo]

Set theory, where is the set theory?

Quote:

Due to the interest and discussions on logic, I've decided to put together some tutorials on logic

I'm skeptical on the effectiveness of this set of tutorials.
Deductive reasoning, where is the deductive reasoning?
Also can you explain the differences between inductive and deductive? I know the difference however you could compare the two in a logic tutorial.

Too much computer science.

[Complexity]

A boolean expression is said to be in a normal form if it satisfies the requirements of that normal form.

A boolean expression is in Negative Normal Form (NNF) iff every negator (not) immediately precedes a literal (occurrence of a variable).

'A and ( not B or not A ) ' is in NNF.

'A and not ( B and not A )' is not in NNF.

A boolean expression is in Conjuctive Normal Form (CNF) iff it consists of one or more subexpressions anded together and each subexpression consists of one or more (possibly negated) literals ored together.

'( A or B or not C ) and ( ( not B ) or D ) and ( not A )' is in CNF.

By the way, some operators (negators and junctors) have higher precedence (stick more tightly) than others. If this is understood, some of the parentheses can be dropped.

For example, not has highest precedence (sticks tightest), so that we may write 'not B or D' rather than '( not B ) or D'. More on precedence later.

A boolean expression is in Disjunctive Normal Form (DNF) iff it consists of one or more subexpressions ored together and each subexpression consists of one or more (possibly negated) literals anded together.

'( A and B and not C ) or ( ( not B ) and D ) or ( not A )' is in DNF.

Any boolean expression can be converted to any of these three normal forms. Converting a general boolean expression to CNF or DNF may involve the construction of a significantly larger expression.

Many algorithms that do things to boolean expressions require that they be be in CNF or in DNF.

I like to devise algorithms that work with expressions that don't need to be in CNF or in DNF. I refer to expressions that are not necessarily in a normal form as general boolean expressions.

[Complexity]

Originally Posted by becomingagodo

Set theory, where is the set theory?

Set theory is usually defined by a set of axioms in second-order predicate calculus. This is what Russell and Whitehead were up to in their landmark Principia Mathematica (1910 - 1913). They were trying to 'derive all mathematical truth from a well-defined set of axioms and inference rules in symbolic logic.' [Wikipedia, http://en.wikipedia.org/wiki/Principia_Mathematica] This goal is what Goedel's Incompleteness theorems proved unachievable.

Set theory comes much later.

Originally Posted by becomingagodo

I'm skeptical on the effectiveness of this set of tutorials.

That's ok. Let's see what happens.

Originally Posted by becomingagodo

Deductive reasoning, where is the deductive reasoning?

We have to lay the foundations, first.

Originally Posted by becomingagodo

Also can you explain the differences between inductive and deductive? I know the difference however you could compare the two in a logic tutorial.

I'll touch on that at some point, but we'll primarily be concerned with deduction.

Originally Posted by becomingagodo

Too much computer science.

Mathematical logic is one of the computing sciences, but I probably will be sticking to mathematical logic rather than looking at it from a computer science perspective.

[Complexity]

A constraint in the context of boolean expressions is a binding (or mapping) of a boolean variable to a boolean constant.

The constraint of a boolean variable X to true will be denoted by +X and the constraint of X to false will be denoted by -X.

A consistent set of constraints does not contain a constraint to true and a constraint to false for the same variable.

An inconsistent set of constraints does contain such a pair of conflicting constraints on at least one variable.

For example, { +A, -B, +C, +D, +G } is a consistent set of constraints and { +A, +B, -B } is an inconsistent set of constraints.

We will use this notion of constraints in several places. I first used constraints and sets of constraints in this way in my Master's thesis.

[Fnord]

Originally Posted by GodMark2

The way it's presented, it's not possible, but that's only because I think you forgot an "or" between the two {0,0,0,1} input lines. The same inputs can't lead to two mutually exclusive outputs for a simple logic device.

Those are output lines. I use the programmer's model, where the result is to the left of the equals sign, and the operations are to the right.

To put it in a more linearized form:

A = { -g, -f, -e, -d, +c, +b, -a, } OR { -g, +f, +e, -d, -c, -b, -a } OR { +a, +b, +c, +d, -e, -f, +g } OR { +a, -b, +c, +d, -e, +f, +g } OR { +a, +b, +c, -d, -e, -f, -g, } OR { +a, +b, +c, -d, -e, +f, +g } OR { +a, +b, +c, +d, -e, +f, +g }

Now, using ALL of the terms as given, can you solve for A?

Similarly, solutions can be found for B, C, and D.

[Complexity]

An interpretation of a boolean expression is a consistent constraint set that cover's the expression's vocabulary - it contains exactly one constraint for each variable in the expression's vocabulary.

The evaluation of a boolean expression under an interpretation is a process in which each literal in the expression is replaced by the boolean value to which the variable is constrained in the interpretation, after which the resulting expression is simplified to either true or false.

For example, let's evaluate the boolean expression 'A or ( B and not A )' under the interpretation { -A, +B }. The sequence of steps is as follows:

A or ( B and not A )
false or ( true and not false )
false or ( true and true )
false or true
true

An interpretation under which an expression evaluates to true is a model for that expression; otherwise, the interpretation is a non-model for that expression.

For example consider the expression '( ( A and not B ) or C ) and B'.

{ +A, +B, -C } is an interpretation under which the expression evaluates to false and is, therefore, a non-model of the expression. { +a, +b, +c } is an interpretation under which the expression evaluates to true and is, therefore, a model of the expression.

[Complexity]

Herding cats sucks.

Nonetheless, I'd appreciate it if, once you raise a question or topic for later consideration, you'd drop it until I bring it up again.

Karnaugh mapping is not where I want to go right now.

If you need to talk about it now, please do so in another thread.

[Complexity]

A boolean expression represents a partition of interpretations into models and non-models.

Two boolean expressions are equivalent iff they represent the same partition (this will be clarified later).

For example, consider '( ( ( A and not B ) or C ) and B )' and '( C and B )'.

The models of the first expression are { +A, +B, +C } and { -A, +B, +C }.

It turns out that constraints of A in the first expression have nothing to do with whether an interpretation is a model of the first expression.

The only model of the second expression is { +B, +C }.

The models for both expressions all have { +B, +C } as a subset.

Both expressions represent the same partition and are equivalent.

[Complexity]

An expression is a tautology if all of its interpretations are models - if it always evaluates to true.

An expression is a contradiction if none of its interpretations are models - if it always evaluates to false.

An expression that has at least one model is satisfiable.

An expression that has at least one non-model is falsifiable.

The logical class of an expression is one of { contradiction, satisfiable and falsifiable, tautology }.

'A and not A' is a simple contradiction.

'A or not A' is a simple tautology.

'A and B' is both satisfiable and falsifiable. It has { +A, +B } as its only model.

[Jimbo07]

Originally Posted by Complexity

If you need to talk about it now, please do so in another thread.

Done.

Please continue.

This thread has great value...

[Complexity]

It is one thing to know that two boolean expressions can be equivalent to each other, but how do can we construct an expression that is equivalent to the one we start with?

There are several rules that we can follow that can convert an expression into an equivalent expression.

One of the simplest is that we can always remove a 'not not' from any expression without changing its set of models.

For example, 'A and ( B or not not C )' is logically equivalent to 'A and ( B or C )'.

This suggests that another simple rule is that we can insert a 'not not' before any literal or left parenthesis.

'A and ( B or C )' is logically equivalent to 'A and not not ( B or C )'.

'A and ( B or C )' is logically equivalent to 'A and ( not not B or C )'.

I'm going to use emoticons to denote boolean expressions (I'm having trouble inserting special characters, and emoticons are fun). This will help me express these rules more clearly.

' is logically equivalent to 'and and '.

Note that we can go either direction: inserting an 'and and' or removing an 'and and'.

What can we do when a not appears before a left parenthesis that is helping to contain an or? For example, 'A and not ( B or C )'.

This one is pretty cool - we get to move the not into the parentheses, flip the or to an and, and negate the two subexpressions to the left and right of the old or.

What? This is what it looks like after we distribute the not over the or:

'A and ( not B and not C )'

'A and not ( B or C )' is logically equivalent to 'A and ( not B and not C )'.

More generally,

not ( or ) is logically equivalent to ( not and not ).

We can also distribute a not over an and, flipping the and to an or:

'A and not ( B and C )' is logically equivalent to 'A and ( not B or not C )'.

More generally,

not ( and ) is logically equivalent to ( not or not ).


Let's use these three equivalences to transform a boolean expression into Negative Normal Form:

A and ( not ( not B or not ( not A or C ) ) )

A and ( not ( not B or ( not not A and not C ) ) )

A and ( not ( not B or ( A and not C ) ) )

A and ( not not B and not ( A and not C ) )

A and ( B and not ( A and not C ) )

A and ( B and ( not A or not not C ) )

A and ( B and ( not A or C ) )

There are many more equivalences that allow us to transform one boolean expressions to another that it is logically equivalent to. They all have names and several more will be introduced later.

Why would we want to transform a boolean expression? We may want to convert it to a normal form, simplify it, or modify its structure so we can do something else to it.

[Yiab]

Originally Posted by Complexity

Set theory is usually defined by a set of axioms in second-order predicate calculus. This is what Russell and Whitehead were up to in their landmark Principia Mathematica (1910 - 1913).

I was under the impression that Russel and Whitehead (and Hilbert and many others) were trying to develop set theory in a first-order predicate calculus. After all, Goedel's theorem doesn't apply to second-order number theory, let alone second order set theory.

[JoeTheJuggler]

Originally Posted by Jimbo07

This thread has great value...

Amen

Keep it coming, Complexity! (And thanks for this.)

[Tobermory]

Complexity, thank you. I love this thread. It's a real treat, and it's clear as can be.

[Complexity]

Originally Posted by Yiab

I was under the impression that Russel and Whitehead (and Hilbert and many others) were trying to develop set theory in a first-order predicate calculus. After all, Goedel's theorem doesn't apply to second-order number theory, let alone second order set theory.

I will check and get back to you. If I'm wrong, I've been wrong for years, but it wouldn't be the first time.

I believe that Goedel's proof of the incompleteness of the second-order predicate calculus made explicit use of the logical system that Russell and Whitehead constructed in Principia Mathematica. I've been under the impression that he proved that this system was incomplete and that any attempt to 'patch' it would necessarily result in another incomplete system.

[Complexity]

Originally Posted by JoeTheJuggler

Amen

Keep it coming, Complexity! (And thanks for this.)

Originally Posted by bluharmony

Complexity, thank you. I love this thread. It's a real treat, and it's clear as can be.

Thanks for the positive feedback. I spent a bit too much time on this today and my brain is running out of my ears.

[Complexity]

I'm going to take a break for a bit and talk about some of the big problems that are found in the world of boolean expressions.

What do I mean by a big problem? For now, let's say that it is a problem that we don't know how to solve efficiently for all boolean expressions.

There are three I'd like to mention now.

1. Is a specified boolean expression satisfiable? That is, does there exist an interpretation under which it evaluates to true and, if so, what is an example of such a model?
2. What is the simplest boolean expression that is equivalent to a specified boolean expression, given an appropriate definition of 'simpler'?
3. Are two different boolean expressions equivalent?

Determining the satisfiability of a boolean expression doesn't sound that hard, but finding an algorithm for doing so 'efficiently' for all boolean expressions has, so far, eluded everyone.

Getting into what we mean by 'efficiently' will have to wait until we can talk about the complexity of problems and the complexity of algorithms.

Determining the satisfiability or falsifiability of boolean expressions has applications in circuit design, automated reasoning, and many other areas.

The definition of 'simpler' for 2. will usually involve ideas like 'smaller', 'faster to evaluate', and can have a big impact in things as varied as circuit design and query optimization.

I did my master's work on a new method for determining boolean satisfiability and did my doctoral work on a new algorithmic framework for simplifying boolean expressions. I'll write about these in pieces when they will fit in well.

There are many other problems of interest in the field of boolean expressions, but I think these three are the most important.

[Naughtyhippo]

Hi!

Thanks very much for being willing to educate. Despite taking several mathematic courses as an undergraduate I never covered logic so I'm really doing my best to grasp the things you're showing here. In post #15 you said:

Originally Posted by Complexity

For example, let's evaluate the boolean expression 'A or ( B and not A )' under the interpretation { -A, +B }. The sequence of steps is as follows:

A or ( B and not A )
false or ( true and not false )
false or ( true and true )
false or true
true

Why does false or true evaluate to true? why can't it be false?

[cyborg]

Originally Posted by Naughtyhippo

Why does false or true evaluate to true? why can't it be false?

You're thinking of the English use of the word 'or', as in, "pick one of these choices: A or B or C or D," but that is not really what it means here. What it means here is, "if this is true, or if this is true then the whole thing is true."

As such in a 'or' (or more precisely, inclusive-or) operation you only need one of the variables to evaluate to true for the whole thing to be true.

Remember, English is not your friend here. It is ambiguous at the best of times. What we are doing is trying to capture some semantic essence of what we mean but if ever in doubt you simply remember that you are applying rules that say: "given A and given B and given some boolean function give me C, the result." For or C is true any time A or B is.

[Naughtyhippo]

Thanks cyborg looking over the thread, I see I missed this

Quote:

or will be used for the 'inclusive or'. 'A or B' is true iff A is true, or B is true, or both A and B are true.

I'm going to have to work my way through this again.

[Jeff Corey]

Originally Posted by Naughtyhippo

Thanks cyborg looking over the thread, I see I missed this



I'm going to have to work my way through this again.

Exclusive OR is A OR B but NOT A AND B. Inclusive OR is A OR B OR A AND B. Connect two inputs together in parallel to get an inclusive OR gate.

[Naughtyhippo]

Originally Posted by Jeff Corey

Exclusive OR is A OR B but NOT A AND B. Inclusive OR is A OR B OR A AND B. Connect two inputs together in parallel to get an inclusive OR gate.

whoah,whoah,whoah....... I have NEVER studied logic before! why would I connect them to get a gate? what does a gate do? I was just trying to understand a result. Wah!!!! BTW I haven't really gone through all of complexity's posts again yet. I don't think I can absorb additional things before grasping the basics first.

[Jeff Corey]

Originally Posted by Naughtyhippo

whoah,whoah,whoah....... I have NEVER studied logic before! why would I connect them to get a gate? what does a gate do? I was just trying to understand a result. Wah!!!! BTW I haven't really gone through all of complexity's posts again yet. I don't think I can absorb additional things before grasping the basics first.

Sorry about that. I learned the logic constructing switching devices for lab equipment. A gate is a switching circuit that performs a function, like AND or OR.

[becomingagodo]

Is this tutorial only about Boolean logic?

[Molinaro]

Well here's a bit of the basics that may help: Truth tables for the basic logical operators.

A   B   (A or B)
-------------
T   T      T
T   F      T
F   T      T
F   F      F


A   B   (A and B)
-------------
T   T      T
T   F      F
F   T      F
F   F      F


A   B   (A xor B)
-------------
T   T      F
T   F      T
F   T      T
F   F      F


A     (not A)
------------
T        F
F        T

[Complexity]

Originally Posted by becomingagodo

Is this tutorial only about Boolean logic?

This tutorial will only be about boolean logic.

Once we've progressed to a certain point in this thread, I'll start the next on First-Order Predicate Calculus. After that, a third thread on Second-Order Predicate Calculus.

I'll spend several weeks, at least, getting each thread going. There is a lot of material here.

I wanted to start with Propositional Logic because we can get to know several concepts in a fairly simple logic before we get reacquainted with them in a richer, more complex logic.

Don't make the mistake of thinking that boolean logic and boolean expressions aren't worth spending more than a day on. It is an active area of research. The problem of determining boolean satisfiability is intimately connected to one of the Clay Math Foundation's Millenium Problems.

[becomingagodo]

Quote:

I wanted to start with Propositional Logic because we can get to know several concepts in a fairly simple logic before we get reacquainted with them in a richer, more complex logic.

Okay, I will trust you on this.

Quote:

Don't make the mistake of thinking that boolean logic and boolean expressions aren't worth spending more than a day on. It is an active area of research. The problem of determining boolean satisfiability is intimately connected to one of the Clay Math Foundation's Millenium Problems.

P versus NP is computer science. I don't want to learn computer science.

[Complexity]

Originally Posted by becomingagodo

Okay, I will trust you on this.

Thanks! I think you'll find this interesting and, by going through it in a reasonable order, you'll have a nice foundation from which to approach the more advanced stuff.

Originally Posted by becomingagodo

P versus NP is computer science. I don't want to learn computer science.

You did identify the right Millennium Problem - P =? NP.

I'll talk about this in a while, but it has to do with the complexity of problems and of algorithms for solving those problems. This area of mathematics is also one of the computing sciences.

Don't forget, becomingagodo, that the P =? NP problem is regarded by the Clay Math Foundation as one of the most important open problems in mathematics.

Math and computer science overlap a lot.

[JoeTheJuggler]

Originally Posted by Complexity

An interpretation of a boolean expression is a consistent constraint set that cover's the expression's vocabulary - it contains exactly one constraint for each variable in the expression's vocabulary.

Minor typo: there shouldn't be an apostrophe in "cover's" above.

Again, this is wonderful, Complexity. I backed into quite a bit of Boolean Logic without every studying it systematically. (Had a very rough--and sometimes wrong--intro in an Intro to Philosophy class I interpreted, but with nowhere near the rigor as this.)

[Complexity]

Molinaro was quite right to introduce truth tables - they should help clarify things a lot at this point.

I'm going to list the truth tables for the negator (not) and 7 of the 16 junctors.

Truth tables can be used to define operators such as negators and junctors, as well as explore how boolean expressions evaluate under different interpretations.

A truth table is presented as a sequence of rows.

The heading row lists the boolean variables and boolean expressions made up from those variables that we are interested in defining / exploring.

Following the heading row are 2-to-the-kth-power rows (where k is the number of boolean variables listed in the first row), covering every possible combination of those k variables having values of false and true.

The rest of the truth values on a row show the truth value that the expression heading that column has given the truth values of the variables earlier on the line.

Each row, therefore, spells out one interpretation.

For example, consider the truth table for and:

A       B         A and B
false   false     false
false   true      false
true    false     false
true    true      true

The third row says that, if A is true and B is false, then 'A and B' is false. The interpretation { +A, -B } is not a model of 'a and b'.

To make comparisons easier, I'll put the definitions of related junctors in the same truth table.

A       not A
false   true
true    false
 
A       B        A and B    A nand B           'nand' is short for 'not and'
false   false    false      true
false   true     false      true
true    false    false      true
true    true     true       false
 
A       B        A xor B    A or B    A nor B  'xor' is short for 'exclusive or'
                                               'or' is short for 'inclusive or'
false   false    false      false     true     'nor' is short for 'not or'
false   true     true       true      false
true    false    true       true      false
true    true     false      true      false
 
A       B        A implies B
false   false    true
false   true     true
true    false    false
true    true     true
 
A       B        A equals B    A xor B
false   false    true          false
false   true     false         true
true    false    false         true
true    true     true          false

I've decided for now to go with the name 'equals' rather than the name 'is-equivalent-to' for the junctor. It is short and sweet.

[Complexity]

An operator in this context is either the negator (i.e. not) or one of the 16 junctors (e.g. and, nand, or, nor, xor, implies, equals).

How many of these operators do we actually need? I haven't even given the names of nine of the junctors - do we need them?

If we have the right subset of the operators, we can mimic or 'fake' the other operators.

For example, since 'A implies B' is equivalent to '( not A ) or B', any time we've got the and and or operators to work with, we don't really need implies operator.

A set of operators is called a complete set of operators or a complete system of operators if every operator that is not in the set can be mimicked or 'faked' from the operators that are in the set.

One complete set of operators is { and, or, not }.

Using just and, or, and not, you can construct boolean expressions that are equivalent to each of the other operators.

This is the set of operators that I'll usually work with unless I'm trying to make a point about some other operators.

Another useful complete set of operators is { nand }. Yep - it just contains one operator, nand, which is short for 'not-and'.

Using just nand, you can construct boolean expressions that are equivalent to each of the other operators.

If you've got some time, it might be fun to construct expressions equivalent to some of the operators that aren't in a complete set using only those operators in the complete set.

Why are complete sets of operators important?

Because electronic circuitry is made up of gates corresponding to various operators that hook up together into a network of gates.

Each network of gates evaluates a boolean expression under the interpretation specified by its inputs.

Depending on the fabrication technology, some gates are better than others - they may be faster, take up less space on a chip, or produce less heat.

Since the nand operator is the only one you really need, you can implement any boolean expression on a chip using only nand gates. If the fabrication technology favors nand gates, they may be the way to go.

There are more than two complete sets of operators, but I won't worry about the others.