## Qdk

A or B or both

True

True

True

True

False

True

False

True

True

False

False

False

The validity of an inference in the sentential calculus can be established using the model theory of the calculus. Table III shows how premises can be used to eliminate possibilities from a truth table. When you have eliminated the impossible then, as Sherlock Holmes remarked, whatever remains, however improbable, must be the case. In other words, an inference is valid if the conjunction of its premises with the negation of its conclusion is inconsistent (i.e., not a single row in the resulting truth table contains the entry "true"). For instance, if you conjoin the negation of the conclusion in Table III, "The engine is not ready to start,'' to the premises, then it would eliminate the last remaining possibility in the truth table. It is therefore impossible for the premises to be true and for the conclusion to be false: The inference is a valid.

Any conclusion that can be proved using formal rules for the sentential calculus is also valid using truth tables and vice versa. There is also a decision procedure for the calculus; that is, the validity or invalidity of any inference can be established in a finite number of steps. Unfortunately, sentential inferences are computationally intractable. It is feasible to test the validity of inferences based on a small number of atomic sentences. However, as the number of atomic sentences in an inference increases, its evaluation in any system —no matter how large or how rapid—takes increasingly longer and depends on increasingly more memory, to the point that a decision will not emerge during the lifetime of the universe.

The sentential calculus has a decision procedure, but it is intractable. The predicate calculus includes the sentential calculus, but also deals with quanti-fiers—that is, with sentences containing such words as "any" and "some," as in "Any electrical circuit contains some source of current." The predicate calculus does not even have a decision procedure. Any valid inference can be proved in a finite number of steps, but no such guarantee exists for demonstrations of invalidity. Attempts to show that an inference is invalid may, in effect, get lost in the "space" of possible derivations. The principal discovery of 20th century logic, however, is Godel's famous proof that no consistent calculus is powerful enough to yield derivations ofall the valid theorems ofarithmetic. Arithmetic is thus incomplete. This result drives a wedge between syntax (proof theory) and semantics (model theory). Any attempt to argue that semantics can be reduced to syntax is bound to fail. Semantics has to do with truth and validity, whereas syntax has to do with proofs and formal derivability.

Table III

The Validity of an Inference Is Shown Using a Truth Table0

1. If the brakes are on and the switches are on then the engine is ready to start.

2. The brakes are on.

3. The switches are on.

All that remains is the first possibility, and so it follows validly: Therefore, the engine is ready to start.

Brakes are on Switches are on The engine is ready to start Possibilities that are eliminated

True

True

True