Propositional and First Order Logic Questions and Answers

Answer: C

Horn clauses correspond to rules with a conjunction of conditions and a single conclusion, and inference over them is linear rather than exponential, which is why logic programming and production systems are built on them. Clause length, positivity and resolvability are different properties. A syntactic restriction that buys a dramatic improvement in complexity, while remaining expressive enough for a great many applications, is a bargain worth recognising.

Answer: D

Applying each rule as soon as its conditions are satisfied derives the whole set of consequences in time linear in the size of the knowledge base, which is why deductive databases and Prolog are practical. Symbol counts are unrelated, satisfiability is not automatic since a set of Horn clauses may be contradictory, and resolution still applies. A restriction that converts an intractable problem into a linear one, at a stated cost in expressiveness, is the clearest possible illustration of the expressiveness against tractability trade.

Answer: A

Modus ponens is the rule that from p implies q and p, conclude q, and it is sound in every logic that has implication. Affirming the consequent, the second option, is a fallacy. Contraposition is an equivalence rather than an inference from premises, and the fourth is disjunctive syllogism. Distinguishing the sound rule from the plausible looking fallacy that reverses it is the single most useful thing to be clear about in elementary logic. Most errors here come from carrying a result across from a neighbouring case where it does not hold.

Answer: B

From rain implies wet ground and wet ground, one cannot conclude rain, since a burst pipe would serve equally well. The implication holds and the consequent is true, yet the antecedent may be false. Truth functionality holds and the implication is granted. Recognising that a true conditional and a true consequent leave the antecedent undetermined is what separates valid inference from plausible reasoning, and the distinction matters constantly in diagnosis.

Answer: C

Modus tollens reasons backwards from a false consequent to a false antecedent, and is the rule underlying refutation and much of scientific method. Modus ponens is the forward direction, hypothetical syllogism chains implications and simplification extracts conjuncts. The backward direction being valid, while affirming the consequent is not, is an asymmetry worth being able to state precisely rather than merely recognising by example. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

Answer: D

Soundness guarantees that no false conclusion is produced from true premises, which is the minimum requirement of any reasoning system. Completeness is the converse, that everything entailed can be derived. Termination and proof length are separate properties. A procedure that is complete but unsound is worthless, whereas one that is sound but incomplete is merely limited, which is why soundness is never traded away.

Answer: A

Completeness guarantees that the procedure will find a proof whenever one exists, though it may take arbitrarily long. Soundness is the converse, and decidability, that every question receives an answer, is a stronger property first order logic lacks. Halting is related but distinct. A procedure may be sound and complete and still fail to terminate on an unprovable question, which is exactly the situation in first order logic and is worth being precise about.

Answer: B

First order logic commits to a world of objects with properties and relations, and permits quantification over those objects, so a general statement need be made only once. Implication exists in both, decidability is lost rather than gained, and the truth values are unchanged. Gaining the ability to say something about every object of a kind, at the cost of decidability, is the central trade the step upward involves.

Answer: C

Terms are constants, variables and function applications, and they denote objects rather than having truth values. Applying a predicate to terms gives an atomic sentence, which does have a truth value. Quantifiers bind variables in sentences. Keeping the two categories apart, expressions that denote and expressions that assert, is what prevents the commonest syntactic errors in writing formulas.

Answer: D

A function symbol such as father of maps each object to exactly one object, so it may be used wherever a term is expected. A predicate expresses a relation and yields a truth value instead. Procedures and properties are different notions, the last being a unary predicate. The distinction between a function, which denotes, and a predicate, which asserts, is what determines where each may appear in a formula.