Unit1 - Subjective Questions

Truth Table Construction:

Conclusion:
Since the last column contains only True (T) values for all possible assignments of truth values to and , the proposition is a Tautology.

1. Tautology:
A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it.

• Example: $p \lor
  eg p$ (Law of Excluded Middle).

2. Contradiction:
A compound proposition that is always false.

• Example: $p \land
  eg p$.

3. Contingency:
A compound proposition that is neither a tautology nor a contradiction (it can be true or false depending on the variables).

• Example: (True if , False if ).

Statement of De Morgan's Laws:

1. $
   eg (p \land q) \equiv
   eg p \lor
   eg q$
2. $
   eg (p \lor q) \equiv
   eg p \land
   eg q$

Proof for First Law ($
eg (p \land q) \equiv
eg p \lor
eg q$):

Since columns 4 and 7 are identical, the logical equivalence holds.

Derivation:

Conclusion: The statement is proven.

Universal Quantifier ():

• Denoted by , it asserts that is true for every element in the domain.
• English phrases: "for all", "for every", "for each".

Existential Quantifier ():

• Denoted by , it asserts that is true for at least one element in the domain.
• English phrases: "there exists", "for some", "there is at least one".

Translation:

• Let denote " is a student in this class".
• Let denote " has studied Calculus".
• Notation: (Assuming the domain is all people).
• Alternative: If the domain is restricted to "Students in this class", then: .

Step-by-Step Negation:

1. Original: $
   eg [\forall x \exists y (P(x, y) \to Q(x, y))]$
2. Apply De Morgan's Law for quantifiers (change to ):
   $\exists x
   eg [\exists y (P(x, y) \to Q(x, y))]$
3. Apply De Morgan's Law for quantifiers again (change to ):
   $\exists x \forall y
   eg (P(x, y) \to Q(x, y))$
4. Negate the implication (Recall $
   eg(A \to B) \equiv A \land
   eg B$):
   $\exists x \forall y (P(x, y) \land
   eg Q(x, y))$

Final Answer:

Proof:

1. Assumption: Assume that is an odd integer.
2. Definition: By definition of odd integers, there exists an integer such that .
3. Squaring: We need to examine .
   
   
   
4. Factorization: We can factor out 2 from the first two terms:
   
5. Conclusion: Let . Since is an integer, is also an integer. Therefore, .
6. By the definition of odd integers, is odd.

Q.E.D.

Structure of Contraposition:
To prove , we prove $
eg q \to
eg p$.

• : is odd.
• : is odd.
• $
  eg qn$ is even.
• $
  eg p3n + 2$ is even.

Proof:

1. **Assume $
   eg qn$ is an even integer.
2. Definition: By definition, for some integer .
3. Substitution: Substitute into the expression :
   
   
   
4. Factorization: Factor out 2:
   
5. Conclusion: Let , which is an integer. Thus . This means is even.
6. We have shown that if is even, then is even. Therefore, by contraposition, if is odd, then is odd.

Q.E.D.

1. Vacuous Proof:

• Used to prove an implication when the hypothesis is known to be false.
• Since is always true regardless of , the statement holds.
• Example: Prove "If , then ". Since is false, the implication is vacuously true.

2. Trivial Proof:

• Used to prove an implication when the conclusion is known to be true.
• Since is always true regardless of , the statement holds.
• Example: Prove "If it rains today, then ". Since is always true, the implication is trivially true.

Proof:

1. Assumption (Negation): Assume is rational.
2. Definition: There exist integers and ($b
   eq 0\sqrt{2} = \frac{a}{b}\gcd(a, b) = 1$).
3. Algebraic Manipulation:
   
4. Inference 1: Since , is even. If is even, then must be even (proven previously). So, let for some integer .
5. Substitution: Substitute back into the equation:
   
   
   
   
   
6. Inference 2: Since , is even, which implies is even.
7. Contradiction: We concluded that both and are even. This means they share a common factor of 2. However, we initially assumed that (simplest form).
8. Conclusion: The assumption leads to a contradiction. Therefore, is irrational.

Q.E.D.

Proof using Truth Table:

Explanation:
Comparing the column for and $
eg p \lor q$, the truth values are identical in every row. Therefore, the statements are logically equivalent.

$p \to q \equiv
eg p \lor q$

Definition:
A counterexample is a specific instance or case in the domain of a universal quantification () for which the statement is false. Finding just one counterexample is sufficient to disprove a universal statement.

Disproof of the statement:

• Statement: is prime for all .
• Let's test .
• Substitute :
  
  
  
