A clause is a Boolean expression of containing only ORs of Boolean variables or

Question

A clause is a Boolean expression of containing only ORs of Boolean variables or of their negation: C=a_1 logicalo a_2 logicalor ... logicalor a_h, where a_i is either a Boolean variable or its complement. A truth assignment assigns a true or false value to Boolean variables. A truth assignment satisfies a clause if the clause is true under that truth assignment. a. Give a clause and a truth assignment that makes the clause true. b. Give a truth assignment that makes the same clause false. c. Give a set of clauses not all of which can be simultaneously satisfied by a truth assignment. d. Describe an approximation algorithm that given p clauses produces a truth assignment that satisfies at least half of them.

Explanation / Answer

a)So we consider the truth assignment i as below.

pi = 1
qi = 0
ri = 1

we can see that i satisfies (p q) (¬q r).

(p q) (¬ q r)
(1 0) (¬ 0 1)
1 (¬ 0 1)
1 (1 1)
1 1
1

b) Lets make it false:

Now consider truth assignment j defined as follows.

pj = 0
qj = 1
rj = 0

In this case, j does not satisfy (p q) (¬q r).

(p q) (¬q r)
(0 1) (¬1 0)
1 (¬1 0)
1 (0 0)
1 0
0

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.