AOS1 Topic 1: Logic and Proof


1. Propositional Logic

Propositional logic deals with statements that can be true or false, using logical operators.

Propositional logic deals with propositions or statements that can be either true or false. These propositions are represented by variables such as \(P\), \(Q\), \(R\), etc., and logical operators are used to combine or manipulate these propositions to form compound statements.


Propositional Logic and Logical Operators

Propositional logic deals with propositions or statements that can be either true or false. Logical operators are used to form compound statements.

Logical Operators:

  • AND (\(\land\)): Represents conjunction, where both statements must be true for the compound statement to be true.
  • OR (\(\lor\)): Represents disjunction, where at least one of the statements must be true for the compound statement to be true.
  • NOT (\(\lnot\)): Represents negation, where the statement is reversed (true becomes false, false becomes true).
  • IMPLICATION (\(\rightarrow\)): Represents implication, where \(P \rightarrow Q\) is true unless \(P\) is true and \(Q\) is false.
  • BICONDITIONAL (\(\leftrightarrow\)): Represents biconditional or equivalence, where \(P \leftrightarrow Q\) is true if both \(P\) and \(Q\) have the same truth value.


Example: Let \(P\) be "It is raining" and \(Q\) be "I will take an umbrella."

\[ P \land Q \text{ (AND)} \]

\[ P \lor Q \text{ (OR)} \]

\[ \lnot P \text{ (NOT)} \]

\[ P \rightarrow Q \text{ (IMPLICATION)} \]

\[ P \leftrightarrow Q \text{ (BICONDITIONAL)} \]

These logical operators are fundamental in constructing compound statements and analyzing their truth values.


Types of Propositional Logic:

  1. Conjunction (AND): denoted by \(\land\), represents the conjunction of two propositions where both must be true for the compound statement to be true.
  2. Disjunction (OR): denoted by \(\lor\), represents the disjunction of two propositions where at least one must be true for the compound statement to be true.
  3. Negation (NOT): denoted by \(\lnot\), represents the negation or opposite of a proposition.
  4. Implication (IF-THEN): denoted by \(\rightarrow\), represents the implication where one proposition implies another.
  5. Biconditional (IF AND ONLY IF): denoted by \(\leftrightarrow\), represents the biconditional or equivalence between two propositions.

These types of propositional logic are fundamental in constructing logical statements and reasoning about their truth values based on the truth values of their components.


2. Predicate Logic

Predicate logic extends propositional logic with variables, predicates, and quantifiers.

Example: For all real numbers \(x\), if \(x\) is positive, then \(x^2\) is positive: \(\forall x \in \mathbb{R}, \, (x > 0 \rightarrow x^2 > 0)\).


3. Inductive Logic

Inductive logic involves reasoning from specific instances to general conclusions, often used in mathematical induction.

Example (Mathematical Induction): Prove that \(\sum_{i=1}^n i = \frac{n(n+1)}{2}\) for all natural numbers \(n\).


4. Deductive Logic

Deductive logic derives conclusions from general principles, commonly used in formal proofs.



What is Proof?

A mathematical proof is an argument that confirms the truth of a mathematical statement. It shows that a list of stated assumptions will guarantee a conclusion.

For example, consider the following simple claim involving even and odd numbers.

Assumption Conclusion
If m and n are odd integers then m + n is an even integer

Proof:

Assume that both \( m \) and \( n \) are odd integers. Then \( m = 2a + 1 \) and \( n = 2b + 1 \), for integers \( a \) and \( b \).

Therefore,

\[ m + n = (2a + 1) + (2b + 1) \] \[ = 2a + 2b + 2 \] \[ = 2(a + b + 1) \] \[ = 2k \]

where \( k = a + b + 1 \) is an integer. Hence \( m + n \) is even.



Proof Techniques

Divisibility

Let \( a \) and \( b \) be integers. Then we say that \( a \) is divisible by \( b \) if there exists an integer \( k \) such that \( a = kb \). In this case, we also say that \( b \) is a divisor of \( a \).

Note: Alternatively, we can say that \( a \) is a multiple of \( b \) and that \( b \) is a factor of \( a \).

For example:

  • 12 is divisible by 3, since \( 12 = 4 \times 3 \)
  • \(-6\) is divisible by 2, since \( -6 = -3 \times 2 \)
  • 0 is divisible by any integer \( n \), since \( 0 = 0 \times n \).

