### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 601 at UMass(27)

### View Full Document

## 12

## 0

## Popular in Course

## Popular in Department

This 17 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 601 at UMass(27)

### What is Karma?

#### Karma is the currency of StudySoup.

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

Date Created: 02/06/15

CMPSCI 601 Recall From Last Time Lecture 10 Thm The following problems are in polynomial time EmptyNFA N 1 Nisan NFA N 1 2DFA D 1 DisaDFA D 2 MemberNFA Nw 1 Nis an NFA w E N EqualDFA 101021 1 13102 DFAs 101 1021 EmptyCFL G 1 GisaCFG 10 1 MemberCFL Gw 1 GisaCFG w E G Thm E CFL is coRE complete CMPSCI 601 Logic Lecture 10 We turn now to a unit on mathematical logic the study of how mathematicians do mathematics We model this process as a piece of mathematics itself de ning mathe matical entities such as propositions and proof systems and proving things about them Because our problems are so general and abstract it is of ten hard to see exactly what real problems we are dealing with Logic is important to computer science in two main ways 1 Because computers implement mathematicallyde ned rules the results of logic tell us things about com putability and complexity 2 The problems of logic themselves provide applica tions for computing CMPSCI 601 Boolean Logic Syntax Lecture 10 Boolean variables X x1x2x3 A boolean variable represents an atomic statement that may be either true or false Boolean expressions 0 atomic xi T l 0 a ea for a Boolean eXp s A literal is an atomic expression or its negation xi xi T l Abbreviations lt gt is an abbreviation for is an abbreviation for a 5 gt ba V W a gt 5 lt gt w v 5 CH gt5 gt a gt gta Examples of boolean expressions 0 x1 0 2 V 152 0 171 lt gt 82 a gtbb gtc gta gtc CS601CM730A Boolean Logic Semantics Lecture 8 Truth assignment T X g X gt true false Xltp EX xi occurs in cp If X cp g X then T is appropriate to p T assigns truth value to p TT Tk i T ltgt true Ta ltgt TizaorTiz Tiz a ltgt Tb a Lemma101 Ta8 ltgt TaandT8 Ta gt ltgt Tbv aorTiz Talt gt ltgt Tai T2 De nition 102 a and B are semantically equivalent a E 5 iff for all T appropriate to a and T l a ltgt 0931 E x1Vi a gta E T a H E b gt a a gtb avb ab E av b ab E aA b tavb E bVa 0avbc E aVbc taVbc E aVbac 0 E lla Proposition 103 Every boolean expression up is equiv alent to one in Conjunctive Normal Form CNF and to one in Disjunctl ve Normal Form DNF Proof DNF look at the truth table for p HHHHOOOOR HHOOHHOOQ z lt gt y 0 1 O 1 1 1 O O 1 1 O O O O 1 1 O O O 1 O 1 1 1 itAngz ityAi xAgjM atyAz CNF put ap in DNF Use De Morgan s law C 1vCk og Ck De nition 104 A boolean expression 0 is satis able iff there exists T p p is valid iff for all T appropriate to p T p Q Proposition 105 For any boolecm expression up 906 UNSAT ltgt we VALID UNSAT g VALID VALID g UNSAT I t Proposition 106 0 p is unsatis able i cp p is satis able i cp E L a pisvalidi cp E T Proposition 107 SAT 6 NP Proof 0 6 SAT ltgt ETXT i 90 Given ltpwith Xltp 21 52 x3 xn1 x Nondeterminsitically T 1 b2 b3 bn1 bn Accept iff T p CMPSCI 601 HornSAT Lecture 10 Horn formulas are CNF formulas with at most one posi tive literal per clause Compare to PROLOG not that I know anything about PROLOG l Vy 2 ngVi 3 lylt x RI 3 2l lt xyz 351 lt T Theorem 108 HORNSAT E P Algorithm 109 HORNSATltp l T D no variables assigned true 2 While T PE 0 3 choose clause lt al or not satis ed 4 T T U B 5 if i e T then reject else accept 10 CMPSCI 601 2SAT Lecture 10 2SAT 90 6 SAT p e CNF with two literals per clause p0 x1VT2x2VT3x3x1 Fact 1010 2SAT E P and infact 2SAT is complete for NSPACElog Given a 2CNF formula 0 de ne the directed graph f 90 V90 E90 as follows Vgo 58178717 axnvxin E90 uv a v or v 22 occurs in 90 Two bars cancel out so i u 90 E 2SAT ltgt Vx e Xltp x i not in same SCC SCC strongly connected component 11 90 E 2SAT ltgt Vx e Xltp x i not in same SCC There is a path from 1 to T so T must hold There is a path from 2 to Z so 3 must hold Either y or y may hold 0 E 2SAT 12 CMPSCI 601 Boolean Circuits Lecture 10 De nition 1011 A boolean circuit is a rooted directed acyclic graph DAG C V E 81quot 8 V gt truefalse V U 551x2 13 CMPSCI 601 CircuitSAT Lecture 10 Proposition 1012 CircuitSAT E NP 14 CMPSCI 601 CVP Lecture 10 Proposition 1013 Circuit Value Problem CVP E P 15 CMPSCI 601 Circuit Classes Lecture 10 Circuits give a lowlevel model of computation partic ularly of parallel computation since gates on the same level operate in parallel C 01 02 Cg a sequence of boolean circuits where On has inputs x1 x2 2 36 w 6 071 1 0120100 1 Circuits are a hardware implementation of straightline programs gate inputl gate input2 gate not gatel gatel and gate4 gate2 and gate3 6 l 2 3 gate 4 not gate2 5 6 7 gate5 or gate 16 Complexity Resources for Circuits 0 Size number of gates and Wires 0 Depth length of longest path from r to leaf 0 Uniformity complexity of f n r gt On We de ne classes based on these just as we de ned classes based on time and space for Turing machines We ll see much more about these classes later 17

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.