Propositional and First Order Logic Questions and Answers

Q: What is an interpretation in first order logic?

An interpretation supplies a non-empty domain of objects and assigns each constant an object, each function symbol a mapping and each predicate a relation, and a sentence is then true or false in it. Truth value assignment is the propositional analogue and is insufficient here. Proofs and translations are different objects. Specifying meaning by fixing a domain and interpreting every symbol is what makes truth in first order logic precise. Checking the units of each quantity catches a wrong formula before the arithmetic begins.

Q: Why is first order entailment only semidecidable?

A complete procedure will eventually derive any entailed sentence, but when the sentence is not entailed it may search forever without ever concluding that. That is the semidecidability result. Procedures are complete, and infinite domains and quantifiers are the reasons behind it rather than the statement. A guarantee that holds in one direction only is a genuine limitation rather than a defect of implementation, and no better algorithm will remove it.

Q: What practical consequence follows from semidecidability?

A user who has waited an hour cannot tell whether the conjecture is false or the proof is merely long, which is why provers report timeouts rather than negative answers. Theorems are provable and questions are often answered, and propositional encodings are one response among several. Knowing that a negative result is unobtainable, rather than merely slow, changes how a tool's output must be interpreted.

Q: What is the Herbrand universe of a set of clauses?

The Herbrand universe is the syntactic domain of all closed terms, and the Herbrand theorem shows that unsatisfiability may be established by considering only ground instances over it. That reduces first order refutation to a propositional question, though possibly an infinite one. Models, intended domains and atoms are different objects. Reducing a question about all interpretations to one about a single syntactic structure is what makes mechanical first order proof possible.

Q: Why is the Herbrand theorem important for automated reasoning?

If a set of clauses is unsatisfiable, some finite set of ground instances is already unsatisfiable, so a prover may enumerate instances and use propositional methods. Finite models do not always exist, no decision procedure follows, and completeness of resolution is a separate result. Reducing an apparently infinite question to a finite one that can be found by enumeration is what turns semidecidability from an abstract statement into an actual algorithm.

Q: What is skolemisation?

Skolemisation replaces each existential variable by a term built from a fresh function symbol applied to the enclosing universal variables, which removes the existential quantifiers while preserving satisfiability. It is a step in converting to clausal form. Universal removal, normal form conversion and standardising apart are the neighbouring steps. Preserving satisfiability rather than equivalence is the subtlety, and it is exactly what a refutation procedure needs.

Q: What is unification?

Unification computes the most general substitution that makes two atoms syntactically the same, and it is what allows resolution to apply to first order clauses without enumerating ground instances. Clause combination is resolution itself, and the other options describe different operations. Working with variables directly, rather than instantiating them, is what makes first order proof tractable, and unification is the mechanism. The shared properties explain why these belong to one family, and the differences explain why more than one exists.

Q: What is the most general unifier?

Among all unifying substitutions the most general one leaves every choice open that need not be settled, and every other unifier is an instance of it. Committing further than necessary would lose completeness by ruling out proofs. Variable counts, clause length and arbitrary unifiers are different notions. Making the weakest commitment that achieves the immediate objective is a principle that keeps a search from foreclosing options prematurely. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

31.

What is an interpretation in first order logic?

A.A translation of the sentence into natural language
B.An assignment of truth values to the atomic sentences
C.A domain together with meanings for the symbols
D.A proof that a sentence follows from the premises

Answer: C

An interpretation supplies a non-empty domain of objects and assigns each constant an object, each function symbol a mapping and each predicate a relation, and a sentence is then true or false in it. Truth value assignment is the propositional analogue and is insufficient here. Proofs and translations are different objects. Specifying meaning by fixing a domain and interpreting every symbol is what makes truth in first order logic precise. Checking the units of each quantity catches a wrong formula before the arithmetic begins.

Discuss in Forum

32.

Why must the domain of an interpretation be non-empty?

A.Otherwise the constants would have nothing to denote
B.Otherwise the logic would become decidable
C.Otherwise equality could not be interpreted at all
D.Otherwise a universally quantified sentence would be trivially true

Answer: D

Both reasons apply, but the convention is adopted chiefly so that from a universal statement an existential one may be inferred, which fails in an empty domain. Constants needing denotations is the other half of the same point. Decidability and equality are unaffected. A convention adopted to preserve a desired inference, rather than for any deep reason, is worth recognising as such since free logics that drop it exist and behave differently. The quantity that varies and the quantity that does not are worth naming before any substitution is attempted.

Discuss in Forum

33.

Why is first order entailment only semidecidable?

A.A proof will be found if one exists but not otherwise
B.The proof procedures available are all incomplete
C.The domain of an interpretation may be infinite
D.Quantifiers cannot be eliminated from a formula

