Conditioned Disjunction¶

A ternary Boolean connective whose middle argument selects the first branch when true and the third branch when false: [p,q,r] = (q ∧ p) ∨ (¬q ∧ r).

Version: v3 · 2026-09-07 · History
Domain-specific #: 1531
Origin domain: mathematics
Subdomain: propositional logic
Aliases: Conditional disjunction

Core Idea¶

Conditioned disjunction is a ternary truth-functional connective introduced by Alonzo Church^[1]. In Church's argument order, [p,q,r] takes q as the condition, p as the true branch, and r as the false branch:

[p,q,r] \equiv (q\to p)\land(\neg q\to r) \equiv (q\land p)\lor(\neg q\land r).

When q is true, the connective has the value of p; when q is false, it has the value of r. It is therefore the Boolean “if q, then p, else r” operation. The name emphasizes a disjunction whose alternatives are gated by complementary conditions rather than an ordinary inclusive disjunction between peers.

The operation has three exact interpretations. In propositional logic it is a primitive ternary connective with a fixed eight-row truth table. In digital switching theory it is a one-bit two-to-one multiplexer: q selects which data input reaches the output. In programming notation it shares a Boolean result table with a conditional expression such as q ? p : r, after correcting for Church's unusual written order [p,q,r]. The logical connective alone does not inherit a programming language's evaluation order, side effects, typing, or short-circuit guarantees.

With truth constants, conditioned disjunction is functionally complete for classical propositional logic^[2]. Negation, conjunction, and disjunction can be defined from it, making the connective not merely an abbreviation but a viable primitive basis and a compact expression of Boolean case analysis.

Structural Signature¶

The mandatory roles are:

a selector proposition q with a classical truth value;
a true-branch proposition p;
a false-branch proposition r;
two complementary gates, q and \neg q;
conjunction of each branch with the gate that admits it;
disjunction of the gated branches into one output;
the invariant that exactly one branch value determines the result under a classical valuation;
a fixed argument convention, because Church's [p,q,r] places the selector in the middle;
extensional truth-function semantics independent of how formulas are evaluated operationally; and
optional truth constants 0 and 1 when the connective is used as a functionally complete primitive.

The signature is:

two Boolean alternatives + one Boolean selector + complementary gating + one merged output → selector-indexed branch value.

For each valuation v:

v([p,q,r]) = v(p) if v(q)=1, and v([p,q,r]) = v(r) if v(q)=0.

This pointwise equation is the recognition test. A notation that selects branches in another order is equivalent only after explicit argument permutation.

What It Is Not¶

Conditioned disjunction is not ordinary binary disjunction. p\lor r can be true because either alternative is true; [p,q,r] ignores the unselected branch's truth value. For example, with q true, p false, and r true, ordinary p\lor r is true but conditioned disjunction is false.

It is not material implication, although Church's definition uses two implications. The conjunction (q\to p)\land(\neg q\to r) coordinates both conditional cases into a ternary selection function.

It is not contraposition. Contraposition transforms an implication into an equivalent implication with negated and reversed terms; it neither introduces two alternatives nor selects between them.

It is not automatically a programming-language control-flow construct. A pure truth function treats p, q, and r as truth values under a valuation. A conditional expression may evaluate the condition first and only one branch, may carry non-Boolean types, may raise exceptions, and may perform side effects. Truth-table equivalence does not establish operational equivalence.

It is not every ternary connective and not a “majority” operator. A majority function returns the value held by at least two inputs; conditioned disjunction assigns distinct selector and branch roles.

It is not a free-standing functionally complete basis without constants under the stated construction. Constants permit definitions of negation and the usual binary connectives; any completeness claim must state the available primitives.

Scope of Application¶

In propositional logic, conditioned disjunction supplies a compact primitive for case splits and permits alternate axiom systems for classical propositional calculus^[1]. Church's treatment shows how familiar connectives can be defined through the ternary operator and constants, allowing metatheoretic questions about sufficiency, independence, and proof systems.

In Boolean algebra, the connective is an if–then–else operator. It supports decomposition of Boolean functions by a chosen variable: split the function into the case where q=1 and the case where q=0, then reassemble the cofactors with conditioned disjunction. This is closely related to Shannon expansion and underlies decision diagrams and logic synthesis^[3].

In digital logic, a two-input one-bit multiplexer realizes the truth function directly. The select line is q; the data inputs are p and r. Cascading such selectors constructs wider multiplexers and arbitrary Boolean functions, subject to constants and available complemented controls.

In automated reasoning and formal methods, if–then–else terms can preserve shared branch structure more compactly than immediate expansion into conjunctions and disjunctions. Solvers may treat the operator natively or lower it into core Boolean connectives.

In programming-language semantics, the truth function is a useful extensional comparison point, but typing, laziness, strictness, exceptions, undefined values, and effects require additional semantics. The node should not silently claim that all language conditional operators are identical.

Clarity¶

A conditioned-disjunction statement should answer:

