Boolean algebra — Safekipedia Discoverer

In mathematics and mathematical logic, Boolean algebra is a special kind of algebra that is very different from the algebra most people learn in school. Instead of using numbers like 1, 2, or 3, Boolean algebra uses only two values: true (usually written as 1) and false (usually written as 0). This makes it a powerful tool for thinking about logic and decision-making.

Boolean algebra uses special operations to combine these true and false values. The main operations are conjunction (called "and," shown as ∧), disjunction (called "or," shown as ∨), and negation (called "not," shown as ¬). These operations help us understand how different logical statements relate to each other, much like how addition and multiplication relate numbers in regular algebra.

Boolean algebra was created by George Boole in the mid-1800s. His work laid the foundation for many modern technologies. Today, Boolean algebra is essential for building digital electronics, such as computers and smartphones, and it is built into every programming language we use. It also helps scientists and mathematicians work with sets and data in fields like set theory and statistics.

History

Boolean algebra grew from ideas by Gottfried Wilhelm Leibniz, who used binary thinking inspired by the I Ching. Later, George Boole created an algebra that used just two values, true and false, instead of numbers. This idea was expanded by many mathematicians in the late 1800s.

In the 1930s, Claude Shannon showed that Boole’s algebra could help design electrical circuits, calling it switching algebra. Today, Boolean algebra is important for building and testing computer circuits and solving logic problems in computer science.

Values

In Boolean algebra, instead of using numbers like in regular math, we use two special values: true and false. We write these as 1 for true and 0 for false. These values work differently from normal numbers. For example, in regular math, 1 + 1 equals 2, but in Boolean algebra, 1 + 1 equals 0.

Boolean algebra also looks at special kinds of rules and patterns using these true and false values. One common example is looking at sequences of 0s and 1s, like a code made up of these values. This helps us understand how things can be true or false in many different situations.

Operations

Further information: Truth table

Boolean algebra uses three main operations: AND, OR, and NOT. These operations help us understand how true and false values work together.

The AND operation (∧) checks if both values are true. The OR operation (∨) checks if at least one value is true. The NOT operation (¬) flips a value from true to false or vice versa. These operations can be shown in tables called truth tables, which list all possible results for different combinations of true and false.

Logical operation	Operator	Notation	Alternative notations	Definition
Conjunction	AND	x ∧ y	x AND y, Kxy	x ∧ y = 1 if x = y = 1, x ∧ y = 0 otherwise
Disjunction	OR	x ∨ y	x OR y, Axy	x ∨ y = 0 if x = y = 0, x ∨ y = 1 otherwise
Negation	NOT	¬x	NOT x, Nx, x̅, x', !x	¬x = 0 if x = 1, ¬x = 1 if x = 0

Material conditional:	x → y = ¬ x ∨ y {\textstyle x\rightarrow y=\neg {x}\vee y}
Material biconditional:	x ↔ y = ( x ∧ y ) ∨ ( ¬ x ∧ ¬ y ) = ( x ∨ ¬ y ) ∧ ( ¬ x ∨ y ) {\textstyle x\leftrightarrow y=(x\land y)\lor (\neg x\land \neg y)=(x\lor \neg y)\land (\neg x\lor y)}
Exclusive OR (XOR):	x ⊕ y = ¬ ( x ↔ y ) = ( x ∨ y ) ∧ ¬ ( x ∧ y ) = ( x ∨ y ) ∧ ( ¬ x ∨ ¬ y ) = ( x ∧ ¬ y ) ∨ ( ¬ x ∧ y ) {\textstyle x\oplus y=\neg (x\leftrightarrow y)=(x\vee y)\wedge \neg (x\wedge y)=(x\vee y)\wedge (\neg x\vee \neg y)=(x\wedge \neg y)\vee (\neg x\wedge y)}

Secondary operations. Table 1
x {\displaystyle x}	y {\displaystyle y}	x → y {\displaystyle x\rightarrow y}	x ⊕ y {\displaystyle x\oplus y}	x ↔ y , x ≡ y {\displaystyle x\leftrightarrow y,x\equiv y}
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

Laws

A law of Boolean algebra is a rule, like x ∨ (y ∨ z) = (x ∨ y) ∨ z, that shows how different parts of Boolean algebra work together. Boolean algebra uses only two values: true (1) and false (0). It has special rules for combining these values using operations like and (∧), or (∨), and not (¬).

Boolean algebra shares some rules with regular algebra, but it also has unique rules. For example, in Boolean algebra, x ∧ ¬ x always equals 0, and x ∨ ¬ x always equals 1. These rules help us understand how true and false values combine in logic and computing.

