Boolean algebra

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

In mathematics, digital electronics and computing, Boolean algebra, also called Boolean algebra, is an algebraic structure that schematizes logical operations.

History

It is named after George Boole (1815-1864), a self-taught English mathematician who was the first to define it as part of a logical system, initially in a small pamphlet from 1847, The Mathematical Analysis of Logic, published in response to an ongoing controversy between Augustus De Morgan and sir William Rowan Hamilton. Boolean algebra was an attempt to use algebraic techniques to deal with expressions of propositional logic. It was later extended as a larger book: An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities (also known as An Investigation of the Laws of Thought or simply The Laws of Thought), published in 1854.

The respective interpretations of symbols 0 and 1 in the logic system are Nada and Universo.
George Boole

Today, Boolean algebra is widely applied in the field of electronic design. Claude Shannon was the first to apply it in the design of bistable electrical switching circuits, in 1948. This logic can be applied to two fields:

To analysis, because it is a concrete way to describe how circuits work.
To design, since having a function the algebra is applied in order to develop a function implementation.

Definition

Given a set ${mathfrak {B}}$ which defines two internal composition laws ${displaystyle oplusodot }$ . The structure ${displaystyle ({mathfrak {B}},oplusodot)}$ It's a Boole algebra if and only if ${displaystyle ({mathfrak {B}},oplusodot)}$ is a Distribution Reticle, and complementary, that is:

$odot$ is distributive to $oplus$ :

{displaystyle aodot (boplus c)=(aodot b)oplus (aodot c)}

$oplus$ is distributive to $odot$

{displaystyle aoplus (bodot c)=(aoplus b)odot (aoplus c)}

Based on this definition, the following is determined.

Beginning

Given a set: ${mathfrak {B}}$ formed at least by the elements: $varnothing;U$ which has been defined:

An internal unit operation, we'll call Complement:

{begin{array}{rrcl}sim:&{mathfrak {B}}&to &{mathfrak {B}}\&a&to &b=sim aend{array}}

In this operation we define an application that, to each element a of B, assigns you a b of B.

{displaystyle forall ain {mathfrak {B}},:quad exists !bin {mathfrak {B}};/quad b=sim a}

For every element a in B, it is fulfilled that there is only one b in B, such that b is the complement of a.

The internal binary operation, we'll call amount:

{begin{array}{rrcl}oplus:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=aoplus bend{array}}

by which we define an application that, at each ordered pair (a, b) B for B, assigns you a c of B.

forall (a,b)in {mathfrak {B}}times {mathfrak {B}},:quad exists !cin {mathfrak {B}};/quad c=aoplus b

For all ordered pairs (a, b) in B for B, it is fulfilled that there is only one c in B, such that c is the result of sumar a with b.

The internal binary operation, we'll call product:

{begin{array}{rrcl}odot:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=aodot bend{array}}

With what we define an application that, at each ordered pair (a, b) B for B, assigns you a c of B.

forall (a,b)in {mathfrak {B}}times {mathfrak {B}},:quad exists !cin {mathfrak {B}};/quad c=aodot b

For all ordered pairs (a, b) in B for B, it is fulfilled that there is only one c in B, such that c is the result of the product a and b.

Given the definition of Boolean algebra as a generic algebraic structure, depending on the specific case in question, the symbology and the names of the operations may vary.

Necessary axioms

We will say that this set and operations as defined: $({mathfrak {B}},simoplusodot)$ They're a Boole algebraif you fulfill the following axioms:

1st: The associative law of the sum:

forall a,b,cin {mathfrak {B}}:;(aoplus b)oplus c=aoplus (boplus c)

2nd: Existence of the neutral element for the sum:

forall ain {mathfrak {B}}:;aoplus varnothing =a

3a: The commutative law of the sum:

forall a,bin {mathfrak {B}}:;aoplus b=boplus a

4a: Distributive law of the sum for the product:

forall a,b,cin {mathfrak {B}}:;aoplus (bodot c)=(aoplus b)odot (aoplus c)

5a: There is a supplementary element for the sum:

forall ain {mathfrak {B}};;exists sim ain {mathfrak {B}}:;aoplus sim a=U

1b: The associative law of the product:

forall a,b,cin {mathfrak {B}}:;(aodot b)odot c=aodot (bodot c)

2b: Existence of the neutral element for the product:

forall ain {mathfrak {B}}:;aodot U=a

3b: The commutative law of the product:

forall a,bin {mathfrak {B}}:;aodot b=bodot a

4b: Distributive product law in respect of the sum:

forall a,b,cin {mathfrak {B}}:;aodot (boplus c)=(aodot b)oplus (aodot c)

5b: There is a complementary element for the product:

forall ain {mathfrak {B}};;exists sim ain {mathfrak {B}}:;aodot sim a=varnothing

Fundamental Theorems

Starting from the five previous axioms, the following fundamental theorems can be deduced and proved:

6a: Law of idempotence for the sum:

forall ain {mathfrak {B}}:;aoplus a=a

7a: Law of domination for the sum:

forall ain {mathfrak {B}}:;aoplus U=U

8th: Identity Law for the sum:

forall ain {mathfrak {B}}:;aoplus varnothing =a

9a: Absorption Act for the sum

{displaystyle forall a,bin {mathfrak {B}}:;aoplus (aodot b)=a}

10th: Morgan Act for the sum:

{displaystyle forall a,bin {mathfrak {B}}:;aoplus b=sim (sim aodot sim b)}

6b: idempotency law for the product:

forall ain {mathfrak {B}}:;aodot a=a

7b: Law of domination for the product:

forall ain {mathfrak {B}}:;aodot varnothing =varnothing

