Midterm_notes

2.3 The Disjunction and Conjunction of Statements

• The disjunction of statements P and Q is expressed as "P or Q" and is denoted by P v Q.

  • The disjunction P v Q is true if at least one of P or Q is true.

  • It is false only when both P and Q are false.

• If it is not possible for both statements to be true (e.g., "n is even or n is odd"), this scenario is referred to as exclusive or (XOR).

• The conjunction of the statements P and Q is expressed as "P and Q" and is denoted by P ^ Q.

  • The conjunction P ^ Q is true if both P and Q are true.

  • It is false if at least one of P and Q is false.

2.3.1 Example

• Let:

  • P: 3 is odd

  • Q: 57 is prime

• Here, P v Q is true because P is true.

• However, P ^ Q is false because Q is false.

2.4 The Implication

• For statements P and Q, the implication (or conditional) is the statement "If P, then Q" or "P implies Q" and is denoted by P ⇒ Q.

  • P is the hypothesis or premise, while Q is the conclusion.

  • The implication P ⇒ Q is false only when P is true and Q is false.

Example

• Let:

  • P: 3 is odd

  • Q: 57 is prime

• The implication P ⇒ Q: If 3 is odd, then 57 is prime is false, as P is true but Q is false.

• Conversely, Q ⇒ P: If 57 is prime, then 3 is odd is a true statement because P is true.

2.4.1 Expressions for Implication

• The implication P ⇒ Q can also be expressed in other ways:

  • "Q if P"

  • "P only if Q"

  • "P is sufficient for Q"

  • "Q is necessary for P"

Example: Constructing a Truth Table

• For statements P and Q, construct a truth table for (P ⇒ Q) ⇒ (~P).

2.5 More on Implications

• Consider the open sentences P(x): x=-3 and Q(x): |x|=3.

• We can form other open sentences:

  • ~P(x): x ≠ -3

  • P(x) v Q(x): x=-3 or |x|=3

  • P(x) ^ Q(x): x=-3 and |x|=3

  • P(x) ⇒ Q(x): If x=-3, then |x|=3.

Example

• For x = -3,

  • ~P(-3) is false.

  • P(-3) v Q(-3) and P(-3) ^ Q(-3) are both true.

  • However, P(3) v Q(3) is true while P(3) ^ Q(3) is false since P(3) is false.

2.6 The Biconditional

• The biconditional for statements P and Q combines P ⇒ Q and Q ⇒ P.

• It is denoted as P ⇔ Q and means that both statements are true simultaneously.

• The biconditional P ⇔ Q is expressed as:

  • "P if and only if Q"

  • "P is equivalent to Q"

• This statement is only true when P and Q have the same truth value.

Example

• Let:

  • P: 3 is odd

  • Q: 57 is prime

• The biconditional "3 is odd if and only if 57 is prime" is false since its parts have differing truth values.

2.7 Tautologies and Contradictions

• The symbols ~, v, ^, ⇒, and ⇔ are called logical connectives.

• A compound statement is formed by combining component statements using at least one logical connective.

• A compound statement is a tautology if it is true for all possible combinations of truth values of its components.

Example

• The statement P v (~P) is a tautology:

• Conversely, a compou...

2.8 Logical Equivalence

• Two compound statements R and S are logically equivalent if they have the same truth values for all possible combinations of truth values of their components. This is denoted by R = S.

Example of Logical Equivalence

• (P ^ Q) = (Q ^ P)

• (P ⇒ Q) = (~P v Q)

2.9 Fundamental Properties of Logical Equivalence

• Commutative Laws:

  • P v Q = Q v P

  • P ^ Q = Q ^ P

• Associative Laws:

  • P v (Q v R) = (P v Q) v R

  • P ^ (Q ^ R) = (P ^ Q) ^ R

2.10 Quantified Statements

• Adding quantifiers to open sentences results in quantified statements.

• The universal quantifier (for all) is denoted by ∀:

  • For all x in S, P(x)

• The existential quantifier (there exists) is denoted by ∃:

  • There exists x in S such that P(x).

• The truth of a quantified statement depends on the truth of the underlying open sentence for respective components.

2.11 Direct Proofs

A direct proof is a method of proving a statement by straightforward logical deductions from accepted truths or previously established statements. In a direct proof, the conclusion is reached by a chain of logical implications from the hypothesis.

Example

To prove that if n is an even integer, then n^2 is even:

• Assume n is even (there exists an integer k such that n = 2k).

• Therefore, n^2 = (2k)^2 = 4k^2 = 2(2k^2), which is also even.

2.12 Trivial Proofs

A trivial proof occurs when the conclusion follows immediately from the hypothesis. In these cases, the statement is straightforward and requires minimal justification.

Example

To prove that if P is true, then Q is true when Q is inherently true (regardless of P).

Statement

If it rains, then 2 + 2 = 4. Since the conclusion is always true, the proof is considered trivial.

2.13 Vacuous Proofs

A vacuous proof is a special type of proof that occurs when the hypothesis of an implication is false. In this case, the implication is considered true regardless of the truth value of the conclusion.

Example

To prove that if x > 5, then x^2 < 0:

• Here, the hypothesis x > 5 is false because x cannot be simultaneously greater than 5 and have a square less than 0. Therefore, the implication is vacuously true.