### Create a StudySoup account

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

Already have a StudySoup account? Login here

# DISCRETEMATHEMATICS MATH245

SDSU

GPA 3.72

### View Full Document

## 16

## 0

## Popular in Course

## Popular in Mathematics (M)

This 8 page Class Notes was uploaded by Burnice Ratke on Tuesday October 20, 2015. The Class Notes belongs to MATH245 at San Diego State University taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/225273/math245-san-diego-state-university in Mathematics (M) at San Diego State University.

## Popular in Mathematics (M)

## Reviews for DISCRETEMATHEMATICS

### 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: 10/20/15

Math 245 Discrete Mathematics The Logic of Compound Statements Logical Form and Logical Equivalence Lecture Notes 2 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminus SDSU EDU http terminus SDSU EDU 51d lecturetexv 15 20060830 215601 blomgren Exp S The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 129 Two arguments Logical Form If the program syntax is faulty or if program execution results in division by zero then the computer will generate an error message Therefore ifthe computer does not generate an error message then the program syntax is correct and program execution does not result in division by zero If 2 is a real number such that 2 lt 72 or 2 gt 2 then 22 gt 4 Therefore if 22 g 4 then 2 2 72 and 2 g 2 The content of these arguments is very different Nevertheless their logical form is the same If p or q then r Therefore if not r then not p and not q The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 229 identifying Logical Form 1 of 2 Example111 Fill in the blanks so that argument b has the same form as argument a Then represent the common form of the arguments using letters to stand for component structures Statement A If Jane is a math major or Jane is a CS major then Jane will take Math 245 Jane is a CS major Therefore Jane will take Math 245 Statement B If logic is easy or I will study hard then I will get an A in this course I will study hard Therefore I will get an A in this course The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 329 identifying Logical Form 2 of 2 Statement A If Jane is a math major or Jane is a CS major then Jane will take Math 245 Jane is a CS major Therefore Jane will take Math 245 Statement B If logic is easy or I will study hard then I will get an A in this course I will study hard Therefore I will get an A in this course Common Form If p or q then r q Therefore r The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 429 Statements In any mathematical theory new terms are defined using previously defined terms This process has to start somewhere ln logic the words sentence true and false are initial undefined terms Definition Statement A statement or proposition is a sentence that is true or false but not both Examples The square root of9 is 3quot The square root of9 is 81quot are both statements the first one is true and the second false The Logic of Compound Stetemente Logical Foxm end Ldgmel Equwelence e p 529 Nonstatements The sentence She is a college studentquot Sure looks like a statement However the truth or falsity depends on the reference for the pronoun she If the sentence was preceded by additional information that made the pronoun39s reference clear then the sentence would be a statement On its own the sentence is neither true nor false hence it is not a statement in the language of mathematics Similarly 2 y gt 0quot is not a statement because the truth or falsity depends on the values of 2 and y The Logic of Compound Stetemente Ldgmel Foxm end Ldgmel Equwelence e p 629 Compound Statements and Introduction of Symbols 1 of 3 In order to express complicated statement clearly we introduce three symbols The symbol denotes not The symbol A denotes and The symbol V denotes or N pquot is read not pquot and is called the negation of p n u I Side note In the computer language C the symbol for not is hence 1p means not pquot in C The Logic of Compound Stetemente Logical Foxm end Ldgmel Equwelence e p 729 Compound Statements and Introduction of Symbols 2 of 3 The conjunction of p and q pqquot is read p and qquot The disjunction of p and q p Vqquot is read p or qquot The order of evaluation matters N has the highest order of precedence eg pAqpAq We use parentheses to override andor clarify the order of operations thus N pAq represents the negation of the conjunction of p and q The Logic of Compound Stetemente Ldgmel Foxm end Ldgmel Equwelence e p 529 Compound Statements and Introduction of Symbols 3 of 3 The symbols A and V are considered coequal in order of operation and an expression such as pAqu is considered ambiguous This expression must be written as either pAmVr or pAde to have meaning Note The statements p A q V r and p A q V r are not the same We will discuss this in detail soon The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 929 Translating from English to Symbols Example112 Write each of the following sentences symbolically letting pquotit is hotquot and qquotit is sunnyquot a It is not hot but sunnyquot b It is neither hot nor sunnyquot Solution a By convention but and so the sentence is equivalent to It is not hot and it is sunny which we write symbolically as ltqu b The phrase neither A nor Bquot means the same as not A and not Bquot To say it is neither hot nor sunny means it is not hot and it is not sunny Therefore the given sentence can be written symbolically as N p A N q In both a and b the parentheses around the negations are optional The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 1029 Translating Mathematical inequalities to Symbols Note the notation for inequalities involves both and and or state ments For instance if 22 a and b are particular real numbers then xga means zlta or 22a agxgb means ages and xgb which expands to altz or az and zltb or 2219 The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 1129 More examples Example113 Suppose 2 is a particular real number Let pquot0 lt 22quot qquotz lt 3quot and rquotz 3quot respectively Write the following inequalities symbolically a ag b 0ltzlt3 c 0ltx 3 Solution aqu lpAq dpAde The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 1229 De nition and Truth Tables Negation not Definition Negation lfp is a statement variable the negation ofp is not p or It is not the case that pquot The negation is denoted Np It has the opposite truth value from p ifp is true then not p is false if p is false then not p is true The truth values for negation are summarized in a truth table P NP T F F T Truth table for Np The Logic of Compound Stetemente Logical Foxm end Logical Eqnwelence e p 1329 De nition and Truth Tables Conjunction and Definition Conjunction lfp and q are statement variables the conjunction ofp and q is p and qquot The conjunction is denoted pq It is true when and only when both p and q are true If either p or q is false or if both are false then pq is false P q n 4 4s i3939i 11gtQ T F F F F F Truth table for p q The Logic of Compound Stetemente Logical Foxm end Logical Eqnwelence e p 1429 Definition and Truth Tables Disjunction or V Definition Disjunction If p and q are statement variables the disjunction of p and q is p or qquot The disjunction is denoted pV q It is true when at least one ofp and q is true and false only when both p or q are false P q niibo iTI 11gtQ V T T T F F F Truth table for pV q Note that disjunction is an inclusive or its truth value is true when both p and q are true Th e Logic of Compound Stetemente Logical Foxm end Logical Eqnwelence e p 1529 Definition and Truth Tables Exclusive Or We can express exclusive or as a compound statement For the statement variables p and q we want an expression which is true if exactly one ofp or q is true and false otherwise p q qu pAq Mq quMNUMQl T T T T F F T F T F T T F T T F T T F F F F T F Sometimes we use the notation 1369 q for exclusiveeor The Logic of Compound Stetemente Logical Foxm end Logical Eqnwelence e p 1629 General Compound Statements Definition Statement form A statement form or propositional form is an expression made up of statement variables such as p q and r and logical con nectives such as N A and V that becomes a statement when actual statements are substituted for the component statement variable The truth table for a given statement form displays the truth values that correspond to the different combinations of truth values for the variables To compute the truth values for a statement form For each combi nation of truth values for the statement variables first evaluate the expressions within the innermost parentheses then evaluate the ex pressions within the next innermost parentheses and so forth until you have the truth values for the complete expression The Ldgtc of Compound Stetemente Logical Foxm end Logical Equivalence e p 1729 Example Truth Table for p q v N r e Z d 5 gt Q lt Z d l nl nlTIll P q 39n39n39n39n i i i ioo n n ll39nn llto T T F F F F F F m i nlTI l39n l l39n l39n l39n in The Logic of Compound Stetemente Logical Foxm end Logical Equivalence e p 1329 Logical Equivalence The statements 8 gt 3 and 3 lt 8 are two different ways of saying the same thing by the definition of lt and gt The statements Pigs fly and cats bark and Cats bark and pigs flyquot are also two different ways of saying the same thing The reason is the logical form of the statement Any two statements having the same form as these statements would either be both true or both false In such a case the statements are said to be logically equivalent The Ldgtc of Compound Stetemente Logical Foxm end Logical Equivalence e p 1929 Logical Equivalence Truth Table The expressions p Ag and qu are logically equivalent qup nn 4 4e 39n l39n iQ T T F F F F F F Since the p A q and q p columns in the table have the same values the statements are logically equivalent The Logic of Compound Stetemente Logical Foxm end Logical Equivalence e p 2o29 Logical Equivalence Definition Checking for Logical Equivalence To test whether two statement forms P and Q are logically equivalent Definition Logical equaence Two statement forms are called logically equivalent if and only if they have identical truth values for each possible substitution of statements for their statement variables The logical equivalence 1 Construct the truth tables for P and Q using the same statement variables for identical component statements of forms P and Q is denoted by writing P E Q 2 Check each combination of truth values of the statement vari39 Two statements are called logically equivalent if and only if ables to see whether the truth value of P is the same as the truth when the same statement variables are used to represent identical Value 0f Q component statements their forms are logically equivalent a If in each row the truth value for P is the same as the truth value for Q then P and Q are logically equivalent b Otherwise P and Q are not logically equivalent The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 2129 The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 2229 De Morgan s Laws Negations of AND and OR De Morgan s Laws Truth Table for AND For the statement John is tall and Jim is shortquot to be true both components must be true It follows that for the statement to be false one or both com onents must be false 9 p q 19 q pAq pAq 19 Vq Thus the negation is John is not tall or Jim is not shortquot T T F F T F F T F F T F T T In general the negation of a conjunction is logically equivalent to the F T T F F T T disjunction of their negations T T T T F T T NPAQ E NP VNq ThisshowsthatpAqEp Vq The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 2329 The Logic of Compound Stetemente Logical Foxm end Logical Equwelence e p 2429 De Morgan s Laws Truth Table for OR p q Np q qu 4PVq NPA T T F F T F F T F F T T F F F T T F T F F F F T T F T T This shows that N qu E Np A q The Logic of Compound Stetennente Logxcal Foxm end Logxcal Equwelence e p 2529 De Morgan s Laws A Warning According to De Morgan39s Laws the negation of p Jim is tall and Jim is thin Np Jim is not tall or Jim is not thin In English we can write the statement p more compactly as Jim is tall and thinquot q Jim is tall and thin q Jim is not tall and thin The problem here is that we do not have complete statements on both sides of the AND Although the laws of logic are extremely usefulY they should be used as an aid to thinkingY not as a mechanical substitute for it The Logic of Compound Stetennente Logxcal Foxm end Logxcal Equwelence e p 2629 Ta utologies and Contradictions Definition Tautology and Contradiction A tautology is a statement form that is always true regardless of the truth values of the individual statements substituted for its statement variables A statement whose form is a tautology is called a tautological statement A contradiction is a statement form that is always false regardless of the truth values of the individual statements substituted for its statement variables A statement whose form is a contradiction is called a contradictory statement The Logic of Compound Stetennente Logxcal Foxm end Logxcal Equwelence e p 2729 Tautologies and Contradictions Example p Np pVNP FANP T F T F F T T F Hence p V Np is a tautology and p Np a contradiction The Logic of Compound Stetennente Logxcal Foxm end Logxcal Equwelence e p 2529 Logical Equivalences Given any statement variables p q and r a tautology t and a contradiction c the following equivalences hold Commutative laws Associative laws Distributive laws Identity laws 19qu Mp MqMTEPMqM MqWEMqVPM pAtEP quEqu PV4VTEPV 1VT pVqMEPVqMPW pVCEp Negation laws pVNpEt pANpEc Double negative law N Np E p ldempotent laws pAp E p pr E p De Morgan s laws pAqE NPVNq NONI NPANq Universal bound laws pvt Et pAc E 6 Absorption laws pV pAq E p pA qu E p Negations of t and 6 wt E c NC 7 The Logic of Compound Statements Logical Foxm and chmi Equivalence 7 p 2929

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

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

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