8b: Identity Law for the Product:

forall ain {mathfrak {B}}:;aodot U=a

9b: Product Absorption Act

{displaystyle forall a,bin {mathfrak {B}}:;aodot (aoplus b)=a}

10b: De Morgan Act for the product:

{displaystyle forall a,bin {mathfrak {B}}:;aodot b=sim (sim aoplus sim b)}

11: Involution Act:

forall ain {mathfrak {B}}:;sim (sim a)=a

12: Supplementary Act:

{displaystyle sim U=varnothing ;,quad sim varnothing =U}

Order in Boolean algebra

Be: $({mathfrak {B}},simoplusodot)$ an algebra of Boole, be it a, b two elements of the whole, then we can say that a before b and we denote it:

apreceq b

if any of the following conditions are met:

$aoplus b=b$
$aodot b=a$
$sim aoplus b=U$
$aodot sim b=varnothing$

These four conditions are considered equivalent and the fulfillment of one of them necessarily implies the fulfillment of the others. Defining a partially ordered set.

If it is true that:

a,bin {mathfrak {B}};:quad apreceq b;lor ;bpreceq aquad longrightarrow quad a,brightarrow {mathit {comparables}}

For values a, b of ${mathfrak {B}}$ that they fulfill a before bor what b before aIt's said that a and b They are. comparable.

If it is true that:

a,bin {mathfrak {B}};:quad anpreceq b;land ;bnpreceq aquad longrightarrow quad a,brightarrow {mathit {no;comparables}}

For values a, b of ${mathfrak {B}}$ that they fulfill a does not precede band what b does not precede aIt's said that a and b They are. not comparable.

Principle of duality

The concept of duality allows this fact to be formalized: any logical relationship or law will correspond to its dual, formed by the exchange of the operators amount with the productand $U;$ with $varnothing$ .

	Addendum	Output
1	$aoplus sim {a}=U,$	$aodot sim {a}=varnothing$
2	$aoplus varnothing =a,$	$aodot U=a,$
3	$aoplus U=U,$	$aodot varnothing =varnothing ,$
4	$aoplus a=a,$	$aodot a=a,$
5	$aoplus b=boplus a,$	$aodot b=bodot a,$
6	$aoplus (boplus c)=(aoplus b)oplus c,$	$aodot (bodot c)=(aodot b)odot c,$
7	$aoplus (bodot c)=(aoplus b)odot (aoplus c),$	${displaystyle aodot (boplus c)=(aodot b)oplus (aodot c,)}$
8	$aoplus aodot b=a,$	$aodot (aoplus b)=a,$
9	$sim {(aoplus b)}=sim {a}odot sim {b}$	$sim {(aodot b)}=sim {a}oplus sim {b},$

Other forms of notation for Boolean algebra

In binary Logic, notation is usually used $({0,1},{bar {}},+,cdot)$ , common in digital technology, being the most common and most comfortable way to represent.

For example, De Morgan's laws are represented like this:

overline {a+b}={bar {a}}cdot {bar {b}},

overline {acdot b}={bar {a}}+{bar {b}},

When Boolean algebra is used in electronics, the same denomination is usually used as for the AND (AND), OR (OR) and NOT (NOT) logic gates, sometimes being extended with X-OR (exclusive OR) and its negated NAND (NOT AND), NOR (NOT OR) and X-NOR (equivalence). Variables can be represented by uppercase or lowercase letters, and can take the values {0, 1}.

Using this notation, De Morgan's laws are represented:

{mbox{NOT }}(a{mbox{ OR }}b)={mbox{NOT }}a{mbox{ AND }}{mbox{NOT }}b,

{mbox{NOT }}(a{mbox{ AND }}b)={mbox{NOT }}a{mbox{ OR }}{mbox{NOT }}b,

In its application to logic is used notation $land lor lnot$ and variables can take the values {F, V}, false or true, equivalent to {0, 1}

With logical notation, De Morgan's laws would look like this:

lnot {(alor b)}=lnot {a}land lnot {b},

lnot {(aland b)}=lnot {a}lor lnot {b},

In the Theory format of sets the Boole Algebra takes the look: $({mathcal {P}}(U),simcupcap)$

In this notation, De Morgan's laws would be as follows:

sim {(acup b)}=;sim {a};cap sim {b},

sim {(acap b)}=;sim {a};cup sim {b},

Another form in the algebra of sets of Boolean Algebra, De Morgan's laws would be like this:

{(Acup B)}^{C}=;{A}^{C}cap {B}^{C}

{(Acap B)}^{C}=;{A}^{C}cup {B}^{C}