On the other hand, the integer 14 is not divisible by 3. In this case, the best we can write is

14 = 4 × 3 + 2

We say that 14 leaves a remainder of 2 when divided by 3. More generally, we have the following important result.



Euclidean Division

If \( a \) and \( b \) are integers with \( b \neq 0 \), then there are unique integers \( q \) and \( r \) such that

$$ a = qb + r $$

where \( 0 \leq r < |b| \)

Note: Here \( q \) is the quotient and \( r \) is the remainder when \( a \) is divided by \( b \).



Conditional Statements and Direct Proof

The statement proved in Example 1 can be broken down into two parts:


Statement: If \( n \) is an integer then \( n^3 - n \) is divisible by 3.

This is an example of a conditional statement and has the form:


Statement: If \( P \) is true then \( Q \) is true.

This can be abbreviated as \( P \Rightarrow Q \), which is read as ‘\( P \) implies \( Q \)’. We call \( P \) the hypothesis and \( Q \) the conclusion.

To give a direct proof of a conditional statement \( P \Rightarrow Q \), we assume that the hypothesis \( P \) is true, and then show that the conclusion \( Q \) follows.



The negation of a statement

To negate a statement \( P \) we write its very opposite, which we call ‘not \( P \)’. Negation turns a true statement into a false statement, and a false statement into a true statement.


Statement: The sum of any two odd numbers is even. (true)


Negation: There are two odd numbers whose sum is odd. (false)

Negating statements that involve ‘and’ and ‘or’ requires the use of De Morgan’s laws.



De Morgan’s laws

  • not (P and Q) is the same as (not P) or (not Q)
  • not (P or Q) is the same as (not P) and (not Q)

For example, we can use the second law to negate the following statement about integers \( a \) and \( b \):

Statement: \( a \) is odd or \( b \) is odd

Negation: \( a \) is even and \( b \) is even

Note: When negating a statement involving variables, it helps to know the set that each variable takes its value from. For example, if we know that \( a \) is an integer, then the negation of ‘\( a \) is odd’ is ‘\( a \) is even’.



Proof by Contrapositive:

Consider this statement about an integer \( n \):

Statement: If \( n^2 + 2n \) is odd, then \( n \) is odd.

By switching the hypothesis and the conclusion and negating both, we obtain the contrapositive statement:

Contrapositive: If \( n \) is even, then \( n^2 + 2n \) is even.

Note that a conditional statement and its contrapositive are always logically equivalent:

  • If the original statement is true, then the contrapositive is true.
  • If the original statement is false, then the contrapositive is false.

This means that to prove a conditional statement, we can instead prove its contrapositive. This is helpful, as it is often easier to prove the contrapositive than the original statement.

  • The contrapositive of \( P \Rightarrow Q \) is the statement \( \neg Q \Rightarrow \neg P \).
  • To prove \( P \Rightarrow Q \), we can prove the contrapositive instead.



Proof by Contradiction:

