Boolean & Formal Logic Structures

← Back to Domain-Specific Families

Abstractions about the algebraic and syntactic structure of formal logic, including Boolean algebra and its operators (logic gate, XOR gate, disjunctive and negation normal forms), formal fragments and expressiveness results (monadic second-order logic, functional completeness, MAX-3SAT), and foundational logical principles (deductive closure, vicious circle principle, principle of distributivity).

29 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Action algebra — An algebraic-logic structure combining Kleene algebra's composition and iteration with residuated semilattice implication operations.
• Apartness relation — A constructive positive notion of distinction, typically irreflexive, symmetric and cotransitive, that is stronger than merely denying equality.
• Boolean algebra — An algebraic structure with conjunction, disjunction and complementation satisfying laws that model two-valued logic and set operations.
• Boolean network — A discrete dynamical system of Boolean variables whose values update according to assigned Boolean functions of other network nodes.
• Deductive closure — The smallest superset of a set of formulas that contains every formula derivable from it under a specified consequence relation or proof system.
• Definable set — A subset or relation in a mathematical structure consisting exactly of tuples satisfying a first-order formula, with or without named parameters.
• Disjunctive normal form — A Boolean formula represented as a disjunction of conjunctions of literals—an OR of AND terms.
• Fragment (logic) — A syntactically restricted sublanguage of a logic interpreted with the parent logic's semantics, often trading expressive power for decidability or lower computational complexity.
• Functional completeness — The property of a set of Boolean connectives from which every Boolean function can be expressed by composition.
• Fuzzy number — A normalized convex fuzzy subset of the real line, usually with upper-semicontinuous membership and compact support, representing graded compatibility with numerical values.
• Inclusion (Boolean algebra) — The canonical partial order on a Boolean algebra, where a≤b exactly when a∧¬b=0, equivalently a∧b=a or a∨b=b.
• Infinite expression — A mathematical expression with infinitely many operands or unbounded nesting whose meaning is defined only through a limit, fixed point, formal topology or other explicit semantic construction.
• Logic gate — A functional element that maps one or more logical input values to an output value according to a Boolean operation.
• Logical connective — A formal operator that forms a compound formula from one or more formulas and whose semantics determines the compound's truth or satisfaction from its arguments.
• Material Nonimplication — Material nonimplication is the classical binary truth function P ∧ ¬Q, true only when P is true and Q is false.
• MAX-3SAT — The optimization problem of assigning truth values to maximize the number or weight of satisfied clauses in a Boolean formula with at most three literals per clause.
• Modal algebra — A Boolean algebra equipped with a unary normal meet-preserving modal operator, providing algebraic semantics for normal propositional modal logics.
• Monadic predicate calculus — The function-free fragment of first-order logic whose predicate symbols all have arity one.
• Monadic second-order logic — The fragment of second-order logic that permits quantification over individual elements and unary predicates or sets, but not arbitrary higher-arity relations.
• Negation normal form — A logical formula form using only conjunction, disjunction and literals, with every negation applied directly to an atomic proposition.
• Positive set theory — A family of alternative set theories permitting comprehension for positive membership formulas while restricting negation so broad set formation avoids classical paradoxes.
• Principle of distributivity — The propositional-logic laws stating that conjunction distributes over disjunction and disjunction distributes over conjunction.
• Product term — A Boolean expression formed as the conjunction of one or more literals, with a minterm as the special case containing every variable exactly once.
• Syntax (logic) — The formal symbols, formation rules and derivation or transformation rules that determine which expressions and proofs are well formed independently of their interpretation.
• Truth-table reduction — Reduce membership in one decision problem to a finite, nonadaptive batch of oracle queries whose answer bits are combined by an input-computable Boolean truth table.
• Ugly duckling theorem — A formal result showing that, when every logically definable predicate is weighted equally, any two distinct objects share the same number of properties, so similarity requires inductive bias.
• Unate function — A Boolean function that is monotone in each variable after independently choosing whether that variable is interpreted positively or negatively.
• Vicious circle principle — A predicativist restriction forbidding definition of an entity by quantification over a totality that already contains the entity being defined.
• XOR gate — A digital logic gate that outputs true exactly when an odd number of its binary inputs are true, implementing exclusive disjunction and two-input inequality.