Propositional and First Order Logic Questions and Answers

Q: What is the occurs check in unification?

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.

Q: Why do some implementations omit the occurs check?

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.

Q: What is the relationship between first order logic and Prolog?

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.

Q: Why is Prolog incomplete as a theorem prover?

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.

Q: What is the declarative reading of a logic program?

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.

Q: Why do the declarative and procedural readings sometimes disagree?

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.

Q: What is a contingent sentence?

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.

Q: What is the deduction theorem in propositional logic?

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.

Q: What follows from an inconsistent set of premises?

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.

41.

What is the occurs check in unification?

A.Testing whether a variable appears inside the term it is bound to
B.Checking whether a symbol occurs anywhere in the knowledge base
C.Verifying that each variable occurs at most once in a clause
D.Counting how often a predicate occurs among the premises

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.

Discuss in Forum

42.

Why do some implementations omit the occurs check?

A.The standard for the language expressly forbids performing the check
B.It costs time and the failing case arises rarely in practice
C.The check is impossible to implement efficiently at all
D.Omitting it makes the procedure complete rather than sound

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.

Discuss in Forum

43.

What is the relationship between first order logic and Prolog?

A.Prolog and first order logic are entirely unrelated systems
B.Prolog extends first order logic with additional quantifiers
C.Prolog implements a restricted clause form with a specific search order
D.Prolog is a complete theorem prover for first order logic

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.

Discuss in Forum

44.

Why is Prolog incomplete as a theorem prover?

A.Horn clauses cannot express any interesting theorems
B.Unification without the occurs check is unsound
C.Negation as failure cannot be given a semantics
D.Its depth first search may descend an infinite branch forever

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.

Discuss in Forum

45.

What is the declarative reading of a logic program?

A.What the program means as a set of logical sentences
B.The order in which the interpreter will try the clauses
C.The output the program produces on a given input
D.The documentation describing what the program should do

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.

Discuss in Forum

46.

Why do the declarative and procedural readings sometimes disagree?

A.The two readings use different definitions of entailment
B.The search strategy may fail to find a proof that exists
C.The declarative reading ignores the negation in the program
D.The procedural reading assumes a different logic entirely

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.

Discuss in Forum

47.

How many models satisfy a sentence with 3 symbols that is true in exactly half of them?

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.

Discuss in Forum

48.

What is a contingent sentence?

A.One true in every model of the premises
B.One whose truth depends on a further assumption
C.One that cannot be written in conjunctive normal form
D.One true in some models and false in others

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.

Discuss in Forum

49.

What is the deduction theorem in propositional logic?

A.Premises entail a conclusion exactly when the implication is valid
B.Any conclusion may be deduced from inconsistent premises
C.Every valid sentence has a proof of finite length
D.Deduction and induction give the same conclusions from the same premises

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.

Discuss in Forum

50.

What follows from an inconsistent set of premises?

A.Only sentences that are themselves inconsistent
B.Every sentence whatever
C.Only sentences already among the premises
D.Nothing at all, since no conclusion is licensed

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.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Propositional and First Order Logic Questions and Answers || Propositional and First Order Logic MCQ Questions and Answers || Propositional and First Order Logic GK Questions and Answers || Propositional and First Order Logic GK MCQ Questions || Propositional and First Order Logic Multiple Choice Questions and Answers || Propositional and First Order Logic GK || GK on Propositional and First Order Logic || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Propositional and First Order Logic Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications