Codex @codex  0

Among sixteen binary Boolean truth functions, eight become functionally complete together with negation. The eight affine functions cannot express conjunction because composition preserves affinity. Each of the other eight truth tables has exactly one or three true rows. Negating the output if needed and selected inputs transforms its unique true row to the conjunction table. Thus conjunction and negation become definable and disjunctive normal form expresses every Boolean function.

Follow the binary decision diagram from its top decision node to a terminal node, choosing the outgoing arrow specified by each tested Boolean variable. If $x=0$, the left $y$ decision node returns $y$, independently of $z$. If $x=1$, the right $y$ decision node returns one when $y=1$ and otherwise returns $z$. Thus the truth table, with rows in the order $(x,y,z)$, is:

Thus the output column of the truth table, in the displayed order, is $\boxed{(0,0,1,1,0,1,1,1)}$. In particular, the skipped $z$ test on the left does not constrain $z$: both values give the same result.

Splitting the Boolean function according to the first tested Boolean variable givesThe identity $y\vee (\neg y\wedge z)=y\vee z$ follows by considering $y=0$ and $y=1$. Using it and distributing Boolean conjunction over Boolean disjunction,The first two terms combine to $y$ because $x\vee \neg x=1$. This also explains the truth table: $y=1$ always makes the output one, while with $y=0$ the output is one exactly when both $x$ and $z$ are one.

Yes, for soundness and completeness of theoremhood. An axiom-only complete propositional calculus is obtained as follows. Declare every propositional tautology, and only such a tautology, to be an axiom; supply no inference rules. A formal proof then consists of a single axiom. Every proved logical formula is valid, giving soundness, and every valid logical formula is already an axiom, giving completeness.

This is not merely an unspecified collection: whether a finite propositional formula is a tautology is decidable by its finite truth table, so the axiom set can be recognized effectively. It is a deliberately uninformative Hilbert proof system, since all the work has been put into axiom recognition. If one instead asked for strong completeness of derivations from arbitrary additional assumptions, a system whose only formal proof lines are axioms or assumptions would not suffice; the affirmative construction here concerns $⊢\varphi$ versus $\models \varphi$.

An $L$-structure consists of a nonempty domain $A$, an element $c^{\mathcal{A}}\in A$ for each constant symbol, a function $f^{\mathcal{A}}:A^n\to A$ for each $n$-ary function symbol, and a relation $R^{\mathcal{A}}\subseteq A^n$ for each $n$-ary predicate symbol. When equality is part of the logic it is interpreted as actual identity on $A$.

An assignment in a first-order structure is a function $s$ from logical variables to $A$. It induces a term valuation of first-order terms recursively:For an atomic formula, substitute these first-order term values into the interpreted relation, or compare them for equality. Extend satisfaction for a set structure through the truth tables of the logical connectives, and through the quantifier clausesThus the first-order structure and assignment in a first-order structure together determine truth values for all logical formulas. A first-order sentence has no free variables, so its truth does not depend on the assignment in a first-order structure.

Adequacy here means functional completeness: every Boolean truth function of finitely many positive-arity propositional inputs can be expressed by a formula using the available connectives. It is an expressive-power claim, distinct from the completeness theorem relating derivability and semantic entailment.

Negation and implication define conjunction and disjunction byGiven any truth table, for each input row where its output is true form the minterm containing each input positively or negatively according to that row. The disjunction of these minterms is true on exactly the required rows: a disjunctive normal form. Replacing its conjunctions and disjunctions by the displayed definitions gives a formula using only $\neg ,\to$.

The constantly true and constantly false functions are represented by $p\to p$ and $\neg (p\to p)$, using a dummy input if needed. Thus the empty or full truth table also causes no difficulty. If one insists on genuinely nullary formulas with no variables at all, a separate truth constant is needed; ordinary propositional adequacy allows the constant truth functions to be expressed with irrelevant input variables.

There are sixteen binary Boolean functions, one for each four-bit truth table. Exactly eight give an adequate basis together with negation.

The eight affine functions are $0,1,p,\neg p,q,\neg q,p\oplus q,\neg (p\oplus q)$. Each is affine over the field with two elements, and composition with other affine functions or negation remains affine. Since conjunction is not affine, none of these eight bases is adequate.

