satisfiabilitypropositional-calculus

Is satisfiability related to a set of sentences of a single sentence?


While going through online resources, I have noticed that satisfiability is taken differently.

Sometimes resources ask for showing that a given proposition is satisfiable or not?

However, sometimes they ask for showing that a set of propositions is satisfiable or not?

I am confused as to what exactly does satisfiability relate to. Does it have to do something with a single proposition or with a set of propositions?


Solution

  • Both make sense.

    In general, when you have a set of propositions and ask for satisfiability, you are asking if there is a satisfying assignment that makes all of those propositions true at the same time. So, you can consider a single proposition as a singleton set, in which case its satisfiability is the same as the satisfiability of a set of propositions which happens to have only one element.

    Aside: When you talk about a set of propositions one should be clear about the possibility of an empty set. Is the empty set of propositions satisfiable? The answer is simple: Yes, trivially. Any assignment satisfies an empty set of propositions. This is akin to True being the identity element for boolean conjunction.

    Note

    As noted by @Tim in the comments, the other direction is to consider what happens if the set is infinite. How is satisfiability defined then? In this case we allude to compactness (https://en.wikipedia.org/wiki/Compactness_theorem), which states an infinite set of propositions is satisfiable if all finite subsets are. The details are probably beyond the OP's intent though, so leaving that for a different question.

    Note that in most practical applications in SAT and SMT-solvers, you need not worry about the infinite case unless you have quantifiers. So long as you stick to quantifier-free subsets, everything is finite.