Class 1 on Jan 19: 2.1-2.3 ch

Please provide a detailed summary of a chapter on discrete structures. BE VERY COMPACT, CONSISE BECAUSE TOO MANY WORDS AND WATER MAKES IT HARD TO GRASP, USE EASY LANGUAGE, EXAMPLES AND REALLY EASY. Include the following elements:

1. Key Definitions & Concepts: List and briefly explain essential terms (e.g., sets, relations, functions, graphs, logic, combinatorics).
3. Major Theorems & Formulas: Highlight important theorems, principles, or equations with their significance.

Format the summary in clear sections, using bullet points for readability. Now prepare this summary with this text:

now do all the exercises by the end for me TO HELP ME PRACTICE FOR MY QUIZ, REALLY IMPORTANT, I NEED MORE EXAMPLES, I NEED YOU TO SHOW ME HOW TO DO EVERYTHING DISCUSSED IN THIS CHAPTER

2.1: CHAPTER Key Definitions & Concepts

  • Logical Equivalence: Two statements are logically equivalent if they have the same truth value in every possible scenario. They mean the same thing, logically. We write this with ≡.

  • Tautology: A statement that is always true (e.g., "It is raining or it is not raining").

  • Contradiction: A statement that is always false (e.g., "It is raining and it is not raining").

  • De Morgan's Laws: Rules for distributing a "NOT" (∼) over "AND" (∧) and "OR" (∨).

    • Law 1: ∼(p ∧ q) is equivalent to (∼p ∨ ∼q).

      • Example: "It's NOT true that I like apples AND bananas" means "I DON'T like apples OR I DON'T like bananas."

    • Law 2: ∼(p ∨ q) is equivalent to (∼p ∧ ∼q).

      • Example: "It's NOT true that I like apples OR bananas" means "I DON'T like apples AND I DON'T like bananas."

3. Major Theorems & Formulas (The "Laws")

