patternMinor
Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula
Viewed 0 times
booleanpolynomialdesignsatisfiabilitynormalalgorithmconjectiveforcomplexitydeciding
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#75324, answer score: 4
Revisions (0)
No revisions yet.