What notation and argument order are used?
Which argument is the selector?
Which branch is chosen when the selector is true?
Is the logic classical and two-valued?
Are p and r propositions, Boolean values, or terms of a wider type?
Is the claim extensional—about the returned truth value—or operational—about evaluation?
Are truth constants available for a functional-completeness result?
Is the expression being expanded into (q\land p)\lor(\neg q\land r)?
Is a circuit implementation being modeled as an ideal multiplexer?
Are nonclassical truth values, hazards, side effects, or undefined branches in scope?

Argument order is the commonest source of error. Church's [p,q,r] corresponds to conventional q ? p : r, not p ? q : r^[1]. Writing named roles alongside the first use prevents silent permutation.

Manages Complexity¶

The connective compresses a two-case proof or definition into one compositional object. Instead of repeating “if q then use p; otherwise use r,” an analyst carries one term with explicit selector and branches. Nested terms build decision trees while retaining the conditional structure.

In Boolean-function manipulation, conditioned disjunction separates the choice of decomposition variable from the two cofactors. A complex function f can be written as [f_{q=1},q,f_{q=0}]. Repeating this decomposition yields a binary decision diagram; recognizing identical cofactors permits sharing and reduction^[4].

In circuit reasoning, the operator maps directly to a selector component, so Boolean algebra, gate-level networks, and truth tables share one interface. The DNF expansion exposes AND/OR/NOT implementation; the multiplexer view exposes routing; the primitive-connective view exposes logical sufficiency.

The abstraction also prevents operational details from contaminating extensional proofs. A logician can prove a truth identity without deciding whether a programming runtime evaluates one branch or both. Conversely, a language designer can identify exactly which additional properties lie beyond the Boolean function.

Abstract Reasoning¶

The equivalence follows by cases. If q=1, then q\to p has value p and \neg q\to r is true, so their conjunction is p. If q=0, the first implication is true and the second has value r, so the conjunction is r. Rewriting implications gives (q\land p)\lor(\neg q\land r).

Functional completeness with constants can be demonstrated constructively:

\neg q = [0,q,1];
p\land q = [p,q,0];
p\lor q = [1,q,p].

Because negation together with conjunction or disjunction forms a complete Boolean basis, conditioned disjunction plus 0 and 1 can define every Boolean truth function. The claim is about expressibility, not necessarily formula size or proof convenience.

The connective also supplies Boolean cofactor decomposition. For any Boolean function f(q,\mathbf{x}),

f = [f(1,\mathbf{x}), q, f(0,\mathbf{x})].

This makes the selector variable explicit and predicts that branches identical under reduction can be collapsed. It also gives falsifiers: a proposed implementation that sometimes combines both branch values, selects the wrong argument order, or changes the result based on an unselected proposition is not the classical conditioned-disjunction function.

Knowledge Transfer¶

The mechanism transfers exactly among classical propositional logic, Boolean algebra, ideal switching circuits, SAT/SMT representations, binary decision diagrams, and pure Boolean conditional expressions. The roles map without metaphor: selector, true branch, false branch, and one output.

The transfer to general programming is partial. A language-level conditional may return arbitrary typed values and choose only one branch for evaluation. That operational laziness can prevent an exception or side effect in the unselected branch, whereas the truth function merely specifies the result under a valuation. The logic supplies the extensional skeleton; the language specification supplies evaluation semantics.

The transfer to multiplexing hardware is exact at one bit, but the Encyclopedia's Multiplexing prime concerns sharing channels among streams and later separation. A selector gate is a neighboring engineering realization rather than the minimal parent chosen here.

Outside formal and computational systems, “choose one consequence according to a condition” resembles conditional selection. The substrate-neutral residue is carried by Selection and conditional rules. The named truth function remains tied to propositions, valuations, Boolean constants, and equivalence transformations.

Examples¶

Direct valuation. Let p=0, q=1, and r=1. Then [p,q,r]=0 because the true selector chooses p. This differs from p\lor r=1.

False-selector case. Let p=1, q=0, and r=0. The connective returns r=0, irrespective of p.

Negation. [0,q,1] returns 0 when q is true and 1 when false, so it is \neg q.

Logic synthesis. A one-bit two-to-one multiplexer with data inputs p and r and select input q implements (q\land p)\lor(\neg q\land r).

Shannon decomposition. A Boolean function is split into its q=1 and q=0 cofactors, then represented as a conditioned disjunction. Recursively applying the step yields a decision structure.

Programming boundary. In q ? p() : r(), a language may call only the chosen function. The returned Boolean value can match conditioned disjunction, but the absence of effects from the other call is a language rule, not part of the truth connective.

Nonexample—majority. With inputs (p,q,r)=(1,0,0), majority returns 0; conditioned disjunction returns r=0 here, but on (0,0,1) majority returns 0 while conditioned disjunction returns 1. The operators are distinct.

Structural Tensions¶

Primitive status versus definability. The connective can be defined using implication, negation, and conjunction, yet can itself serve as a primitive from which familiar connectives are defined.

Extensional equality versus operational difference. Formulas and conditional programs can share a truth table while differing in evaluation order, effects, and undefined behavior.