The chapter presents Theorem 2.1.1, a set of logical equivalence laws. Think of them as algebra rules, but for logic. The most useful ones include:

  • Commutative Laws: p ∧ q ≡ q ∧ p (order doesn't matter for AND/OR).

  • Associative Laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (grouping doesn't matter).

  • Distributive Laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (AND distributes over OR, like multiplication over addition).

  • Identity Laws: p ∧ True ≡ p and p ∨ False ≡ p.

  • Negation Laws: p ∨ ∼p ≡ True (Tautology) and p ∧ ∼p ≡ False (Contradiction).

  • Double Negative Law: ∼(∼p) ≡ p ("It's NOT NOT raining" means "It IS raining").

4. Problem-Solving Techniques

  1. Simplification using Laws: Use the logical laws (Theorem 2.1.1) step-by-step to rewrite a complex statement into a simpler, equivalent one.

    • Example from text: They simplified ∼(∼p ∧ q) ∧ (p ∨ q) down to just p by applying De Morgan's, Double Negative, Distributive, and other laws.

  2. Verification using Truth Tables: Build a truth table listing all possible true/false combinations for the variables. If the final columns for two statements are identical, they are logically equivalent.

    • Pro: Always works and is easy for computers.

    • Con: Can be long (2^n rows for n variables).

PRACTICE

Let's start with the "Test Yourself" questions—these are the absolute basics you must know cold.

Answers to Test Yourself:

  1. True (An AND statement is true only when both parts are true.)

  2. False (An OR statement is false only when both parts are false.)

  3. The same truth values (This is the definition of logical equivalence.)

  4. (1) OR, negated; (2) AND, negated (This is De Morgan's Laws in simple language.)

  5. True (A tautology is always true, like p ∨ ∼p.)

  6. False (A contradiction is always false, like p ∧ ∼p.)

Part 2: Symbolic Translation & Truth Tables

This is about going from English to logic symbols and back.

Exercise 6:

  • s = "stocks are increasing"

  • i = "interest rates are steady"

a. "Stocks are increasing but interest rates are steady."

  • "but" means and.

  • Answer: s ∧ i

b. "Neither are stocks increasing nor are interest rates steady."

  • "Neither A nor B" means not A and not B.

  • Answer: ∼s ∧ ∼i

Exercise 7:

m = "Juan is a math major", c = "Juan is a computer science major"

  • "Juan is a math major but not a computer science major."

  • Answer: m ∧ ∼c

Exercise 8:

h = "John is healthy", w = "John is wealthy", s = "John is wise"

a. John is healthy and wealthy but not wise.

  • Answer: h ∧ w ∧ ∼s

b. John is not wealthy but he is healthy and wise.

  • Answer: ∼w ∧ h ∧ s

c. John is neither healthy, wealthy, nor wise.

  • "Neither A, nor B, nor C" = ∼A ∧ ∼B ∧ ∼C

  • Answer: ∼h ∧ ∼w ∧ ∼s

d. John is neither wealthy nor wise, but he is healthy.

  • Answer: (∼w ∧ ∼s) ∧ h (which is the same as h ∧ ∼w ∧ ∼s)

e. John is wealthy, but he is not both healthy and wise.

  • "Not both healthy and wise" = ∼(h ∧ s) (This is different from ∼h ∧ ∼s!)

  • Answer: w ∧ ∼(h ∧ s)

Part 3: Logical Equivalence & Truth Tables (Exercises 16-24)

The key here: Build the truth table. If the final columns are identical, they are equivalent.

Example: Exercise 16: p ∨ (p ∧ q) and p

Truth Table:

p

q

(p ∧ q)

p ∨ (p ∧ q)

T

T

T

T

T

F

F

T

F

T

F

F

F

F

F

F

Compare the last column to a column for just p (the T, T, F, F in the first column). They are the same! So p ∨ (p ∧ q) ≡ p. This is the Absorption Law.

Quick Guide to Checking Others:

  • 17. ∼(p ∧ q) and ∼p ∧ ∼q: NOT EQUIVALENT. This is a common mistake! De Morgan's Law says ∼(p ∧ q) ≡ ∼p ∨ ∼q.

  • 18. p ∨ t and t (where t = true): NOT EQUIVALENT. If p is true, p ∨ t is true. If p is false, p ∨ t is still true (because t is true). So p ∨ t is a tautology (always true), which is equivalent to t. Wait, that means they ARE equivalent. Let's check: A column for t would be all T. The column for p ∨ t would also be all T. Yes, equivalent. This is the Identity Law: p ∨ True ≡ True.

  • 19. p ∧ t and p: EQUIVALENT. (Identity Law: p ∧ True ≡ p)

  • 22. p ∧ (q ∨ r) and (p ∧ q) ∨ (p ∧ r): EQUIVALENT. This is the Distributive Law.

Part 4: Applying De Morgan's Laws (Exercises 25-31)

This is crucial: You're negating an entire English sentence.

Rule: ∼(A ∧ B) ≡ ∼A ∨ ∼B and ∼(A ∨ B) ≡ ∼A ∧ ∼B. Negation changes AND to OR (and vice versa) and negates the simple parts.

Exercise 25: "Hal is a math major and Hal’s sister is a computer science major."

  • Let M = "Hal is a math major", C = "Sister is a CS major".

  • Sentence is M ∧ C.

  • Negation: ∼(M ∧ C) ≡ ∼M ∨ ∼C.

  • English: "Hal is not a math major or Hal’s sister is not a computer science major."

Exercise 27: "The connector is loose or the machine is unplugged."

  • L = "connector is loose", U = "machine is unplugged".

  • Sentence: L ∨ U.

  • Negation: ∼(L ∨ U) ≡ ∼L ∧ ∼U.

  • English: "The connector is not loose and the machine is not unplugged." (i.e., "The connector is tight and the machine is plugged in.")

Exercise 30: "The dollar is at an all-time high and the stock market is at a record low."

  • H = "dollar high", L = "market low".

  • Sentence: H ∧ L.

  • Negation: ∼H ∨ ∼L.

  • English: "The dollar is not at an all-time high or the stock market is not at a record low."

Part 5: Tautologies & Contradictions (Exercises 40-43)

How to check: Build the truth table. If the final column is all T, it's a tautology. If all F, it's a contradiction. If a mix, it's neither.

Example: Exercise 40: (p ∧ q) ∨ (∼p ∨ (p ∧ ∼q))

Let's simplify first using laws (good practice!):

  1. (p ∧ q) ∨ (∼p ∨ (p ∧ ∼q))

  2. Associative/Commutative: (p ∧ q) ∨ (p ∧ ∼q) ∨ ∼p

  3. Distributive (on first two): p ∧ (q ∨ ∼q) ∨ ∼p

  4. Negation Law: p ∧ True ∨ ∼p

  5. Identity Law: p ∨ ∼p

  6. Negation Law: True (Tautology).

So without a full table, we proved it's always true.

Example: Exercise 41: (p ∧ ∼q) ∧ (∼p ∨ q)

Let's test a case. If p is T and q is T:

  • (T ∧ ∼T) = (T ∧ F) = F

  • (∼T ∨ T) = (F ∨ T) = T

  • F ∧ T = **F**
    Now if p is T and q is F:

  • (T ∧ ∼F) = (T ∧ T) = T

  • (∼T ∨ F) = (F ∨ F) = F

  • T ∧ F = **F**
    It's already not all T (so not a tautology) and not all F (yet). Let's check p=F, q=T:

  • (F ∧ ∼T) = (F ∧ F) = F

  • (∼F ∨ T) = (T ∨ T) = T

  • F ∧ T = F
    All results so far are F. Check last row (p=F, q=F):

  • (F ∧ ∼F) = (F ∧ T) = F

  • (∼F ∨ F) = (T ∨ F) = T

  • F ∧ T = F
    Final column is all F. This is a CONTRADICTION.

Part 6: Using the Logical Laws Step-by-Step (Exercises 48-54)

This mimics the book's Example 2.1.14. You must state the law used at each step.

Exercise 48: Prove (p ∧ ∼q) ∨ (p ∧ q) ≡ p

text

(p ∧ ∼q) ∨ (p ∧ q) ≡ p ∧ (∼q ∨ q)   by the Distributive Law (factor out p)
                    ≡ p ∧ (q ∨ ∼q)   by the Commutative Law for ∨
                    ≡ p ∧ t          by the Negation Law (q ∨ ∼q is always true)
                    ≡ p              by the Identity Law

Exercise 50: Verify (p ∧ ∼q) ∨ p ≡ p

text

(p ∧ ∼q) ∨ p ≡ p ∨ (p ∧ ∼q)          by the Commutative Law for ∨
              ≡ p                    by the Absorption Law (p ∨ (p ∧ ?) ≡ p)

(The Absorption Law wasn't formally in Theorem 2.1.1, but it's a common derived rule. Alternatively, you could use Distributive Law: p ∨ (p ∧ ∼q) ≡ p ∧ (True ∨ ∼q) ≡ p ∧ True ≡ p).

Exercise 52: Verify ∼(p ∨ ∼q) ∨ (∼p ∧ ∼q) ≡ ∼p

This looks messy. Let's apply De Morgan to the first part.

text

∼(p ∨ ∼q) ∨ (∼p ∧ ∼q) ≡ (∼p ∧ ∼(∼q)) ∨ (∼p ∧ ∼q)   by De Morgan's Law
                       ≡ (∼p ∧ q) ∨ (∼p ∧ ∼q)        by the Double Negative Law
                       ≡ ∼p ∧ (q ∨ ∼q)               by the Distributive Law (factor out ∼p)
                       ≡ ∼p ∧ t                      by the Negation Law
                       ≡ ∼p                          by the Identity Law

2.3. CHAPTER Key Definitions & Concepts

  • Conditional Statement (p → q): An "if-then" statement. Only false when p is true and q is false.

    • Example: "If it rains (p), then the ground is wet (q)."

  • Hypothesis (p): The "if" part.

  • Conclusion (q): The "then" part.

  • Related Statements:

    • Converse: q → p (flip it).

    • Inverse: ∼p → ∼q (negate both).

    • Contrapositive: ∼q → ∼p (flip and negate).

  • Biconditional (p ↔ q): "p if and only if q" means p and q have the same truth value. It's like saying both p → q AND q → p.

  • Necessary Condition: For p → q, q is necessary for p. You can't have p without q.

    • Example: "Being human (q) is necessary for being a doctor (p)." (If you're a doctor, you must be human.)

  • Sufficient Condition: For p → q, p is sufficient for q. If p happens, q is guaranteed.

    • Example: "Passing the final (p) is sufficient for passing the class (q)." (If you pass the final, you pass.)

3. Major Theorems & Formulas

  • Equivalence to OR: p → q ≡ ∼p ∨ q

    • Why? The only way p → q is false is if p is true AND q is false (p ∧ ∼q). So its negation is p ∧ ∼q. Therefore, the original statement is ∼(p ∧ ∼q) ≡ ∼p ∨ q.

  • Contrapositive Equivalence: p → q ≡ ∼q → ∼p

    • Most Important Rule! A conditional is logically equivalent to its contrapositive, but NOT to its converse or inverse.

    • Example: "If a shape is a square (p), then it has four sides (q)" is equivalent to "If a shape does not have four sides (∼q), then it is not a square (∼p)."

  • Negation of a Conditional: ∼(p → q) ≡ p ∧ ∼q

    • How to negate an "if-then": You keep the hypothesis true AND make the conclusion false.

    • Example: The negation of "If you study, you will pass" is "You studied AND you did not pass."

Simple Rule of Thumb:

  1. To change → to ∨, negate the first part.

  2. The contrapositive is your friend for proofs.

  3. Converse ≠ Original. "If dog → mammal" is true, but "If mammal → dog" is false.

2.3 PRACTICE

Part 1: Understanding the Basics

Test Yourself Answers (Memorize these!)

  1. True, False (Only way p → q is false: p=T, q=F)

  2. p ∧ ∼q

  3. if q then p

  4. if ∼q then ∼p

  5. if ∼p then ∼q

  6. logically equivalent

  7. logically equivalent (Actually, they are NOT logically equivalent! The answer key is wrong here. The book says "are not" in question 7.)

  8. if R then S

  9. if S then R (Careful! "Necessary condition" reverses direction)

  10. if R then S

Part 2: Translating to If-Then Form (Exercises 1-4)

Rule: Look for logical relationship. "A only if B" = A → B. "B if A" = A → B.

1. "This loop will repeat exactly N times if it does not contain a stop or a go to."

  • A = "it does not contain a stop or a go to"

  • B = "This loop will repeat exactly N times"

  • "B if A" = A → B

  • Answer: If it does not contain a stop or a go to, then this loop will repeat exactly N times.

2. "I am on time for work if I catch the 8:05 bus."

  • A = "I catch the 8:05 bus"

  • B = "I am on time for work"

  • "B if A" = A → B

  • Answer: If I catch the 8:05 bus, then I am on time for work.

3. "Freeze or I'll shoot."

  • Means: If you do NOT freeze, then I'll shoot.

  • Let F = "You freeze", S = "I shoot"

  • Original: ∼F → S

  • Answer: If you do not freeze, then I'll shoot.

4. "Fix my ceiling or I won't pay my rent."

  • Means: If you do NOT fix my ceiling, then I won't pay my rent.

  • Let F = "You fix my ceiling", P = "I pay my rent"

  • Original: ∼F → ∼P

  • Answer: If you do not fix my ceiling, then I will not pay my rent.

Part 3: Truth Tables for Conditionals (Exercises 5-11)

Key Rule: p → q is false only when p=T and q=F.

Example: Exercise 5: ∼p ∨ q → ∼q

  1. Build truth table for 2 variables (p, q):

p

q

∼p

∼p ∨ q

∼q

(∼p ∨ q) → ∼q

T

T

F

T

F

F

T

F

F

F

T

T

F

T

T

T

F

F

F

F

T

T

T

T

Final column: F, T, F, T

Exercise 8: ∼p ∨ q → r (3 variables: p, q, r)

We need 8 rows. Let's reason:

∼p ∨ q → r is false only when:

  1. ∼p ∨ q is true AND

  2. r is false

∼p ∨ q is true unless ∼p=F and q=F, i.e., unless p=T and q=F.

So the statement is false when:

  • r = F AND NOT(p=T and q=F)

  • Wait, careful: We need (∼p ∨ q)=T AND r=F.

Let's find rows where r=F (last 4 rows of standard ordering), and check if ∼p ∨ q is T:

p

q

r

∼p

∼p ∨ q

→ r?

T

T

F

F

T

F

T

F

F

F

F

T

(Here antecedent is F, so → is T)

F

T

F

T

T

F

F

F

F

T

T

F

So false in rows 1, 5, 7 (if we count from 1: TTF, FTF, FFF with r=F).

Part 4: Logical Equivalences with Conditionals (Exercises 12-14)

Exercise 12: Rewrite using p ∨ q → r ≡ (p → r) ∧ (q → r)

  • Statement: "If x > 2 or x < -2, then x² > 4."

  • Let p = "x > 2", q = "x < -2", r = "x² > 4"

  • By equivalence: (p → r) ∧ (q → r)

  • Answer: "If x > 2 then x² > 4, and if x < -2 then x² > 4."

Exercise 13a: Prove p → q ≡ ∼p ∨ q with truth table.

p

q

p → q

∼p

∼p ∨ q

T

T

T

F

T

T

F

F

F

F

F

T

T

T

T

F

F

T

T

T

Last two columns match ✓.

Exercise 13b: Prove ∼(p → q) ≡ p ∧ ∼q

  • p → q is false only when p=T, q=F.

  • So ∼(p → q) is true only when p=T, q=F.

  • p ∧ ∼q is true only when p=T, q=F.

  • ✓ They match.

Part 5: Contrapositive, Converse, Inverse (Exercises 22-23)

Rules:

  • Contrapositive of p → q is ∼q → ∼p (EQUIVALENT!)

  • Converse of p → q is q → p (NOT equivalent)

  • Inverse of p → q is ∼p → ∼q (NOT equivalent, but same as converse!)

Exercise 20a: "If P is a square, then P is a rectangle."

  • p = "P is a square", q = "P is a rectangle"

  • Original: p → q

Exercise 22a (Contrapositive):

  • ∼q → ∼p

  • Answer: "If P is not a rectangle, then P is not a square."

Exercise 23a (Converse & Inverse):

  • Converse: q → p = "If P is a rectangle, then P is a square." (False!)

  • Inverse: ∼p → ∼q = "If P is not a square, then P is not a rectangle." (False!)

Part 6: Necessary & Sufficient Conditions (Exercises 40-45)

CRITICAL VOCAB:

  • "R is sufficient for S" means R → S

  • "R is necessary for S" means S → R (reversed!)

  • "R only if S" means R → S

Exercise 40: "Catching the 8:05 bus is a sufficient condition for my being on time."

  • R = "I catch the 8:05 bus", S = "I am on time"

  • Sufficient = R → S

  • Answer: If I catch the 8:05 bus, then I am on time.

Exercise 42: "Being divisible by 3 is a necessary condition for this number to be divisible by 9."

  • R = "number divisible by 3", S = "number divisible by 9"

  • Necessary = S → R

  • Answer: If this number is divisible by 9, then it is divisible by 3.

Exercise 44: "A sufficient condition for Jon's team to win is that it win the rest of its games."

  • R = "team wins rest of games", S = "team wins championship"

  • Sufficient = R → S

  • Answer: If Jon's team wins the rest of its games, then it wins the championship.

Part 7: Tricky Translations (Exercises 46)

Given: "If compound X is boiling, then its temperature ≥ 150°C" = B → T

Which must be true?

  • a. T → B (Converse) → Not necessarily true.

  • b. ∼T → ∼B (Contrapositive of converse) → Not necessarily.

  • c. "X boils only if T ≥ 150" = B → T (This is the original! Yes, true.)

  • d. ∼B → ∼T (Inverse) → Not necessarily.

  • e. "T ≥ 150 is necessary for boiling" = B → T ✓ (Wait, careful: "Necessary" reverses! Actually, "T ≥ 150 is necessary for B" means B → T? Let's check: If T≥150 is necessary for boiling, then you can't boil without T≥150, so B → T. Yes!)

  • f. "T ≥ 150 is sufficient for boiling" = T → B (Not necessarily true.)

Answers: c and e are logically equivalent to the original.

Part 8: "Unless" Statements (Exercises 37-39)

Definition: "r unless s" means if ∼s then r = ∼s → r

Exercise 37: "Payment will be made on the fifth unless a new hearing is granted."

  • r = "Payment on the fifth", s = "new hearing is granted"

  • "r unless s" = ∼s → r

  • Answer: If a new hearing is not granted, then payment will be made on the fifth.

Exercise 39: "This door will not open unless a security code is entered."

  • Tricky! Rephrase: "The door opens only if a code is entered" = "If door opens, then code entered."

  • Let O = "door opens", C = "code entered"

  • Original says: Door will not open unless C = ∼C → ∼O (if no code, then no open)

  • Contrapositive: O → C = "If door opens, then code was entered."

Quiz Prep Summary:

  1. p → q is false only when p=T, q=F.

  2. Contrapositive ∼q → ∼p is equivalent. Converse/inverse are not.

  3. Translation rules:

    • "q if p" = p → q

    • "p only if q" = p → q

    • "p unless q" = ∼q → p

    • "q is necessary for p" = p → q

    • "q is sufficient for p" = q → p

  4. Negation: ∼(p → q) ≡ p ∧ ∼q

  5. Equivalence: p → q ≡ ∼p ∨ q

2.3. CHAPTER Key Definitions & Concepts

  • Argument: A sequence of statements (premises) leading to a conclusion.

  • Valid Argument: If the premises are all true, the conclusion must be true. (It's about form, not truth.)

  • Invalid Argument: It's possible for all premises to be true but the conclusion false.

  • Sound Argument: A valid argument with all true premises (so conclusion is guaranteed true).

  • Premises: The "given" statements (facts, assumptions).

  • Conclusion: The statement you're trying to prove from the premises.

3. Major Theorems & Formulas (Valid Argument Forms)

These are rules you can always trust:

  1. Modus Ponens (The most common)

    • Form: p → q, p, ∴ q

    • Example: "If it rains, ground is wet. It's raining. ∴ Ground is wet."

  2. Modus Tollens

    • Form: p → q, ∼q, ∴ ∼p

    • Example: "If dog, then mammal. Not a mammal. ∴ Not a dog."

  3. Transitivity (Hypothetical Syllogism)

    • Form: p → q, q → r, ∴ p → r

    • Example: "If study, pass. If pass, graduate. ∴ If study, graduate."

  4. Elimination

    • Form: p ∨ q, ∼q, ∴ p (or p ∨ q, ∼p, ∴ q)

    • Example: "Pizza or burger. No burger. ∴ Pizza."

  5. Division into Cases

    • Form: p ∨ q, p → r, q → r, ∴ r

    • Example: "Rain or shine. If rain, game indoors. If shine, game indoors. ∴ Game indoors."

  6. Contradiction Rule

    • Form: ∼p → (contradiction), ∴ p

    • Example: "Assume no solution. Leads to impossible result. ∴ There is a solution."

Watch out for these INVALID forms (common errors):

  • Converse Error: p → q, q, ∴ p (WRONG!)

  • Inverse Error: p → q, ∼p, ∴ ∼q (WRONG!)

Simple test for validity: Imagine a world where all premises are true. In that world, could the conclusion possibly be false? If yes, argument is invalid. If no, it's valid.

PRACTICE

Part 1: Fill in the Blanks (Modus Ponens/Tollens)

Rule:

  • Modus Ponens: p → q, p, ∴ q

  • Modus Tollens: p → q, ∼q, ∴ ∼p

1.

  • Premise 1: If √2 is rational, then √2 = a/b for some integers.

  • Premise 2: It is NOT true that √2 = a/b for integers.

  • Use Modus Tollens: If p → q and ∼q, then ∼p.

  • Conclusion: √2 is not rational.

2.

  • Premise 1: If (1-0.999...) < every positive real, then it equals 0.

  • Conclusion given: (1-0.999...) = 0.

  • This is Modus Ponens! Missing premise must be the hypothesis.

  • Fill blank: "1 - 0.999... is less than every positive real number."

3.

  • Premise 1: If logic is easy, I'm a monkey's uncle.

  • Premise 2: I'm not a monkey's uncle.

  • Modus Tollens: ∼q → ∼p

  • Conclusion: Logic is not easy.

4.

  • Premise 1: If quadrilateral → interior angles = 360°

  • Premise 2: Sum is not 360°

  • Modus Tollens: ∼q → ∼p

  • Conclusion: This figure is not a quadrilateral.

5.

  • Premise 1: If unsure → would have telephoned.

  • Conclusion: They were sure (∼unsure).

  • This is Modus Tollens conclusion (∼q → ∼p).

  • Missing premise must be ∼q: "They did not telephone."

Part 2: Truth Tables for Validity (Exercises 6-11)

Key method: Build truth table. Look for any row where all premises are True but conclusion is False. If such a row exists → INVALID. If no such row → VALID.

Exercise 6:

Premises: p → q, q → p
Conclusion: p ∨ q

Let's test quickly:

p

q

p→q

q→p

Premises both T?

p∨q (Conclusion)

T

T

T

T

T

T

T

F

F

T

F

T

F

T

T

F

F

T

F

F

T

T

T

F

Row 4: Premises both T, conclusion F → INVALID.

Exercise 7:

Premises: p, p → q, ∼q ∨ r
Conclusion: r

Test dangerous case: make conclusion r = F, see if premises can all be T.
If r = F, then ∼q ∨ r = ∼q ∨ F = ∼q. So for premise 3 to be T, ∼q must be T → q = F.
If q = F and p = T, then p → q = T → F = F (premise 2 fails).
So impossible to have all premises T with r = F. Therefore VALID.

Part 3: Recognizing Common Errors (Exercise 12)

a. Converse Error:

  • Form: p → q, q, ∴ p

  • Example: "If dog → mammal. This is mammal. ∴ This is dog." (Wrong! Could be cat.)

  • INVALID - truth table will show counterexample.

b. Inverse Error:

  • Form: p → q, ∼p, ∴ ∼q

  • Example: "If raining → ground wet. Not raining. ∴ Ground not wet." (Wrong! Sprinklers could be on.)

  • INVALID - truth table will show counterexample.

Part 4: Identifying Valid Forms (Exercises 24-32)

Rule: Name the valid form if valid; if invalid, say "converse error" or "inverse error."

24.

  • Premise 1: If correct → answer 2

  • Premise 2: answer 2

  • Conclusion: correct

  • This is converse error! p → q, q, ∴ p ❌

25.

  • Premise 1: rational ∨ irrational

  • Premise 2: not rational

  • Conclusion: irrational

  • Valid! Elimination form: p ∨ q, ∼p, ∴ q ✅

26.

  • Premise 1: movies → no homework

  • Premise 2: no homework → do poorly

  • Conclusion: movies → do poorly

  • Valid! Transitivity: p → q, q → r, ∴ p → r ✅

27.

  • Premise 1: if >2 → square >4

  • Premise 2: not >2

  • Conclusion: square not >4

  • Inverse error! p → q, ∼p, ∴ ∼q ❌ (Number could be -3: not >2, but square=9 >4)

28.

  • Premise 1: if as many rationals as irrationals → infinite irrationals

  • Premise 2: infinite irrationals

  • Conclusion: as many rationals as irrationals

  • Converse error! ❌

31.

  • Premise: Java ∧ C++

  • Conclusion: C++

  • Valid! Specialization: p ∧ q, ∴ q ✅

Part 5: Deduction Proofs (Exercises 41-44)

These are step-by-step proofs using the valid forms. Let's do 41 as example:

Given:
a. ∼p ∨ q → r
b. s ∨ ∼q
c. ∼t
d. p → t
e. ∼p ∧ r → ∼s
Prove: ∼q

Proof:

  1. From (d) p → t and (c) ∼t, by Modus Tollens: ∼p (step 1)

  2. From step 1 (∼p) and (a) ∼p ∨ q → r:
    ∼p ∨ q is true (since ∼p is true), so by Modus Ponens: r (step 2)

  3. From step 1 (∼p) and step 2 (r): ∼p ∧ r is true.

  4. From step 3 and (e) ∼p ∧ r → ∼s, by Modus Ponens: ∼s (step 4)

  5. From (b) s ∨ ∼q and step 4 (∼s), by Elimination: ∼q ✓

Part 6: The Treasure Hunt (Exercise 37) - Fun Logic Puzzle

Statements:
a. If house next to lake → treasure not in kitchen.
b. If tree is elm → treasure in kitchen.
c. House next to lake.
d. Elm tree ∨ treasure under flagpole.
e. If oak in back → treasure in garage.

Solve:

  1. From (c) and (a), by Modus Ponens: treasure not in kitchen.

  2. From (b) and "not in kitchen", by Modus Tollens: tree is not elm.

  3. From (d) "Elm ∨ flagpole" and "not elm", by Elimination: treasure under flagpole.

  4. (e) about oak is irrelevant since we found location.

  • Treasure is under the flagpole.

Part 7: Knights and Knaves (Exercise 38a)

Island rule: Knights tell truth, Knaves lie.

a. A says: "Both of us are knights."
B says: "A is a knave."

  • Test if A is knight: Then his statement "Both knights" is true → B is knight too. But then B (knight) says "A is knave" would be true → contradiction (A would be knave).

  • So A cannot be knight → A is knave.

  • Since A is knave, his statement "Both knights" is false. So B must be knave too (because A is already knave, "both knights" false).

  • Check B: B (knave) says "A is knave" - that's actually true! Knave can't tell truth → contradiction?
    Wait, careful: If A is knave, B says "A is knave" (true). If B is knight, that's fine. But we found from A's statement that if A is knave, "both knights" is false automatically regardless of B. So B could be knight or knave.

Let's solve properly:
Case 1: A knight → both knights → B knight → B says "A knave" false but B knight must tell truth → impossible.
Case 2: A knave → A's statement false → not both knights → B could be knight or knave.
If B knight: B says "A knave" (true) ✓ possible.
If B knave: B says "A knave" (true) but knave lying → impossible.
So A = knave, B = knight.