Associativity of ∨:	x ∨ ( y ∨ z ) {\displaystyle x\vee (y\vee z)}	= ( x ∨ y ) ∨ z {\displaystyle =(x\vee y)\vee z}
Associativity of ∧:	x ∧ ( y ∧ z ) {\displaystyle x\wedge (y\wedge z)}	= ( x ∧ y ) ∧ z {\displaystyle =(x\wedge y)\wedge z}
Commutativity of ∨:	x ∨ y {\displaystyle x\vee y}	= y ∨ x {\displaystyle =y\vee x}
Commutativity of ∧:	x ∧ y {\displaystyle x\wedge y}	= y ∧ x {\displaystyle =y\wedge x}
Distributivity of ∧ over ∨:	x ∧ ( y ∨ z ) {\displaystyle x\wedge (y\vee z)}	= ( x ∧ y ) ∨ ( x ∧ z ) {\displaystyle =(x\wedge y)\vee (x\wedge z)}
Identity for ∨:	x ∨ 0 {\displaystyle x\vee 0}	= x {\displaystyle =x}
Identity for ∧:	x ∧ 1 {\displaystyle x\wedge 1}	= x {\displaystyle =x}
Annihilator for ∧:	x ∧ 0 {\displaystyle x\wedge 0}	= 0 {\displaystyle =0}

Annihilator for ∨:	x ∨ 1 {\displaystyle x\vee 1}	= 1 {\displaystyle =1}
Idempotence of ∨:	x ∨ x {\displaystyle x\vee x}	= x {\displaystyle =x}
Idempotence of ∧:	x ∧ x {\displaystyle x\wedge x}	= x {\displaystyle =x}
Absorption 1:	x ∧ ( x ∨ y ) {\displaystyle x\wedge (x\vee y)}	= x {\displaystyle =x}
Absorption 2:	x ∨ ( x ∧ y ) {\displaystyle x\vee (x\wedge y)}	= x {\displaystyle =x}
Distributivity of ∨ over ∧:	x ∨ ( y ∧ z ) {\displaystyle x\vee (y\wedge z)}	= ( x ∨ y ) ∧ ( x ∨ z ) {\displaystyle =(x\vee y)\wedge (x\vee z)}

Diagrammatic representations

A Venn diagram is a helpful way to show Boolean operations. It uses overlapping circles to represent variables, with each circle standing for a variable that can be either true (1) or false (0). Shading parts of the circles shows the result of combining these variables.

In digital circuits, logic gates are used to perform Boolean operations. Shapes like triangles and circles represent different gates, such as AND, OR, and NOT gates. These gates take electrical signals (represented by voltages) as inputs and produce outputs based on Boolean rules.

Boolean algebras

Boolean algebra is a special type of algebra where the values are only true or false, shown as 1 or 0. Unlike regular algebra, which uses numbers, Boolean algebra uses these two values to work with logic and sets.

A concrete Boolean algebra is a collection of subsets of a set that follows certain rules. For example, if you have a set like {a, b, c}, the different combinations of these elements (like just {a}, or {a, b}) form a concrete Boolean algebra. These subsets can also be thought of as strings of bits, like 000, 001, up to 111, where each bit shows whether an element is in the subset.

Axiomatizing Boolean algebra

Boolean algebra uses special rules to work with values that are either true (1) or false (0). Instead of using all possible rules, we can use just a few key ones to describe how these values work together. These rules include ideas like combining and switching values in predictable ways.

By using even fewer rules, we can still describe all of Boolean algebra. One special rule using a unique operation can define the whole system. This shows how powerful and organized Boolean algebra can be.

Propositional logic

Main article: Propositional calculus

Propositional logic is closely related to Boolean algebra. Many ideas from Boolean algebra can be used in propositional logic with just a few changes in symbols and words. In propositional logic, the values are true or false, much like the 1s and 0s in Boolean algebra.

In propositional logic, we use letters like P and Q to stand for statements. For example, we might say "P is true if x equals 3." We can combine these statements using operations like "and" (∧), "or" (∨), and "if...then..." (→). This helps us understand how statements relate to each other and what must be true for other statements to be true.

Applications

Boolean algebra is very important because it helps us understand how computers and many types of logic work. It deals with values that are either true (1) or false (0). This simple idea is used in many areas, such as computer circuits, programming, and math.

Computers

In the early 1900s, engineers saw that Boolean algebra could explain how certain electrical circuits worked. Claude Shannon showed this connection in his 1937 thesis, A Symbolic Analysis of Relay and Switching Circuits.

Today, all modern computers use two-value Boolean logic. Their circuits work with high and low voltages to represent 1 and 0. Computers store data as sequences of these values, called bits, such as 01101000110101100101010101001011. Programmers can work with these bits using either regular number rules or Boolean logic rules. The big difference is that with regular numbers, adding can cause a "carry" to the next digit, but Boolean logic does not have this.

Two-valued logic

In places like courts or math, having just two answers — yes or no — can be very useful. For example, in a court, a defendant is either guilty or not guilty. In math, a statement is either true or false. This idea of two values is important in computer hardware, logic, and set theory.

Boolean operations

Boolean operations started in mathematical logic, where they combine true or false values of statements. In everyday language, words like "and," "or," and "not" act like these operations, though they can be tricky because of how we use them in real life.

In digital logic, Boolean operations combine bits in wires. For example, joining two sets of bits can be thought of as a single operation.

In video cards, Boolean operations help change images on screens. They let programmers combine areas of the screen in smart ways.

In design programs, Boolean operations let builders create complex shapes by combining simpler ones — for example, taking away one shape from another to show what remains.

Search engines also use Boolean logic. You can search for pages that include certain words, or exclude others, by using terms like AND, OR, and NOT. For example, searching for "Search term 1" OR "Search term 2" finds pages with either term.