From a practical point of view there is a simplified way to represent boolean expressions. Apostrophes (') are used to indicate negation, the operation addition (+) is represented in the normal way in algebra, and for the product no sign is used, the variables are represented, normally with a capital letter, the sequence of two variables indicates the product between them, not a variable named with two letters.

The representation of De Morgan's laws with this system would look like this, with lowercase letters for the variables:

(a+b)'=a'b',

(ab)'=a'+b',

and so on, using capital letters to represent the variables:

(A+B)'=A'B',

(AB)'=A'+B',

All these forms of representation are correct, are used in fact, and can be seen by consulting the bibliography. The use of one or another notation does not modify Boolean algebra, only its appearance, and it depends on the branch of mathematics or the technology in which it is being used to use one or another notation.

Algebraic structures that are Boolean algebras

There are numerous cases of different analyzes of algebraic structures that correspond to Boolean algebra, although in appearance they are very different, their structure is the same. We are going to see some of them, with the purpose of making palpable the similarities in the structure and the different fields of application and different terminology to refer to operations or variables.

Binary Logic

Main article: Binarian logic

Main article: Digital system

Main article: binary system

Main article: Table of truth

Main article: Combined system

Main article: Canonical forms (Boole algebra)

Main article: Switch circuit

A series of topics, apparently so different, has two things in common, the binary logic based on zeros and ones and the algebra of Boole, possibly the best known form of this algebra, which sometimes gives rise to the interpretation that the algebra of Boole is the binary logic exclusively, so the whole ${mathfrak {B}}$ In this case it is formed by two elements {0.1}, or {F, V}, or {no, yes}, two opposing values, which are the two possible alternatives between two possible situations, here, without loss of generality, we will take the set: {0.1} as we have already said:

{mathfrak {B}}={0,1}

Where:

varnothing =0

U=1;

The internal unit operation, we'll call denial:

{begin{array}{c|c}a&{bar {a}}\hline 0&1\1&0end{array}}

{begin{array}{rrcl}{bar {}}:&{mathfrak {B}}&to &{mathfrak {B}}\&a&to &b={bar a}end{array}}

The internal unary operation negation, we define a mapping that to each element a of {0,1}, assigns a b of {0,1}.

forall ain {mathfrak {B}},:quad exists !bin {mathfrak {B}};/quad b={bar {a}}

For every element a in {0,1}, it is true that there is a unique b in {0,1 }, such that b is the negation of a. As seen in the table.

The internal binary operation, we'll call amount:

{displaystyle {begin{array}{cc|c}a&b&a+b\hline 1&1&1\1&0&1\0&1&1\0&0&0\end{array}}quad longleftrightarrow quad {begin{array}{c|cc}0&1&0\1&1&1\hline +&1&0\end{array}}}

{begin{array}{rrcl}+:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=a+bend{array}}

With the addition operation we define a map that, to each ordered pair (a, b) of B by B, it assigns a c of B to it.

forall (a,b)in {mathfrak {B}}times {mathfrak {B}},:quad exists !cin {mathfrak {B}};/quad c=a+b

For every ordered pair (a,b) in B times B, it is true that there exists a unique c in B, such that c is the result of adding a with b.

the internal binary operation, which we will call product:

{displaystyle {begin{array}{cc|c}a&b&acdot b\hline 1&1&1\1&0&0\0&1&0\0&0&0\end{array}}quad longleftrightarrow quad {begin{array}{c|cc}0&0&0\1&1&0\hline cdot &1&0\end{array}}}

{begin{array}{rrcl}cdot:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=acdot bend{array}}

With the product operation we define a map that, to each ordered pair (a, b) of B by B, it assigns a c of B to it.

forall (a,b)in {mathfrak {B}}times {mathfrak {B}},:quad exists !cin {mathfrak {B}};/quad c=acdot b

For every ordered pair (a, b) in B times B, it holds that there exists a unique c in B, such that c is the result of the product a and b. As can be seen in the table.

Axioms

So. $({0,1},{bar {}},+,cdot)$ It's a Boole algebra following axioms:

1st: The associative law of the sum:

forall a,b,cin {0,1}:;(a+b)+c=a+(b+c)

1b: The associative law of the product:

forall a,b,cin {0,1}:;(acdot b)cdot c=acdot (bcdot c)

2nd: Existence of the neutral element for the sum:

forall ain {0,1}:;a+0=a

2b: Existence of the neutral element for the product:

forall ain {0,1}:;acdot 1=a

3a: The commutative law of the sum:

forall a,bin {0,1}:;a+b=b+a

3b: The commutative law of the product:

forall a,bin {0,1}:;acdot b=bcdot a

4a: Distributive law of the sum for the product:

forall a,b,cin {0,1}:;a+(bcdot c)=(a+b)cdot (a+c)

4b: Distributive product law in respect of the sum:

forall a,b,cin {0,1}:;acdot (b+c)=(acdot b)+(acdot c)

5a: There is a supplementary element for the sum:

forall ain {0,1};;exists {bar {a}}in {0,1}:;a+{bar {a}}=1

5b: There is a complementary element for the product:

forall ain {0,1};;exists {bar {a}}in {0,1}:;acdot {bar {a}}=0

Later. $({0,1},{bar {}},+,cdot)$ It's Boole algebra.

Fundamental theorems

Starting from these axioms, the following theorems can be proved:

6a: Law of idempotence for the sum:

forall ain {0,1}:;a+a=a

6b: idempotency law for the product:

forall ain {0,1}:;acdot a=a

7a: Law of domination for the sum:

forall ain {0,1}:;a+1=1

7b: Law of domination for the product:

forall ain {0,1}:;acdot 0=0

8th: Identity Law for the sum:

forall ain {0,1}:;a+0=a

8b: Identity Law for the Product:

forall ain {0,1}:;acdot 1=a

9a: Absorption Act for the sum

{displaystyle forall a,bin {0,1}:;a+(acdot b)=a}

9b: Product Absorption Act

{displaystyle forall a,bin {0,1}:;acdot (a+b)=a}

10th: Morgan Act for the sum:

{displaystyle forall a,bin {0,1}:;a+b={overline {{bar {a}}cdot {bar {b}}}}}

10th: De Morgan Act for the product:

{displaystyle forall a,bin {0,1}:;acdot b={overline {{bar {a}}+{bar {b}}}}}

11: Involution Act:

forall ain {0,1}:;{bar {{bar {a}}}}=a

12: Supplementary Act:

{bar {1}}=0

{bar {0}}=1

Order in Boolean algebra

Starting from $({0,1},{bar {}},+,cdot)$ Boole algebra, given two binary variables: a, bwhich meet any of these conditions:

{displaystyle left.{begin{array}{l}a+b=b\acdot b=a\{bar {a}}+b=1\acdot {bar {b}}=0end{array}}right}longrightarrow quad aleq b}

so a is less than or equal to b. Given the binary values 0 and 1, we can see:

$0+1=1$
$0cdot 1=0$
${bar {0}}+1=1$
$0cdot {bar {1}}=0$

These four conditions are equivalent and the fulfillment of one of them supposes the fulfillment of the others, in this case it is easy to check them all. Then we can say that 0 precedes 1 and denote it:

0leq 1

If we also know that 0 and 1 are different values:

<math alttext="{displaystyle left.{begin{array}{l}0leq 1\0neq 1end{array}}right}longrightarrow quad 00≤ ≤ 10I was. I was. 1!Δ Δ 0.1{displaystyle left.{begin{array}{l}0leq 1neq 1end{array}}}rightlongrightarrow quad 0≤1}<img alt="{displaystyle left.{begin{array}{l}0leq 1\0neq 1end{array}}right}longrightarrow quad 0

The binary value 0 is less than the binary value 1.

Algebra of sets

Main article: Algebra of sets

Main article: Theory of sets

Main article: Power set

Main article: Venn Diagram

Given any set U, it's called power set Uto all possible subsets of U and we denote it. ${mathcal {P}}(U)$ .

As an example we can consider:

U={a,b,c,d,e,f},

Which has as a power set:

{displaystyle {mathcal {P}}(U)={Big {}{},{a},{b},dots{a,b},{a,c},dots{a,b,c,d,e},dotsU{Big }}}

The empty set is the one that has no elements and is represented:

{displaystyle {}quad equiv quad emptyset quad equiv quad varnothing }

We can define:

{mathfrak {B}}={mathcal {P}}(U)

And of course:

varnothing =varnothing

U=U;

The internal unit operation, we'll call Complement:

{begin{array}{rrcl}{}^{C}:&{mathcal {P}}(U)&to &{mathcal {P}}(U)\&A&to &B=A^{C}end{array}}

In this operation we define a mapping that, to each element A of P(U), assigns a B of P(U).

forall Ain {mathcal {P}}(U),:quad exists !Bin {mathcal {P}}(U);/quad B=A^{C}

For every element A in P(U), there is a unique B in P(U), such that B is the complement of A.

Defining the complement of a set like this:

{displaystyle B=A^{C}longrightarrow quad forall xin B:quad xin U;land ;xnotin A}

B is the complement of A, if it holds that for every x that belongs to B, x belongs to U and x does not belong to A.

The first binary operation will be called union:

{begin{array}{rrcl}cup:&{mathcal {P}}(U)times {mathcal {P}}(U)&to &{mathcal {P}}(U)\&(A,B)&to &C=Acup Bend{array}}

With this inner binary operation we define a map that, to each ordered pair (A, B) of P(U) by P(U), assigns it a C of P(U).

forall (A,B)in {mathcal {P}}(U)times {mathcal {P}}(U),:quad exists !Cin {mathcal {P}}(U);/quad C=Acup B

For every ordered pair (A,B) in P(U) by P(U), it is satisfied that there exists a unique C in P(U), such that C is the union A and B.

Defining the union of two sets as:

{displaystyle C=Acup Blongrightarrow quad forall xin C:quad xin A;lor ;xin B}

The set C is the union of A and B, if for every element x of C, it is true that x is an element of A or B

The second binary operation will be called. intersection:

{begin{array}{rrcl}cap:&{mathcal {P}}(U)times {mathcal {P}}(U)&to &{mathcal {P}}(U)\&(A,B)&to &C=Acap Bend{array}}

With which we define a map that, to each ordered pair (A, B) of P(U) by P(U), assigns a C of P(U) to it.

forall (A,B)in {mathcal {P}}(U)times {mathcal {P}}(U),:quad exists !Cin {mathcal {P}}(U);/quad C=Acap B

For every ordered pair (A,B) in P(U) by P(U), it is true that there exists a unique C in P(U), such that C is the intersection A and B.

Defining the intersection of two sets as:

{displaystyle C=Acap Blongrightarrow quad forall xin C:quad xin A;land ;xin B}

The set C is the intersection of A and B, if for every element x of C, it is true that x is an element of A and B.

Axioms

With what we can say: $({mathcal {P}}(U),{}^{C},cupcap)$ For a U known as Boole algebra if you fulfill the following axioms:

1st: The Associative Law of the Union:

forall A,B,Cin {mathcal {P}}(U):;(Acup B)cup C=Acup (Bcup C)

1b: The Associative Law of Intersection:

forall A,B,Cin {mathcal {P}}(U):;(Acap B)cap C=Acap (Bcap C)

2nd: Existence of the neutral element for the union:

forall Ain {mathcal {P}}(U):;Acup varnothing =A

2b: Existence of the neutral element for intersection:

forall Ain {mathcal {P}}(U):;Acap U=A

3a: The commutative law of union:

forall A,Bin {mathcal {P}}(U):;Acup B=Bcup A

3b: The commutative law of intersection:

forall A,Bin {mathcal {P}}(U):;Acap B=Bcap A

4a: Distributive Law of the Union regarding intersection:

forall A,B,Cin {mathcal {P}}(U):;Acup (Bcap C)=(Acup B)cap (Acup C)

4b: Distributive law of intersection with respect to union:

forall A,B,Cin {mathcal {P}}(U):;Acap (Bcup C)=(Acap B)cup (Acap C)

5a: There is a complementary element for the union:

forall Ain {mathcal {P}}(U);;exists A^{{C}}in {mathcal {P}}(U):;Acup A^{{C}}=U

5b: There is a complementary element for intersection:

