3
$\begingroup$

I undetstand each part of the word group in this question. I have search for a while but I still can't understand what the whole question want me to do. I will state what I know and give an assumption of what I should do, I would be appreciate if someone can guide me.

First a boolean formula is satisfiable if it can be made TRUE by assigning appropriate logical values, so "deciding the satisfiability" means to decide whether this boolean formula can be made a TRUE result.

Then for conjunctive normal form is means a conjunctive of clauses which are disjunctive inside. and 1-conjunctive normal form means each clause contains one variable, such like A\wedge B.

Now is the problem, what means an algorithm to decide it? I mean isn't the way to decide the satifiability of a boolean formula is try ture and false assiagnments to find whether it can be TRUE as a result? For example: since it is conjunctive normal form so each result of clauses needs to be TRUE, and it is 1-conjunctive normal form, so each variables need to be TRUE. Is this one an accpaptable algorithm to deal with the question?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Most satisfiability algorithms do actually find an assignment for the variables to satisfy the equation, but in your case (a conjunction of single variables) this is not necessary.

When the entire logic formula is just a single conjunction of variables, the only way it is not satisfiable is if it contains both $a$ and $\neg a$. If there is no variable which is contained both positive and negatively in the formula, the formula is satisfiable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Only if a 1-cnf formula contains both a and not ¬a, it must be false as result, otherwise, the fomula has the possibility to be TRUE so it is satisfiable. Thank you so much, but on the other hand, can I just write this sentence as an algorithm to decide the satisfiability of 1-cnf? $\endgroup$
    – darknessor
    May 13, 2017 at 12:18
  • $\begingroup$ @darknessor That depends on the standards of rigour of your professor, so I can't answer that. $\endgroup$
    – orlp
    May 13, 2017 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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