Propositional formula¶
Type of logical formula in propositional logic.
Core Idea¶
A propositional formula is a well-formed syntactic expression built recursively from propositional variables or truth constants using logical connectives such as negation, conjunction, disjunction, implication, and equivalence. Formation rules determine which symbol strings count as formulas and how they are parsed. Once an interpretation assigns each variable a truth value and each connective its stipulated truth function, the formula receives a unique truth value. Its syntax can be represented as a parse tree whose leaves are variables and whose internal nodes are connectives.
Scope of Application¶
-
Formal semantics. Assignments determine the truth value of the whole through compositional evaluation.
-
Proof systems. Formulas serve as premises and conclusions under explicit derivation rules.
-
Satisfiability and validity. Truth under some, all, or no assignments classifies expressions semantically.
-
Logical equivalence. Distinct parse trees are compared across the full assignment space.
-
Normal forms. Conjunctive and disjunctive transformations support reasoning and computation with size tradeoffs.
Clarity¶
Propositional formula is a recursively well-formed syntactic expression whose parse tree is built from variables, constants, and connectives. It is distinct from a proposition's truth value, from one interpretation, and from a natural-language sentence. Naming syntax first makes semantic properties precise: satisfiable means true under at least one assignment, valid under every assignment, and equivalent means matching truth under all assignments.
Manages Complexity¶
Propositional formulas compress truth-functional reasoning into a finite parse tree of variables and connectives. The logician tracks assignments, subformula values, normal forms, and proof transformations rather than evaluating natural-language variants independently. Satisfiable, valid, unsatisfiable, contingent, equivalent, and entailment branches follow from the set of satisfying assignments. Truth tables, SAT solvers, Boolean algebra, and deductive systems then operate on the same syntax.
Abstract Reasoning¶
Formation move. Build a formula recursively from propositional variables, truth constants, and truth-functional connectives according to a fixed grammar. Valuation move. Assign truth values to atoms and propagate them through the syntax tree to evaluate the whole. Equivalence move. Compare formulas by truth table, normal form, or proof rather than surface wording. Inference move. Test satisfiability, validity, and entailment by asking which valuations or derivations support them. Transformation move. Rewrite into conjunctive or disjunctive normal form while preserving semantics. Boundary move.
Knowledge Transfer¶
Within the home domain. Propositional formulas transfer across logic, digital circuits, verification, databases, AI, and proof systems as recursively formed expressions from atoms and truth-functional connectives. Syntax tree, valuation, satisfiability, validity, entailment, and normal form retain exact roles. Beyond the home domain (C — formal representation). They apply literally wherever claims are abstracted to Boolean atoms and connectives. Their boundary is expressive: internal structure of atoms, quantification, time, modality, uncertainty, and context are omitted unless added by another logic. A grammatical sentence or proposition is not automatically a well-formed propositional formula, and a formula need not be true.
Relationships to Other Abstractions¶
Current abstraction Propositional formula Domain-specific
Parents (1) — more general patterns this builds on
-
Propositional formula is a kind of Symbolic Representation Prime
Propositional formula is a domain-specific kind of Symbolic Representation: Type of logical formula in propositional logic.
Hierarchy path (1) — routes to 1 parentless root
- Propositional formula → Symbolic Representation → Representation → Abstraction
Neighborhood in Abstraction Space¶
Propositional formula sits in a crowded region of the domain-specific corpus (29th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Logical Semantics & Many-Valued Systems (11 abstractions)
Nearest neighbors
- Propositional logic — 0.92
- Well-Formed Formula — 0.90
- Tautology (Logic) — 0.90
- Formal Theory — 0.89
- Lindström quantifier — 0.88
Computed from structural-signature embeddings · 2026-10-08