CS1231 Discrete Structure Notes PDF

Preview

Summary

Warning: TT: undefined function: 32 Warning: TT: undefined function: 32 Proposition: (p) Chapter 1 - A declarative sentence that is true or false (has a truth value) (eg. 1 + 1 = 2 (true), or 4 + 5 = 6 (false)) - Truth value: the quality of being true or false o True propositions o False proposition...

Description

https://jcmug.com/collections/computer-science?page=2

Proposition: (p) Chapter 1 • A declarative sentence that is true or false (has a truth value) • Truth value: the quality of being true or false o True propositions o False propositions • Example of a proposition: x + y > 0 , when x and y are known •

(eg. 1 + 1 = 2 (true), or 4 + 5 = 6 (false))

Producing new propositions from those we already have: o Negation of a proposition p: –p ▪ –p means NOT p ▪ p and –p have opposite truth values • eg. if p is true, –p is false o Conjunction of two propositions p and q: p∧ ∧q ▪ ▪ ▪ o

p∧ ∧q means p AND q if BOTH p and q are true, p∧q is true if one or both are false, then p∧q is false

Disjunction of two propositions p and q: p∨q ▪ p∨ ∨q means p OR q ▪ ▪

if both p and q are true, p∨q is true if only one is true, then p∨q is also true

Tip: to remember conjunction or proposition, start looking at the sign from the bottom up. If it joins at the top, it’s a conjunction If it splits at the top, it’s a disjunction

Non-propositions: • Predicate: x + y > 0 (x and y are NOT known) Conditional propositions: • • • •

•

p → q (if p then q) p: hypothesis/premise q: conclusion/consequence False ONLY when p is true and q is false o Otherwise it is true (eg. p is false, q is true; p is true, q is true, p is false, q is false) o If p is true, then q must be true; BUT if p is false, q can also be true Given p → q, o Contrapositive form: o Inverse form: o Converse form:

–q → –p –p → –q q→p

Equivalent propositions: • Two compound propositions p and q are Equivalent if they always have the same truth value o When p is true, q is true; when p is false, q is false o NOT equivalent does NOT mean that the truth values are NOT ALWAYS the same (sometimes both T) • To check equivalence, construct a truth table to check if they have the same truth values o Eg. to show that (p∨–q) → (p∧q) ≡ q, p q p∨–q p∧q (p∨–q) → (p∧q) T T T T T T F T F F F T F F T F F T F F Theorem: o p → q ≡ –q → –p (equivalent to contrapositive) o q → p ≡ –p → –q (converse is equivalent to inverse) o p→q≢q→p (NOT equivalent to converse) o

p → q ≡ –p∨ ∨q

***

https://jcmug.com/collections/computer-science?page=2

Biconditional Proposition: • • •

p↔q True when BOTH p and q have the SAME truth values o If BOTH p and q are true/false, then is true True when p ≡ q

“if” p then q 1. p → q • Whenever p is true, q will be true (p implies q) • p is a sufficient condition for q to be true o whenever p is true, q is true o if p is false, does NOT necessarily mean q is false p “if” q (without “then”) 1. q → p p “only if” q 1. –q → –p (if you don’t have q, you can’t have p) 2. p → q (since –q → –p ≡ p → q) • q is a necessary condition for p to be true o for q to be true, it is necessary that p has to be true o if p is false, it means q is false

p is a sufficient condition for q: p→q p is NOT a sufficient condition for q: –(p → q) ≡ p ∧ –q

p is a necessary condition for q: q→p p is NOT a necessary condition for q: –(q → p) ≡ q ∧ –p

“if and only if” (“iff”); p “iff” q (p → q) ∧ (q → p) o (“only if” part) ∧ (“if” part) o p if q (without the “then” word), means q implies p q→p o p only if q, means –q → –p, which means p → q • p↔q Negation of biconditional: • True when BOTH p and q have the same truth values p ↔ q ≡ (p → q) ∧ (q → p) ≡ (–p ∨ q) ∧ (–q ∨p) • p is BOTH necessary and sufficient for q ∴ negation is: (p ∧ –q) ∨ (q ∧–p) Logical operator precedence: (from highest priority to lowest) 1. Negation (–) 2. Conjunction/disjunction (∧,∨) 3. Conditional/biconditional (→, ↔) •

