Question

Incorrect Question 10 0/5 pts Which of the following proposition is false? (A) To prove that a formula F in First-Order Logic (FOL) is a valid formula, is sufficient to prove that the formula -F is a contradiction. (B) To prove that a logical consequence F=G where F and G are formulas in FOL is valid, is sufficient to prove that the formula FA-G is a contradiction. (C) The SAT-problem in First Order Logic is a NP-complete problem. (D) Let F be a closed formula in Skolem form. F is a contradiction if and only if is possible to obtain the empty clause in the resolution process. (A) (B) (C) (D)

Answer 1

The false Option has to be marked here.

Option A: It says, to prove that a formula F in First-Order Logic (FOL) is a valid formula, is sufficient to prove that the formula ~F is a contradiction.

In this method first ~F is assumed to be TRUE and then it is proved as FALSE, which indicates the assumption is wrong. This method is known as proof by contradiction. Sometimes, this may not be sufficient to proof any logic. This is valid in some specific cases, for example:

• Set of two or more mutually exclusive propositions.
• No other possible equivalent proposition and so on.

Thus, it cannot be said that proof by contradiction is sufficient to prove a formula F. Thus, this option is FALSE. So this is the correct answer.

Option B: It says to prove that a logical consequence F->G where F and G are formulas in FOL is valid, is sufficient to prove that the formula F∧~G is a contradiction.

Here, the logical notation says F implies G or F->G, where F and G are valid. It means if F is true, G is also true. The truth table of F->G is given below.

F T T G T F T F F->G T F F T F T

Now, F->G is just opposite to the propositional logic F∧~G. It can be proved using truth table too. The truth table of F∧~G is shown below:

G G T F T T F F F T FAG F T F F T F F T F

For every pair of values of F and G, the two given logics contradict. So F->G can be proved if we can show that ~(F∧~G) is true. In other words, F->G is sufficient to prove that F∧~G is contradiction.

Thus, this option is TRUE. It is an incorrect answer.

Option C: It says that the SAT-problem in first order logic is NP-complete problem.

A SAT problem is a satisfiability problem that tries to determine an interpretation for a boolean expression. All SAT problem (first order logic also) are NP- complete. Thus, this option is also TRUE. So this option is incorrect answer.

Option D: It says, let F be a closed formula in Skolem form. F is a contradiction if and only if is possible to obtain the empty clause in the resolution process.

In skolem form, if F is a contradiction, only empty clause will be found. Thus this option is also TRUE. So this option is incorrect answer.

Thus the correct answer is Option A.