Propositional and First Order Logic Questions and Answers

Answer: C

Denying a universal claim requires only a single counterexample, so the negation is that some student failed, not that all did. The stronger claim that none passed would be the negation of some student passed. Confusing the contrary with the contradictory is among the oldest and commonest errors in reasoning, and writing both in symbols settles it immediately, which is part of what a formal notation is for.

Answer: D

Denying an existential claim requires that no instance exists at all, so the negation is that every student failed. The second and third options are the negation of the universal claim rather than of this one. Working through the four combinations of quantifier and negation once, and writing each in symbols, converts a persistent source of confusion into a mechanical rewriting rule that can be applied without thought.

Answer: A

Since everything is F is equivalent to not something is not F, one quantifier suffices and the other is an abbreviation. Minimal presentations of the logic exploit this. Independence, special cases and mutual necessity are all false. That an apparently primitive notion turns out to be definable from another is worth knowing both for economy of presentation and because it explains why the two behave as dual to one another under negation. A limit that survives making every external component ideal is an intrinsic one, and worth knowing for that reason.

Answer: B

A proof by induction over the structure of formulas needs one case per connective, so taking negation and disjunction as primitive and defining the rest makes every such proof shorter. Formulas themselves become longer rather than shorter. Consistency and truth functionality are unaffected. Reducing the primitives so that metatheoretical proofs are tractable, while retaining the full syntax as abbreviation, is a standard division between a logic's presentation and its use.

Answer: C

Hardware verification, planning to a fixed horizon and scheduling are routinely encoded into propositional satisfiability and solved by tools handling millions of clauses. The reduction from first order requires bounding the domain and loses generality. Sound inference exists for richer logics, and semantics is required. That a weaker logic with extraordinary tools often beats a stronger one with weaker tools is a consideration expressiveness comparisons alone would miss entirely.

Answer: D

Grounding a first order theory requires enumerating the objects, so the domain must be finite and known, and the number of clauses grows rapidly with it. Planning encodings bound the horizon for exactly this reason. Negation is handled correctly, satisfiability is the question being asked, and no world assumption is required. Knowing precisely which generality is surrendered by an encoding is what determines whether the encoding answers the question actually being asked.

Answer: A

Higher order logic quantifies over relations as well as objects, so a statement such as there is a property shared by these two things becomes expressible. It is far more expressive and has no complete proof procedure, so most work stays first order and encodes what it can. Truth values, nesting and metatheory are different notions. Each step up in what may be quantified over buys expressiveness and costs a metatheoretical guarantee, which is the same trade seen throughout.

Answer: B

Completeness means every entailed sentence is provable, which higher order logic lacks under the standard semantics, so automated support is far weaker there. Higher order logic is strictly more expressive and perfectly writable, and neither is decidable. Choosing the formalism for which mechanical support exists, rather than the most expressive available, is the same reasoning that produced description logics at the other end of the scale.

Answer: C

The knowledge base holds the sentences the agent has been told or has inferred, and the inference procedure answers questions against it. The language's sentences are the possibilities rather than the contents, procedures are separate, and percepts are one source among several. Separating what is believed from how conclusions are drawn is what allows a general reasoner to serve any domain, which is the founding architecture of the knowledge based approach.

Answer: D

A knowledge based agent tells the base what it perceives and asks what it should do, and everything else is internal to the inference procedure. Retraction is needed in non-monotonic settings and is a genuine extension. Database style insertion and encoding are different operations. Reducing an interface to two operations, one for adding and one for querying, is what makes the knowledge base a component rather than an architecture.