= Solution
One Hilbert axiomatization of <classical propositional logic> uses the schemas $A\to(B\to A)$, $[A\to(B\to C)]\to[(A\to B)\to(A\to C)]$ and $(\neg B\to\neg A)\to(A\to B)$, with modus ponens as its inference rule. Other connectives can be defined from implication and negation. Syntactic entailment $\Gamma\vdash A$ means that a finite formal proof derives $A$ from the schemas and members of $\Gamma$. Consistency means that no formula and its negation are both derivable, equivalently no contradiction is derivable.
Use the standard deduction theorem, closure of derivability under modus ponens, and the maximal-consistency properties: a maximal consistent set contains exactly one of $A,\neg A$, is closed under derivability, and satisfies $A\to B\in\Phi$ exactly when $A\notin\Phi$ or $B\in\Phi$. These follow from the deduction theorem and the classical schemas; in particular adjoining a missing formula to a maximal set must yield a contradiction. Define $v(p)=T$ iff $p\in\Phi$. Induction on formula construction now proves
$$
v(A)=T\quad\Longleftrightarrow\quad A\in\Phi.
$$
For negation use the exactly-one property, and for implication use its displayed membership rule, which is precisely the Boolean truth table. Thus \b[every member of $\Phi$ is true under $v$], providing the required valuation.
Back to article page
