Propositional and First Order Logic Questions and Answers

Answer: A

A model fixes a truth value for each symbol, and a sentence is true or false in each model, so all the semantic notions are defined by quantifying over models. Sentences true in every model are valid, proofs are syntactic objects, and the physical system is what the logic is about rather than part of it. Defining meaning by reference to a set of possible worlds is what makes entailment a precise relation rather than an intuition. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.

Answer: B

Entailment is a semantic relation defined by model containment: every model of the premises is a model of the conclusion. Derivability is the corresponding syntactic notion, and the two coincide only when the proof system is sound and complete. Assertion context and symbol vocabulary are unrelated. Keeping the semantic and syntactic relations distinct, and then proving them equivalent, is the structure of every result about a logic. Most errors here come from carrying a result across from a neighbouring case where it does not hold.

Answer: C

A valid sentence, or tautology, is true whatever the symbols are assigned, so it carries no information about the world. Truth in some model is satisfiability, entailment is relative to premises, and connective count is a syntactic property. Validity, satisfiability and entailment are three notions defined by quantifying over models in three different ways, and confusing them is the commonest error in a first encounter with the semantics. Framing the question as which quantity the change acts upon makes the answer follow without calculation.

Answer: D

Satisfiability requires only that some assignment makes the sentence true, which is a far weaker demand than validity. A sentence is valid exactly when its negation is unsatisfiable, which is the relationship every proof by refutation exploits. Derivability from nothing is validity in a complete system, and the negation of a satisfiable sentence may or may not be satisfiable. The three notions are connected by negation, and knowing the connections converts one question into another that may be easier.

Answer: A

The refutation identity turns every entailment question into a satisfiability question, which is why resolution proves theorems by deriving a contradiction from the premises together with the negated goal. Joint satisfiability is a much weaker condition, and the conclusion's own satisfiability says nothing. Converting a question about all models into a question about the existence of one is what makes automated theorem proving practical. The shared properties explain why these belong to one family, and the differences explain why more than one exists.

Answer: B

Each symbol takes two values independently, so the count is:

\[ 2^{4} = 16 \]

giving 16 rows. Twenty symbols would give over a million and thirty over a billion, which is why truth tables are a definition rather than an algorithm. That the semantics is defined by an exponentially large object, while practical reasoning must avoid constructing it, is the tension every inference procedure addresses.

Answer: C

With two to the n models, a problem with fifty symbols has more rows than could be enumerated in the age of the universe, so satisfiability solvers search cleverly instead. Implication and negation are handled correctly, and the absence of a proof is a separate objection. A definition that is exponentially large, and an algorithm that must avoid materialising it, is the shape of the whole subject of automated reasoning.

Answer: D

CNF writes a sentence as a set of clauses, each a disjunction of literals, all of which must hold, and every propositional sentence has an equivalent in this form. Resolution and satisfiability solvers both require it. The disjunctive form is the dual, and the other options describe different restrictions. Converting to a canonical form so that a single uniform inference rule applies is the standard preparation for mechanical reasoning. Naming the cost of a choice alongside its benefit is what turns a fact into a design decision.

Answer: A

With everything reduced to clauses, unit propagation and resolution apply uniformly and no special cases are needed for the connectives. The conversion may increase size, exponentially in the worst case unless auxiliary variables are introduced. Satisfiability is preserved rather than created, and negations remain on literals. Standardising the input so that one rule suffices, even at some cost in size, is a trade that mechanical procedures repeatedly make.

Answer: B

Literals are the atoms from which clauses are built, being either a symbol or a negated symbol. A clause is a disjunction of them and a unit clause contains exactly one. Constant symbols belong to first order syntax. Precise vocabulary for the levels of structure, atom, literal, clause and formula, is what allows an algorithm to be described unambiguously.