• Analysis: is a composite number (divisible by 41 and 43), not a prime number.
• Conclusion: Since is not prime, the universal statement is false.

Method Description:
Proof by cases involves breaking the domain into distinct categories (cases) that cover all possibilities and proving the statement for each case individually.

Proof:

We divide the real numbers into two cases: and .

• Case 1:
  By definition of absolute value, if , then .
  Since , it follows that .

• Case 2:
  By definition of absolute value, if , then .
  Since is negative, is positive. Therefore, , which implies .

Conclusion:
In both cases, . Since these cases cover all real numbers, the statement is true.

Strategy:
To prove a biconditional statement ("p if and only if q"), we must prove two separate implications:

1. (Necessity)
2. (Sufficiency)

Proof:

• Part 1: If is odd, then is odd ().

  • Assume .
  • .
  • is in the form , so is odd.

• Part 2: If is odd, then is odd ().

  • We use contraposition: Prove "If is even, then is even".
  • Assume .
  • .
  • is in the form , so is even.
  • Since the contrapositive is true, the original implication ( odd odd) is true.

Conclusion: Since both directions hold, is odd iff is odd.

Common Mistakes: Arithmentic errors, circular reasoning (begging the question), and logical fallacies.

1. Affirming the Consequent:

• Logic: .
• Error: Assuming that if the conclusion is true, the hypothesis must be true. This is invalid.
• Example: "If I have the flu (), I have a fever (). I have a fever (). Therefore, I have the flu ()." (Incorrect, fever could be from infection).

2. Denying the Antecedent:

• Logic: $((p \to q) \land
  eg p) \to
  eg q$.
• Error: Assuming that if the hypothesis is false, the conclusion must be false.
• Example: "If it barks (), it is a dog (). It does not bark ($
  eg p
  eg q$)." (Incorrect, some dogs don't bark/basenji).

Proof Strategy:
This often relies on the Rational Root Theorem or contradiction properties of integers.

Proof by Contradiction:

1. Assume there exists a rational root in lowest terms (, ).
2. .
3. Analysis of Parity (Odd/Even):
   • Case 1: and are both odd. Sum of three odd numbers is odd ($a^3+ab^2+b^3
     eq 0$). Contradiction.
   • Case 2: is even, is odd. (even) + (even) + (odd) = Odd. Contradiction.
   • Case 3: is odd, is even. (odd) + (even) + (even) = Odd. Contradiction.
   • Case 4: and are even. Impossible as .
4. Conclusion: In all cases, cannot equal 0. Therefore, no such rational number exists.

Definitions:

• Constructive Existence Proof: Demonstrates the existence of an element such that is true by finding a specific example or providing a method to construct it.
• Non-constructive Existence Proof: Proves that such an must exist (usually by contradiction or intermediate value theorem) without explicitly identifying the element.

Example of Constructive Proof:

• Statement: Prove there exists a positive integer that can be written as the sum of cubes of positive integers in two different ways.
• Proof: Consider the number 1729.
  
  
  
  
  We have explicitly found the number 1729, proving the existence.

Definition:
A uniqueness proof shows that there is exactly one element satisfying a property . It involves two steps: Existence (there is an ) and Uniqueness (if also satisfies it, ).

Proof:

1. Existence: Let . Since $x
   eq 0$, $\frac{1}{x}x(\frac{1}{x}) = 1$. So, a solution exists.
2. Uniqueness: Suppose there are two numbers and such that and .
   We have .
   Since $x
   eq 0x\frac{1}{x}$).
   
3. Conclusion: Since any other solution must equal , the solution is unique.

Translation:
Let:

• : It rains.
• : I go to the park.
• : I study.

Premises:

1. If it rains, I will not go to the park: $p \to
   eg q$
2. If I do not go to the park, I will study: $
   eg q \to r$

Conclusion:

• Therefore, if it rains, I will study:

Validity Check:
This argument follows the rule of Hypothetical Syllogism:

Since Hypothetical Syllogism is a valid inference rule (tautology), the argument is Valid.

Proof:

1. Assumptions: Let and be two rational numbers.
2. Definition: By definition of rational numbers:
   for integers with $q
   eq 0$.
   for integers with $s
   eq 0$.
3. Operation: Consider the sum :
   
4. Simplification: Find a common denominator:
   
5. Closure Properties: Since are integers, , , and are integers. Consequently, the numerator is an integer, and the denominator is a non-zero integer (since $q
   eq 0s
   eq 0$).
6. Conclusion: Since can be expressed as a ratio of two integers with a non-zero denominator, is rational.

Q.E.D.