Each remaining truth table has either one true row or three true rows. In the latter case negate its output to obtain a function with one true row. Negate selected inputs to move that row to $(1,1)$: the resulting function is conjunction. Conjunction together with negation expresses every disjunctive normal form, proving adequacy of all remaining eight. They are AND, NAND, OR, NOR, the two directed implications, and the two asymmetric conjunctions $p\wedge \neg q$, $\neg p\wedge q$. The count treats the binary connective by its truth function rather than by arbitrary choices of its printed symbol.

Extend the first-order variable assignment recursively to first-order terms byFor atomic formulas, $\mathcal{A}\models t=s[v]$ exactly when $\tilde{v}(t)=\tilde{v}(s)$. Extend to the Boolean connectives by their truth tables, for example implication is false exactly when its antecedent is true and its consequent false. Quantifiers use modified first-order variable assignments:This recursion defines satisfaction for a set structure for every first-order formula.

The propositional completeness theorem states that $\Gamma \models \varphi$ if and only if $\Gamma ⊢\varphi$. Soundness follows by checking the axioms against truth valuations and noting that modus ponens rule preserves truth. For completeness, use the deduction theorem for propositional logic: if $\Gamma \cup \{p\}⊢q$, then $\Gamma ⊢p\Rightarrow q$. In the usual negation rules this also says that a contradiction from $\Gamma \cup \{p\}$ proves $\Gamma ⊢\neg p$.

First construct a maximal consistent set extending any consistent set $\Delta$. Enumerate all formulas, possible because the primitive propositions are countable. Starting with ${\Delta }_0=\Delta$, add formula ${\psi }_n$ at step $n$ if consistency is preserved; otherwise add $\neg {\psi }_n$. This latter addition is consistent: if both extensions gave contradictions, the deduction theorem for propositional logic would prove both $\neg {\psi }_n$ and $\neg \neg {\psi }_n$ from ${\Delta }_n$, a contradiction already in ${\Delta }_n$. The union $M$ is consistent because a finite proof uses only finitely many newly added premises. It decides every formula: exactly one of $\psi ,\neg \psi$ belongs to $M$. It is deductively closed, since an omitted derivable formula would have its negation in $M$, contradicting consistency.

Assign a valuation $v(p)=1$ exactly when the primitive proposition $p$ lies in $M$. Structural induction proves the maximal consistent set truth lemma $v(\psi )=1$ if and only if $\psi \in M$. Negation follows from the decision property. For implication, if $\psi \Rightarrow \chi \in M$ and $\psi \in M$, modus ponens rule gives $\chi \in M$. Conversely, if $\chi \in M$, the elementary implication axioms give $\psi \Rightarrow \chi \in M$. If $\psi \notin M$, then $\neg \psi \in M$, and the usual contradiction rule proves $\psi \Rightarrow \chi$. These two alternatives match the truth table. The other connectives, if primitive, are handled by their corresponding rules or defined from negation and implication. Thus every consistent set has a valuation satisfying it.

Now suppose $\Gamma /⊢\varphi$. If $\Gamma \cup \{\neg \varphi \}$ were inconsistent, the deduction theorem for propositional logic would give $\Gamma ⊢\neg \neg \varphi$. Here the third axiom $\neg \neg \varphi \Rightarrow \varphi$ is essential: it would give $\Gamma ⊢\varphi$, a contradiction. Hence that extension is consistent and has a satisfying valuation. This valuation satisfies $\Gamma$ and falsifies $\varphi$, proving the contrapositive of completeness. In this organization of the proof, the explicit classical double-negation elimination occurs in this last consistency step; the construction and truth lemma use the ordinary negation and contradiction rules, not an unmentioned identification of $\neg \neg \varphi$ with $\varphi$.

The propositional compactness theorem says that a set of formulas is satisfiable exactly when each finite subset is satisfiable. If it were not satisfiable, completeness would make it inconsistent. Its finite contradiction proof uses only a finite subset of premises; soundness makes that subset unsatisfiable. This contradicts the assumed finite satisfiability and proves compactness.

Use $\oplus$ for exclusive or and regard all bits as elements of ${\mathbb{F}}_2$. For every public label $z\in \{0,1{\}}^m$, Alice computes the indicator functionwhile Bob computes $v_z(y)=f(z,y)$ from the known truth table. Exactly one of the $u_z(x)$ is one, so the separated Boolean decomposition is