Compact case structure versus expanded normal form. The ternary notation preserves branch roles; DNF or CNF exposes ordinary connectives but can obscure the selector.

Fixed truth function versus notation variance. Different communities place the selector first or middle, so equivalent symbols can look identical while permuting roles.

Universal Boolean expressibility versus representation cost. Functional completeness guarantees that every Boolean function is expressible, not that the resulting expression is small or efficient.

Logical selection versus physical hazards. An ideal multiplexer has the truth function; transistor delays and select transitions can produce glitches not represented in two-valued semantics.

Structural–Framed Character¶

Conditioned Disjunction is domain-specific and highly structural. It is fully determined by an arity, role assignment, and truth function. Its identities, completeness results, circuit correspondence, and decompositions are formal and repeatable.

It nevertheless remains inside logic and switching theory. Propositions, Boolean valuations, truth constants, logical equivalence, and connectives are constitutive. The selector skeleton transfers more broadly, but Selection already owns that substrate-neutral pattern. The candidate is therefore a domain-specific formal abstraction, not a new prime.

Structural Core vs. Domain Accent¶

The structural core is:

two alternatives + binary criterion + complementary admission + one selected output.

The domain accent makes alternatives proposition truth values, the criterion a Boolean proposition, complement the logical negation, admission conjunction, merge disjunction, and identity equality under every valuation. It also supplies truth-functional completeness and Boolean cofactor decomposition.

Without that accent, the pattern becomes generic Selection. With it, the connective supports proof systems, circuit synthesis, and Boolean normal forms that the broad prime does not specify.

Selection is the minimal prospective parent. Conditioned disjunction is strict truth-functional selection from a two-element branch set: q admits p and rejects r, while \neg q admits r and rejects p. Exactly one branch value continues to the output under a classical valuation.

Multiplexing is the direct one-bit hardware analogue, but the live prime's broader channel-sharing and demultiplexing commitments are not required by the logical connective. Decision adds commitment, uncertainty, and trade-off absent from an extensional truth function. Conditional Probability and Conditional Access attach conditions to other domain relations and do not cover it. Contraposition is logically adjacent only at a vocabulary level.

Only Selection is proposed as a DAG edge.

Relationships to Other Abstractions¶

Current abstraction Conditioned Disjunction Domain-specific

Parents (1) — more general patterns this builds on

Conditioned Disjunction is a kind of Selection Prime

Selection is the minimal prospective parent.

Hierarchy path (1) — routes to 1 parentless root

Conditioned Disjunction → Selection

Neighborhood in Abstraction Space¶

Conditioned Disjunction sits in a sparse region of the domain-specific corpus (76^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Hoare Logic — 0.85
Closed Preordered Set — 0.83
q-Analog — 0.83
Finite-Valued Logic — 0.83
Superpartient Ratio — 0.83

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Disjunction: binary inclusive OR, without selector-gated branches.
Material implication: one antecedent and consequent, not a two-branch selector.
Contraposition: an equivalence transformation of an implication.
If–then–else term: often the same extensional function but possibly broader in type and operational semantics.
Ternary conditional operator: programming syntax whose argument order, typing, laziness, and effects are language-defined.
Two-to-one multiplexer: a circuit implementation that may exhibit timing hazards absent from Boolean truth tables.
Shannon expansion: the general decomposition of a Boolean function into cofactors; conditioned disjunction is the combining operator.
Majority connective: a symmetric ternary function, unlike the role-asymmetric selector.
Conditional probability: probabilistic conditioning, not branch selection.
Exclusive OR: parity, not condition-directed choice.

References¶

[1] Church, Alonzo. “Conditioned Disjunction as a Primitive Connective for the Propositional Calculus”. Portugaliae Mathematica, 1948. Church's 1948 Portugaliae Mathematica paper, which introduces conditioned disjunction under that name as a primitive ternary connective for the propositional calculus. Church's 1948 paper, whose subject is conditioned disjunction as a primitive connective for the propositional calculus and which proves it complete and independent together with the truth constants. Fixes the argument order of Church's ternary notation: [p,q,r] is the conditional whose test is the MIDDLE argument, i.e. conventional q ? p : r and not p ? q : r. registry ↩a ↩b ↩c

[2] Church, Alonzo. Introduction to Mathematical Logic, Volume I. Princeton University Press, 1956. Church's textbook is where the connective is developed at length; the functional-completeness result quoted here is the one Church states in his 1948 paper, the textbook passage not having been consulted. registry ↩

[3] Shannon. “A symbolic analysis of relay and switching circuits”. Transactions of the American Institute of Electrical Engineers, 1938. Shannon's 1938 paper, which states the expansion of a Boolean function about a variable (equations 10a-10b) and applies it to circuit synthesis; the decision-diagram half of the sentence is later work. registry ↩

[4] Bryant. “Graph-Based Algorithms for Boolean Function Manipulation”. IEEE Transactions on Computers, 1986. Bryant's 1986 paper, which builds the graph by repeated Shannon expansion under a fixed variable order and reduces it by merging isomorphic subgraphs into a canonical form. registry ↩