Propositional and First Order Logic Questions and Answers

Answer: C

Truth functionality means a connective's behaviour is fully described by a table, so no further information about the parts is needed. Natural language connectives such as because are not truth functional, which is one reason translating English into logic loses content. Return types, applicability and evaluation cost are different matters. A property that makes a complete tabular semantics possible is what separates the connectives of logic from those of ordinary speech.

Answer: D

If the moon is made of cheese then two plus two is five counts as true, because a false antecedent makes the material conditional true whatever the consequent says. Everyday conditionals carry a suggestion of relevance the truth table cannot express. Truth tables exist, the direction is preserved, and the last option describes conjunction. Knowing exactly where a formalisation departs from the idiom it renders is what allows the departure to be lived with rather than stumbled over.

Answer: A

A rule whose conditions are never satisfied is trivially true and contributes nothing, which is why an existential claim written with implication says almost nothing. It is the same phenomenon as a universal restriction satisfied by an individual with no such role. Conditionals are essential, converses are separate claims, and conjunction changes the meaning. One phenomenon appearing in three different formalisms, each time catching people out, is worth recognising once and for all.

Answer: B

Well formedness is purely syntactic, decided by whether the expression can be built from atoms by the formation rules, and it says nothing about truth. Sentences are the well formed formulas without free variables, and normal forms are particular shapes. Truth and provability are semantic and proof theoretic notions respectively. Being able to say whether an expression is even a candidate for having a truth value is the first thing a syntax must settle.

Answer: C

Arity fixes how many terms the predicate must be applied to, and applying it to the wrong number gives an expression that is not well formed. A unary predicate expresses a property and a binary one a relation. Frequency, model counts and domain size are different quantities. Declaring the arity of each symbol is part of specifying the language, and it is what allows syntactic errors to be caught before any reasoning is attempted.

Answer: D

A unary predicate such as Student applies to one term and asserts that the object it denotes has that property, corresponding to a category in an ontology. Binary predicates express relations, functions denote objects rather than asserting, and zero arity gives a proposition symbol. Recognising unary predicates as the logical form of categories connects first order logic to the taxonomies of the previous topic directly.

Answer: A

The straightforward rendering makes a category a unary predicate, though reifying it as an object with a membership relation is also common when properties of the category itself must be stated. Both appear in practice and the choice depends on whether the category must be quantified over. Function symbols and bare constants are less convenient. Two legitimate renderings of the same notion, suiting different needs, is a modelling choice rather than a matter of correctness.

Answer: B

Saying that the category of dogs is popular, or has many members, requires the category to be an object that a predicate can be applied to, which a unary predicate cannot be in first order logic. Member counts and axiom usage are irrelevant. Nested categories are one situation where it helps but not the general criterion. Needing to say something about a predicate, rather than with it, is exactly the circumstance in which reification becomes necessary.

Answer: C

Looking for an unintended model, such as a domain of stones satisfying a badly written existential, catches both classic quantifier errors immediately. Brevity, word order and quantifier economy are poor guides and the second two actively mislead, since English word order does not track scope. Testing a candidate formula against a deliberately awkward interpretation is the same technique used to check any specification, and it is more reliable than reading the formula back.

Answer: D

Someone who knows what the formula was meant to say will read it that way, and the unintended reading remains invisible, which is why constructing a counter-model is the better check. English does render the connectives, if imperfectly, and the direction of translation is not the difficulty. That a check performed by the author of the artefact is compromised by the author's own intention is a general problem, and the answer is always to seek an independent test.