forall Ain {mathcal {P}}(U);;exists A^{{C}}in {mathcal {P}}(U):;Acap A^{{C}}=varnothing

Concluding that $({mathcal {P}}(U),{}^{C},cupcap)$ It's a boole algebra.

Fundamental theorems

Starting from these axioms, the following theorems can be proved:

6a: Law of idempotence for union:

forall Ain {mathcal {P}}(U):;Acup A=A

6b: idempotence law for intersection:

forall Ain {mathcal {P}}(U):;Acap A=A

7a: Law of domination for union:

forall Ain {mathcal {P}}(U):;Acup U=U

7b: Law of domination for intersection:

forall Ain {mathcal {P}}(U):;Acap varnothing =varnothing

8th: Identity Law for Union:

forall Ain {mathcal {P}}(U):;Acup varnothing =A

8b: Identity Law for Intersection:

forall Ain {mathcal {P}}(U):;Acap U=A

9a: Law of absorption for union:

{displaystyle forall A,Bin {mathcal {P}}(U):;Acup (Acap B)=A}

9a: Law of absorption for intersection:

{displaystyle forall A,Bin {mathcal {P}}(U):;Acap (Acup B)=A}

10th: Law of De Morgan for union:

{displaystyle forall A,Bin {mathcal {P}}(U):;Acup B={({A}^{C}cap {B}^{C})}^{C}}

10b: Morgan's Law for Inerstion:

{displaystyle forall a,bin {mathcal {P}}(U):;Acap B={({A}^{C}cup {B}^{C})}^{C}}

11: Involution Act:

forall Ain {mathcal {P}}(U):;{{A}^{C}}^{C}=A

12: Supplementary Act:

{U}^{C}=varnothing

{varnothing }^{C}=U

Order in Boolean algebra

Done $({mathcal {P}}(U),{}^{C},cupcap)$ Boole algebra, we can check:

$Acup B=B$
$Acap B=A$
${A}^{C}cup B=U$
$Acap {B}^{C}=varnothing$

For the sets A and B that satisfy these properties, we can say that A precedes B, that in the case of sets we would say A is equal to or a subset of B and we denote it:

Asubseteq B

Understanding that A is equal to or a subset of B when:

Asubseteq Blongrightarrow quad forall xin A:;xin B

The set A is equal to or a subset of B, if for every element x belonging to A, x belongs to B.

You can also check:

{displaystyle forall Bin {mathcal {P}}(U):;{begin{array}{|l}Bcup U=U\Bcap U=B\{B}^{C}cup U=U\Bcap {U}^{C}=varnothing end{array}}longrightarrow quad Bsubseteq U}

For all B of the parts of U, if it is fulfilled that: the union of B and U is U, the intersection of B and U is B, the union of the complement of B and U is U, the intersection of B and the complement of U is the empty set, then B is equal to or a subset of U.

This conclusion is part of the definition of the parts of U, but it can be reached by fulfilling one of the four conditions exposed, as already mentioned, the four conditions are equivalent and the fulfillment of one of them implies the fulfillment of the others.

Applying the same reasoning we can see:

{displaystyle forall Ain {mathcal {P}}(U):;{begin{array}{|l}varnothing cup A=A\varnothing cap A=varnothing \{varnothing }^{C}cup A=U\varnothing cap {A}^{C}=varnothing end{array}}longrightarrow quad varnothing subseteq A}

Being A a set of the parts of U, concluding that the empty set is equal to or a subset of A.

Propositional Logic

Main article: Propositional logic

Main article: Proposed

Main article: Logical calculation

Main article: Mathematical Logic

A proposition, or a predicate, is a truth value that can be expressed verbally or with mathematical or logical expressions or relationships, for example:

'Today is Wednesday.'
'The building is high.'
'The dog is barking.'

They are verbally expressed propositions, and so are:

'x = 3'
'mcd(a, b) = 2n + 1'

Since each of them can be true or false, propositions are often designated by letters:

p= rain
♪ It's raining a lot ♪
R= 'I've got umbrellas'
S= 'The street is wet.'

Statements true and false are also propositions, we will designate with: ${mathfrak {B}}$ to the set of propositions, in order to see that the logic of propositions is an algebra of Boole, we will also consider:

varnothing longrightarrow quad bot =F=falso

Ulongrightarrow quad top =V=verdadero

The internal operation, which we shall call negation:

{begin{array}{rrcl}lnot:&{mathfrak {B}}&to &{mathfrak {B}}\&a&to &b=lnot aend{array}}

The internal unary operation negation, we define an application that to each proposition a, assigns another proposition b.

forall ain {mathfrak {B}},:quad exists !bin {mathfrak {B}};/quad b=lnot {a}

For every proposition a, it is true that there exists a unique proposition b, such that b is the negation of a.

The first internal binary operation, which we will call disjunction:

{begin{array}{rrcl}lor:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=alor bend{array}}

With the disjunction operation, we define a mapping that to each ordered pair (a, b) of B by B, it assigns a c of B to it.

forall (a,b)in {mathfrak {B}}times {mathfrak {B}},:quad exists !cin {mathfrak {B}};/quad c=alor b

For every ordered pair (a,b) in B times B, it is true that there exists a unique c in B, such that c is the result of the disjunction of a and b.

The second internal binary operation, which we will call conjunction:

{begin{array}{rrcl}land:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=aland bend{array}}

With the conjunction operation we define a map that, to each ordered pair (a, b) of B by B, it assigns a c of B to it.

forall (a,b)in {mathfrak {B}}times {mathfrak {B}},:quad exists !cin {mathfrak {B}};/quad c=aland b

For every ordered pair (a, b) in B times B, it holds that there exists a unique c in B, such that c is the result of the conjunction of a and b.