The basic outline of a proof by contradiction is:

  • Assume that the statement we want to prove is false.
  • Show that this assumption leads to mathematical nonsense.
  • Conclude that we were wrong to assume that the statement is false.
  • Conclude that the statement must be true.



    • Proof by Induction:

    A proof by induction of \( P(n) \), a mathematical statement involving a value \( n \), involves these main steps:

  • Prove directly that \( P \) is correct for the initial value of \( n \) (for most examples you will see this is zero or one). This is called the base case.
  • Assume for some value \( k \) that \( P(k) \) is correct. This is called the induction hypothesis. We will now prove directly that \( P(k) \Rightarrow P(k + 1) \). That means prove directly that \( P(k + 1) \) is correct by using the fact that \( P(k) \) is correct. This is called the induction step.

    • The combination of these steps shows that \( P(n) \) is true for all values of \( n \).



    The converse of a conditional statement:

    Consider this statement about integers \( m \) and \( n \):

    Statement: If \( m \) and \( n \) are odd then \( m + n \) is even. (true)

    By switching the hypothesis and the conclusion, we obtain the converse statement:

    Converse: If \( m + n \) is even then \( m \) and \( n \) are odd. (false)

    The converse of a true statement may not be true. When we switch the hypothesis and the conclusion of a conditional statement, \( P \Rightarrow Q \), we obtain the converse statement, \( Q \Rightarrow P \).



    Equivalent statements:

    Now consider the following two statements about a particular triangle:

    P: The triangle has three equal sides.

    Q: The triangle has three equal angles.

    Both \( P \Rightarrow Q \) and its converse \( Q \Rightarrow P \) are true statements. In this case, we say that \( P \) and \( Q \) are equivalent statements. We write \( P \Leftrightarrow Q \).

    We can also say that \( P \) is true if and only if \( Q \) is true. So in the above example, we can say that a triangle has three equal sides if and only if it has three equal angles.

    To prove that two statements \( P \) and \( Q \) are equivalent, you have to prove two things: \( P \Rightarrow Q \) and \( Q \Rightarrow P \).

    Example 1

    Direct proof:

    Prove that the product of two even numbers is also even.

    Let \( a \) and \( b \) be even numbers. Therefore, \( a = 2m \) and \( b = 2n \), where \( m \) and \( n \) are integers.

    \( a \times b = 4mn = 2(2mn) \)

    Because \( 2 \), \( m \), and \( n \) are all integers, their product is also an integer. Let \( 2mn = k \).

    Therefore, \( a \times b = 2(2mn) = 2k \), where \( k \) is an integer.

    Therefore, \( a \times b \) is even as required.

    Proof by contradiction:

    Prove that the sum of a rational number and an irrational number is also irrational.

    Let a be a rational number, and b be an irrational number.

    Let a = \( \frac{p}{q} \)

    Assume \( a + b = c \) is a rational number, and let \( c = \frac{m}{n} \)

    Therefore, \( b = c - a = \frac{m}{n} - \frac{p}{q} = \frac{mq - pn}{nq} \), which suggests \( b \) can be expressed as a fraction.

    But \( b \) is irrational and therefore cannot be expressed as a fraction, leading to a contradiction.

    Therefore, the sum of a rational number and an irrational number must be irrational.

    Proof by contrapositive:

    Sometimes it is easier to prove the statement's contrapositive rather than the statement itself.

    Prove that if \( n^2 \) is odd, then n is odd.

    We will use the contrapositive to prove this statement.

    Contrapositive of if p => q is ~q => ~p

    If n is even, then \( n^2 \) is also even.

    Since n is even, \( n = 2m \), where m is an integer

    Therefore, \( n^2 = (2m)^2 = 4m^2 = 2(2m^2) \)

    Therefore, \( n^2 = 2k \), where k is an integer

    Therefore, if n is even, then \( n^2 \) is also even. This implies that if \( n^2 \) is odd, then n is odd.

    Example 2

    Divisibility of integers

    Let \( n \in \mathbb{Z} \). Prove that \( n^3 - n \) is divisible by 3.

    Solution

    Note that \( n^3 - n = n(n - 1)(n + 1) \).

    When the integer \( n \) is divided by 3, the remainder must be 0, 1, or 2. Therefore, \( n \) can be written in the form \( 3k \), \( 3k + 1 \), or \( 3k + 2 \), for some integer \( k \).

    Case 1: \( n = 3k \). Then \( n^3 - n = n(n - 1)(n + 1) = 3k(3k - 1)(3k + 1) \).

    Case 2: \( n = 3k + 1 \). Then \( n^3 - n = n(n - 1)(n + 1) = (3k + 1)(3k)(3k + 2) = 3k(3k + 1)(3k + 2) \).

    Case 3: \( n = 3k + 2 \). Then \( n^3 - n = n(n - 1)(n + 1) = (3k + 2)(3k + 1)(3k + 3) = 3(k + 1)(3k + 1)(3k + 2) \).

    In all three cases, we see that \( n^3 - n \) is divisible by 3.

    Example 3

    Direct Proof

    Show that if \( n \) is an odd integer, then it is the sum of two consecutive integers.

    Solution

    Assume that \( n \) is an odd integer. Then \( n = 2k + 1 \) for some integer \( k \). We can write

    \( n = 2k + 1 \)

    \( = k + (k + 1) \)

    Hence \( n \) is the sum of the consecutive integers \( k \) and \( k + 1 \).

    Example 4

    Proof by contrapositive

    Let \( n \in \mathbb{Z} \). Prove that if \( n^2 + 2n \) is odd, then \( n \) is odd.

    Solution

    We will prove the contrapositive statement: If \( n \) is even, then \( n^2 + 2n \) is even.

    Assume that \( n \) is even. Then \( n = 2k \) for some \( k \in \mathbb{Z} \). Therefore

    \( n^2 + 2n = (2k)^2 + 2(2k) \)

    \( = 4k^2 + 4k \)

    \( = 2(2k^2 + 2k) \)

    Hence \( n^2 + 2n \) is even, since \( 2k^2 + 2k \in \mathbb{Z} \).

    As the contrapositive is equivalent to the original statement, we have proved the claim.

    Example 5

    Proof by contradiction

    Suppose \( x \) satisfies \( 2^x = 5 \). Using a proof by contradiction, show that \( x \) is irrational.

    Solution

    Suppose that \( x \) is rational. Since \( x \) must be positive, we can write \( x = \frac{m}{n} \) where \( m, n \in \mathbb{N} \).

    Therefore

    \( 2^x = 5 \Rightarrow 2^{\frac{m}{n}} = 5 \Rightarrow \left(2^{\frac{m}{n}}\right)^n = 5^n \) (raise both sides to the power \( n \))

    \( \Rightarrow 2^m = 5^n \)

    The left-hand side of this equation is even and the right-hand side is odd. This gives a contradiction, and so \( x \) is not rational.

    Example 6

    The converse of a conditional statement

    a. Let \( n \) be an integer. Statement: If \( n^2 \) is divisible by 2, then \( n \) is divisible by 2.
    Write the converse statement and show that it is true.

    b. Let \( S \) be a quadrilateral. Statement: If \( S \) is a square, then \( S \) has equal diagonals.
    Write the converse statement and show that it is not true.

    Solution

    a. Converse: If \( n \) is divisible by 2, then \( n^2 \) is divisible by 2.

    Assume that \( n \) is divisible by 2. Then \( n = 2k \) for some integer \( k \). Therefore \[ n^2 = (2k)^2 = 2(2k^2) \]

    which is divisible by 2.

    b. Converse: If \( S \) has equal diagonals, then \( S \) is a square.

    The converse statement is false, since any rectangle has equal diagonals.

    Example 7

    Equivalent statements

    Let \( n \in \mathbb{Z} \). Prove that \( n \) is divisible by 3 if and only if \( n^2 \) is divisible by 3.

    Solution

    (⇒) Assume that \( n \) is divisible by 3. We want to show that \( n^2 \) is divisible by 3. Since \( n \) is divisible by 3, there exists an integer \( k \) such that \( n = 3k \). Therefore \( n^2 = (3k)^2 = 3(3k^2) \). Hence \( n^2 \) is divisible by 3.

    (⇐) Assume that \( n^2 \) is divisible by 3. We want to show that \( n \) is divisible by 3. When the integer \( n \) is divided by 3, the remainder must be 0, 1, or 2. Therefore, \( n \) can be written in the form \( 3k \), \( 3k + 1 \), or \( 3k + 2 \) for some integer \( k \).

    Case 1: \( n = 3k \). This is the case where \( n \) is divisible by 3.

    Case 2: \( n = 3k + 1 \). Then \( n^2 = 9k^2 + 6k + 1 \), which leaves remainder 1 when divided by 3. This contradicts our assumption that \( n^2 \) is divisible by 3. So this case cannot occur.

    Case 3: \( n = 3k + 2 \). Then \( n^2 = 9k^2 + 12k + 4 \), which leaves remainder 1 when divided by 3. This contradicts our assumption that \( n^2 \) is divisible by 3. So this case cannot occur.

    Hence \( n \) must be divisible by 3.

    Example 8

    (Proof by Contradiction):

    Prove that \( \sqrt{2} \) is irrational.

    Solution

    Assume, by contradiction, that \( \sqrt{2} \) is rational, leading to a contradiction and proving its irrationality.

    Proof that \( \sqrt{2} \) is Irrational

    Assume, by contradiction, that \( \sqrt{2} \) is rational. Then, it can be expressed as \( \frac{p}{q} \) where \( p \) and \( q \) are coprime integers. \[ 2 = \left(\frac{p}{q}\right)^2 \] \[ 2q^2 = p^2 \]

    This implies that \( p^2 \) is even, hence \( p \) must also be even (since the square of an odd number is odd). Let \( p = 2k \) for some integer \( k \). \[ 2q^2 = (2k)^2 \] \[ 2q^2 = 4k^2 \] \[ q^2 = 2k^2 \]

    This means that \( q^2 \) is also even, hence \( q \) must be even. However, this contradicts our assumption that \( p \) and \( q \) are coprime. Therefore, our initial assumption that \( \sqrt{2} \) is rational must be false, proving that \( \sqrt{2} \) is irrational.

    Example 9

    Proof of Proposition by cases:

    Prove the following proposition: If \( x \) is a real number, then \( |x + 3| - x > 2 \).

    We consider two cases: \( x \geq -3 \) and \( x < -3 \).

    1. Case 1: \( x \geq -3 \). Then \( |x + 3| = x + 3 \), so we have \( |x + 3| - x = x + 3 - x = 3 > 2 \), so the proposition holds.

  • Case 2: \( x < -3 \). Then \( |x + 3| = -(x + 3) \), so we have \( |x + 3| - x = -3 - x - x = -3 - 2x \). Since \( x < -3 \), we must have \( -x > 3 \), so \( -3 - 2x > -3 + 2(3) = 3 > 2 \). Therefore, the proposition holds.

    • Since the proposition holds in all cases, it must be true that if \( x \) is a real number, then \( |x+3|−x > 2 \).

    Example 10

    Proof buy Induction

    Prove by induction that \( n^3 + 2n \) is divisible by 3 for every non-negative integer \( n \).

    Proof

    Let \( P(n) \) be the mathematical statement " \( n^3 + 2n \) is divisible by 3."

    Base Case: When \( n = 0 \), we have \( 0^3 + 2 \times 0 = 0 \), which is divisible by 3 since \( 0 = 3 \times 0 \). So \( P(0) \) is correct.

    Induction Hypothesis: Assume that \( P(k) \) is correct for some positive integer \( k \). That means \( k^3 + 2k \) is divisible by 3, and hence \( k^3 + 2k = 3m \) for some integer \( m \).

    Induction Step: We will now show that \( P(k + 1) \) is correct. So we will take the original formula and replace the \( n \) with \( k + 1 \) to get \( (k + 1)^3 + 2(k + 1) \) and we will show that this is divisible by 3. At some stage in the proof, we will need to use the fact that \( k^3 + 2k = 3m \), so when we rearrange the formula we will try to get \( k^3 + 2k \) as part of it.

    \[ \begin{align*} (k + 1)^3 + 2(k + 1) & = k^3 + 3k^2 + 3k + 1 + 2k + 2 & \text{by expanding the brackets} \\ & = k^3 + 2k + 3(k^2 + k + 1) & \text{by rearranging the formula} \\ & = 3m + 3(k^2 + k + 1) & \text{by the induction hypothesis} \\ & = 3(m + k^2 + k + 1) & \text{since both parts of the formula have a common factor of 3}. \end{align*} \]

    As \( m + k^2 + k + 1 \) is an integer, we have that \( (k + 1)^3 + 2(k + 1) \) is divisible by 3, so \( P(k + 1) \) is correct. Hence, by mathematical induction, \( P(n) \) is correct for all non-negative integers \( n \).

    Exercise &&1&& (&&1&& Question)

    What logical operator represents conjunction in propositional logic

    1
    Submit

    Exercise &&2&& (&&1&& Question)

    In the statement \( P \leftrightarrow Q \), when is it true?

    2
    Submit

    Exercise &&3&& (&&1&& Question)

    What will be converse of this : If \(S\) is a square, then \(S\) has equal diagonals.

    3
    Submit

    Exercise &&4&& (&&1&& Question)

    Assume you want to prove that the \(\sqrt(3)\) is irrational. Which is the correct method to use?

    4
    Submit

    Exercise &&5&& (&&1&& Question)

    If \( P \) represents "It is raining" and \( Q \) represents "I will take an umbrella", what does the statement \( P \rightarrow Q \) mean?

    5
    Submit

    Exercise &&6&& (&&1&& Question)

    In a proof, a statement is shown to be true by directly verifying its truth based on known facts and axioms. Which proof method does this describe?

    6
    Submit