Translating English Sentences into logical expressions: •

•

Use symbols to represent various things o Eg. “you can access the internet from campus (a) only if you are a computer science major (c) or you are not a freshman (f)” o Translation: a → (c∨–f) Eg. Finding an instance when all 3 expressions are true: o Diagnostic message is not stored in the buffer ▪ –s is true when s is false o If the diagnostic message is stored in the buffer then it is retransmitted ▪ If s is false, then s → r is true when r is either true or false o Diagnostic message is stored (s) in buffer or it is retransmitted (r) ▪ If s is false, s∨r is true when r is true ∴ all 3 expressions are true when s is false and r is true

–s s→r s∨r

https://jcmug.com/collections/computer-science?page=2

Tautology (T) • A compound proposition that is always true •

Eg. p∨–p

(p or not p)

Contradiction (C) • A compound proposition that is always false (opposite of a tautology) •

Eg. p∧–p

(p and not p)

Contingency • A compound proposition that is neither a tautology nor a contradiction •

Sometimes true, sometimes false

Theorem: • Commutative Laws o Does NOT matter which order you write, the truth value does not change

•

•

o p∧q ≡ q∧p o p∨q ≡ q∨p Associative Laws: o When you take conjunction of 3 propositions, of same “sign” (all conjunction, or all disjunction) o It’s like addition, does NOT matter which order you add first, always same result o (p∧q)∧r ≡ p∧(q∧r) o (p∨ ∨q)∨r ≡ p∨(q∨r) Distributive Laws*: o Different signs (both conjunction and disjunction) o Like multiplying inside the brackets o p∧(q∨r) ≡ (p∧q)∨(p∧r) ▪ p AND (q OR r), is the same as: (p AND q) OR (p AND r) ▪

p∨(q∧r) ≡ (p∨q)∧(p∨r) ▪ p OR (q AND r), is the same as: (p OR q) AND (p OR r) Identity Laws: o p∧T ≡ p (T = tautology) (p AND tautology is always truth value of p) o

•

•

•

•

•

•

o p∨C ≡ p Negation Laws: o p∧–p ≡ C

(C = contradiction)

(p OR contradiction is always truth value of p)

(p AND negation of p cannot exist together, so always false ≡ C)

o p∨–p ≡ T (p OR negation of p is always true because it’s either one) Double Negation Laws: o Negation of the negation is p o –(–p) ≡ p Idempotent Laws: o p∧p ≡ p (truth value of (p AND p) is equivalent as truth value of p) o p∨p ≡ p (truth value of (p OR p) is equivalent as truth value of p) Universal bound Laws: o p∧C ≡ C o p∨T ≡ T De Morgan’s Laws*: o o o

(p AND contradiction (always false) is always false (coz of the contradiction part)) (p OR tautology (always true) is always true (coz whether p is true or not, T is true))

(Bring the negation inside the brackets, change conjunction to disjunction) –(p∧q) ≡ –p∨–q –(p∨q) ≡ –p∧–q (Bring the negation inside the brackets, change disjunction to conjunction) Using De Morgan’s Law:

https://jcmug.com/collections/computer-science?page=2

Eg. What is the negation of –1 < x ≤ 4? ▪ Let p be –1 < x (–p is –1 ≥ x) ▪ Let q be x ≤ 4 (–q is x > 4) ▪ ▪

•

•

–1 < x ≤ 4 Negation:

→ →

p∧q –(p∧q)

