Propositional and First Order Logic Questions and Answers

Answer: A

Binding a variable to a term containing that same variable would create an infinite term, so the check rejects it, and omitting it makes the procedure unsound though faster. Many Prolog implementations omit it by default for that reason. Symbol occurrence, linearity and frequency are different notions. A soundness check omitted for speed, with the unsoundness considered acceptable in practice, is an engineering compromise worth knowing about explicitly.

Answer: B

Testing every binding for occurrence adds cost to the innermost operation of the system, and programs that would trigger it are uncommon, so many implementations trade soundness for speed while providing a sound unification predicate for those who need it. Implementability is not the obstacle, completeness is unaffected, and standards permit both. A known unsoundness accepted deliberately, with an escape hatch provided, is a defensible engineering position provided it is documented.

Answer: C

Prolog uses Horn clauses, depth first search with backtracking and negation as failure, which makes it fast and incomplete rather than a general prover. The restrictions are deliberate and are what make it a practical programming language. It adds no quantifiers and is certainly related. Recognising a language as a logic with a fixed proof strategy explains both its declarative reading and the places where that reading breaks down. Checking the units of each quantity catches a wrong formula before the arithmetic begins.

Answer: D

Choosing clauses in order and backtracking gives a depth first search that may follow a left recursive rule indefinitely without ever reaching a proof that a breadth first strategy would find. Reordering the clauses often fixes it, which is why the declarative reading is only an approximation. Horn expressiveness, the occurs check and negation semantics are separate issues, though the last two also affect soundness. A search strategy fixed for efficiency, at the cost of completeness, is the same trade depth first search always presents.

Answer: A

The declarative reading treats the clauses as implications and asks what follows, while the procedural reading describes how the interpreter will actually search. The two agree only when the program terminates and the search strategy finds what is entailed. Output and documentation are different notions. Having two readings of the same text, one of which is a guarantee and the other a behaviour, is characteristic of logic programming and is the source of most of its surprises.

Answer: B

A left recursive rule is perfectly true declaratively and sends a depth first interpreter into an infinite loop, so the program means one thing and does another. Reordering clauses changes the behaviour without changing the meaning. Negation, logic and entailment are the same in both readings, though negation as failure complicates the declarative account separately. A gap between what a program means and what it does is uncomfortable precisely because the language's appeal rests on the two coinciding.

Answer: C

Three symbols give eight models altogether, so half of them is:

\[ \tfrac{8}{2} = 4 \]

that is 4 models. A sentence true in every model would be valid and one true in none unsatisfiable, so this sentence is contingent. Counting models is the most direct way to see the difference between the three semantic categories, and it is worth doing once explicitly on a small example.

Answer: D

A contingent sentence is satisfiable but not valid, so it carries genuine information about which world we are in. Valid sentences are uninformative and unsatisfiable ones are impossible. Every sentence has a conjunctive normal form. Classifying a sentence as valid, unsatisfiable or contingent is the first thing to establish about it, since only the third kind says anything.

Answer: A

The theorem converts a question about entailment into a question about the validity of a single implication, which is why proving a theorem and checking a tautology are the same task. The second option states ex falso quodlibet, and the third completeness. Deduction and induction are quite different. Converting one kind of question into another, so that a single algorithm serves both, is the recurring pattern in this part of the subject. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.

Answer: B

Since an inconsistent set has no models, every sentence is vacuously true in all of them, so everything is entailed. That is why detecting inconsistency matters so much: a system that has quietly become inconsistent will cheerfully derive anything asked of it. The other options understate the consequence. A property that makes a system useless rather than merely wrong is one worth checking for actively rather than hoping to notice. Framing the question as which quantity the change acts upon makes the answer follow without calculation.