On this page & study actions
Assessed progress
Sign in and complete the verified MCQs to track mastery.
Learning resources
Unit 1: Mathematical logic4 min read
Propositional logic serves as the foundational mathematical framework for computer science, bridging human reasoning with the binary operations executed by CPU transistors. This guide covers how simple statements are formalized, combined into complex expressions, simplified using algebraic equivalences, and directly executed as high-performance bitwise operations in hardware.
At the core of discrete mathematics is the proposition—a declarative sentence that is either strictly True ( / ) or False ( / ), but never both simultaneously.
To formulate logical models, we must separate statements with absolute truth values from subjective, imperative, or open-ended sentences.
Valid Propositions:
We represent propositions using propositional variables (). The set of possible assignments to a propositional variable is bounded by the Boolean domain:
We form compound propositions by combining individual variables using logical operators (or connectives).
The negation of a proposition is denoted by (or ). It asserts the opposite truth value.
+---+----+
| P | ¬P |
+---+----+
| T | F |
| F | T |
+---+----+The conjunction of and is written as . It is true only when both operands are true.
+---+---+-------+
| P | Q | P ∧ Q |
+---+---+-------+
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
+---+---+-------+The disjunction of and is written as (representing an inclusive OR). It evaluates to true if at least one of the operands is true.
+---+---+-------+
| P | Q | P ˅ Q |
+---+---+-------+
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
+---+---+-------+To model rules, guarantees, and systems behavior, mathematical logic relies heavily on directional relationships.
The statement "If , then " is denoted as .
The implication is false only when a true hypothesis leads to a false conclusion. If the hypothesis is false, the implication is vacuously true, regardless of 's value.
+---+---+-------+
| P | Q | P → Q |
+---+---+-------+
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
+---+---+-------+Given the implication , we define three related conditional statements:
Crucial Property: An implication and its contrapositive are logically equivalent (). The converse and inverse are also logically equivalent to each other ().
The statement " if and only if " is denoted by (or ). It asserts that both variables share the identical truth value.
+---+---+-------+
| P | Q | P ↔ Q |
+---+---+-------+
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
+---+---+-------+In software design, natural requirements must be systematically translated into propositions before implementation. Let's look at a classic condition:
"You cannot ride the roller coaster if you are under 4 feet tall, unless you are older than 16 years old."
We begin by establishing atomic variables:
Let's break the sentence down:
Alternatively, this can be written as:
As compound propositions grow, they are classified by their truth profiles across all rows of their truth tables.
[ Compound Propositions ]
|
+---------------+---------------+
| |
[ Tautology ] [ Contradiction ]
(Always T) (Always F)
e.g., P ∨ ¬P e.g., P ∧ ¬PIf a formula is a tautology, any substitution instance of is also a tautology. A substitution instance is constructed by consistently replacing a propositional variable in with a compound formula.
For example, consider the known tautology:
Let's substitute with the compound expression everywhere occurs:
Because is universally true, is guaranteed to be a tautology without needing a -row truth table.
Two compound propositions and are logically equivalent (written ) if is a tautology.
We can prove that by showing that they yield identical truth columns:
+---+---+---+--------+--------+
| P | Q | ¬P| ¬P ∨ Q | P → Q |
+---+---+---+--------+--------+
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
+---+---+---+--------+--------+Since the fourth and fifth columns match exactly, the equivalence is proven.
Using known equivalence rules, we can prove relationships step-by-step:
\neg(P \to Q) &\equiv \neg(\neg P \vee Q) && \text{by Conditional Identity} \\ &\equiv \neg(\neg P) \wedge \neg Q && \text{by De Morgan's Law} \\ &\equiv P \wedge \neg Q && \text{by Double Negation} \end{aligned}$$ ### The Duality Law Let $A$ be a logical formula containing only the operators $\wedge$, $\vee$, and $\neg$. The **dual** of $A$, denoted $A^*$, is obtained by: 1. Replacing every occurrence of $\wedge$ with $\vee$. 2. Replacing every occurrence of $\vee$ with $\wedge$. 3. Replacing every truth constant $T$ (or $1$) with $F$ (or $0$), and vice-versa. For example, given the expression: $$A: (P \vee Q) \wedge R$$ Its dual is: $$A^*: (P \wedge Q) \vee R$$ ### Functionally Complete Sets of Connectives A set of logical connectives is **functionally complete** if any arbitrary truth function can be expressed solely using those connectives. * The set $\{\neg, \wedge, \vee\}$ is functionally complete. * By De Morgan's Laws, we can reduce this further to $\{\neg, \wedge\}$ or $\{\neg, \vee\}$. * Even single-operator sets like $\{\text{NAND}\}$ or $\{\text{NOR}\}$ are functionally complete on their own. --- ## 6. Alternative Logic Gates: NAND and NOR In computer engineering, logic gates must be physically fabricated using transistors. **NAND** and **NOR** are highly efficient to build in silicon, serving as "universal" logical building blocks. ### Logical NAND (Sheffer Stroke) The **NAND** operation ($P \uparrow Q$ or $P \mid Q$) outputs false if and only if both inputs are true. $$P \uparrow Q \equiv \neg(P \wedge Q)$$ ```text +---+---+-------+ | P | Q | P ↑ Q | +---+---+-------+ | T | T | F | | T | F | T | | F | T | T | | F | F | T | +---+---+-------+ ``` ### Logical NOR (Peirce Arrow) The **NOR** operation ($P \downarrow Q$) outputs true if and only if both inputs are false. $$P \downarrow Q \equiv \neg(P \vee Q)$$ ```text +---+---+-------+ | P | Q | P ↓ Q | +---+---+-------+ | T | T | F | | T | F | F | | F | T | F | | F | F | T | +---+---+-------+ ``` --- ## 7. Bitwise Operations and Computers Computers represent information using physical states called **bits**. By convention, we map our logical domain directly: $$1 \equiv T \quad \text{and} \quad 0 \equiv F$$ ### Bitwise Operators When logical operators are applied to ordered strings of bits (registers), they operate **element-wise**: * **Bitwise AND ($\wedge$):** Standard logical AND per column. * **Bitwise OR ($\vee$):** Standard inclusive OR per column. * **Bitwise XOR ($\oplus$):** Exclusive OR. Evaluates to $1$ if the bits are different, and $0$ if they are identical ($P \oplus Q \equiv (P \wedge \neg Q) \vee (\neg P \wedge Q)$). Let's compute the bitwise values for two 10-bit strings: $$\begin{aligned} X &= 01\ 1011\ 0110 \\ Y &= 11\ 0001\ 1101 \end{aligned}$$ ```text X: 0 1 1 0 1 1 0 1 1 0 Y: 1 1 0 0 0 1 1 1 0 1 ---------------------------- AND: 0 1 0 0 0 1 0 1 0 0 OR: 1 1 1 0 1 1 1 1 1 1 XOR: 1 0 1 0 1 0 1 0 1 1 ``` ### Code Example: Practical Bitwise Manipulation in Python The following program demonstrates how computer processors use bitwise operations to represent Boolean states and apply mask structures efficiently. ```python # Bitwise Demonstration x = 0b0110110110 # Binary literal (Decimal 438) y = 0b1100011101 # Binary literal (Decimal 797) # Bitwise Operations bitwise_and = x & y bitwise_or = x | y bitwise_xor = x ^ y # Print output formatted to 10 binary places print(f"X: {x:010b}") print(f"Y: {y:010b}") print("-" * 15) print(f"AND: {bitwise_and:010b}") # Output: 0100010100 print(f"OR: {bitwise_or:010b}") # Output: 1110111111 print(f"XOR: {bitwise_xor:010b}") # Output: 1010101011 ``` --- ## 8. Operator Precedence and Polish Notation To parse compound propositions correctly without ambiguous interpretations, mathematical systems rely on operator priority. ### Precedence Hierarchy If parentheses are omitted, the order of evaluations flows from highest precedence (1) to lowest (5): ```text +------------+-------------+-------------+ | Precedence | Operator | Description | +------------+-------------+-------------+ | 1 | ¬ | Negation | | 2 | ∧ | Conjunction | | 3 | ν | Disjunction | | 4 | → | Implication | | 5 | ↔ | Equivalence | +------------+-------------+-------------+ ``` For instance, the expression $P \wedge Q \vee R$ is parsed as $(P \wedge Q) \vee R$ because $\wedge$ has higher precedence than $\vee$. Conversely, $P \vee Q \wedge R$ is interpreted as $P \vee (Q \wedge R)$. ### Parentheses Levels and Parsing Trees In a **fully parenthesized expression**, every operator is bounded by corresponding brackets indicating its depth. Consider: $$(P \vee ((Q \wedge R) \wedge \neg S))$$ We can map this hierarchical formula using an expression tree: ```text ∨ / \ P ∧ / \ ∧ ¬ / \ \ Q R S ``` ### Prefix, Infix, and Postfix Notations To eliminate parentheses entirely in parsing algorithms, computer systems utilize alternative notations: * **Infix Notation**: Operators are placed *between* operands (e.g., $P \vee Q$). This is the standard mathematical format but requires precedence rules and parentheses. * **Prefix Notation (Polish)**: The operator is placed *before* its operands (e.g., $\vee P Q$). * **Postfix Notation (Reverse Polish)**: The operator is placed *after* its operands (e.g., $P Q \vee$). This format is easily evaluated using a computational stack. Let's convert the expression $(P \vee Q) \wedge R$: ```text Infix: (P ∨ Q) ∧ R Prefix: ∧ ∨ P Q R Postfix: P Q ∨ R ∧ ``` --- ## Summary * A **proposition** is a declarative statement with a definitive binary truth value ($T$ or $F$). * **Implications** ($P \to Q$) represent conditions. The **contrapositive** ($\neg Q \to \neg P$) is logically equivalent to the original implication, while the converse and inverse are not. * **Compound propositions** are classified as **tautologies** (always True), **contradictions** (always False), or **contingencies** (conditionally True/False). * **The Duality Law** allows us to generate related logical formulas by swapping AND ($\wedge$) with OR ($\vee$), and True ($1$) with False ($0$) constants. * **Bitwise operations** apply Boolean logic to registers, enabling high-performance binary manipulations at the hardware level. * **Polish (Prefix/Postfix) notations** streamline execution by removing parsing ambiguity without needing parentheses.A declarative statement that is cleanly resolved to a single truth value of either True (T) or False (F), but not both.
Two compound propositions are logically equivalent if they share identical truth values under all possible truth value assignments of their variables.
A principle where swapping conjunctions with disjunctions and True/False constants with each other yields the algebraic dual of a given logical formula.
A set of logical operators (like NAND or NOR) capable of expressing any possible Boolean function on its own without needing other operators.
A parenthesized-free notation format for logic and arithmetic expressions where operators strictly precede (prefix) or follow (postfix) their operands.
Test your understanding with 5 questions
Which of the following represents the contrapositive of the conditional implication: 'If it is Sunday ($P$), then I will wash the car ($Q$)'?
Let $B$ be the logical tautology $P \to (Q \to P)$. If we construct a substitution instance $A$ by substituting the variable $P$ with $(R \to S)$ throughout the formula, which statement is correct?
What is the bitwise XOR ($\oplus$) of the two 10-bit strings $X = 0110110110$ and $Y = 1100011101$?
Using the Duality Law, what is the logical dual of the compound statement $(P \vee Q) \wedge (R \vee \text{F})$, where $\text{F}$ is the constant False?
Which of the following correctly pairs the prefix (Polish) and postfix (Reverse Polish) representations of the infix propositional expression $(P \vee Q) \wedge R$?
Non-Propositions (Invalid):
6 Modules
6 Modules