Unit 2 Summary

Math for CS · Axiom Academy

Key concepts from the entire unit in one place Six core operations on propositions: NOT ( ), AND ( ), OR ( ), XOR ( ), NAND , and NOR . AND requires both true; OR requires at least one; XOR requires exactly one. NAND and NOR are universal gates — any circuit can be built from just one of them. n variables produce 2^n rows. Add a column for each sub-expression, evaluate inside-out. The final column reveals whether the proposition is a tautology (all T), contradiction (all F), or contingency (mixed). De Morgan's Laws are paramount: (p q) p q and (p q) p q . Other essential laws: double negation, distributive, absorption, identity, domination, complement. Prove equivalences by truth table or algebraic derivation. A predicate P(x) is a Boolean function over a domain. The universal quantifier x\, P(x) claims all elements satisfy P. The existential quantifier x\, P(x) claims at least one does. Negation flips the quantifier: and . Order matters when mixing and . x\, y (each x gets its own y) is weaker than y\, x (one y works for all x). Same-type quantifiers can be freely reordered. Modus Ponens: p q, p q . Modus Tollens: p q, q p . Plus hypothetical syllogism, disjunctive syllogism, addition, simplification, and resolution. Watch out for the fallacies: affirming the consequent and denying the antecedent.

This is the written version of the interactive lesson above. See the full Math for CS course.