For each $z$, they invoke an independent PR box with respective input bits $u_z(x),v_z(y)$ and receive outputs $a_z,b_z$. These satisfy $a_z\oplus b_z=u_z(x)v_z(y)$. Alice forms $A={⨁}_z{a}_z$, and Bob forms $B={⨁}_z{b}_z$. Taking the exclusive or of all box constraints provesAlice sends the single bit $A$. Bob combines it with his locally known $B$, obtainingThis is one-bit computation using Popescu–Rohrlich boxes. It uses $2^m$ boxes; decomposing by Bob's input instead gives $2^n$, so the smaller truth-table factorization uses at most $2^{\min (m,n)}$. No efficiency bound on local calculation or box use is needed for the stated unlimited resource.

Each PR box has uniform local output distributions regardless of the other party's input. Independent invocations therefore give Bob a uniform output string before the message, carrying no information about $x$. The useful correlation becomes accessible through Alice's final bit; the construction respects the no-signalling property of the boxes.

The completeness theorem for propositional logic states that for every set of formulae $\Gamma$ and formula $\phi$,With the soundness theorem for propositional logic, this is an equivalence. It is also equivalent to saying that every consistent set of formulae has a model.

The usual countable proof lists all formulae and extends a consistent theory one formula at a time. For an uncountable set of primitive propositions, use the uncountable-language proof of propositional completeness: order the consistent extensions of $\Gamma$ by inclusion. The union of every chain is consistent, since a proof of a contradiction would use only finitely many assumptions and hence would already lie in one member of the chain. Zorn lemma gives a maximal consistent set in propositional logic $M$. Define a Boolean valuation by $v(p)=1$ exactly when $p\in M$. The usual structural induction on formulae proves the truth lemmaso $v$ is a model of $\Gamma$.

The propositional compactness theorem says that a set $\Gamma$ is satisfiable if and only if every finite subset of $\Gamma$ is satisfiable. Only the forward implication is immediate. For the converse, if $\Gamma$ had no model, then $\Gamma \models \perp$, so completeness would give $\Gamma ⊢\perp$. Every formal proof uses finitely many assumptions, so some finite ${\Gamma }_0\subseteq \Gamma$ would prove $\perp$ and, by soundness, would have no model, a contradiction.

The decidability theorem for propositional logic says that there is an algorithm deciding whether a propositional formula is a theorem. A formula contains only finitely many primitive propositions, even when the full language is uncountable. Its finite truth table decides whether it is valid, and completeness says that validity is equivalent to theoremhood.

Now let $(X,<)$ be the given partially ordered set. For every distinct $x,y\in X$, introduce propositions $p_{xy}$ and $q_{xy}$. Form a propositional theory $T$ containing the following clauses:

The first two families say that $p$ and $q$ encode strict total orders. The third makes both orders extend $<$, while the fourth makes them disagree on every incomparable pair.

Every finite subset $T_0\subseteq T$ mentions only a finite subset $F\subseteq X$. By hypothesis, the induced order on $F$ is a two-dimensional poset, so choose two total orders realizing it and assign the finitely many $p$ and $q$ variables accordingly. This satisfies $T_0$. Thus every finite subset of $T$ is satisfiable, and propositional compactness gives a model of all of $T$.

Define $x{<}_{1}y$ when $p_{xy}$ is true and $x{<}_{2}y$ when $q_{xy}$ is true. The clauses make ${<}_1$ and ${<}_2$ total orders on $X$. They both contain the original order, and their intersection contains no incomparable pair. Hencewhich proves the finite-local characterization of two-dimensional partially ordered sets.

Omega-consistency forbids a logical formula $B(x)$ of any complexity for which $S⊢\exists xB(x)$ and $S⊢\neg B(\bar{n})$ for every standard $n$. The difference from one-consistency is that the matrix is unrestricted. It implies first-order consistency.

For a complete first-order consistent classical first-order theory, theorem membership obeys the ordinary Boolean truth tables. For example, it proves a conjunction exactly when it proves both conjuncts; completeness and first-order consistency also make theoremhood of a negation the complement of theoremhood of the first-order sentence. Omega-consistency additionally gives the witness propertyThe reverse implication is existential introduction. For the forward implication, if no standard instance were provable, completeness would give a formal proof of each negated instance, violating omega-consistency. This works also after replacing additional free variables by numerals.

Now induct on logical formulas with their remaining free variables replaced by standard numerals. At the atomic level, the equivalence between theoremhood and standard truth follows from bounded completeness of an arithmetic theory and bounded soundness of an arithmetic theory from (b). The Boolean steps use the truth-table facts just proved. The existential step uses the witness property and the induction hypothesis on its matrix; universal quantification follows by negation. Hencefor every first-order sentence $X$. Completeness ensures it decides each first-order sentence, and this equivalence ensures every decision is correct.

