Propositional and First Order Logic Questions and Answers

Q: Why is consistency checking important in a large knowledge base?

One contradictory pair among a hundred thousand axioms silently licenses every conclusion, and the system continues to answer queries confidently. That is why description logic reasoners check consistency as a matter of course. Storage, query preconditions and termination are different concerns. A fault whose symptom is confident wrong answers rather than an error message is the most dangerous kind, and mechanical detection is the only reliable defence.

Q: What is a logical equivalence?

Equivalent sentences have identical truth in every model, so either may replace the other anywhere without changing what is entailed. Mutual derivability coincides with it in a sound and complete system. Symbol counts are irrelevant and the last option is far too weak. Equivalences such as De Morgan's laws and the distributive laws are the tools by which a formula is rewritten into normal form, so knowing them as equivalences rather than as inference rules is what licenses the rewriting.

Q: What do De Morgan's laws state?

The laws say that the negation of a conjunction is the disjunction of the negations, and dually, which is what drives negations inward during conversion to normal form. Distribution, double negation elimination and implication elimination are the other rewriting rules used in the same procedure. Having a named set of equivalences that between them suffice to reach a normal form is what makes the conversion a mechanical procedure rather than an art.

Q: Why is implication eliminated during conversion to clausal form?

A clause is a disjunction of literals, so every connective must first be rewritten in terms of negation, conjunction and disjunction, and the implication rewrite is the first step. Implication is perfectly truth functional and may be nested freely, and the rewrite generally leaves the size unchanged. Reducing a rich syntax to a minimal one, so that a single inference rule suffices, is the purpose of the whole conversion.

Q: What is the risk of converting a formula to conjunctive normal form naively?

Distributing disjunction over conjunction can square the size at each step, so a formula with nested alternations blows up exponentially. Introducing auxiliary variables gives a linear conversion that preserves satisfiability though not equivalence, which is what practical tools use. Equivalence is preserved by the naive method, termination is guaranteed, and new variables appear only in the improved method. Trading equivalence for satisfiability, to avoid an exponential, is a trade a refutation procedure can afford.

Q: What is the Tseitin transformation?

Naming each subformula with a new variable and asserting the equivalence gives a clause set linear in the original size, equisatisfiable though not equivalent. Every practical satisfiability tool uses it. Quantifier elimination, simplification and equivalence checking are different procedures. A transformation whose output is larger in variables but linear in clauses, and which preserves exactly the property being tested, is a good illustration of choosing the right notion of correctness.

Q: Consider the following statements about propositional logic. 1. A sentence is valid when it is true in every model 2. Premises entail a conclusion when their models include the conclusion's 3. A valid sentence carries information about which world we are in Which of the statements given above is or are correct?

The first two are correct. A valid sentence is true whatever the world is like, so it distinguishes nothing and carries no information. Only contingent sentences say anything about which world obtains. The three statements together cover validity, entailment and informativeness, and the third inverts the relationship between logical strength and empirical content in a way worth being clear about.

Q: Consider the following pairings in first order logic. Universal quantifier - naturally paired with implication Existential quantifier - naturally paired with conjunction Function symbol - denotes an object Predicate symbol - denotes an object How many of the pairs given above are correctly matched?

The first three are correct. A predicate denotes a relation and yields a truth value, whereas a function denotes an object and may appear wherever a term is expected. The distinction determines where each may legally appear in a formula, and confusing them produces expressions that are not well formed at all rather than merely false, which is at least an error that a parser will catch.

51.

Why is consistency checking important in a large knowledge base?

A.Consistency is required before any query may be answered
B.An inconsistency prevents the reasoner from terminating
C.An inconsistency makes every conclusion derivable and worthless
D.Inconsistent knowledge bases cannot be stored efficiently

Answer: C

One contradictory pair among a hundred thousand axioms silently licenses every conclusion, and the system continues to answer queries confidently. That is why description logic reasoners check consistency as a matter of course. Storage, query preconditions and termination are different concerns. A fault whose symptom is confident wrong answers rather than an error message is the most dangerous kind, and mechanical detection is the only reliable defence.

Discuss in Forum

52.

What is a logical equivalence?

A.Two sentences that can be derived from one another
B.Two sentences with the same number of symbols
C.Two sentences that are both valid or both unsatisfiable
D.Two sentences true in exactly the same models

Answer: D

Equivalent sentences have identical truth in every model, so either may replace the other anywhere without changing what is entailed. Mutual derivability coincides with it in a sound and complete system. Symbol counts are irrelevant and the last option is far too weak. Equivalences such as De Morgan's laws and the distributive laws are the tools by which a formula is rewritten into normal form, so knowing them as equivalences rather than as inference rules is what licenses the rewriting.

Discuss in Forum

53.

What do De Morgan's laws state?

A.Negation converts conjunction into disjunction and the reverse
B.Conjunction distributes over disjunction and the reverse
C.Double negation may always be eliminated from a formula
D.Implication may be rewritten using negation and disjunction

Answer: A

