en:mathematics:logic:boolean

If “today is Monday'” is true then “Not(today is Monday)” is false. This logical expression translates into English as “today is Not Monday” and this makes it easier to see that it is false if today is indeed Monday. Explanations like that rapidly become convoluted and difficult to follow and this is part of the power of Boolean logic. You can write down arguments in symbolic form. To simplify the handling of complex binary connectives, the mathematician George Boole developed Boolean Algebra, using ordinary algebraic notations AND, OR and NOT. Alternatives that you may encounter are ^ for AND, v for OR, and either over-score or prefix for NOT.

And … The Boolean AND is the same as the English use of the term, but the Boolean OR is a little different: If you are asked “coffee OR tea?”, in most western households you are not expected to say “yes” to both, while in the Boolean case OR includes both. The Boolean operator that corresponds to the English use of the term “OR” is the XOR.

Suppose you want to build a security system which only works at night and responds to a window or the front door being opened. If you have light sensors you can use these for giving off a signal indicating the truth of the statement:

Front door open | Window open | Burglary in progress |
---|---|---|

False | False | False |

False | True | True |

True | False | True |

True | True | True |

We can make the propositions as complex as we want:

(Burglary in progress) = (NOT(It is daytime)) AND ((Window open) OR (Front door open)) --------- Front door open -----> | | | OR |----- Window open -----> | | | --------- --------- +-----> | | | AND |-----> Burglary in progress --------- +-----> | | | | | --------- It is day time -----> | NOT |----- | | ---------

Boolean operations are carried out in a well defined order or “precedence”:

Operator | Symbol | Precedence |
---|---|---|

NOT | ' | Highest |

AND | . | Middle |

OR | + | Lowest |

Expressions inside brackets are always evaluated first, overriding the default precedence order. The Boolean equation of the Burglary in progress block diagram in fully bracketed form:

B = ((T'). ((W) + (F)))

Using the precedence rules this can be simplified to:

B = T'. (W + F)

And there are rules to manipulate Boolean expressions. The most simple are the rules for the unary operator NOT:

(A')' = A A' . A = 0 A' + A = 1

For more see Group theory Boolean Algebra

Associative:

(A . B) .C = A . (B . C) (A + B) + C = A + (B + C)

Commutative:

A . B = B . A A + B = B + A

Distributive:

A . (B + C) = A . B + A . C A + (B . C) = (A + B) . (A + C)

The first group of simplification rules uses one variable:

A . A = A A + A = A

The second group uses Boolean constants:

A . 0 = 0 A . 1 = A A + 0 = A A + 1 = 1

en/mathematics/logic/boolean.txt · Last modified: 2018/08/18 15:50 by Digital Dot