Boolean algebra (logical)

See also: Boolean algebra

The Boolean algebra is the part of the Mathématiques, the Logique and the electronic which is interested in the operations and the functions on the logical variables. The name comes from George Boole, a British mathematician who, during the middle of the 19th century, restructured completely the Logique in a formal Système. More specifically, the Boolean algebra makes it possible to use algebraic techniques to treat the expressions with two values of the logical of the proposals.

Today, the Boolean algebra finds many applications in data processing and in the design of the electronic circuits. It was used the first time for the telephone gates by Claude Shannon.

The Boolean algebra of the switching functions makes it possible to model logical reasoning, by expressing a “state” according to conditions. For example:

Communication = Émetteur AND Receiving

Communication is “TRUE” So Transmitting credit AND active Receiver (it is a switching function depending on the Émetteur variables and Receiver)

Décrocher = (Decision to answer AND Ringing) OR decision to call

Décrocher is “TRUE” If the ringing is heard AND that one decides to answer OR if one decides to call.

The Boolean algebra being a field common to three disciplines, one meets different notations to indicate the same object. In the remainder of the article, one will indicate the various notations, but one will privilege some to preserve a certain homogeneity.

Boolean algebra of the values of truth

One calls B the unit made up of two elements called values of truth {TRUE, FALSE}. This unit is also noted

• B = {1, 0}
• B = $\backslash \; \{\backslash \; signal,\; \backslash \; perp\; \backslash \}$.

One will privilege in the continuation the notation B = {1, 0}.

On this unit one can define two laws (or operations or functors), the laws And OR and a transformation called the complementary one, the inversion or the opposite.

The law AND, known as conjunction

It is in the following way defined: has AND B is TRUE if and only if has is TRUE and B is TRUE. This law is also noted

• $\backslash \; cdot\; \backslash ,$
• $\backslash \; wedge$
• “&” or “&&” in some computer programming languages (Perl, C,…)
• “ AND ” in certain computer programming languages (Pascal, Python,…)
• “∧” in some algebraic notations, or in APL

One will privilege in the continuation the notation $\backslash \; cdot\; \backslash ,$

One can build the table of this law (like a table of addition or multiplication of our childhood) but one will not confuse it with a Truth table.

The law OR, known as disjunction or inclusive disjunction

It is in the following way defined: has OR B is TRUE if and only if has is TRUE or B is TRUE. (let us note that if has is true and that B is true also, then has OR B is true.) This law is also noted

• $+\; \backslash ,$
• $\backslash \; vee$
• “ | ” or “ || ” in some computer programming languages
• “ GOLD ” in certain computer programming languages
• “∨” in some algebraic notations or in APL.
• “<” very seldom.

One will privilege in the continuation the notation $+\; \backslash ,$ but one will take guard which this law does not have of relationship with the addition that one knows.

Opposite, known as negation

Opposite of " a" is TRUE if and only if has is FALSE. The opposite of has is noted

• non-a
• $\backslash \; bar\; \{has\}$
• $\backslash \; neg\; (a)$
• “! ” in some computer programming languages
• “ NOT ” in certain computer programming languages
• “~” in some algebraic notations or in APL.

One will privilege in the continuation the notation $\backslash \; bar\; \{has\}$.

One obtains then $\backslash \; bar\; \{0\}\; =1$ and $\backslash \; bar\; \{1\}\; =0$

Properties

Associativeness

As with the usual operations, certain brackets are useless:
$(has\; +\; b)\; +\; C\; =\; has\; +\; (B\; +\; c)\; =\; has\; +\; B\; +\; c$
$(A.\; b).\; C\; =\; A.\; (B.\; c)\; =\; A.B.\; c$

Commutation

The order is without importance.
$a\; +\; B\; =\; B\; +\; a$
$a.\; B\; =\; B.\; a$

Distributivity

As with the usual operations, it is possible to distribute:
$a.\; (B\; +\; c)\; =\; A.B\; +\; A.\; c$
Caution: different behavior compared to the operators + and * usual:
$a\; +\; (B.\; c)\; =\; (+\; b)\; has.\; (+\; c)$ has

Idempotence

$a\; +\; has\; +\; has\; =\; a$
$a.\; A.\; has\; =\; a$

Neutral element