The laws say that the negation of a conjunction is the disjunction of the negations, and dually, which is what drives negations inward during conversion to normal form. Distribution, double negation elimination and implication elimination are the other rewriting rules used in the same procedure. Having a named set of equivalences that between them suffice to reach a normal form is what makes the conversion a mechanical procedure rather than an art.

Discuss in Forum

54.

Why is implication eliminated during conversion to clausal form?

A.The elimination reduces the size of the formula
B.Clauses are built from disjunction and negation only
C.Implication has no truth table in propositional logic
D.Implication cannot be nested inside other connectives

Answer: B

A clause is a disjunction of literals, so every connective must first be rewritten in terms of negation, conjunction and disjunction, and the implication rewrite is the first step. Implication is perfectly truth functional and may be nested freely, and the rewrite generally leaves the size unchanged. Reducing a rich syntax to a minimal one, so that a single inference rule suffices, is the purpose of the whole conversion.

Discuss in Forum

55.

What is the risk of converting a formula to conjunctive normal form naively?

A.The result may contain variables not in the original
B.The conversion may fail to terminate on some inputs
C.The result may be exponentially larger than the original
D.The result may not be equivalent to the original formula

Answer: C

Distributing disjunction over conjunction can square the size at each step, so a formula with nested alternations blows up exponentially. Introducing auxiliary variables gives a linear conversion that preserves satisfiability though not equivalence, which is what practical tools use. Equivalence is preserved by the naive method, termination is guaranteed, and new variables appear only in the improved method. Trading equivalence for satisfiability, to avoid an exponential, is a trade a refutation procedure can afford.

Discuss in Forum

56.

What is the Tseitin transformation?

A.A method of eliminating quantifiers from first order formulas
B.A technique for simplifying a formula before proving it
C.A procedure for checking whether two formulas are equivalent
D.A linear conversion to clausal form using auxiliary variables

Answer: D

Naming each subformula with a new variable and asserting the equivalence gives a clause set linear in the original size, equisatisfiable though not equivalent. Every practical satisfiability tool uses it. Quantifier elimination, simplification and equivalence checking are different procedures. A transformation whose output is larger in variables but linear in clauses, and which preserves exactly the property being tested, is a good illustration of choosing the right notion of correctness.

Discuss in Forum

57.

Consider the following statements about propositional logic.

1. A sentence is valid when it is true in every model

2. Premises entail a conclusion when their models include the conclusion's

3. A valid sentence carries information about which world we are in

Which of the statements given above is or are correct?

A.1 and 2 only
B.1 and 3 only
C.2 and 3 only
D.1, 2 and 3

Answer: A

The first two are correct. A valid sentence is true whatever the world is like, so it distinguishes nothing and carries no information. Only contingent sentences say anything about which world obtains. The three statements together cover validity, entailment and informativeness, and the third inverts the relationship between logical strength and empirical content in a way worth being clear about.

Discuss in Forum

58.

Match each semantic notion with its definition.

List I

A. Valid

B. Satisfiable

C. Unsatisfiable

D. Entailed

List II

P. true in every model

Q. true in at least one model

R. true in no model

S. true in every model of the premises

Select the correct match.

A.A-P, B-R, C-Q, D-S
B.A-P, B-Q, C-R, D-S
C.A-Q, B-P, C-S, D-R
D.A-R, B-S, C-P, D-Q

Answer: B

All four notions are defined by quantifying over models in different ways, which is why they are so easily confused and so easily distinguished once that pattern is noticed. Entailment is validity relative to a set of premises, and validity is entailment from no premises at all, which connects the two ends of the list.

Discuss in Forum

59.

Consider the following pairings in first order logic.

Universal quantifier - naturally paired with implication

Existential quantifier - naturally paired with conjunction

Function symbol - denotes an object

Predicate symbol - denotes an object

How many of the pairs given above are correctly matched?

A.Only two
B.All four
C.Only three
D.Only one

Answer: C

The first three are correct. A predicate denotes a relation and yields a truth value, whereas a function denotes an object and may appear wherever a term is expected. The distinction determines where each may legally appear in a formula, and confusing them produces expressions that are not well formed at all rather than merely false, which is at least an error that a parser will catch.

Discuss in Forum

60.

Three of the following are syntactic notions. Which is the odd one out?

Entailment

Conjunctive normal form

Literal

Clause

A.Conjunctive normal form
B.Literal
C.Clause
D.Entailment

Answer: D

Normal forms, literals and clauses are all defined by the shape of an expression and can be checked by inspection. Entailment is semantic, defined by quantifying over models, and cannot be read off the syntax. Keeping the syntactic and semantic vocabularies apart is what allows soundness and completeness to be stated as a relationship between them rather than as a tautology.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Propositional and First Order Logic Questions and Answers || Propositional and First Order Logic MCQ Questions and Answers || Propositional and First Order Logic GK Questions and Answers || Propositional and First Order Logic GK MCQ Questions || Propositional and First Order Logic Multiple Choice Questions and Answers || Propositional and First Order Logic GK || GK on Propositional and First Order Logic || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Propositional and First Order Logic Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications