Logic

Logic refers to the reasoning used by electronic machines. The term is also used in reference to the circuits that make up digital devices and systems.

Boolean Algebra

Boolean algebra is a system of mathematical logic using the numbers 0 and 1 with the operations AND (multiplication), OR (addition), and NOT (negation). Combinations of these operations are NAND (NOT AND) and NOR (NOT OR). This peculiar form of mathematical logic, which gets its name from the nineteenth century British mathematician George Boole, is used in the design of digital logic circuits.

Symbology

X Y -X X*Y X+Y
0 0 1 0 0
0 1 1 0 1
1 0 0 0 1
1 1 0 1 1

In Boolean algebra, the AND operation, also called logical conjunction, is written using an asterisk (*), a multiplication symbol (×), or by running two characters together, for example, X*Y. The NOT operation, also called logical inversion, is denoted by placing a tilde (~) over the quantity, as a minus sign (−) or dash (-) followed by the quantity, as a “lazy inverted L” (¬) followed by the quantity, or as the quantity followed by an accent or “prime sign” (′). An example is −X. The OR operation, also called logical disjunction, is written using a plus sign (+), for example,
X + Y.
The foregoing are the symbols used by engineers. Above table shows the values of these functions, where 0 indicates “falsity” and 1 indicates “truth.” In mathematics and philosophy courses involving logic, you may see other symbols used for conjunction and disjunction. The AND operation in some texts is denoted by a detached arrow head pointing up () or by an ampersand (&), and the OR operation is denoted by a detached arrowhead pointing down ().

Theorems

Theorem (logic equation) What it’s called
X+0 = X OR identity
X*1 = X AND identity
X+1 = 1  
X*0 = 0  
X+X = X  
X*X = X  
−(−X) = X Double negation
X+(−X) = 1  
X*(−X) = 0 Contradiction
X+Y = Y+X Commutativity of OR
X*Y = Y*X Commutativity of AND
X+(X*Y) = X  
X*(−Y)+Y = X+Y  
X+Y+Z = (X+Y)+Z = X+(Y+Z) Associativity of OR
X*Y*Z = (X*Y)*Z = X*(Y*Z) Associativity of AND
X*(Y+Z) = (X*Y)+(X*Z) Distributivity
−(X+Y) = (−X)*(−Y) DeMorgan’s Theorem
−(X*Y) = (−X)+(−Y) DeMorgan’s Theorem

Above table shows several logic equations. Such facts are called theorems. Statements on either side of the equals sign in each case are logically equivalent. When two statements are logically equivalent, it means that one is true if and only if (iff ) the other is true. For example, the statement X = Y means that X implies Y, and also that Y implies X. Logical equivalence is sometimes symbolized by a double arrow with one or two shafts (↔or⇔). Boolean theorems are used to analyze and simplify complicated logic functions. This makes it possible to build a circuit to perform a specific digital function, using the smallest possible number of logic switches.