▪ De Morgan’s Law: → –p∨–q ▪ In words: → –1 ≥ x OR x > 4 Absorption Laws: o LHS is true/false when p is true/false o p∧(p∨q) ≡ p (p AND (p OR q) is equivalent to truth value of p) ▪ if p is true, p OR q is true, p is also true ▪ if p is false, p OR q can be true or false, but p is false, so p AND (p or q) is false (p OR (p AND q) is equivalent to truth value of p) o p∨(p∧q) ≡ p ▪ if p is true, p AND q can be true or false, but p OR (p and q) is true ▪ if p is false, p AND q is false, so p OR (p and q) is false Negations of T and C: o –T ≡ C (negation of tautology is contradiction) o –C ≡ T (negation of contradiction is tautology)

1.3 PREDICATES & QUANTIFIERS Predicate: • A sentence that contains a finite number of variables o The predicate itself has no truth value o Predicate is like a function o Eg. x2 > x • If the predicate variable is specialized (eg. x = 2, x = John Tan), then it becomes a proposition o It has a truth value (can be True or False) o Eg. 22 > 2 is true • Domain of a predicate is the set of all possible values of the variable Universal and Existential Quantifiers Universal Quantification: • ∀𝒙 ∈ 𝑫, 𝑷(𝒙) o ∀ is the Universal Quantifier, read as “for all” o 𝑥 is the variable o 𝑃(𝑥) is the predicate ▪ Eg. x2 > x, or ∈ ℚ o 𝐷 is the domain ▪ Can also use: ∀𝑥𝑃(𝑥) (if Domain is understood/not important to discussion) • For Universal Quantification: o True if 𝑃(𝑥) is true for all 𝑥 ∈ 𝐷 o False if 𝑃(𝑥) is false for at least one 𝑥 ∈ 𝐷 ▪ An 𝑥 for which 𝑃(𝑥) is false is called a counter example to the universal statement • Identifying universal quantifiers in sentences: o “for every”, “all of”, “for each”, “given any”, “for arbitrary”, “for each” o Eg. “every integer is rational” → write as ∀𝑥 ∈ ℤ, 𝑥 ∈ ℚ ▪ Note: ”rational” means fraction of 2 integers (eg. 5/6) • If consider a larger domain (eg. all humans, or all university students), use implies in predicate

https://jcmug.com/collections/computer-science?page=2

Existential Quantification: •

•

•

•

∃𝒙 ∈ 𝑫, 𝑷(𝒙) o ∃ is the Existential Quantifier, read as “there exists” o 𝑥 is the variable o 𝑃(𝑥) is the predicate ▪ Eg. x2 = x o 𝐷 is the domain ▪ Can also use: ∃𝑥𝑃(𝑥) (if Domain is understood/not important to discussion) For Existential Quantification: o True if 𝑃(𝑥) is true for at least one 𝑥 ∈ 𝐷 ▪ Eg. x2 = x because it is true when x = 0 o False if 𝑃(𝑥) is false for all 𝑥 ∈ 𝐷 Identifying existential quantifiers in sentences: o “Some”, “can be”, “there is a”, “there exists a” o Eg. ”the integer 24 ‘can be’ written as a sum of two integers”: ▪ ∃𝒎, 𝒏 ∈ ℤ(𝟐𝟒 = 𝒎 + 𝒏) [24=m+n] is the predicate P(m,n) If consider a larger domain (eg. all humans, or all university students), use conjunction in predicate

Negation of Universal •

Negation of Universal quantification ≡ Existential quantification o –∀𝑥𝑃(𝑥) ≡ ∃𝑥(−𝑃(𝑥)) (Negation of implies) o –(∀𝑥𝑃(𝑥) → 𝑄(𝑥)) ≡ ∃𝑥(𝑃(𝑥) ∧ −Q(x)) ▪

Proof: • •

•

𝑃(𝑥) → 𝑄(𝑥) ≡ −𝑃(𝑥) ∨ 𝑄(𝑥)

−(𝑃(𝑥) → 𝑄(𝑥)) ≡ −(−𝑃(𝑥) ∨ 𝑄(𝑥)) ≡ 𝑃(𝑥) ∧ −𝑄(𝑥)

