Semiconductor & Computer Engineering
m |
|||
| Line 6: | Line 6: | ||
== Variables == | == Variables == | ||
{{main|/variables|boolean data type|l1=Boolean Variables}} | {{main|/variables|boolean data type|l1=Boolean Variables}} | ||
| − | Boolean algebra uses variables just like normal algebra. Those variables can only have one of two values - either a 0 or a 1. Variable are commonly represented as a single alphabet letter. While there is no one acceptable convention, a it's not uncommon to see letters such as <math>A, B, \text{ and } C</math> used for inputs and <math>P, Q, R, \text{ and } Z</math> for output. That's also the convention used on WikiChip. Sometimes it's desired to represent the [[negated]] (opposite) value of a variable, that's often done with a bar or a tick (prime) above or next to the letter, for example <math>\bar A</math> or <math>\neg B</math> although [[negation|other values are possible]]. | + | Boolean algebra uses variables just like normal algebra. Those variables can only have one of two values - either a 0 or a 1. Variable are commonly represented as a single alphabet letter. While there is no one acceptable convention, a it's not uncommon to see letters such as <math>A, B, \text{ and } C</math> used for inputs and <math>P, Q, R, \text{ and } Z</math> for output. That's also the convention used on WikiChip. Sometimes it's desired to represent the [[negated]] (opposite) value of a variable, that's often done with a bar or a tick (prime) above or next to the letter, for example <math>\bar A</math> or <math>\neg B</math> although [[negation|other notations exist]]. <math>\bar A</math> is read "not A", regardless of notation. |
| + | |||
| + | == Operations & Truth tables == | ||
| + | {{main|/operations|truth table|l1=Boolean Operations}} | ||
| + | Boolean algebra has a set of operations that can be performed on Boolean values. The three common Boolean operators are '''[[conjunction|AND]]''', '''[[disjunction|OR]]''', and '''[[negation|NOT]]'''. Understanding those operators can better be done by examining their behavior via tool called a truth table. '''[[truth tables]]''' is a table that lists all possible input values and their respective output values. Truth tables are an excellent way of seeing the relationships between input values and given Boolean expressions. | ||
| + | |||
| + | === AND operator === | ||
| + | {{main|logical conjunction}} | ||
| + | <div style="float: right;">{{truth table/and}}</div> | ||
| + | The Boolean operator [[conjunction|AND]] is usually represented by either <math>\land</math>, <math>\cdot</math>, or no symbol at all: for example "<math>A \land B</math>", "<math>A \cdot B</math>", and "<math>AB</math>" are all equivalent and are read "A AND B". The behavior of this operator is shown in the [[truth table]] on the right. The result of "A AND B" is true if both A and B are true; otherwise the result is false. This expression is also called a '''Boolean product'''. | ||
| + | |||
| + | For example, suppose we have the function <math>f(a,b,c) = (a \land b) \land c</math> | ||
| + | ::<math> | ||
| + | \begin{align} | ||
| + | Q &= f(1,0,1) \\ | ||
| + | &= (1 \land 0) \land 1 \\ | ||
| + | &= 0 \land 1 \\ | ||
| + | &= 0_2 \\ | ||
| + | \end{align} | ||
| + | </math> | ||
| + | |||
| + | Or | ||
| + | ::<math> | ||
| + | \begin{align} | ||
| + | Q &= f(1,1,1) \\ | ||
| + | &= (1 \land 1) \land 1 \\ | ||
| + | &= 1 \land 1 \\ | ||
| + | &= 1_2 \\ | ||
| + | \end{align} | ||
| + | </math> | ||
| + | {{clear}} | ||
| + | === OR operator === | ||
| + | {{main|logical disjunction}} | ||
| + | <div style="float: right;">{{truth table/or}}</div> | ||
| + | The Boolean operator [[disjunction|OR]] is usually represented by <math>\lor</math> or <math>+</math> operators. For example "<math>A \lor B</math>" and "<math>A+B</math>". The expression <math>A+B</math> is read "A or B". The result of "A OR B" is true if either A is true or B is true; otherwise the result is false. This expression is also called a '''Boolean sum'''. | ||
| + | |||
| + | For example, suppose we have the function <math>f(a,b,c) = (a \lor b) \lor c</math> | ||
| + | ::<math> | ||
| + | \begin{align} | ||
| + | Q &= f(1,0,1) \\ | ||
| + | &= (1 \lor 0) \lor 1 \\ | ||
| + | &= 1 \lor 1 \\ | ||
| + | &= 1_2 \\ | ||
| + | \end{align} | ||
| + | </math> | ||
| + | Or | ||
| + | ::<math> | ||
| + | \begin{align} | ||
| + | Q &= f(0,0,1) \\ | ||
| + | &= (0 \lor 0) \lor 1 \\ | ||
| + | &= 0 \lor 1 \\ | ||
| + | &= 1_2 \\ | ||
| + | \end{align} | ||
| + | </math> | ||
Revision as of 23:02, 28 November 2015
Boolean algebra (or less commonly symbolic logic) is a branch algebra that deals with only two logic values - 0 (corresponding to false) and 1 (corresponding to true).
Today, Boolean algebra is the primary mathematical tool used in designing modern digital systems. Switching functions are described using Boolean algebra since they deal with two discrete states - ON and OFF (or 1 and 0). Those functions are in turn implemented via transistors which act as switches, a natural implementation for representing Boolean algebra operations. Once primitive Boolean operation circuits such as NOT, AND, and OR gates are implemented, any conceivable system of logic can be implemented using them like Lego pieces.
Variables
- Main articles: Boolean Variables and boolean data type
Boolean algebra uses variables just like normal algebra. Those variables can only have one of two values - either a 0 or a 1. Variable are commonly represented as a single alphabet letter. While there is no one acceptable convention, a it's not uncommon to see letters such as used for inputs and for output. That's also the convention used on WikiChip. Sometimes it's desired to represent the negated (opposite) value of a variable, that's often done with a bar or a tick (prime) above or next to the letter, for example or although other notations exist. is read "not A", regardless of notation.
Operations & Truth tables
- Main articles: Boolean Operations and truth table
Boolean algebra has a set of operations that can be performed on Boolean values. The three common Boolean operators are AND, OR, and NOT. Understanding those operators can better be done by examining their behavior via tool called a truth table. truth tables is a table that lists all possible input values and their respective output values. Truth tables are an excellent way of seeing the relationships between input values and given Boolean expressions.
AND operator
- Main article: logical conjunction
| Inputs | Outputs | |
|---|---|---|
| A | B | Q |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The Boolean operator AND is usually represented by either , , or no symbol at all: for example "", "", and "" are all equivalent and are read "A AND B". The behavior of this operator is shown in the truth table on the right. The result of "A AND B" is true if both A and B are true; otherwise the result is false. This expression is also called a Boolean product.
For example, suppose we have the function
Or
OR operator
- Main article: logical disjunction
| Inputs | Outputs | |
|---|---|---|
| A | B | Q |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The Boolean operator OR is usually represented by or operators. For example "" and "". The expression is read "A or B". The result of "A OR B" is true if either A is true or B is true; otherwise the result is false. This expression is also called a Boolean sum.
For example, suppose we have the function
Or