Boole’s Logic

In Boolean logic, there are three operations: x + y, x ∙ y, and 1 - x. These operations are governed by the following laws (note that the numbering in TTT is slightly different):

1. x + (y + z) = x + (y + z)

2. x ∙ (y ∙ z) = (x ∙ y) ∙ z

3. x + y = y + x

4. x ∙ y = y ∙ x

5. x ∙ (y + z) = x ∙ y + x ∙ z

6. x + (y ∙ z) = (x + y) ∙ (x + z)

7. x + 0 = x

8. x ∙ 1 = x

9. x ∙ (1 - x) = 0

10. x + (1 - x) = 1

11. 0 ≠ 1

Furthermore, the usual laws of equality hold: equality is reflexive, symmetric, and transitive, and one can substitute equal values for any variable in an equation.

Note that some of the algebraic laws above hold for the integers, and some don’t!

Here is an example of an equation that can be derived from the laws above:

y + (1 - y) = 1 (10)

x ∙ (y + (1 - y)) = x ∙ 1 multiply both sides by x (substitution)

x ∙ (y + (1 - y)) = x ∙ y + x ∙ (1 - y) (5)

x ∙ 1 = x ∙ y + x ∙ (1 - y) symmetry and transitivity of equality

x ∙ 1 = x (8)

x ∙ y + x ∙ (1-y) = x symmetry and transitivity of equality

Boole’s insight is that one can assign multiple interpretations to the algebraic system above.

Interpretation 1

· Letters stand for propositions (statements) that can be true or false

· x ∙ y is the proposition “x and y”

· x + y is the proposition “x or y”

· 1 - x is the proposition “not x”

· 1 is true

· 0 is false

In the example above, if x is “I am tired” and y is “I am hungry”, the identity asserts:

“Either I am tired and hungry or I am tired and not hungry”

is equivalent to

“I am tired.”

Interpretation 2

This is really two interpretations combined.

· Letters stand for properties, or

subsets of a “universe of discourse”

· x ∙ y stands for conjunction (the property “is x and is y”) or

intersection (the set of things in both x and y)

· x + y stands for disjunction (the property “is x or y”) or

union (the set of things in either x or y)

· 1 - x stands for negation (the property “is not x”) or

complement (the set of things not in x)

· 1 stands for the universally true property or

the entire universe

· 0 stands for the universally false property

or the empty set

In the example above, if x is the property “is tall” and y is the property “is handsome”, the identity above shows that the property

“is tall and handsome or is tall and not handsome”

is equivalent to

“is tall.”

Or, if our “universe of discourse” is the set of people in this room, x is the set of people who are tall, and y is the set of people who are handsome, then the identity above shows that

the set of people who are either tall and handsome or tall and not handsome

is the same as

the set of people who are tall.

Interpretation 3

· Letters stand for 0 or 1.

· x ∙ y is ordinary multiplication

· x + y is modified addition, where 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, but 1 + 1 = 1

· 1 - x is ordinary subtraction

· 1 and 0 stand for ordinary 1 and 0, respectively.

In this case, the identity above asserts that the two sides come out the same for every pair of values for x and y. For example, if x is 1 and y is 0 we have

1 ∙ 0 + 1 ∙ (1-0) = 1

Validity

A symbolic expression of the form E(x,y,z,…) = F(x,y,z...) is said to be valid if no matter how you interpret x, y, z, ... as propositions, either both sides come out true, or both come out false.

In particular, an expression E(x,y,z,...) is said to be valid if the equation E(x,y,z,...) = 1 is valid, i.e. if E(x,y,z,...) always comes out true.

An inference of the form

From E1(x,y,z,...), E2(x,y,z,...), ..., En(x,y,z)

Conclude F(x,y,z,...)

is said to be valid if no matter how you interpret x, y, z, ... as propositions, if the hypotheses come out true, so does the conclusion. Note that this is the same sense of “validity” that we used in talking about Aristotle’s syllogism.

This notion of validity just described corresponds to the first interpretation. Now here is the big idea! It turns out that the following are equivalent:

E(x,y,z,...) is valid in the sense of the first interpretation

E(x,y,z,...) is valid in the sense of the second interpretation

E(x,y,z,...) is valid in the sense of the third interpretation

E(x,y,z,...) = 1 can be derived from the laws for a Boolean algebra

There is a similar characterization of the valid inferences. This equivalence is very powerful. It implies, for example, that one test the validity of a logical formula by substituting all possible combinations of 0’s and 1’s, and calculating. It also means that algebraic proofs from the laws above can be used to infer logical validities.

Thus Boole’s logic builds on ideas that trace back to Aristotle, Lull, Hobbes, and Leibniz (among others):

· As far as validity goes, what is important about a statement or an inference is its logical form.

· Symbols can be used to represent propositions, or properties.

· Reasoning is a form of calculation.

· Reasoning can be carried out mechanically.

· Symbolic processes can be used to infer general truths.