Boolean Algebra and Logical Laws

Boolean Algebra and Digital Logic

Introduction to Boolean Algebra

• Boolean algebra is a variant of propositional logic that serves as the framework for the design of digital circuits.
• This topic is directly relevant to computer architecture modules, particularly at the digital logic level.
• Digital circuits are composed of small, primitive digital devices called gates.
• Each gate computes a value based on a logical function.
• Digital values are represented by $0$ or $1$ (binary).
  • These correspond to a switch being off/on or a low/high voltage.
  • $1$ often corresponds to the presence of a pulse, and $0$ to the absence of a pulse.
• In diagrams, $A$ and $B$ typically represent input variables, and $O$ represents the output.

Primitive Logical Gates

1. NOT Gate

• Input(s): Single input $A$
• Output(s): Single output $O$
• Graphical Representation: An isosceles triangle on its side with a small circle at the end.
• Functionality:
  • If input $A$ is $0$, output $O$ is $1$.
  • If input $A$ is $1$, output $O$ is $0$.
• Correspondence: This gate corresponds directly to the negation operation ($\neg A$) in propositional logic.

2. AND Gate

• Input(s): Two inputs $A$ and $B$
• Output(s): Single output $O$
• Graphical Representation: Looks like a square with a semicircle attached to its side.
• Functionality:
  • Output $O$ is $1$ only when both inputs $A$ and $B$ are $1$.
  • Otherwise, the output is $0$.
    • $A=0, B=0 \Rightarrow O=0$
    • $A=0, B=1 \Rightarrow O=0$
    • $A=1, B=0 \Rightarrow O=0$
    • $A=1, B=1 \Rightarrow O=1$
• Correspondence: This gate corresponds directly to the conjunction operation ($A \land B$) in propositional logic.

3. OR Gate

• Input(s): Two inputs $A$ and $B$
• Output(s): Single output $O$
• Graphical Representation: Resembles a Star Trek insignia.
• Functionality:
  • Output $O$ is $1$ in every case except when both inputs $A$ and $B$ are $0$.
    • $A=0, B=0 \Rightarrow O=0$
    • $A=0, B=1 \Rightarrow O=1$
    • $A=1, B=0 \Rightarrow O=1$
    • $A=1, B=1 \Rightarrow O=1$
• Correspondence: This gate corresponds directly to the disjunction operation ($A \lor B$) in propositional logic.

Differences Between Gates and Propositional Logic

• Input/Output Distinction:
  • In digital gates, there's a clear distinction between inputs (knowns) and output (dependent unknown). For example, the NOT gate takes input $A$ and produces output $O$.
  • In propositional logic, formulas generally do not have an explicit notion of