13 · Flashcards
Setup
Install the Spaced Repetition community plugin (Settings → Community plugins → Browse → “Spaced Repetition”). The tag above turns this note into a deck. Open it via the 🗂 icon or the command “Review flashcards”. Syntax used:
Question::Answer(one line) and?on its own line for multi-line answers.
Basics
What is a proposition?::A declarative sentence that is either TRUE or FALSE, but not both. Is “x + 1 = 2” a proposition?::No — its truth depends on the free variable x. Is “There is life on Mars” a proposition?::Yes — it has a truth value even though we don’t know it. Two other names for propositional logic?::Sentential logic and statement logic. Number of rows in a truth table with n variables?::2ⁿ Number of distinct Boolean functions of n variables?::2^(2ⁿ)
Connectives
When is p ∧ q true?::Only when both p and q are true. When is p ∨ q false?::Only when both p and q are false. When is p ⊕ q true?::When exactly one is true (values differ). When is p → q false?::Only when p = T and q = F. When is p ↔ q true?::When p and q have the same truth value. What does “but” translate to?::∧ (conjunction). If p is false, what is p → q?::TRUE, regardless of q (vacuous truth). p ↔ q in terms of implications?::(p → q) ∧ (q → p) p ↔ q in terms of ⊕?::¬(p ⊕ q) — XNOR.
Implication variants
“p only if q” in symbols?::p → q “p if q” in symbols?::q → p “q is necessary for p” in symbols?::p → q “p is sufficient for q” in symbols?::p → q “A unless B” in symbols?::A ∨ B (≡ ¬B → A) In p → q, which is sufficient and which necessary?::p is sufficient, q is necessary (“Sufficient Starts, Necessary Next”). Converse of p → q?::q → p Inverse of p → q?::¬p → ¬q Contrapositive of p → q?::¬q → ¬p Which form is equivalent to p → q?::Only the contrapositive (¬q → ¬p). Converse is equivalent to…?::The inverse.
Precedence
Order of precedence, highest to lowest?::¬, ∧, ∨, →, ↔ (“Not All Ostriches Imitate Birds”) Is → associative?::No. (p→q)→r ≢ p→(q→r); counter-example p = F, r = F. Is ↔ associative?::Yes.
Tautology & satisfiability
Tautology?::A formula that is always TRUE. Contradiction?::A formula that is always FALSE. Contingency?::A formula that is sometimes TRUE and sometimes FALSE. Satisfiable?::At least one assignment makes it TRUE. Valid means…?::Tautology. Is a contingency valid?::No — it is satisfiable but invalid. F is a tautology iff ¬F is…?::Unsatisfiable (a contradiction). Fastest way to check if A → B is a tautology? ? Assume it is FALSE (A = T, B = F) and propagate. Contradiction ⇒ tautology; a consistent assignment ⇒ not a tautology. What does P ⇒ Q (logical implication) mean?::P → Q is a tautology.
Equivalences
p → q as a disjunction?::¬p ∨ q ¬(p → q) ≡ ?::p ∧ ¬q De Morgan’s laws?::¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q Absorption laws?::p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p (p → r) ∧ (q → r) ≡ ?::(p ∨ q) → r (p → r) ∨ (q → r) ≡ ?::(p ∧ q) → r (p → q) ∧ (p → r) ≡ ?::p → (q ∧ r) ¬(p ↔ q) ≡ ?::p ↔ ¬q ≡ ¬p ↔ q ≡ p ⊕ q p ↔ q in sum-of-products form?::(p ∧ q) ∨ (¬p ∧ ¬q) Boolean shortcut p + p’q = ?::p + q
Inference
Valid argument?::Impossible for all premises to be TRUE and the conclusion FALSE. Modus Ponens?::p → q, p ∴ q Modus Tollens?::p → q, ¬q ∴ ¬p Hypothetical Syllogism?::p → q, q → r ∴ p → r Disjunctive Syllogism?::p ∨ q, ¬p ∴ q Resolution?::p ∨ q, ¬p ∨ r ∴ q ∨ r Addition?::p ∴ p ∨ q Simplification?::p ∧ q ∴ p Affirming the consequent (fallacy)?::p → q, q ∴ p — INVALID Denying the antecedent (fallacy)?::p → q, ¬p ∴ ¬q — INVALID Why can’t propositional logic prove “Everyone enrolled lived in a dorm; Mia never did ∴ Mia isn’t enrolled”?::It has no quantifiers (“everyone”) — needs First Order Logic.
Extras
Is {∧, ∨} functionally complete?::No — it can’t express ¬ (monotone). Is {¬, →} functionally complete?::Yes — p ∨ q ≡ ¬p → q. Single-connective complete sets?::{NAND} and {NOR}. ¬p using NAND?::p ↑ p Dual of a formula?::Swap ∧ ↔ ∨ and T ↔ F (after removing →, ↔). PDNF is built from…?::Minterms — one per TRUE row. PCNF is built from…?::Maxterms — one per FALSE row. Complexity of SAT? Of 2-SAT?::SAT is NP-complete; 2-SAT is in P.
Prev ← 12 Practice Problems · Next → 14 Memory Tricks and Traps