that shelf." A minimal tautology is a tautology that is not the instance of a shorter tautology. is a tautology, but not a minimal one, because it is an instantiation of . Verifying tautologies The problem of determining whether a formula is a tautology is fundamental in propositional logic. If there are n variables occurring in a formula then there are 2n distinct valuations for the formula. Therefore, the task of determining whether or not the formula is a tautology is a finite and mechanical one: one needs only to evaluate the truth value of the formula under each of its possible valuations. One algorithmic method for verifying that every valuation makes the formula to be true is to make a truth table that includes every possible valuation. For example, consider the formula There are 8 possible valuations for the propositional variables A, B, C, represented by the first three columns of the following table. The remaining columns show the truth of subformulas of the formula above, culminating in a column showing the truth value of the original formula under each valuation. Because each row of the final column shows T, the sentence in question is verified to be a tautology. It is also possible to define a deductive system (i.e., proof system) for propositional logic, as a simpler variant of the deductive systems employed for first-order logic (see Kleene 1967, Sec 1.9 for one such system). A proof of a tautology in an appropriate deduction system may be much shorter than a complete truth table (a formula with n propositional variables requires a truth table with 2n lines, which quickly becomes infeasible as n increases). Proof systems are also required for the study of intuitionistic propositional logic, in which the method of truth tables cannot be employed because the law of the excluded middle is not assumed. Tautological implication A formula R is said to tautologically imply a formula S if every valuation that causes R to be true also causes S to be true. This situation is denoted . It is equivalent to the formula being a tautology (Kleene 1967 p. 27). For example, let be . Then is not a tautology, because any valuation that makes false will make false. But any valuation that makes true will make true, because is a tautology. Let be the formula . Then , because any valuation satisfying will make true—and