Propositional and First Order Logic Questions and Answers

Answer: A

Universal quantification says that the body holds whatever object the variable is taken to denote, and it is naturally combined with implication. Existential quantification claims one such object, and validity concerns models rather than objects. Distinguishing quantification over objects within a model from quantification over models is essential, since both appear in the semantics and confusing them makes the definitions incoherent. The quantity that varies and the quantity that does not are worth naming before any substitution is attempted.

Answer: B

Saying that all students are diligent is written as: for every object, if it is a student then it is diligent, since using conjunction would claim that every object in the domain is a student. That error is among the two commonest in translating English into logic. Disjunction and negation have their own uses. The pairing of universal with implication, and existential with conjunction, is worth learning as a rule because both errors produce formulas that look plausible.

Answer: C

Saying that some student is diligent is written as: there is an object which is a student and is diligent, since using implication would be satisfied by any object that is not a student at all. That is the second of the two classic translation errors. The pairing is not a convention but a consequence of what the quantifiers mean, and working through why the wrong connective gives an unintended reading is what fixes it in mind. Naming the cost of a choice alongside its benefit is what turns a fact into a design decision.

Answer: D

Writing for every x, x is a student and x is diligent asserts that everything whatever is a student, which is far stronger than intended. The third option describes the error made by using implication with the existential quantifier instead. Finiteness is irrelevant. Working out what the wrong formula actually says, rather than merely noting that it is wrong, is what prevents the error from recurring.

Answer: A

Writing there exists x such that x is a student implies x is diligent is made true by any object that is not a student, since a false antecedent makes the implication true, so the sentence says almost nothing. The formula is satisfied in a domain containing a single stone. Recognising vacuous satisfaction as the mechanism of the error connects it to the same phenomenon in universal restrictions in description logics.

Answer: B

There exists an x such that for all y, x loves y asserts that one particular individual loves everybody, whereas reversing the order says only that everybody is loved by someone or other. The two are quite different claims and only one implies the other. Quantifiers of different kinds do not commute, and remembering which direction the implication runs is worth more than remembering the rule that they differ.

Answer: C

If one individual loves everybody then certainly everybody is loved by someone, but the converse fails since each person might be loved by a different individual. The stronger claim implies the weaker. Working out which of two similar formulas is stronger, by finding a model of one that is not a model of the other, is the standard technique for settling such questions and it is more reliable than intuition.

Answer: D

Equality relates terms and asserts identity of the objects they denote, which is why it permits substitution and why counting statements can be written. Truth value equality is equivalence between formulas, indiscernibility is a consequence rather than the definition, and syntactic identity is a different relation entirely. Having identity available in the logic is what allows uniqueness and cardinality to be expressed at all. A limit that survives making every external component ideal is an intrinsic one, and worth knowing for that reason.

Answer: A

Uniqueness requires both existence and the statement that anything with the property is identical to the witness, which needs equality. The shorthand notation for unique existence abbreviates exactly this. The second option denies the existence of anything else at all, and the third is not well formed. Constructing a compound claim from existence plus a uniqueness clause is a pattern that recurs whenever counting is required.

Answer: B

Two existentially quantified variables may be satisfied by the same object unless their distinctness is asserted, so at least two requires an inequality. Nesting, reference and domain size are unaffected. That variables do not automatically denote different objects surprises most people learning the notation, and it is precisely why explicit inequalities litter formulas that count.