The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

Not Decidable. Not even Semidecidable.

As Wikipedia states :

The question whether a sentence in propositional logic is satisfiable is a decidable problem. In general, the question whether sentences in first-order logic are satisfiable is not decidable.

Satisfiability in first-order logic is undecidable and indeed it isn't even a semidecidable property of formulae in first order logic (FOL).

I don't yet know the formal proof But In case you are interested in Proof then Refer here : http://kilby.stanford.edu/~rvg/154/handouts/fol.html

**Satisfiability in Propositional Logic :**

Satisfiability(SAT) is Standard NP-Complete Problem, Hence It is Decidable. Since, Every NP problem is Decidable. Actually, SAT is the first problem that was proven to be NP-Complete. Since, It is Decidable, It is Semi-decidable as well, Because Every Decidable problem is Semi-decidable.

More about SAT problem can be studied in Complexity Classes, which unfortunately is not in GATE syllabus. But worth learning for Knowledge' sake.(Or After GATE you can learn about it)

The **Boolean satisfiability problem** (sometimes called **propositional satisfiability problem** and abbreviated as **SATISFIABILITY** or **SAT**) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to True. If this is the case, the formula is called *satisfiable*. On the other hand, if no such assignment exists, the function expressed by the formula is False for all possible variable assignments and the formula is *unsatisfiable*.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,610 answers

132,247 comments

49,238 users