×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Jacey Olson

23

0

5

# TopComputer Sci & Engineering CSE 291

Jacey Olson

GPA 3.69

Sorin Lerner

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Sorin Lerner
TYPE
Class Notes
PAGES
5
WORDS
KARMA
25 ?

## Popular in Computer Science and Engineering

This 5 page Class Notes was uploaded by Jacey Olson on Thursday October 22, 2015. The Class Notes belongs to CSE 291 at University of California - San Diego taught by Sorin Lerner in Fall. Since its upload, it has received 23 views. For similar materials see /class/226786/cse-291-university-of-california-san-diego in Computer Science and Engineering at University of California - San Diego.

×

## Reviews for TopComputer Sci & Engineering

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15
Last time Main search strategy Crosscutting aspects Today Last time Main search strategy Crosscutting aspects 9quotth Today Search in the semantic domain Some definitions atomic formula smallest formula possible no sub formulas literal atomic formula or negation of an atomic formula clause disjunction of literals literal dauseAv s BVC D v B v E atomic CNF Conjunction of clauses DPLL backtracking search algorith DavidPuttnamLogemannLoveland Algorithm given a formula return SAT or UNSAT SAT there some truth assignment that makes the formula true UNSAT formula is false on all truth assignments Key idea Pick a litera Assign literal to true simplify the formula and recurse Assign literal to false simplify the formula and ecurse In more detail If formula is false return UNSAT else If formula istrue return SAT else Pick a literal Assign literal to true simplify the formula and recurse ll recursive call returns SAT return SAT Assign literal to false simplify the formula and recurse it recursive call returns SAT return SAT If both recursive calls return UNSAT return UNSAT Example simplification AV BVC Atotrue W DVBVE DVBVE aAvaaE XvaaE AV BVC Atolalse XV BVC DVBVE 4 DVBVE eAvaeE How do formulas become T or F Formula becomes true when conjunction becomes empty Formula becomes false when clause becomes empty Search tree WEE V V4 1 BA 15 quot VB P F Search tree Choice of literal matters Choice of literal matters Choice of literal matters Some heuristics for picking literal CEAWC A Pick literals that appear in unit clauses called mean unit propagation C 7 HAW c4 c4 AVaB 1 e 39u Aquot y 394 Plck lIterals that always appear In the same V quot f polarity A or a A 14 F F M y 7 Because olthelollowing 14 WV E optlr mzau onA h KA d an i ll l t l t l ml spiresWile p F p F ecvea r lilerallS AJhen plCK A don t explore A branch Some heuristics for picking literal Extending backtracking search Pick literals forwhich the formula can be expressed as R V A Q V a A S Can then merge both Let s assume we also have equality with uninterpreted function symbols for example ffa a V abfa subtrees into just one subtree that checks R V O S These are just a few simple heuristics Many other heuristics have been developed Decades of research on this a fa fb ffb Some observatio We can still simplify a formula based on a literal being T or F But we can only simplify that literal For instance in the example ab a ssumed a ow d false ove once we39ve 0 we know that a fa fb is Keep an environment Keep an environment EM 0quot Hunw AWMMQAV or Aerwlm VV g B avk or M 5 Vm A gt114 39 515 e K2 1 I l M39 Keep an environment ltttaavalttaawn CMquot agMattltb N A a 3914 55quot nu4a v a 1 Nquot V v F elmHa Keep an environment wan a v a ma b A ngbwa Hub bar I 15 11m In an I3 5 39 DavisPutnam paper Semialgorithm forfirstorder logic Refutation based negation formula and show that formula is unsatisfiable Uses successive SAT instances Prenex normal form Prenex normal form all quantifiers on the outslde Some example conversions Vx pm A Vx om m 90 an 3 xPx v 3 x 000 Bu 5 7 9 V 00 yx Px vvx Qx VLVY 96 v 47 In general can convert any formula into prenex normal form might possibly strengthen Getting rid of existentials Replace existential with a function symbol that takes as parameters the enclosing universally quantified variables Transform 5 Vxl 3 x2 Vx3 3 x4 Rxl X2X3X4 Into V x V x3 Rx f2xx3f4x X3 Herbrand s universe of a formula Given a formula F we call H the Herbrand universe of the formula All constants in F belong to H if F does not have constants then H includes a fresh constant a For any function symbol of arity n occurring in F and g belonging to H ft tquot also belongs to H H is the minimal set that satis es these constraints Quantifier free lines Quantifier free lines lnstantiate body of a formula F with elements of H Each quantifierfree line is implied by original F formula suppose F VX X2 Rb fx X2 As a result if the conjunction of some quantifier free lines is inconsistent so is the original HF l 3 fa ffa formu a Quantifierfree lines If the conjunction of the 39rstn quantifierfree We fa a lines is consistent for n then the original Y Y Eachlmelslmplied by formula is consistent Ra fa a or gma ormu a Follows from the fact that an in nite set of quantifier Rma Kan a jnf ufg g lzime free formulas is inconsistent iff some finite subset is quantifier iree lines is 39ncon5395t5nt inconsistent so is the original formula Example Example VX PXV3XPX VX PXV3XPX flaw 4 humor Th 9km Vx m 9KV79041l7 M hm WM V Hahn FR o SKVYJMA IPM 91123 V1 VIIA 391 1713 m in quot 0 9h 4 7 a ATP using Lazy Proof Explication ATP using Lazy Proof Explication 39 a b A a fa fb V b c A a fa fc a b A a fa fb V b c A a fa fc Ki x x A Assign proxies x X2VX3 x4 Use SAT solver if SAT solver says unsatisfiable then original formula is unsatisfiable

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over \$500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com