Lecture 5 - Boolean Logic & Circuits

Flashcards covering key vocabulary terms and definitions from the lecture notes on Boolean Algebra, Boolean functions, laws, and basic gates.

Boolean Algebra

A set of rules and operations for working with variables whose values are either 0 or 1.

Boolean Multiplication

An operation denoted by '•', similar to a logical AND, where the result is 1 only if all inputs are 1.

Boolean Addition

An operation denoted by '+', similar to a logical OR, where the result is 1 if at least one input is 1.

Complement of an Element

An operation denoted by a bar symbol or a prime symbol ('), similar to a logical NOT, which inverts the value (0 becomes 1, 1 becomes 0).

Boolean Function

A function that maps one or more Boolean input variables to the set of {0, 1}, meaning its output can be either 0 or 1.

Input/Output Table

A table that shows the output value of a Boolean function for every possible combination of input values, similar to a truth table.

Literal (Boolean Algebra)

A variable that appears in a Boolean expression in either its true form (e.g., x) or its complemented form (e.g., x').

Minterm

A product term within a Boolean expression that includes exactly one literal for every input variable.

Idempotent Laws

Laws stating that x + x = x and x • x = x.

Associative Laws

Laws stating that (x + y) + z = x + (y + z) and (xy)z = x(yz).

Commutative Laws

Laws stating that x + y = y + x and xy = yx.

Distributive Laws

Laws stating that x + yz = (x + y)(x + z) and x(y + z) = xy + xz.

Identity Laws

Laws stating that x + 0 = x and x • 1 = x.

Domination Laws

Laws stating that x • 0 = 0 and x + 1 = 1.

Double Complement Law

A law stating that the double complement of a variable returns the original variable (e.g., (x')' = x).

Complement Laws

Laws stating that x • x' = 0 and x + x' = 1.

De Morgan’s Laws

Laws providing equivalences for the complement of sums and products (e.g., (x + y)' = x'y' and (xy)' = x' + y').

Absorption Laws

Laws stating that x + (xy) = x and x(x + y) = x.

Gate (Digital Circuits)

An electrical device that implements a Boolean function, forming the basic building blocks of circuits.

AND Gate

A gate that performs Boolean multiplication, with an output of 1 only if all inputs are 1.

OR Gate

A gate that performs Boolean addition, with an output of 1 if at least one input is 1.

Inverter (NOT Gate)

A gate that performs the Boolean complement operation, changing a 0 to 1 and a 1 to 0.

Combinational Circuits

Circuits constructed using a combination of inverters, OR gates, and AND gates (or other basic gates) to implement a specific Boolean function.