from p → q ≡ –p∨ ∨q from De Morgan’s laws

Negation of Existential quantification ≡ Universal quantification so, −∃𝑥 − 𝑃(𝑥) ≡ ∀𝑥(𝑃(𝑥)) o −∃𝑥𝑃(𝑥) ≡ ∀𝑥(−𝑃(𝑥))

Translating from English to Logical Expressions: ▪

Eg. “Every student in this class has studied calculus” o “Every”: Universal Quantification o Domains: ▪ Let C be students in class ▪ Let U be students in university o Predicates: ▪ Let Q(x) be “x is in the class” ▪ Let P(x) be “x has studied calculus” o Answers: 1. If take the domain of C: • ∀𝑥 ∈ 𝐶, 𝑃(𝑥) 2. If take the larger domain of U: • • •

∀𝑥 ∈ 𝑈, 𝑄(𝑥) → 𝑃(𝑥) Use implies as predicate because it is a Universal Quantification Explanation of why can use implies when considering all students: o Case 1: x is NOT a student in class: ▪ Q(x) is false ▪ So Q(x) → P(x) is true (since not in class, so not studying calculus) o Case 2: x is a student in class:

https://jcmug.com/collections/computer-science?page=2

▪

▪ Q(x) is true ▪ So Q(x) → P(x) is true (since in class, so studying calculus) • If use conjunction instead of implies: o If x is NOT a student in class, Q(x) is false, which means Q(x) ∧ P(x) is false o Thus, even if every student in class has studied calculus, it would be false if there is a student that’s NOT in the class o Since we are taking the University as the domain, there will be students NOT in the class, and hence it will be false, which is incorrect Eg. “Some students in this class have not studied calculus” o “Some”: Existential Quantification o Domains: ▪ Let C be students in class ▪ Let U be students in university o Predicates: ▪ Let Q(x) be “x is in the class” ▪ Let -P(x) be “x has studied calculus” o Answers: 1. If take the domain of C: • ∃𝑥 ∈ 𝐶, −𝑃(𝑥) 2. If take the larger domain of U: ∃𝑥 ∈ 𝑈, 𝑄(𝑥) ∧ −𝑃(𝑥) Use conjunction as predicate because it is an Existential Quantification Explanation of why can use conjunction when considering all students: o If include all students in university, then need to be: 1. In class, and 2. Not studied calculus Eg. “Every multiple of 5 ends in either 0 or 5” o ∀𝑛 ∈ ℤ, 𝑀(𝑛) → 𝑍(𝑛) ∨ 𝐹(𝑛) Negation of: “for all prime p, p is odd” o Answer: “there exists a prime p, such that p is not odd (or even)” Eg. “All balls in the bowl are blue”. If the bowl is empty, is ∀𝑥 ∈ 𝐵, 𝑃(𝑥) true or false? o Let B be the set of balls in the bowl, P(x) be ball x is blue o Look at the negation: ▪ ∃𝑥 ∈ 𝐵, −𝑃(𝑥) ▪ “there is at least one ball in the bowl that is not blue” ▪ Since the bowl is empty, there is NOT at least one ball in the bowl that is blue ▪ Hence, the negation is false ▪ Hence, the original proposition is true o OR, let C be the set of all balls, let Q(x) be ball x is in the bowl ▪ ∀𝑥 ∈ 𝐶, 𝑄(𝑥) → 𝑃(𝑥) ▪ Since the bowl is empty, Q(x) is false for every x ▪ Therefore, 𝑄(𝑥) → 𝑃(𝑥) is true for every x ▪ Hence, the original proposition is true o In this situation, when the proposition is true even though it is empty, it’s called vacuously true ▪ When the previous term is always false, so the ‘implies’ term is always true no matter what • • •

▪ ▪ ▪

https://jcmug.com/collections/computer-science?page=2

1.4 NESTED QUANTIFIERS Nested Quantifiers: • •

•

•

•