$a\; +\; 0\; =\; a$
$a\; .1\; =\; a$

Absorption

$a\; +\; A.B\; =\; a$
$a.\; (has\; +\; b)\; =\; a$

Simplification

$a\; +\; \backslash \; overline\; \{has\}.\; B\; =\; has\; +\; b$
$a.\; (\backslash \; overline\; \{has\}\; +\; b)\; =\; A.\; b$

Redundancy

$a.\; B\; +\; \backslash \; overline\; \{has\}.\; C\; =\; A.B\; +\; \backslash \; overline\; \{has\}.\; C\; +\; B.\; c$

Complementarity

$a\; =\; \backslash \; overline\; \{\backslash \; overline\; \{has\}\}$

(“the light is lit” = “the light is not lit”)

$a\; +\; \backslash \; overline\; \{has\}\; =\; 1$

(“TRUE” IF lumière_allumée OR IF lumière_non_allumée → it is always the true case → in all the always TRUE cases →, therefore =1)

$a.\; \backslash \; overline\; \{has\}\; =\; 0$

(“TRUE” IF lumière_allumée AND IF lumière_non_allumée → impossible false → in all the cases → always FALSE thus =0)

Structure

One then finds all the properties which confer on B a structure of Boolean algebra

Priority

To facilitate their comprehension, it was decided that these operations would be subject to the same rules as the operations “of the every day”, the function AND (logical multiplication) is thus priority compared to the function OR (logical sum); one can, to help, place brackets in the operations.

Example:

$\{has\; =\; 0;\; B\; =\; 1;\; does\; C\; =\; 1\}$

One seek $a.\; B\; +\; C\; =???$

Initially one calculates $a.\; b$:

$a.\; B\; =\; 0.\; 1$

$0\; .\; 1\; =\; 0$

Then, one calculates $0\; +\; c$:

$0\; +\; C\; =\; c$

$c\; =\; 1$

the end result is thus:

$a.\; B\; +\; C\; =\; 1$

Theorem of Morgan

|}

In both cases, the expression will not be TRUE that if has and B are fausses.

|}

In both cases, the expression will be FALSE only if has and B are true.

Switching functions

Mathematically, a switching function or logical operator is an application of Bⁿ in B .

In electronics, a switching function is a block box which receives in entry a certain number of logical variables and which returns at exit a logical variable depending on the variables of entry. The article Switching function specifies how to build the block boxes of some fundamental functions.

A Truth table makes it possible to specify the state of the exit according to the states of the entries.

It is shown that any switching function can be described using the three basic operations.

• $+\; \backslash ,$
• $\backslash \; cdot\; \backslash ,$
• $\backslash \; bar\; \{\}\; \backslash ,$

Fundamental switching functions

They result from the three basic operations and define

• then a function of B in B : the complementary one or inversion
• two functions of B² in B which are the sum (or OR) and the product (or AND)

Made up switching functions

They are the switching functions with two variables. Among those, one counts some of them sufficiently interesting so that them a name is given.

OR exclusive, known as exclusive disjunction

OR studied until now must include itself/understand in the following way: “one or the other or both”. It is also called “OR inclusive”. The OR exclusive (or clusive XOR for “E” X' OR' ) gets along like: “one or the other but not both”.

It is composed in the following way:

$a\; \backslash \; \backslash \; operatorname\; \{XOR\}\; \backslash \; B\; =\; (a+b).\; \backslash \; overline\; \{(a.b)\}\; =\; has\; \backslash \; bar\; \{B\}\; +\; \backslash \; bar\; \{has\}\; b$

“The or exclusive one” is sometimes noted by the arithmetic sign $\backslash \; ne$ ( different from ), to which it is equivalent. Functionally, one uses also one + surrounded: $a\backslash oplus\; b$.

Equivalence

Equivalence (noted EQV) is true if the two entries have the same value and false if not. It is also called “not-or exclusive” It is composed as follows:

$a\; \backslash \; \backslash \; operatorname\; \{EQV\}\; \backslash \; B\; =\; \backslash \; overline\; \{(a+b)\}\; +\; (a.b)$

One can as say as:

$a\; \backslash \; \backslash \; operatorname\; \{EQV\}\; \backslash \; B\; =\; \backslash \; overline\; \{has\; \backslash \; \backslash \; operatorname\; \{XOR\}\; \backslash \; B\}$

