# Propositional Logic

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/propositional-logic

## Propositional Logic Basics

A **proposition** is a statement that is definitely true or false, like "7 is prime" (true) or "$3 > 5$" (false). We build compound statements using **connectives**.

| Connective | Symbol | Meaning | True When | DirectX |
| --- | --- | --- | --- | --- |
| Negation | $\neg p$ | not $p$ | $p$ is false | -
| Conjunction | $p \land q$ | $p$ and $q$ | both true | -
| Disjunction | $p \lor q$ | $p$ or $q$ | at least one | -
| Biconditional | $p \leftrightarrow q$ | $p$ iff $q$ | $p$ and $q$ match | -

A **tautology** is true under **every** assignment ($p \lor \neg p$). A **contradiction** is false under every assignment. Two propositions are **logically equivalent** if they share the exact same truth table.

## Mastering Implication

The **implication** $p \to q$ ("if $p$ then $q$") is false in **only one case**: when $p$ is true and $q$ is false. 

When $p$ is false, the implication is **vacuously true** regardless of $q$. For example, "if the moon is cheese, $2+2=5$" is a true implication.

| Term | Definition / Rule | Pitfall |
| --- | --- | --- |
| **Implication** ($p \to q$) | False only if $p$ is true and $q$ is false | **Vacuously true** when $p$ is false |
| **Contrapositive** ($\neg q \to \neg p$) | Logically equivalent to $p \to q$ | Do not confuse with converse $q \to p$ |
| **Converse** ($q \to p$) | Not equivalent to $p \to q$ | Classic logical error to swap them |

## Practice questions

3 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. A compiler rewrites `if (!(a && b))` as `if (!a || !b)`. Which law licenses that, and why does the compiler bother?

A. Distributivity, which allows negations to be factored out
B. No law licenses it; the rewrite changes behaviour and is a compiler bug
C. The compiler is eliminating a redundant negation for readability
D. De Morgan's law, and the rewritten form can short-circuit on !a

**Answer:** D. De Morgan's law, and the rewritten form can short-circuit on !a

**Why:** The truth tables match, so the substitution is safe, and the second form reaches a decision on `!a` alone where the first must evaluate the whole conjunction before negating. Equivalence is what licenses it and short-circuiting is what makes it worth doing, which is the same pairing as in logic minimisation.

Page: https://tryals.app/practice/computer-science-i/propositional-logic/a-compiler-rewrites-if-a-b-as-if-a-b-which-law

### 2. Select every proposition that is logically equivalent to 'if p then q'.

A. if q then p
B. (NOT p) AND q
C. p AND q
D. (NOT p) OR q
E. if (NOT q) then (NOT p)

**Answer:** D. (NOT p) OR q; E. if (NOT q) then (NOT p)

**Why:** 'not p or q' and the contrapositive 'if not q then not p' both give T, T, F, T. The converse 'if q then p' gives T, F, T, T, which differs on two rows, and the two conjunctions are true on at most one row. Treating the converse as equivalent is the classic error the lesson names.

Page: https://tryals.app/practice/computer-science-i/propositional-logic/select-every-proposition-that-is-logically-equivalent-to-if-p-then

### 3. The convention that p → q is true whenever p is false exists so that a universal statement is not falsified by cases it never applies to.

**Answer:** True

**Why:** True. 'All swans in this empty lake are green' has to come out true, or a universally quantified claim would be refuted by irrelevant cases. The convention makes $\forall x (P(x) \to Q(x))$ behave: only an x with P true and Q false counts against it.

Page: https://tryals.app/practice/computer-science-i/propositional-logic/the-convention-that-p-q-is-true-whenever-p-is-false-exists-so-that