Propositional and First Order Logic Questions and Answers

Answer: C

One contradictory pair among a hundred thousand axioms silently licenses every conclusion, and the system continues to answer queries confidently. That is why description logic reasoners check consistency as a matter of course. Storage, query preconditions and termination are different concerns. A fault whose symptom is confident wrong answers rather than an error message is the most dangerous kind, and mechanical detection is the only reliable defence.

Answer: D

Equivalent sentences have identical truth in every model, so either may replace the other anywhere without changing what is entailed. Mutual derivability coincides with it in a sound and complete system. Symbol counts are irrelevant and the last option is far too weak. Equivalences such as De Morgan's laws and the distributive laws are the tools by which a formula is rewritten into normal form, so knowing them as equivalences rather than as inference rules is what licenses the rewriting.

Answer: A

The laws say that the negation of a conjunction is the disjunction of the negations, and dually, which is what drives negations inward during conversion to normal form. Distribution, double negation elimination and implication elimination are the other rewriting rules used in the same procedure. Having a named set of equivalences that between them suffice to reach a normal form is what makes the conversion a mechanical procedure rather than an art.

Answer: B

A clause is a disjunction of literals, so every connective must first be rewritten in terms of negation, conjunction and disjunction, and the implication rewrite is the first step. Implication is perfectly truth functional and may be nested freely, and the rewrite generally leaves the size unchanged. Reducing a rich syntax to a minimal one, so that a single inference rule suffices, is the purpose of the whole conversion.

Answer: C

Distributing disjunction over conjunction can square the size at each step, so a formula with nested alternations blows up exponentially. Introducing auxiliary variables gives a linear conversion that preserves satisfiability though not equivalence, which is what practical tools use. Equivalence is preserved by the naive method, termination is guaranteed, and new variables appear only in the improved method. Trading equivalence for satisfiability, to avoid an exponential, is a trade a refutation procedure can afford.

Answer: D

Naming each subformula with a new variable and asserting the equivalence gives a clause set linear in the original size, equisatisfiable though not equivalent. Every practical satisfiability tool uses it. Quantifier elimination, simplification and equivalence checking are different procedures. A transformation whose output is larger in variables but linear in clauses, and which preserves exactly the property being tested, is a good illustration of choosing the right notion of correctness.

Answer: A

The first two are correct. A valid sentence is true whatever the world is like, so it distinguishes nothing and carries no information. Only contingent sentences say anything about which world obtains. The three statements together cover validity, entailment and informativeness, and the third inverts the relationship between logical strength and empirical content in a way worth being clear about.

Answer: B

All four notions are defined by quantifying over models in different ways, which is why they are so easily confused and so easily distinguished once that pattern is noticed. Entailment is validity relative to a set of premises, and validity is entailment from no premises at all, which connects the two ends of the list.

Answer: C

The first three are correct. A predicate denotes a relation and yields a truth value, whereas a function denotes an object and may appear wherever a term is expected. The distinction determines where each may legally appear in a formula, and confusing them produces expressions that are not well formed at all rather than merely false, which is at least an error that a parser will catch.

Answer: D

Normal forms, literals and clauses are all defined by the shape of an expression and can be checked by inspection. Entailment is semantic, defined by quantifying over models, and cannot be read off the syntax. Keeping the syntactic and semantic vocabularies apart is what allows soundness and completeness to be stated as a relationship between them rather than as a tautology.