Axioms

So. $({mathfrak {B}},lnot {},lorland)$ It's a Boole algebra the following axioms:

1st: Associative Law of Disjunction:

forall a,b,cin {mathfrak {B}}:;(alor b)lor c=alor (blor c)

1b: The association law of the conjunction:

forall a,b,cin {mathfrak {B}}:;(aland b)land c=aland (bland c)

2nd: Existence of the neutral element for disjunction:

forall ain {mathfrak {B}}:;alor F=a

2b: Existence of the neutral element for the conjunction:

forall ain {mathfrak {B}}:;aland V=a

3a: The commutative law of disjunction:

forall a,bin {mathfrak {B}}:;alor b=blor a

3b: The commutative law of the conjunction:

forall a,bin {mathfrak {B}}:;aland b=bland a

4a: Disjunction Distributive Act for the conjunction:

forall a,b,cin {mathfrak {B}}:;alor (bland c)=(alor b)land (alor c)

4b: Distributive law of the conjunction with respect to disjunction:

forall a,b,cin {mathfrak {B}}:;aland (blor c)=(aland b)lor (aland c)

5a: There is a complementary element for disjunction:

forall ain {mathfrak {B}};;exists lnot {a}in {mathfrak {B}}:;alor lnot {a}=V

5b: There is a complementary element for the conjunction:

{displaystyle forall ain {mathfrak {B}};;exists lnot {a}in {mathfrak {B}}:;aland lnot {a}=F}

Later. $({mathfrak {B}},lnot {},lorland)$ It's boole algebra.

Fundamental theorems

Starting from these axioms, the following theorems can be proved:

6a: Law of idempotence for disjunction:

forall ain {mathfrak {B}}:;alor a=a

6b: Law of idempotence for conjunction:

forall ain {mathfrak {B}}:;aland a=a

7a: Law on Domination for Disjunction:

forall ain {mathfrak {B}}:;alor V=V

7b: Law of domination for conjunction:

forall ain {mathfrak {B}}:;aland F=F

8a: Identity Law for Disjunction:

forall ain {mathfrak {B}}:;alor F=a

8b: Identity Law for conjunction:

forall ain {mathfrak {B}}:;aland V=a

9a: Absorption Act for Disjunction:

{displaystyle forall a,bin {mathfrak {B}}:;alor (aland b)=a}

9b: Absorption Act for conjunction:

{displaystyle forall a,bin {mathfrak {B}}:;aland (alor b)=a}

10th: Morgan Act for Disjunction:

{displaystyle forall a,bin {mathfrak {B}}:;alor b=lnot {(lnot {a}land lnot {b})}}

10b: Morgan Act for conjunction:

{displaystyle forall a,bin {mathfrak {B}}:;aland b=lnot ({lnot {a}lor lnot {b})}}

11: Involution Act:

forall ain {mathfrak {B}}:;lnot lnot a=a

12: Supplementary Act:

lnot V=F

lnot F=V

Order in Boolean algebra

Knowing that $({mathfrak {B}},lnot {},lorland)$ it's Boole algebra, you can check that:

$alor b=b$
$aland b=a$
$lnot alor b=V$
$aland lnot b=F$

For the propositions: a, b that meet any of these conditions, it can be said that a precedes b. That in the case of propositions or predicates it is said that a is as strong or stronger than b, or that b is weaker than a, and we represent it:

apreccurlyeq b

So for example given the propositions:

A It rains a lot
b= Rain

we can see:

$alor b=b$

Yes: It's raining. or ♪ then. ♪.

If either of the two circumstances occurs, it rains a lot or it rains, clearly it rains in either case.

$aland b=a$

Yes: It's raining. and ♪ then. It's raining..

If we affirm that it rains a lot and that it rains, and both circumstances are met, then it rains a lot.

$lnot alor b=V$

Yes: No. It's raining. or ♪ That's it. true.

It does not rain a lot indicates that it may rain a little or not at all, if it does not rain a lot or rain it covers all the possibilities, from dry to very rainy weather, then the statement is true in any case.

$aland lnot b=F$

Yes: It's raining. and No. ♪ That's it. false.

If we affirm that it rains a lot and simultaneously that it rains, the affirmation is clearly false.

The most restrictive statement is the strongest and the least restrictive is the weakest, in this case:

llueve;muchopreccurlyeq llueve

The proposition it rains a lot is as strong or stronger than it rains, the statement it rains a lot is a particular case or the same case of it's raining.

Operations in Boolean algebra

Main article: Logical connectivity

Main article: Mathematical operation

Boolean algebra is based on a set in which three internal operations have been defined: one unary and two binary, as we have already seen, this definition being comfortable. Strictly speaking, only two are necessary, the unary and one of the binary, so, for example, in binary logic with the negation and the product we can define the sum.

With De Morgan's law:

forall a,bin {0,1}:;overline {a+b}={bar {a}}cdot {bar {b}}longrightarrow quad a+b=overline {{bar {a}}cdot {bar {b}}}

This expression is more complex, but starting from the binary negation and the binary product, the binary sum is defined.

In the image on the right we can see a parallel circuit of two buttons a and b, which corresponds to the binary sum of a and b, and their series-circuit equivalent of a and b, both give the same truth table, and therefore they are equivalent, the artifice of the series circuit to obtain the same result as in a parallel circuit shows how convenient it is to consider this function, the possibility of obtaining the sum of two binary variables through the negation and the product indicate that, in such a way primary, Boolean algebra is based on only two operations, and that any expression involving addition can be transformed into an equivalent expression involving only negation and product.

In the case of set theory with the complement and the intersection we can define the union:

{(Acup B)}^{C}={A}^{C}cap {B}^{C}longrightarrow quad Acup B={({A}^{C}cap {B}^{C})}^{C}

In a similar way to binary algebra, or any other Boolean algebra, the definition of the algebra with only two operations complicates the expressions, but allows us to determine some very useful relationships, as well as various other operations.

In the Boole algebra defined in a set ${mathfrak {B}}$ operations are internal, as part of element ${mathfrak {B}}$ to get a result in ${mathfrak {B}}$ .

Without loss of generality, and given the different forms that Boolean algebra can take, we will consider propositional logic with the propositions: a, c, b etc. Which can take the values true: V or false: F. And the logical connectives over those propositions that result in other logical propositions, each proposition: a, b, c, etc. Defines an array A, B, C, etc. That we can represent graphically in a Venn diagram.

We can see these logical connectives for: 0, 1 and 2 variables in a Hasse diagram:

Operations by the number of arguments

If we see the different operations by their number of arguments we can distinguish:

No arguments

Main article: Nullary operation

The logical operations without arguments are:

Nullary operation
Positive		Negative
${displaystyle top }$	Tautology	$bot$	Contradiction

With one argument

Main article: Unit operation

Operations with only one argument are:

Unit operation
Positive		Negative
$a,$	Logical assertion	${displaystyle neg a}$	Logical denial

With two arguments

Main article: Binarian operation

Operations that need two arguments are:

Binarian operation
Positive		Negative
${displaystyle alor b}$	Logical disjunction	${displaystyle adownarrow b}$	Opposition
${displaystyle aland b}$	Logical conjunction	${displaystyle auparrow b}$	Opposite conjunction
${displaystyle ato b}$	Logical involvement	${displaystyle anot rightarrow b}$	Logical attachment
${displaystyle aleftarrow b}$	Opposite implication	${displaystyle anot leftarrow b}$	Opposite attachment
${displaystyle aleftrightarrow b}$	Biconditional	${displaystyle anot leftrightarrow b}$	Exclusive disjunction

Null operations

A unitary operation is the one that returns a value without the need for arguments, we can see tautology and contradiction.

{begin{array}{|c||c|}hline &top \hline hline &V\hline end{array}}

The tautology presents the true value without the need for arguments or regardless of the variables on which it is calculated. In set theory it corresponds to the universal set.

In propositional logic it corresponds to the value: true:

{begin{array}{ccll}top:&varnothing &longrightarrow &{mathbb {U}}\&()&longrightarrow &a=top ()equiv a=Vend{array}}

In a switching circuit it corresponds to a fixed connection or closed bridge.

{begin{array}{|c||c|}hline &bot \hline hline &F\hline end{array}}

The contradiction, on the other hand, always presents the value false, without needing arguments or independently of the arguments presented. In set theory it corresponds to the empty set.

In propositional logic it corresponds to the value: false:

{begin{array}{ccll}bot:&varnothing &longrightarrow &{mathbb {U}}\&()&longrightarrow &a=bot ()equiv a=Fend{array}}

In a switching circuit, it corresponds to no connection or open jumper.

Unary Operations

A unary operation is one that only needs one argument to present a result, we can see two unary operations: identity and negation.

{begin{array}{|c||c|}hline a&a\hline hline V&V\F&F\hline end{array}}

The identity operation of an assertion returns the value of the variable.

{begin{array}{ccll}id:&{mathbb {U}}&longrightarrow &{mathbb {U}}\&a&longrightarrow &b=id(a)equiv b=aend{array}}

This operation can be done with the buffer amplifier electronic device.

In a commutation circuit it corresponds to a normally open switch: NO switch.

{begin{array}{|c||c|}hline a&lnot a\hline hline V&F\F&V\hline end{array}}

The logical negation operation of a variable presents the opposite value of the argument, or the opposite cases of those included in the argument.

{begin{array}{ccll}lnot:&{mathbb {U}}&longrightarrow &{mathbb {U}}\&a&longrightarrow &b=lnot (a)equiv b=lnot aend{array}}

This operation is done with the NOT Gate.

In a commutation circuit it corresponds to a normally closed switch: NC switch.

Binary operations

The binary operation is the one that needs two arguments, in fact it is the most generalized form of operation, normally when we refer to operations, we refer to binary operations, in Boolean algebra we can see the following binary operations:

{begin{array}{|c|c||c|}hline a&b&alor b\hline hline V&V&V\V&F&V\F&V&V\F&F&F\hline end{array}}

The Logical Disjunction accepts two arguments presenting as a true result if one or another of the arguments is true.

Disjunction can be expressed:

alor b;=;lnot (lnot aland lnot b)

The logical disjunction operation of propositions is equivalent to the union of sets in set theory, to the logical OR gate:

and to the parallel circuit in switching circuits

{begin{array}{|c|c||c|}hline a&b&adownarrow b\hline hline V&V&F\V&F&F\F&V&F\F&F&V\hline end{array}}

The opposite Disjunction presents true result only when its two arguments are false. This operation is the denial of disjunction.

adownarrow b;=;lnot (alor b);=;lnot aland lnot b

The joint negation of propositions is equivalent to the logical NOR gate.

{begin{array}{|c|c||c|}hline a&b&aland b\hline hline V&V&V\V&F&F\F&V&F\F&F&F\hline end{array}}

The logical conjunction presents true results only when its two arguments are true.

{begin{array}{ccll}land:&{mathbb {U}}times {mathbb {U}}&longrightarrow &{mathbb {U}}\&(a,b)&longrightarrow &c=land (a,b)equiv c=aland bend{array}}

Usually represented:

aland b

The logical conjunction of propositions is equivalent to the intersection of sets in set theory, or the logical AND gate:

in switching circuits it would be a series circuit of switches.

{begin{array}{|c|c||c|}hline a&b&auparrow b\hline hline V&V&F\V&F&V\F&V&V\F&F&V\hline end{array}}

The opposite conjunction presents true results in all cases except when their two arguments are true. This operation is the denial of the conjunction.

auparrow b;=;lnot (aland b);=;lnot alor lnot b

The logical conjunction of statements is equivalent to the NAND logic gate.

{begin{array}{|c|c||c|}hline a&b&ato b\hline hline V&V&V\V&F&F\F&V&V\F&F&V\hline end{array}}

Logical Implication presents a false result if the first argument is true and the second false, in the rest of the cases presents true result, this operation is not commutative and can be expressed:

ato b;=;lnot alor b;=;(aland b)lor lnot a

This operation is also called implication: a implies b:

Yeah. a It's true. b It's true.

Yeah. a It's fake and b It's true, involvement is false.

Yeah. a is false, implication is true independently the value of b.

This operation corresponds to a set of complex logic gates:

{begin{array}{|c|c||c|}hline a&b&anrightarrow b\hline hline V&V&F\V&F&V\F&V&F\F&F&F\hline end{array}}

The logical Attachment presents true result if the first argument is true and the second false, in the rest of the cases presents false result, this operation is not commutative and is the denial of the material conditional, also called a and b difference, can be expressed:

anrightarrow b;=;lnot (ato b);=;aland lnot b;=;a-b

This operation corresponds to a set of complex logic gates:

{begin{array}{|c|c||c|}hline a&b&aleftarrow b\hline hline V&V&V\V&F&V\F&V&F\F&F&V\hline end{array}}

The opposite Implication is the operation that presents false result if the first argument is false and the second true, in the rest of the cases presents true result, this operation is not commutative and is the result of permuting a and b on conditional material, can be expressed:

aleftarrow b;=;alor lnot b

This operation corresponds to a set of complex logic gates:

{begin{array}{|c|c||c|}hline a&b&anleftarrow b\hline hline V&V&F\V&F&F\F&V&V\F&F&F\hline end{array}}

The opposite Attachment presents true result if the first argument is false and the second true, in the rest of the cases presents false result, this operation is not commutative and is the denial of the reverse condition, also called difference: b - a, can be expressed:

anleftarrow b;=;lnot (aleftarrow b);=;lnot aland b;=;b-a

This operation corresponds to a set of complex logic gates:

{begin{array}{|c|c||c|}hline a&b&aleftrightarrow b\hline hline V&V&V\V&F&F\F&V&F\F&F&V\hline end{array}}

The Biconditional presents true result if the two arguments are equal, that is: if a and b They're real or a and b They're fake.

aleftrightarrow b;=;(aland b)lor (lnot aland lnot b)

The XNOR Gate corresponds to it.

{begin{array}{|c|c||c|}hline a&b&anleftrightarrow b\hline hline V&V&F\V&F&V\F&V&V\F&F&F\hline end{array}}

The Exclusive Disjunction presents true result if the two arguments are disparate, this is whether of the two arguments one is true and another false, is the denial of the biconditional:

anleftrightarrow b;=;lnot (aleftrightarrow b);=;(aland lnot b)lor (lnot aland b)

This operation is also called or exclusive, one or the other but not both, it corresponds to the logic gate: XOR.

Well-formed Boolean formula

Main article: Formal grammar

Main article: Formal language

Main article: Semantic formal

Main article: Formula well formed

Starting from a set: ${mathfrak {B}}$ and where a, b, c, d,... are variables or constants that can take values of the set ${mathfrak {B}}$ where the following internal operations have been defined:

{begin{array}{rrcl}sim:&{mathfrak {B}}&to &{mathfrak {B}}\&a&to &b=sim aend{array}}

{begin{array}{rrcl}oplus:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=aoplus bend{array}}

{begin{array}{rrcl}odot:&{mathfrak {B}}times {mathfrak {B}}&to &{mathfrak {B}}\&(a,b)&to &c=aodot bend{array}}

we can say that they are well-formed formulas: wff:

1: A variable or constant:

a;

2: The negation of a variable or constant:

sim a;

3: The binary operation between two variables or constants:

aoplus b;

4: The result of substituting in a well-formed formula, a variable or constant by a well-formed formula:

{displaystyle left.{begin{array}{l}aoplus b\a=codot dend{array}}right}longrightarrow quad (codot d)oplus b}

Repeated application of these criteria will always give a well-formed formula.

example:

{displaystyle left.{begin{array}{l}left.{begin{array}{l}sim a\a=bodot cend{array}}right}longrightarrow quad sim (bodot c)\;c=doplus eend{array}}right}longrightarrow quad sim (bodot (doplus e))}

You can use as many parentheses as necessary to avoid ambiguities, always avoiding the superfluous use of parentheses.

Hierarchy of operators

When evaluating a Boolean expression, operations must be performed according to their hierarchical level, performing the highest-ranking one first. If parentheses exist, the innermost ones must be resolved first and worked out. In the absence of parentheses, the hierarchy of operations is, from highest to lowest, as follows:

$sim$
$odot$
$oplus$

If there are several operations with the same hierarchy, they can be evaluated from right to left or from left to right, the result will be the same.

As an example, consider the evaluation of the following Boolean expressions:

sim aodot bquad longleftrightarrow quad (sim a)odot b

aoplus bodot cquad longleftrightarrow quad aoplus (bodot c)

aoplus boplus cquad longleftrightarrow quad (aoplus b)oplus cquad longleftrightarrow quad aoplus (boplus c)

Contenido relacionado

Más resultados...