It happens that equivalence is noted by the sign $\backslash \; Leftrightarrow$, although this choice is not recommended taking into account the other possible directions attached to this sign.

Implication

Implication (noted IMP) is written in the following way:

$a\; \backslash \; \backslash \; operatorname\; \{IMP\}\; \backslash \; B\; =\; \backslash \; overline\; \{has\}\; +b$

This operation is not commutative. is a condition sufficient has for B, which, it, is a necessary condition for A.

Inhibition

Inhibition (noted INH) is composed as follows:

$a\; \backslash \; \backslash \; operatorname\; \{INH\}\; \backslash \; B\; =\; A.\; \backslash \; overline\; \{B\}$

This operation is not commutative.

Example of switching functions to three or four variables

Switching function with three variables

If the example of the telephone is taken again, one is in the presence of 3 variables:

• has = " the telephone sonne"
• B = " one wants of répondre"
• C = " one wants to call quelqu'un"

the variable D = " one décroche" is switching function of the 3 preceding ones. It will be written that

$D\; =\; a.b\; +\; c$

because one takes down when that sounds and that one wants to answer or when one wants to call somebody.

The truth table of this function D is then the following one:

The observation of the table shows that our analysis first comprised a situation absurdity: the telephone sounds, one wants to call somebody, but one does not want to answer and one takes down nevertheless. That is certainly not the desired behavior, it is thus preferable to modify the function to take down so that the following table is obtained:

By reading the process of the simplification of the expressions below, you will see that the formula of décrocher2 corresponds to $d2\; =\; \backslash \; bar\; a.c\; +\; a.b$.

Switching function with four variables

A good pupil questions himself if it is wise to leave one evening. He must decide according to four proposals:

• he has enough money

• he finished his duties

• public transport is in strike

• the car of his/her father is available

This pupil will be able to leave if:

• it has enough money, has = true

• it finished its duties, therefore B = true
• public transport is not burdens some, therefore C = false
• or if the car of his/her father is available, therefore D = true

Thus the logical expression to leave according to the state the variables has, B, C and D; and it can be written as follows:

To leave = $a.b.\; (\{\backslash \; bar\; C\}\; +d)$

Minimization of an expression

A switching function can be given

• either in the form of an expression utilizing the 3 operations ($+\; \backslash ,$, $\backslash \; cdot\; \backslash ,$, $\backslash \; bar\; \{\}\; \backslash ,$)
• or in the form of its truth table. In this case it will be always possible to write this function like a sum of products.

Example: In the example of " téléphoner2" , one realizes that the result is to 1 when (has, B, c) = (0, 0,1) or (0, 1,1) or (1, 1,0) or (1, 1,1).

That makes it possible to define d2 by $d2\; =\; \backslash \; bar\; A.\; \backslash \; bar\; b.c\; +\; \backslash \; bar\; a.b.c\; +\; a.b.\; \backslash \; bar\; C\; +\; a.b.c$

It is then interesting to find an expression minimizing the number of terms and the number of letters in each term. It is the objective of certain techniques like the Méthode of Quine-Mc Cluskey, the Karnaugh maps…

Example (continuation): the preceding sum can be reduced in

$d2\; =\; \backslash \; bar\; a.c\; +\; a.b$

by factorization of the first two terms by $\backslash \; bar\; a.c$ and factorization of the last two terms by $a.b\; \backslash ,$

Tree of expression

The logical expressions are often represented in Informatique in the form of tree structure. The latter comprises a top (the root in fact) to which are attached different under trees (or branches). The junctions are internal tops. The number of under-trees connected to the same top is called Arité. The tops without exit are called sheets. Each internal top is identified by a Boolean operator whereas the sheets represent the variables which undergo these operations.

See too

Internal bonds

• Switching function ~ Calculation of the proposals ~ numerical Numbering system ~ Electronic ~ Neuron ~ George Boole ~ Operations on the bits
• the wikilivre architecture of the computers: how to synthesize logical doors by assembly of transistors CMOS?

External bond

Boolean algebra applied to electronics

Simple: Boolean will algebra

Random links:

Cannes festival 1972 | First class | Thret bourbon | Tales of Canterbury | Franz Josef Holzer

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org