Propositional and First Order Logic Questions and Answers

Answer: A

Both are true and the second is the commonest specific reason. Using conjunction with a universal quantifier claims everything is of the kind concerned, and implication with an existential is satisfied vacuously by anything outside it, and both mistakes produce formulas that read plausibly. Checking what a candidate formula actually says, by looking for a model that satisfies it unintentionally, is the reliable defence.

Answer: B

An atomic sentence applies a predicate to the right number of terms and is the smallest expression having a truth value, so everything else is built from atoms by connectives and quantifiers. Quantifier free sentences may still be compound, terms have no truth value at all, and unstructured symbols belong to propositional logic. Identifying the smallest unit that can be true or false is what organises the syntax of any logic into levels. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Answer: C

Ground terms are built from constants and function symbols alone, so they denote a definite object in every interpretation without any variable assignment. The Herbrand universe consists of exactly these. Physical reference, parse position and assignment are different notions. Distinguishing expressions whose meaning depends on a variable assignment from those whose does not is what makes the semantics of quantification statable. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Answer: D

A sentence has every variable bound by a quantifier, so it has a truth value in an interpretation without any further assignment. A formula with a free variable is true or false only relative to an assignment to that variable. Quantifier presence, provability and notation are different matters. Being precise about which expressions have truth values on their own is what allows entailment to be defined without ambiguity.

Answer: A

A bound variable is a placeholder whose name is irrelevant, so renaming it consistently changes nothing, whereas a free variable's name matters because an assignment refers to it. Assignment, repetition and renaming sensitivity are different notions, the last being the opposite of the truth. That the name of a bound variable carries no information is what licenses the standardising apart step in clausal conversion.

Answer: B

Since each clause is implicitly universally quantified on its own, a variable in one has nothing to do with a variable of the same name in another, and unifying them would be an error. Renaming apart makes that explicit. Resolution handles variables by unification, clause counts are unchanged, and the occurs check is a separate safeguard. A step that exists purely to prevent an accidental name collision is easy to omit and produces wrong proofs when it is.

Answer: C

A clause with a variable asserts that the disjunction holds however the variable is instantiated, which is why unification may instantiate it as convenient during a proof. Truth in every model is validity, replacement is what unification performs, and clauses may be used repeatedly, which is essential. Recognising the implicit quantification is what makes clausal form intelligible rather than a mysterious list of disjunctions.

Answer: D

Because the clause holds for every instantiation, distinct instances may be used at different points in the same derivation, with fresh variables each time. That is exactly why standardising apart must be repeated per use rather than done once. Caching, literal consumption and copying are implementation matters. A premise that is a universally quantified statement is an inexhaustible resource, which is a genuine difference from a propositional premise.

Answer: A

Scope is a syntactic matter fixed by the brackets, and a variable occurring outside the scope of its quantifier is free rather than bound. The range of objects is the domain, which is a semantic notion, and a quantifier introduces exactly one variable. Getting the scope wrong changes the meaning entirely, which is why formulas are written with explicit brackets even when convention would permit them to be dropped, and it is a discipline worth keeping.

Answer: B

Not everything is F means something is not F, and not something is F means everything is not F, so pushing a negation through a quantifier exchanges the two quantifiers. That is the quantifier form of De Morgan's laws and it is what drives negations inward during clausal conversion. Commuting freely, disappearing and being restricted to atoms are all false. A rewriting rule that exchanges one operator for another, rather than merely moving it, is worth stating carefully because the exchange is easy to forget.