Homework Help is Here – Start Your Trial Now!
Engineering
AI and Machine Learning
X1 X2 X3 y 1 1 1 + 001+ 0 1 1 01 0 10 100 +++

X1 X2 X3 y 1 1 1 + 001+ 0 1 1 01 0 10 100 +++

icon
Related questions
Question

Definition of 3SAT : In the 3SAT problem, the input is a Boolean expression formed by m clause and n variables (each variable x can have a positive literal x and negative literal x). Each clause formed by disjunction of three
literals and the formula is formed by the conjunction of the m clauses. For example, the following formula
is an instance of the 3SAT problem: (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3), which is formed by 3 variables x1, x2, x3 and three clauses. The objective is to find an assignment of Boolean values to variables to satisfy the formula. In the example above, one possible satisfying assignment is to let x1 to be false and x2, x3 to be true. 

Problem : 
A 2SAT formula is a conjunction of clauses like a 3SAT formula, except that each clause is a disjunction of 2 literals (rather than 3). For example (x1 ∨ x2) ∧ (x2 ∨ x3) ∧ (x3 ∨ x1) is a 2SAT formula.Use consistency model to provide a 2SAT formula consistent with the following labelled data (or specify
that there is no such consistent formula). Show your work.

X1 X2 X3 y 1 1 1 + 001+ 0 1 1 01 0 10 100 +++
Transcribed Image Text:X1 X2 X3 y 1 1 1 + 001+ 0 1 1 01 0 10 100 +++
Expert Solution
steps

Step by step

Solved in 2 steps with 3 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer