Practice Verification Of Cnf (3.8) - SAT Problem - Discrete Mathematics

Practise this section

10 questions

Flashcard drill
4 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
4 questions · about 3 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
Define the satisfiability problem.
Show hintHide hint
Focus on the meaning of 'satisfy'.
Question 2.
What is CNF?
Show hintHide hint
Recall how clauses are structured.
3Question 3.
What is a satisfiable proposition?
- Always false
- Always true
- True for at least one assignment
Show hintHide hint
Remember the definition of satisfiability.
4Question 4.
In CNF, what does each clause consist of?
- Conjunctions of literals
- Disjunctions of literals
- Tautologies
Show hintHide hint
Recall the structure of CNF.
Question 5.
Given the expression (p ↔ q) ∧ (¬q ∨ r), convert it to CNF and explain each step.
Show hintHide hint
Sequential transformations are hand in hand with logical identities.
Question 6.
Create an unsatisfiable proposition and explain why it cannot be satisfied.
Show hintHide hint
Review the properties of contradictions to guide your creation.

6 more questions in this section. Enroll free to practise them all.