2 quantifiers are nested if one is within the scope of the other ∀𝑥∃𝑦(𝑥 + 𝑦 = 0) o For all x, there exists a y for which x + y = 0 is true o (x + y=0) is the predicate of y o ∃𝑦(𝑥 + 𝑦 = 0) is the proposition of x → ∃𝑦(𝑥 + 𝑦 = 0) is the same as Q(x), so ∀𝑥𝑄(𝑥) Different Domains for x and y: o ∀𝑥 ∈ 𝑫 ∃𝑦 ∈ 𝑬(𝑥 + 𝑦 = 0) o Eg. x has domain D, y has domain E For every x in domain D, there is a y in domain E such that (x + y = 0) Order of quantifiers: o Left to Right o If same quantifiers (eg. both universal quantifiers, or both existential): ▪ Order does NOT matter, same meaning ▪ Eg. ∀𝑥∀𝑦𝑃(𝑥, 𝑦) has the same meaning as ∀𝑦∀𝑥𝑃(𝑥, 𝑦) ▪ Eg. ∃𝑥∃𝑦𝑃(𝑥, 𝑦) has the same meaning as ∃𝑦∃𝑥𝑃(𝑥, 𝑦) o If different quantifiers (eg. one universal, one existential): ▪ Order matters. CANNOT exchange order, different meaning ▪ Eg. ∀𝑥∃𝑦𝑃(𝑥, 𝑦) means “for all x, there is a y for which P(x,y) is true” ▪ Eg. ∃𝑦∀𝑥𝑃(𝑥, 𝑦) means “there is at least one y, where P(x,y) is true for every x” Negation of Nested Quantifiers: 1. Change universal to existential, existential to universal 2. Add a –ve to the P(x) or take away if it already has –ve Examples o Negation of ∀ ∃ ▪ −∀𝑥∃𝑦𝑃(𝑥, 𝑦) ≡ ∃𝑥∀𝑦 − 𝑃(𝑥, 𝑦) o Negation of ∃ ∀ ▪ −∃𝑥∀𝑦𝑃(𝑥, 𝑦 ) ≡ ∀𝑥∃𝑦 − 𝑃(𝑥, 𝑦) o Write down normal logical expression first, then negate it

1.5 VALID AND INVALID ARGUMENTS Argument Form: • A sequence of propositions: o p1, p2, ... ,pn, c ▪ p1, p2, … , pn: premises, or assumptions, or hypotheses ▪ c: conclusion • An argument is valid when: 1. All premises are true, and 2. Conclusion is also true ▪ p1, p2, ... ,pn → c is true (this implication is true) o Valid argument is also known as a rule of inference o Conclusion is highlighted with a ∴ symbol Testing for a Valid Argument Form: 1. Identify the premises and conclusion 2. Construct a truth table 3. If the truth table contains a row in which all the premises are true and the conclusion is false, the argument form is invalid. Otherwise, the form is valid.

https://jcmug.com/collections/computer-science?page=2

Valid Argument Forms 1) Modus Penens (Method of Affirming) p→q p ∴ q p T T F F

p→q T F T T premises

q T F T F

p T T F F

when p is true, so q must be true (otherwise p → q will be false)

q T F T F conclusion

All premises true, and conclusion true, so it is a valid argument form

Example p → q: If there are more pigeons than pigeon holes, then two pigeons roost in the same hole p: there are 5 pigeons and 3 pigeon holes (more pigeons than holes) ∴ q: Therefore there are 2 pigeons in the same hole 2) Modus Tollen (Method of Denying) p→q –q ∴ –p p T T F F

p→q –q T F F T T F T T premises

q T F T F

when q is false, so p must be false (otherwise p → q will be false)

–p F F T T conclusion

Example p → q: If an integer is divisible by 6, then it is divisible by 3 –q: 870232 is not divisible by 6 ∴ –p: Therefore 870232 is not divisible by 6 3) Specialization, Generalization • Specialization: o You prove more than what you need o

p∧ ∧q, ∴p ▪ If p AND q is true, then of course p is true

∧q, ∴q p∧ ▪ If p AND q is true, then of course q is true Generalization: o You prove less than what you need o p, ∴ p∨q ▪ If p is true, then p OR q will be true o

•

o

q, ▪

∴ p∨q If q is true, then p OR q will be true

All premises true, and conclusion true, so it is a valid argument form

https://jcmug.com/collections/computer-science?page=2

4) Elimination •

•

p∨q, o o p∨q, o o

–p, ∴q You know either p OR q is true, the second premise says that p is false So by elimination, conclude that q is true –q, ∴p You know either p OR q is true, the second premise says that q is false So by elimination, conclude that p is true

5) Transitivity •

p → q, q → r, ∴ p → r o p implies q is true, and q implies r is true, therefore p implies r must be true

6) Proof by Cases •

p ∨ q, p → r, q → r, ∴ r o If p OR q is true, and p implies r, and q implies r, then r must be true (because either p or q is true) o If at least one of two (or several) possibilities is true and each possibility leads to the same conclusion, then the conclusion must also be true

7) Proof by Contradiction •

–p → c which is a contradiction, ∴ p o if negation of p implies contradiction is true, the p must be true o If an assumption leads to a contradiction, then that assumption must be false

Application of Valid Argument Forms First, define propositions, then write out logical expressions EXAMPLE 1: Knights and Knaves Knights always tell the Truth, Knaves always Lie. Can we tell what A and B are from what they say below? 𝑎 → 𝑏 and −𝑎 → −𝑏 or −𝑎 ∨ 𝑏 and 𝑎 ∨ −𝑏 A: “B is a knight” (consider when A is true, and when A is false: if A is a knight, it implies B is; if A is a knave, it implies B is a knave) B: “A and I are of opposite type” 𝑏 → −𝑎 and −𝑏 → −𝑎 or −𝑏 ∨ −𝑎 and 𝑏 ∨ −𝑎 (consider when B is true, and when B is false: if B is a knight, it implies A is not; if B is knave, it implies A is also knave) Let: a = “A is a knight”, b = “B is a knight” Solution 1 1. 2. 3. 4. 5. 6.

𝑎→𝑏 𝑏 → −𝑎 ∴ 𝑎 → −𝑎 ∴ −𝑎 ∨ −𝑎 = −𝑎 −𝑎 → −𝑏 ∴ −𝑏

from statement A from statement B From 1, 2 (transitivity) From 3 (rewrite into this form easier to understand than: a implies not a) from statement A From 4, 5 (modus penens: since –a is true, and −𝑎 → −𝑏 is true, ∴ −𝑏 is true)

If there is a solution, it must be that both A and B are knaves. This can be checked with the given facts. Solution 2 (using conjunctions & disjunctions) 1. −𝑏 ∨ 𝑎 2. −𝑏 ∨ −𝑎 3. ∴ (−𝑏 ∨ 𝑎) ∧ (−𝑏 ∨ −𝑎) 4. ∴ −𝑏 ∨ (𝑎 ∧ −𝑎) = −𝑏 ∨ 𝑪 = −𝑏 5. 𝑏 ∨ −𝑎 6. ∴ −𝑎

from statement A from statement B since 1 and 2 are true, both have to be true (conjunction) From 3 (distributive law); (negation law: 𝑎 ∧ −𝑎 ≡ C); (identity law) from statement B From 5 (elimination: since b is false (from 4), –a has to be true)

https://jcmug.com/collections/computer-science?page=2

EXAMPLE 2 Will (a), (b), (c), (d) lead to the conclusion (e)? (a) (b) (c) (d) (e)

It is cold and not sunny this afternoon We will go swimming only if it is sunny If we do not go swimming, then we will take a canoe trip If we take a canoe trip, then we will be home by sunset We will be home by sunset

cold ∧ –sun swim → sun –swim ∧ canoe canoe ∧ home home

Let: s...