### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction to Discrete Systems CSE 2500

UCONN

GPA 3.73

### View Full Document

## 25

## 0

## Popular in Course

## Popular in Engineering Computer Science

This 7 page Class Notes was uploaded by Americo Huel on Thursday September 17, 2015. The Class Notes belongs to CSE 2500 at University of Connecticut taught by Chun-Hsi Huang in Fall. Since its upload, it has received 25 views. For similar materials see /class/205927/cse-2500-university-of-connecticut in Engineering Computer Science at University of Connecticut.

## Reviews for Introduction to Discrete Systems

### 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: 09/17/15

CSE 2500 Intro to Discrete Systems Logic Mathematical logic is a tool for dealing with formal reasoning In a nutshell ChunrHSl Vincent Huang Dept of Computer Science and En 39neering Logic does University of Connecticut 0 Assess If an argument Is valid nvalid Nutes 312 based untne buuk DlsEiEtE MathematicsMhAp llcalluns Thlid Euiiiun by Susanna am in cunsultatiun Mn Equivalent cuurses even at Diner unNersities lnE l u lsVlE the Unix MAle a V Eulitk the NEWmG Univeislv A Euknamvich as W a unlinematenalspvwidedbyEvuuksCule Logic does not directly a Assess the truth of atomic statements Logic Connectives 0 Logic can deduce that Storrs is in New England given these facts 0 Storrs is in Connecticut o Connecticut is a pan of New England V or Dif ferent notations have been in use We will use the common math notation and the de nitions of 39 A o to be a part or o gt Implies If then o to be in39 lt gt if and only if V for all 0 Logic does not knowconcern whether these atomic a 3 eXIsts statements actually hold true In real life See the reverse of the text s front cover Logical Statement Logical Statement 0 De nition P6 0 Alogical statement or proposition is either true or A statement form or propositional form is an falsei bUt quot0 bom expression made up of statement variables and 0 Atomic P Q X Y logical connectives that becomes a statement when 0 Negation P atcttial stattemen ls areTUbtstitteIforfthe component Commotive p A Q p A NQY s a emen varia es e ru a e or a given A statement form displays the truth values that Dlsjuncnve39 P V Q P V P Xquotquot correspond to all possible combinations of truth 39 conditional P 9 Q values for its component statement variables 0 Biconditional P H Q Order of Precedence Determining Truth Values highest Atomic statement given A Compound statement via meaning of u v the connectives a lt gt lowest Suppose P is true Q is false To avoid confusion use and HOW abOUt P V Q P quot Q V X 39 P Q VX Truth tables for P A Q P v Q P Conditionals Truth Table o Ifl go to Walmart tomorrow I will buy one pound of coffee therequot N Independent atomic variables a 2N rows combinations N20 220 1 million Consider A a B B S I go to Walmart gt I buy one pound of coffee 0 When is 8 true7 hen Iwent to Walmart and bought one pound of coffee a When II didn t go there at all c When is Sfals a When Iwent there but didn t buy one pound of coffee A B A T T F F 39I39I l39I39I l i in ii More Terminology BiConditionals A gt B 0 Michael will take CSE2500 if and only if Debra does soquot A is caed S Michael takes CSE2500 H Debra takes 0 Hypothesis CSE2500 or Antecedent When is S quotUS 0 When Michael takes it and Debra lakes ii u when Michael doesn39t take it and neither does Debra I BIS called 0 When isS else 0 Concluslon 0 When one onhem takes it but not the other o or Consequent Truth Table IA IT IT IF IF A n in im i n n i More on Conditional Statements I Suppose I B I39ll buy a Ferrariquot I S The Ferrari is on salequot I Iwill buy a Ferrari if it is on sale s a B I Iwill buy a Ferrari if and only if it is on sale a s H B I Iwill buy a Ferrari only if it is on sale Sufficient Necessary Conditions I Suppose X is a statement I A is a suf cient condition for X iffwe can prove that A implies Xquot I A is necessary condition for X iff we can prove that X implies Aquot I A is a criterion for X iff we can prove that X holds if and only ifA holdsquot Contradictions amp Tautologies I Contradiction O A statement that is always false regardless of the values of its variables Example A n I Tautology I A statement that is always true regardless of the values of its variables Example A v A Contingencies I What if I have a logical statement that is sometimes true and sometimes false I It is called a contingency I Example I Aquot B Wnere A and B are independent variables Interpretation I In propositional logic interpretation is an assignment of truth values of variables in the logical statement expression Example 0 Formula A v B I Interpretation A true B false Statement Classifications Tautology T o all interpretations satisfy the logical statement Contradiction C c all interpretations falsify the logical statement Contingency v some interpretations satisfy and some falsifythe logical statement ModelsCountermodels An interpretation is called a model for statemen i o It satis es F ie makes Ftrue An interpretation is called a countermodel for statement F if39f lt falsi es F ie makes Ffalse no on once Logical Equivalence 32 8339 Statements A and B are logically equivalent wh 39 en 0 A holds if and only if B holds Notation A E B Examples 0 Av A is equivalent to A o Av A is equivalent to T a tautology Equivalence amp Tautology Suppose A and B are logically equivalent Considerthe proposition A lt gt B What can we say about it n It is a tautology I VVhy A B Alt gtB T T T F F T More Equivalences Alex is not unemployed 0 Alexis employe n P E P Doublenegation It is not true that he is single and he is cute 0 He is not single or he is not cute A quot B E A v B De Morgan s law It is not true that he is single or he is cute o He is not single and he is not cute A v B E A quot B De Morgan s law Boolean Algebra Page 14 presents Theorem 111 with 11 logical equivalences Example Let s prove that P v C E P 4 P v c E PvPquotP by 5 E PVPquotPVP by3 2PVPquotT by5 EPVP by4 E P by 7 Proving Equivalences Suppose F and Q can take on T and F only Then all equivalences can be proven by definition using truth tables P Q P v Q P quot Q Another Example ProvePaQEPvQ Truth tables no on union Uses of Equivalences 32 Simplification Suppose someone gives you o PvAaBvCv DaHv PvX and asks you to compute it for all possible input values You can either immediately draw a truth table with 27 128 rows Or you can simplify it first Simplification PvAaBvCvDaHvPvX EPvPvAaBvCvDaHvX ETvAaBvCvDaHvX ET The statement is a tautology Test Drive Let s take our equivalence tool box for a spin What can we tell about 0 IX B and its contraposition A They are equivalent Proof By truthtable By logical equivalence IX B E Av B EBVA EBgtA Test Drive Let s try another one What can we tell about 0 Agt and its inverse v A gt B 7 They are not equivalent Countermodel A is false and B is true Summary Implication A gt B is equivalent to o B gt A its contraposition But is not equivalent to o Aa B its inverse Or to a B gt A its converse no on union Another Lesson Learned g Proving equivalences o viatruthtables o via other equivalences Proving nonequivalence 0 Finding an instantiation that makes one statement hold and the other doesn t Biconditionals How can we express 0 A lt gt B with A v 7 n It is simply AA B vAquot B How can we express it with a Why but of course it is just AaBquotBaA Another Spin Ok let s try this fun ride P a Q A P n In English it would sound If Pis true then Q is true and P Istrue What does it tell us One would intuitively thinks Q is true Let s provedisprove it Proving PHQAP EPVQquotP EPquotPVQquotP EFvQquotP EQAP ButwewantjustQnotQquotP IsQAPEQ No countermodel QT and PF What is the matter 0 Not all arguments have the form of a chain of equivalences 0 Example a PgtQ lfSocrates is human then Socrates is mortalquot o P Socrates is humanquot A conjunction ofthese two is NOT equivalent to Q Socrates is mortalquot Why a Name a dog Socrates It is mortal 0 holds But it is NOT human P does not hold Logical Argument o Acollection of statements P1 Pn premises logically implies entails statement Q conclusion if and only if Whenever all premises hold the conclusion holds 0 Example 0 Premises a P1 lfSocrates is human then Socrates is mortalquot a P2 Socrates is humanquot 0 Conclusion 0 Q Socrates is mortalquot ValidInvalid Arguments Suppose someone makes an argument 0 P1 PN therefore Q n The argument is called valid if39f 0 P1 PN logIcallyImply Q That is a Q must hold when all P hold Otherwise the argument is called invalid Relation to Tautologies c We already know that statements A and B are equivalent iff A H B is a tautology ie holds for any interpretation How about entailment Statement A entails logically implies statement Biff A a B is a tautology o In general premises P1 PN entail logicallyimply Q iffP1 quot quot PN a Q is atautology 0 Refer to Table 131 on P40 of Textbook for a summary of Rules of Inference

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

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

#### "I made $350 in just two days after posting my first study guide."

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

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

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