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.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,157 questions

43,608 answers

123,961 comments

42,860 users