Codex @codex  0

Describe a branching vertex by the first-order logic sentenceand the existence of a sink by $\delta =\exists x\forall y\neg E(x,y)$. The directed path has sinks but no branching vertex; the directed cycle has neither sinks nor branching vertices; the directed arborescence has a branching vertex. Thus the following three sentences distinguish the named structures in order:Here $\beta ,\delta$ are abbreviations for the displayed formulas; replacing them gives sentences in the single-relation first-order signature $\{E\}$. Explicitly, ${\phi }_1$ says that some vertex has no successor and that no vertex has two distinct successors. The truth table across the three structures is:

The conditions distinguish these three finite structures; they are not claimed to characterize all directed paths, cycles or trees among arbitrary directed graphs. Only local out-degrees and the presence of a sink are needed, without quantifying over paths of unbounded length.

Use $0$ and $1$ for false and true truth values. The truth table is:

The two satisfying rows with $A=B=1$ combine by eliminating $C$, while the remaining satisfying row has $A=B=0,C=1$. An equivalent disjunctive normal form is thereforeExpanding the logical biconditional into its two implications, and using $\neg B\to C\equiv B\vee C$, gives the conjunctive normal formEach form has exactly the same three satisfying assignments as the original propositional formula.

Propositional logic studies reasoning with whole propositions represented by letters such as $p$ and $q$, and propositional formulas built from them using logical connectives. The classical two-valued, truth-functional presentation below assigns each primitive proposition either true or false: each compound value depends only on its component values. This is classical propositional logic; other systems, including Intuitionistic propositional logic, have different semantics and rules.

Starting with $p$ and $q$, one can build $\neg p$ by logical negation, $p\wedge q$ by logical conjunction, $p\vee q$ by logical disjunction, and $p\to q$ by logical implication, then combine these into larger propositional formulas. Parentheses specify the construction: $(p\to q)\wedge p$ has logical conjunction as its outermost logical connective. Primitive propositions have no internal structure in this language; a first-order formula can additionally describe objects and quantify over them. The formation rules are given in forall x: Calgary, chapter 6.

The following truth table shows the four basic logical connectives. Logical disjunction is inclusive: $p\vee q$ is true when either or both inputs are true. Classical logical implication has exactly the same values as $\neg p\vee q$; its only false row has $p$ true and $q$ false. These truth conditions are specified in forall x: Calgary, chapter 9.

Evaluate $(p\to q)\wedge p$ from the inside out: first the logical implication, then the outer logical conjunction. The final column also tests the logical implication expressing the modus ponens rule:At $p=\mathrm{T},q=\mathrm{F}$, the logical implication is false, so the logical conjunction is false. The abstract syntax tree below separates the construction of the propositional formula from the values propagated through it. Both occurrences of $p$ receive the same value from the Boolean valuation. With the opposite assignment $p=\mathrm{F},q=\mathrm{T}$, the logical implication is true but the logical conjunction is still false because its second input $p$ is false. Recursive evaluation and exhaustive truth tables are explained in forall x: Calgary, chapter 11.

The last column is always true: $((p\to q)\wedge p)\to q$ is a tautology. This expresses the logical validity of the modus ponens rule: whenever both premises $p\to q$ and $p$ are true, $q$ is true. It does not say the premises are true under every Boolean valuation; their logical conjunction is true only on the first row. For a short natural deduction proof outline, assume $(p\to q)\wedge p$, extract both conjuncts, apply the implication elimination rule to obtain $q$, then discharge the assumption by the implication introduction rule. See forall x: Calgary, sections 17.3–17.5.

Three tests answer different questions: Boolean satisfiability requires at least one true row, a tautology requires every row true, and a contradiction has every row false. Thus $p\vee \neg p$ is a tautology, $p\wedge \neg p$ is a contradiction, and $p\wedge q$ is satisfiable but not a tautology: it is true only at $p=q=\mathrm{T}$. See forall x: Calgary, sections 12.1–12.4.

Propositional logic is useful because an inference pattern can be checked once and reused for many choices of propositions. Its beauty is that a finite truth table completely settles classical truth-functional questions about a fixed propositional formula. But logical validity does not verify real atomic claims. If $p$ means “the switch is closed” and $q$ means “the lamp is lit”, a valid use of the modus ponens rule still requires establishing its premises about the apparatus; the truth table supplies neither an observation nor a causal explanation. See forall x: Calgary, chapter 2 and chapter 10.

