0
$\begingroup$

I need to proof that if formula F in CNF form is satisfiable, then any subset of CNF which belongs to F must be satisfiable. I know that CNF is basically conjuncted sets of disjunctions so from definition it is kind of obvious that if whole formula in CNF is satisfiable, then any subset will definitely be satisfiable as well because any subset will have an interpretation which will be True. However, I am not sure how to start to proof it formally.

$\endgroup$
0
$\begingroup$

Yeah, it is kind of obvious ... to make it hard, I would say: if $F$ is satisfiable, then that means that there is some truth-value assignment that sets all of the conjuncts of its CNF to true. So, that verysame truth-value assignment will certainly set any subset of those conjuncts to true, meaning that that set is satisfiable.

$\endgroup$
  • $\begingroup$ Is there any way to show that subset is satisfiable via induction or other way but more formally? $\endgroup$ – Augustas Feb 6 '19 at 0:09
  • 1
    $\begingroup$ @Augustas Not sure how induction would help with this .... I think what I wrote is a perfectly acceptable proof. Maybe if the porblem statement was given more formally itself, but it isn't so I think this is the 'appropriate' level of detail. $\endgroup$ – Bram28 Feb 6 '19 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.