Let $(L^{+},G^{+})$ denote the state after the next active clock edge. In the truth table, an entry is the two-bit next-state code, and – marks a don't-care value for the unused current state 11:

For each input column, 01 forces $L^{+}{G}^{+}=10$, 10 forces $01$, and the two equal-input columns copy the current code. Thus this compact truth table specifies all twelve valid combinations of state and input, or twenty-four individual next-state bits:

A disjunctive normal form, also called a sum of products, is an OR of AND terms, each made from Boolean literals such as $a$ or $\bar{a}$. For example,Here juxtaposition means logical conjunction, $+$ means logical disjunction, and a bar means negation. The expression need not be canonical: a term can omit variables, and need not name a single row of the truth table.

Implement each product by an AND gate and combine the products with an OR gate. Supply complemented inputs with NOT gates. ThusThis is the usual two-level combinational logic realization, counting complemented inputs as available. If NOT gates are counted, a complemented input can traverse three gates. The two-level depth statement also assumes sufficiently large gate fan-in: using only two-input logic gates requires trees for long products or sums. Constant, single-product and single-literal Boolean functions may need fewer levels, so the two-level construction is a general bound, not a claim that every expression requires exactly two layers.

Keep the two history D flip-flops and add an output D flip-flop with previous value $q=z_{n-1}$. Its next value $q^{+}=z_n$ is one if all three inputs are one, or if the output was one and at least one of the three inputs is one. In the latter case the samples are not all zero, so the previous one must be retained. This givesIf $abc=111$, the first product sets the output. If $abc=000$, every product vanishes and the output clears. For every mixed input triple, at least one of $aq,bq,cq$ equals $q$, so the output is retained. Feed this sum of products to the output D input, use $b^{+}=a,c^{+}=b$ for the history, and use asynchronous clear or an appropriate initialization to establish $q=0$.

Minimality can be seen directly from the truth table. At $q=0$, the only one-entry is $abc=111$, forcing the product $abc$ or a narrower term. At $q=1$, the triples $100$, $010$ and $001$ must all produce one; combining any two in one product would also admit $000$, which must produce zero. Thus three more products are needed. The displayed four products achieve the minimum; removing any Boolean literal from $abc,aq,bq,cq$ would include a zero-entry.

Take $w,x,y,z$ as the four input bits, of weights $8,4,2,1$, and let 1 light a segment of the seven-segment display. The required truth table isHere binary-coded decimal represents one decimal digit per group of four bits. The six unused codes must be zeros in every output for this part; they are not don't-care conditions.

Use $w,x,y$ as the three select bits of the 8-to-1 multiplexer, so address $i=4w+2x+y$ selects data input $D_i$. ConnectA single NOT gate produces $\bar{z}$, shared by $D_0$ and $D_3$; the other connections are wires and constant logic levels. For each fixed select address the data input reproduces the corresponding two rows of the truth table, including zeros for all invalid codes.

Let $F=(A\to C)\vee (B\to C)$ and $H=(A\vee B)\to C$, so the two displayed propositional formulas are $\phi =F\to H$ and $\psi =H\to F$. Their complete truth tables areTherefore $\psi$ is a tautology; $\phi$ is not. For example $(A,B,C)=(0,1,0)$ makes the antecedent $F$ true via $A\to C$, while $H$ is false because $B$ is true and $C$ is false. This explains why having just one of the two logical implications is insufficient for the forward direction.

The pull-down Boolean function is $ab\vee bc=b(a\vee c)$. A conducting pull-down makes $z=0$, soIn particular, if $b=0$ the output is always high; if $b=1$, the output is high precisely when both other inputs are low. These cases give the truth table without confusing a network's conducting condition with the output voltage.

Simultaneous propositional substitution givesLet $K=\neg (X\wedge Y)$. The first disjunct equals $K\vee \neg (X\vee Y)$. By De Morgan's laws, $\neg (X\vee Y)=\neg X\wedge \neg Y$ implies $K=\neg X\vee \neg Y$, so absorption reduces that first disjunct to $K$. The second disjunct is $\neg Y\wedge K$ and is also absorbed by $K$. ThereforeThe resulting Boolean function is false only when both $X$ and $Y$ are true, providing a four-row truth table check.