143-boolean-algebra Flashcards
role of binary
- computers; calculations & logic
- two states: true or false
- creation of circuits
- store data
Boolean Basics and Expressions
Boolean logic and logic gates used in computer circuitry
Boolean expressions used to describe electric circuits and selection statements in programming
Boolean expressions evaluated to either TRUE or FALSE
boolean operations
Conjunction - AND
Disjunction - OR
Negation - NOT
Exclusive disjunction- XOR
AND gate: takes two inputs and outputs 1 only if both inputs are 1. Symbol: ∧ or & or ^ or *.
OR gate: takes two inputs and outputs 1 if at least one input is 1. Symbol: ∨ or + or v or ||.
NOT gate: takes one input and outputs the opposite truth value. Symbol: ¬ or ~ or ! or —.
XOR gate: outputs 1 if exactly one input is 1, otherwise outputs 0. Symbol: ⊕ or V or = with 3 lines and a diagonal cross out.
Logic Gates and Transistors in CPUs
Computers use binary values of 0 and 1 to represent off (false) and on (true) respectively.
Logic gates take binary inputs and output a result based on a decision-making process.
Transistors inside a CPU store binary values of 0 or 1 and are used to perform logical operations using logic gates.
Truth tables
A table showing every possible permutation of inputs to a logic gage and the corresponding output
number of rows tip check: 2^inputsx
Simplifying boolean expressions
-to use as few expressions (gates/electric components) as possible to
-reduce the size of the circuit
-reduce cost of manufacturing circuit
-reduce power consumption of the circuit
-execute instructions as quickly as possible by reducing the need to fetch variables from memory
-reduce physical circuit costs
- rid of redundant parts of expression
-miimum number of physical logic gates
karmaugh maps
A Karnaugh map is used to simplify Boolean expressions by grouping together adjacent cells containing ones.
The rules for simplification are: no zeros allowed, no diagonals, only power of 2 number of cells in each group, groups should be as large as possible, every one must be in at least one group, overlapping allowed, wrap around allowed, and fewest number of groups possible.
To simplify a Boolean expression, first write the truth table as a Karnaugh map using Gray code. Then, highlight all of the 1s in the map with a rectangle, keeping in mind that only groups of 1s with edges equal to a power of 2 can be highlighted.
Using the highlighted portions of the Karnaugh map, the expression can be significantly reduced.
Karnaugh maps provide a method of simplifying boolean expressions, reducing the number of components required and saving money and power.
To determine the simplified expression from the boxes on the Karnaugh map, take each box and each variable in any order. If the digit for the variable in the heading stays the same, keep the variable. If the digit for the variable in the heading changes, discard the variable.
General rules of Boolean simplification: AND rules
Both terms have to be true (1) for the result to be true
x AND FALSE has to equal FALSE (annulment rule)
x AND TRUE has to equal the value of x (identity rule)
X AND X is the same as X (idempotent rule)
X AND not X is the same as 0 (complement rule)
General rules of Boolean simplification: OR rules
x OR FALSE has to equal the value of x (identity value)
x OR TRUE has to equal TRUE (annulment rule)
x OR x has to equal x (idempotent rule)
x OR not x has to equal TRUE (complement rule)
De Morgan’s laws
De Morgan’s laws involve breaking a negation and changing the operator between two inputs.
They are used when a negation applies to the whole of an operator between two inputs, and result in two negated inputs acted upon by a different operator.
Conjunction is replaced by disjunction and vice versa.
De Morgan’s law is a way of simplifying Boolean expressions by inverting all the variables, changing ANDs to ORs and vice versa, then inverting the whole expression.
Either logical function AND or OR may be replaced by the other, given certain changes to the expression - but the law can only be applied to one operator at a time.
It allows statements to be simplified so they only use NAND or NOR gates - results in simpler logic circuits which makes it easier to build microprocessors.
E.g., solid state drivers are made up of only NAND gates.
De Morgan’s first law: NOT (A AND B) is the same as (NOT A) OR (NOT B)
De Morgan’s second law: NOT (A OR B) is the same as (NOT A) AND (NOT B)
How can De Morgan’s laws be used to simplify the expression X = NOT (NOT A AND NOT B) OR B?
Step 1: Change OR to AND (or vice versa). NOT(NOT A AND NOT B) OR B
Step 2: NOT the terms on either side of the operator. X= NOT( NOT NOT A OR NOT NOT B) OR B
Step 3: NOT everything that has changed
Step 4: Get rid of any double negation. X=(A OR B) OR B
Step 5: Remove unnecessary brackets. X=A OR B OR B
Step 6: Apply the general rule, X OR X is the same as X. X= A or B
Distribution
Distribution applies to conjunction over disjunction as well as disjunction of conjunction.
It can be thought of as similar to expanding brackets.
Conjunction over disjunction: A n (BvC) == (AnB)v(A^C)
Disjunction of conjunction: Av(B^C) == (AvB)^(AvC)
Distribution can also be carried out over the same operator.
Example: A^(B^C) == (A^B)^(A^C)
Example: Av(BvC) == (AvB)v(AvC)
OR Distribution Rule
OR distribution rule allows us to multiply or factor out an expression.
A AND (B OR C) is the same as (A AND B) OR (A AND C).
AND Distribution Rule
AND distribution rule allows us to multiply or factor out an expression.
A OR (B AND C) is the same as (A OR B) AND (A OR C).
Association
Associative laws involve the addition or removal of brackets and reordering of inputs in a Boolean expression.
The associative law for conjunction (AND) is (A AND B) AND C is the same as A AND (B AND C) is the same as A AND B AND C.
The associative law for disjunction (OR) is (A OR B) OR C is the same as A OR (B OR C) is the same as A OR B OR C.
These laws allow us to regroup variables and remove brackets from an expression.
