Propositional logic¶
A formal logic that treats whole propositions as truth-valued atoms and builds compound formulas with connectives, deriving validity, equivalence, satisfiability, and consequence from their truth-functional structure.
Core Idea¶
Propositional logic is a formal calculus that treats whole propositions as truth-valued atoms, combines them with connectives, and evaluates validity, equivalence, satisfiability, and consequence from formula structure and declared semantics. In classical semantics every atom receives true or false, and connective truth tables determine each compound formula. In classical semantics every atom receives true or false, and connective truth tables determine each compound formula.
Scope of Application¶
Propositional logic is used in mathematics, philosophy, digital circuits, SAT solving, verification, AI knowledge bases, proof assistants, logic education, planning, and constraint systems. Use it with atomic-proposition interpretations, formation grammar and connective basis, precedence, classical or nonclassical truth semantics, valuations/models, premises and conclusion, proof calculus/rules, soundness and completeness assumptions, truth-table/normal-form/SAT representation, solver and certificate, translation back to the application, complexity bounds, and a clear boundary from predicate, modal, temporal, probabilistic, circuit-timing, and stateful programming semantics.
- Validity. Tests arguments.
- Satisfiability. Finds valuations.
- Equivalence. Compares formulas.
- Normal forms. Transforms reasoning problems.
- Verification. Encodes finite properties.
Clarity¶
Report vocabulary and atom interpretations, grammar/connective basis, precedence, classical or nonclassical semantics, valuations/models, premises/conclusion, proof calculus and rule set, soundness/completeness assumptions, normal-form transformation, SAT encoding, solver version/options and certificate, complexity claims, and boundary from quantifier/modal/temporal structure. The closest near miss sets the boundary: Boolean algebra is the closest algebraic counterpart; it studies the same two-valued operations abstractly but is not automatically a proof calculus for propositions. A positive case must satisfy this test: A formalism is propositional logic when formulas are built from whole-proposition atoms with declared connectives and evaluated/proved through a sentential consequence relation.
Manages Complexity¶
A small connective basis expresses every Boolean function, but truth tables grow exponentially and formalization can hide internal domain structure. Proof systems compress search differently. The central atomic abstraction–lost internal structure tradeoff is this: Whole statements simplify inference while hiding objects and quantifiers. A second semantic enumeration–proof compression tension matters because Truth tables are transparent while exponential; proofs/SAT scale but need checking. The natural-language fidelity–formal precision tension adds that Formalization removes ambiguity while may alter the claim.
Abstract Reasoning¶
Use three linked moves: atomize only complete propositions appropriate to the question; build formulas with unambiguous scope; choose semantics and consequence relation. As a collapse test, the case exits when quantification or object-level relational structure is essential and cannot be treated as atomic. A fourth check is to prove or refute with a sound method or witness valuation. A final check is to audit translation and escalate to richer logic when internal structure matters.
Knowledge Transfer¶
Truth-functional structure transfers to circuits and constraints, but signal timing, program side effects, uncertainty, and quantification require extra semantics. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. Prospective skeleton. Proof rules derive consequences in the calculus.
Relationships to Other Abstractions¶
Current abstraction Propositional logic Domain-specific
Parents (1) — more general patterns this builds on
-
Propositional logic is a kind of Formal System Prime
Propositional logic is a formal symbolic system with formation, valuation, and consequence rules; it is not a kind of Omega-logic.
Hierarchy paths (2) — routes to 2 parentless roots
- Propositional logic → Formal System → Formalization → Representation → Abstraction
- Propositional logic → Formal System → Formalization → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Propositional logic sits in a crowded region of the domain-specific corpus (19th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Logical Inference, Modality & Conditional Structures (27 abstractions)
Nearest neighbors
- Material conditional — 0.92
- Propositional formula — 0.92
- Valuation (logic) — 0.92
- Tautology (Logic) — 0.90
- Second-Order Predicate — 0.90
Computed from structural-signature embeddings · 2026-10-08