Alpha Geek

(8)

$10/per page/Negotiable

About Alpha Geek

Levels Tought:
University

Expertise:
Accounting,Algebra See all
Accounting,Algebra,Architecture and Design,Art & Design,Biology,Business & Finance,Calculus,Chemistry,Communications,Computer Science,Environmental science,Essay writing,Programming,Social Science,Statistics Hide all
Teaching Since: Apr 2017
Last Sign in: 346 Weeks Ago, 6 Days Ago
Questions Answered: 9562
Tutorials Posted: 9559

Education

  • bachelor in business administration
    Polytechnic State University Sanluis
    Jan-2006 - Nov-2010

  • CPA
    Polytechnic State University
    Jan-2012 - Nov-2016

Experience

  • Professor
    Harvard Square Academy (HS2)
    Mar-2012 - Present

Category > Math Posted 07 May 2017 My Price 5.00

This problem investigates resolution a method for proving

This problem investigates resolution, a method for proving the unsatisfiability of cnf-formulas. Let φ = C1 ∧ C2 ∧ • • • ∧ Cm be a formula in cnf, where the Ci are its clauses. Let C = {Ci| Ci is a clause of φ}. In a resolution step, we take two clauses Ca and Cb in C, which both have some variable x occurring positively in one of the clauses and negatively in the other. Thus, Ca = (x ∨ y1 ∨ y2 ∨ • • • ∨ yk) and Cb = (x ∨ z1 ∨ z2 ∨ • • • ∨ zl), where the yi and zi are literals. We form the new clause (y1 ∨ y2 ∨ • • • ∨ yk ∨ z1 ∨ z2 ∨ • • • ∨ zl) and remove repeated literals. Add this new clause to C. Repeat the resolution steps until no additional clauses can be obtained. If the empty clause ( ) is in C, then declare φ unsatisfiable. Say that resolution is sound if it never declares satisfiable formulas to be unsatisfi- able. Say that resolution is complete if all unsatisfiable formulas are declared to be unsatisfiable.

a. Show that resolution is sound and complete.

b. Use part (a) to show that 2SAT ∈ P.

 

Answers

Alpha Geek
(8)
Status NEW Posted 07 May 2017 04:05 PM My Price 5.00

-----------

Attachments

file 1494175777-Answer.docx preview (234 words )
T-----------his----------- pr-----------obl-----------em -----------inv-----------est-----------iga-----------tes----------- re-----------sol-----------uti-----------on,----------- a -----------met-----------hod----------- fo-----------r p-----------rov-----------ing----------- th-----------e u-----------nsa-----------tis-----------fia-----------bil-----------ity----------- of----------- cn-----------f-f-----------orm-----------ula-----------s. -----------Let----------- φ----------- = -----------C1Â----------- âˆ-----------§ C-----------2 -----------∧----------- ·----------- ·----------- ·----------- âˆ-----------§ C-----------m -----------be -----------a f-----------orm-----------ula----------- in----------- cn-----------f, -----------whe-----------re -----------the----------- Ci----------- a-----------re -----------its----------- cl-----------aus-----------es.----------- Le-----------t C----------- = -----------{Ci-----------| C-----------i -----------is -----------a c-----------lau-----------se -----------of -----------φ}-----------. I-----------n a----------- re-----------sol-----------uti-----------on -----------ste-----------p, -----------we -----------tak-----------e t-----------wo -----------cla-----------use-----------s C-----------a -----------and----------- Cb----------- i-----------n C-----------, w-----------hic-----------h b-----------oth----------- ha-----------ve -----------som-----------e v-----------ari-----------abl-----------e x----------- oc-----------cur-----------rin-----------g p-----------osi-----------tiv-----------ely----------- in----------- on-----------e o-----------f t-----------he -----------cla-----------use-----------s a-----------nd -----------neg-----------ati-----------vel-----------y i-----------n t-----------he -----------oth-----------er.----------- Th-----------us,----------- Ca----------- = -----------(x -----------∨----------- y1----------- â-----------ˆ¨ -----------y2Â----------- âˆ-----------¨ Â-----------·
Not Rated(0)