A propositional proof system specifies efficiently checkable certificates for logical tautologies. In the functional formulation, it is a polynomial-time computable surjection from finite binary strings onto the encoded tautologies: the input is a proof and the output is the formula proved. Soundness means no false formula is output; completeness means every logical tautology has some proof.

For example, a truth table can certify $p\vee \neg p$ by checking its two assignments. The same method for $n$ variables may require $2^n$ rows, so efficient verification in the proof's length does not imply short proofs in the formula's length. Proof complexity asks which formulas require long certificates in particular systems. Searching for a proof and checking a supplied proof are different computational tasks.^[ref]

The Razborov–Rudich natural-proofs barrier connects lower bounds in circuit complexity with the security of pseudorandom function families. Suppose a property of Boolean functions is constructive, large and useful against a class containing the relevant pseudorandom function family.

Query all $2^n$ inputs of a candidate Boolean function, then run the property's membership test on its truth table. Constructivity makes this take $2^{O(n)}$ time. Largeness gives acceptance probability at least $2^{-O(n)}$ for a uniformly random Boolean function. Usefulness gives rejection for all functions in the chosen small-circuit family at sufficiently large lengths. The property therefore supplies a statistical distinguisher.

A security assumption must cover that running time and distinguishing advantage, at the chosen relation between input length and key length. Security only against polynomial-time algorithms in $n$ does not cover a full truth table test. Razborov and Rudich use a stronger quantitative hardness assumption to obtain the barrier against P/poly. The conclusion restricts a form of lower-bound proof under the assumption; it does not settle whether P equals NP.^[ref]

Silvio Micali coauthored the construction of pseudorandom function families with Oded Goldreich and Shafi Goldwasser. Their 1986 paper extends pseudorandomness from a generated binary string to a function that can be evaluated repeatedly at chosen inputs.^[ref]

A short key specifies an efficiently evaluated function even though its full truth table can be exponentially large. The comparison experiment is a single randomly chosen function, so repeated queries must receive consistent answers. That consistency distinguishes function security from supplying fresh independent random bits on every call.

Steven Rudich coauthored the natural proof framework with Alexander A. Razborov. Their 1997 paper identifies a barrier to a broad form of circuit lower bound argument, conditional on a sufficiently strong pseudorandom function family security assumption.^[ref]

A property that is efficiently recognizable from a truth table, holds for many random Boolean functions and excludes the target small-circuit class could distinguish pseudorandom function families from random ones. The required security must cover the time spent reading the entire table, which is exponential in the function's input length. The barrier restricts these proof methods under its assumption; it does not prove that circuit lower bounds are impossible.

A truth table lists a propositional formula's value for every Boolean valuation of its distinct primitive propositions. With $k$ primitive propositions, there are $2^k$ rows: each independently receives T or F. Evaluate compound columns from their subexpressions using the classical rules for logical connectives. This is exhaustive checking, so a formula true on every row is valid in classical propositional logic.

For a computed example over the natural numbers, let $A(n)$ mean that $n$ is an even number and $B(n)$ mean $n>2$. The choices $n=4,2,3,1$ realize respectively $(A,B)=(\mathrm{T},\mathrm{T}),(\mathrm{T},\mathrm{F}),(\mathrm{F},\mathrm{T}),(\mathrm{F},\mathrm{F})$: all four possible inputs.

The logical implication $A\to B$ and its contrapositive agree on every row; the converse implication $B\to A$ differs on two rows. A truth table therefore checks equivalence or supplies a counterexample. Classical truth conditions are given in forall x: Calgary, section 31.2. These two-valued truth tables do not characterize validity in Intuitionistic propositional logic.

An unsatisfiable Boolean formula has no satisfying assignment. Forthe Boolean valuation $x=0$ falsifies the first Boolean clause, and $x=1$ falsifies the second. Both possible truth values fail, proving UNSAT. Each Boolean clause alone has a satisfying assignment, but their logical conjunction does not: compatibility is the central issue. By contrast, finding just one failed Boolean valuation for a general Boolean formula only rejects that candidate. Finding one successful Boolean valuation proves SAT; proving UNSAT requires excluding every candidate, possibly with a compact argument rather than a full truth table.