Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [satisfiability]

For questions on the subject of "satisfiability", that is, whether there exists an interpretation/model in which a given (logical) formula is true.

A formula is valid if it is true for all values of its terms. Satisfiability refers to the existence of a combination of values to make the expression true. So in short, a proposition is satisfiable if there is at least one true result in its truth table, valid if all values it returns in the truth table are true .

332 questions
0
votes
0 answers

Satisfiability of a union of sets

I know this may be a very basic question but I'm new to some of these concepts and I would just like to make sure I understand the reasoning. The question is to say whether the following statement is true or false. If it is true, establish that it…
DiscipleOfKant
  • 313
0
votes
2 answers

[logic]Give sample of 3-element set M so that M is not satisfiable, but every 2-element subset of M is satisfiable.

This is the Exercise 7 in 《Logic for Computer Scientist》(Uwe Schoning) Exercise 7: Give an example of a 3-element set M so that M is not satisfiable, but every 2-element subset of M is satisfiable. Generalize your example to n-element sets. I am…
Keith
  • 165
0
votes
1 answer

Upper bounding randomized k-SAT solver

Problem: Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable. The issue is that…
ddnomad
  • 149
1
2