Answer: A

A complete procedure will eventually derive any entailed sentence, but when the sentence is not entailed it may search forever without ever concluding that. That is the semidecidability result. Procedures are complete, and infinite domains and quantifiers are the reasons behind it rather than the statement. A guarantee that holds in one direction only is a genuine limitation rather than a defect of implementation, and no better algorithm will remove it.

Discuss in Forum

34.

What practical consequence follows from semidecidability?

A.Only propositional encodings may be used in practice
B.A prover may run indefinitely without reporting failure
C.No theorem in first order logic can ever be proved
D.Every first order question must be answered eventually somehow

Answer: B

A user who has waited an hour cannot tell whether the conjecture is false or the proof is merely long, which is why provers report timeouts rather than negative answers. Theorems are provable and questions are often answered, and propositional encodings are one response among several. Knowing that a negative result is unobtainable, rather than merely slow, changes how a tool's output must be interpreted.

Discuss in Forum

35.

What is the Herbrand universe of a set of clauses?

A.The domain of the intended interpretation of the clauses
B.The set of all atomic sentences appearing in the clauses
C.All ground terms built from its constants and function symbols
D.The set of all models satisfying the clauses

Answer: C

The Herbrand universe is the syntactic domain of all closed terms, and the Herbrand theorem shows that unsatisfiability may be established by considering only ground instances over it. That reduces first order refutation to a propositional question, though possibly an infinite one. Models, intended domains and atoms are different objects. Reducing a question about all interpretations to one about a single syntactic structure is what makes mechanical first order proof possible.

Discuss in Forum

36.

Why is the Herbrand theorem important for automated reasoning?

A.It shows that every first order sentence has a finite model
B.It provides a decision procedure for first order validity
C.It proves that resolution is complete for all logics
D.It reduces first order unsatisfiability to the propositional case

Answer: D

If a set of clauses is unsatisfiable, some finite set of ground instances is already unsatisfiable, so a prover may enumerate instances and use propositional methods. Finite models do not always exist, no decision procedure follows, and completeness of resolution is a separate result. Reducing an apparently infinite question to a finite one that can be found by enumeration is what turns semidecidability from an abstract statement into an actual algorithm.

Discuss in Forum

37.

What is skolemisation?

A.Replacing an existentially quantified variable by a new function
B.Removing all universal quantifiers from a formula
C.Converting a formula into conjunctive normal form
D.Renaming variables so that no two quantifiers share a name

Answer: A

Skolemisation replaces each existential variable by a term built from a fresh function symbol applied to the enclosing universal variables, which removes the existential quantifiers while preserving satisfiability. It is a step in converting to clausal form. Universal removal, normal form conversion and standardising apart are the neighbouring steps. Preserving satisfiability rather than equivalence is the subtlety, and it is exactly what a refutation procedure needs.

Discuss in Forum

38.

Why does skolemisation preserve satisfiability but not equivalence?

A.The new symbol may clash with one already in the formula
B.The new function symbol names a witness that the original merely asserted exists
C.The transformation removes information about the domain size
D.The resulting formula has more models than the original

Answer: B

Saying everyone has a mother becomes everyone has mother of themselves, which introduces a specific function the original did not mention, so the formulas are not equivalent though one is satisfiable exactly when the other is. Fresh symbols avoid clashes by construction. Since refutation only asks about satisfiability, the weaker guarantee suffices. Knowing exactly which property a transformation preserves determines where it may legitimately be used.

Discuss in Forum

39.

What is unification?

A.Merging two knowledge bases into one single consistent whole
B.Replacing every variable in a formula by a constant
C.Finding a substitution making two expressions identical
D.Combining two clauses into a single longer clause

Answer: C

Unification computes the most general substitution that makes two atoms syntactically the same, and it is what allows resolution to apply to first order clauses without enumerating ground instances. Clause combination is resolution itself, and the other options describe different operations. Working with variables directly, rather than instantiating them, is what makes first order proof tractable, and unification is the mechanism. The shared properties explain why these belong to one family, and the differences explain why more than one exists.

Discuss in Forum

40.

What is the most general unifier?

A.The substitution replacing the largest number of variables
B.The substitution that produces the shortest resulting clause
C.Any substitution that makes the two expressions identical
D.The substitution making the fewest commitments necessary

Answer: D

Among all unifying substitutions the most general one leaves every choice open that need not be settled, and every other unifier is an instance of it. Committing further than necessary would lose completeness by ruling out proofs. Variable counts, clause length and arbitrary unifiers are different notions. Making the weakest commitment that achieves the immediate objective is a principle that keeps a search from foreclosing options prematurely. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

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