At the heart of every computer is a system of logic, translating complex instructions into simple true or false signals. Propositional logic is the formal language we use to do this. It lets us take statements about the world and represent them with symbols, which can then be manipulated and ultimately turned into physical circuits.

We start with basic propositions, which are declarative sentences that can be either true or false. For example, "The switch is on" is a proposition. In logic, we represent these with variables like $p$, $q$, and $r$. This abstraction allows us to focus purely on the logical structure of an argument or a circuit, regardless of what the propositions actually mean.

Propositions are rarely useful on their own. We combine them using logical connectives, which act as the grammar of our logical language. Each connective has a direct counterpart in digital hardware: a logic gate.

Let's look at the fundamental connectives and their corresponding truth tables, which show the output for every possible combination of inputs.

Each of these logical operations is performed by a physical device called a logic gate. The rules defined in the truth tables are built directly into the electronics.

When designing circuits, complexity costs money, space, and speed. A simpler logical expression translates to a circuit with fewer gates. Logical equivalences are rules that allow us to rewrite a formula into a different, simpler form without changing its overall meaning or truth value. Two expressions are equivalent if they have identical truth tables.

These laws are incredibly useful in circuit design. For example, a NAND gate ($¬(p ∧ q)$) is functionally equivalent to an OR gate with inverted inputs. This gives engineers flexibility to build circuits using fewer types of gates, which can simplify manufacturing.

Other key equivalences include the distributive laws, which work just like in algebra:

Conditional statements are the foundation of decision-making in programs and circuits. They represent "if-then" scenarios.

The conditional statement $p → q$ is only false when a true premise ($p$) leads to a false conclusion ($q$). In all other cases, the promise of the statement is upheld.

The biconditional, $p ↔ q$, is true only when $p$ and $q$ have the same truth value. It's equivalent to $(p → q) ∧ (q → p)$, and it's the logic behind the XNOR (Exclusive NOR) gate.

Since hardware doesn't typically include a dedicated "implication gate," we build conditionals from simpler gates. The conditional $p → q$ is logically equivalent to $¬p ∨ q$. This simple equivalence is fundamental to implementing decision logic in hardware.

The final step is to translate a complete propositional formula into a gate-level diagram. This process turns an abstract mathematical statement into a blueprint for a physical circuit. Each variable becomes an input wire, and each logical connective becomes its corresponding gate.

Let's take the expression $(p ∧ ¬q) ∨ r$. We can build this circuit step-by-step:

1. Start with inputs for $p$, $q$, and $r$.
2. Use a NOT gate to get $¬q$.
3. Feed $p$ and $¬q$ into an AND gate.
4. Take the output of the AND gate and the input $r$ and feed them into an OR gate.

The final output of the OR gate represents the truth value of the entire expression.

This direct translation from logic to hardware is the foundation of digital design. By mastering propositional logic, you understand the fundamental principles that govern how every digital device thinks.

Ready to test your understanding? Let's try a few questions.

Understanding these formal structures allows us to move from abstract logic to concrete, functional hardware, which is the core challenge of computer engineering.