MA100.2 - The Logical Framework

Question 1

What is a proposition?

Answer 1

A proposition is a mathematical statement that is either true or false but not both.

Question 2

What is a definition?

Answer 2

A definition is a precise and unambiguous description of a mathematical term.
- EXAMPLE. A number k is called even only if k = 2n for some integer n.

Question 3

What is a theorem?

Answer 3

A theorem is simply a valid mathematical result.

Question 4

What is a proof?

Answer 4

A proof is an explanation as to why this result/theorem is valid.

Question 5

What is a lemma?

Answer 5

A theorem may be referred to as a lemma; this is a preliminary result whose main role is to help us prove a forthcoming important or general theorem.

Question 6

What is a corollary?

Answer 6

A theorem may also be referred to as a corollary; this is a result whose proof relies heavily on a preceding important or general theorem.

Question 7

What are the logical connectives?

Answer 7

The Operations

• Not (¬)
• And (∧)
• Or (∨)
• If, Then, Implies (⇒)
• If and only if (⇔)

Question 8

What is a Truth Table?

Answer 8

The proposition, p, is either true or false.

• If p is true, we assign to it the truth value T.
• If it is false, we assign to it the truth value F.

Question 9

What is the negation of the proposition?

Answer 9

The negation of a proposition p is denoted by ¬p and is simply the proposition ‘not p’.
- EXAMPLE. Let p be the proposition ‘4 is an even number’. Then ¬p is the proposition ‘4 is not an even number’. In this case, p is true and ¬p is false.

Question 10

What is a compound proposition?

Answer 10

A compound proposition is a proposition that is built up from simpler propositions using linking words such as and, or, if-then, if-and-only-if and defined by their truth tables.

Question 11

What is the conjunction of two propositions?

Answer 11

The conjunction of two propositions p and q is denoted by p ∧ q and is the proposition ‘p and q’. The conjunction p ∧ q is true only if the propositions p and q are both true.
- EXAMPLE. Let p be the proposition ‘11 is a multiple of 2’ and q be the proposition ‘16 is a multiple of 2’. The conjunction p ∧ q amounts to the proposition ‘11 and 16 are multiples of 2’. In this case, the conjunction p ∧ q is false since its first constituent proposition is false.

Question 12

What is the disjunction of two propositions?

Answer 12

The disjunction of two propositions p and q is denoted by p ∨ q and is the proposition ‘p or q’. The disjunction p ∨ q is false only if the propositions p and q are both false.
- EXAMPLE. Let p be the proposition ‘14 is a multiple of 2’ and q be the proposition ‘14 is a multiple of 3’. The disjunction p∨q amounts to the proposition ‘14 is a multiple of 2 or 3’. In this case, the disjunction p ∨ q is true because its first constituent proposition is true.

Question 13

What is the conditional proposition?

Answer 13

The conditional proposition denoted by p ⇒ q is the proposition ‘if p, then q’, also referred to as ‘p implies q’. The conditional proposition is false only if p is true and q is false.

• If the premise on which the conditional proposition rests is not tested (false), then the conditional proposition is declared true.
• EXAMPLE. Let p be the proposition ‘16 is a perfect square’ and q be the proposition ‘64 is a perfect square’. Since both propositions p and q are true, the proposition p ⇒ q is. true.
• EXAMPLE. Let p be the proposition ‘13 is a perfect square’ and q be the proposition ‘64 is a perfect square’. Since p is false, the proposition p ⇒ q is true.
• EXAMPLE. Let p be the proposition ‘3 is an even number’ and q be the proposition ‘π is an even number’. Since p is false, the proposition p ⇒ q is true.
• EXAMPLE. Let p be the proposition ‘5 is an even number’ and q be the proposition ‘5 is not an even number’. Again, since p is false, the proposition p ⇒ q is true. There is no contradiction in the proposition ‘if 5 is an even number, then 5 is not an even number’ because the premise on which it rests is false.
• EXAMPLE. Let p be the proposition ‘5 is not an even number’ and q be the proposition ‘5 is an even number’. Now, p is true and q is false, so the proposition p ⇒ q is false.
• EXAMPLE. Let p be the proposition ‘16 is an even number’ and q be the proposition ‘the sum of the angles of a triangle is 180 degrees’. Since both p and q are true, the proposition p ⇒ q is true. Note that the propositions p and q seem to be logically disconnected here.
• EXAMPLE. Let p be the proposition ‘13 is an even number’ and q be the proposition ‘the sum of the angles of a triangle is 32 degrees’. Since p is false, the proposition p ⇒ q is true.

Question 14

What is the biconditional proposition?

Answer 14

The biconditional proposition denoted by p ⇔ q is the compound proposition ‘p if and only if q’.

• EXAMPLE. The biconditional proposition p ⇔ q may also be referred to as ‘p implies q and q implies p’. This is because it is equivalent to the conjunction of the conditional propositions p ⇒ q and q ⇒ p. We will establish this result in subsection 2.3 where we will introduce the notion of logical equivalence of two propositions.
• EXAMPLE. Let p be the proposition ‘13 is an even number’ and q be the proposition ‘17 is an even number’. Both p and q are false so the biconditional proposition p ⇔ q is true.

Question 15

What is the converse of the conditional proposition?

Answer 15

The converse of the conditional proposition p ⇒ q is the conditional proposition q ⇒ p.
- EXAMPLE. Let p be the proposition ‘4 is even’ and q be the proposition ‘5 is even’. The converse of the conditional proposition ‘if 4 is even, then 5 is even’ is the conditional proposition ‘if 5 is even, then 4 is even’. Here, p is true and q is false, so the conditional proposition p ⇒ q is false and its converse proposition q ⇒ p is true.

Question 16

What is the contrapositive of the conditional proposition?

Answer 16

The contrapositive of the conditional proposition p ⇒ q is the conditional proposition (¬q) ⇒ (¬p).

• Note that the truth table of the proposition p ⇒ q is identical to that of its contrapositive proposition (¬q) ⇒ (¬p).
• EXAMPLE. Let p be the proposition ‘4 is even’ and q be the proposition ‘4 + 1 is odd’. The contrapositive of the conditional proposition ‘if 4 is even, then 4 + 1 is odd’ is the conditional proposition ‘if 4 + 1 is not odd, then 4 is not even’. Here, both p and q are true and hence their negations ¬p and ¬q are both false. The conditional proposition p ⇒ q and its contrapositive proposition (¬q) ⇒ (¬p) are both true.

Question 17

What is meant by ‘p is sufficient for q’ or ‘p is necessary and sufficient for q’?

Answer 17

• The conditional proposition ‘p ⇒ q’ is commonly known as ‘p is sufficient for q’ or, equivalently, as ‘q is necessary for p’
• For similar reasons, the biconditional proposition p ⇔ q is known as ‘p is necessary and sufficient for q’ or, equivalently, as ‘q is necessary and sufficient for p’.

Question 18

What is meant if some logical operations are logically equivalent?

Answer 18

In general, two propositions A and B that are built up from a single proposition p through some logical operations such as ¬, ∧, ∨, ⇒, ⇔ are called logically equivalent if they always have the same truth value; that is, for every truth value of p, the truth value of A and the truth value of B are the same.

Question 19

What are some examples of logical operations that are logically equivalent?

Answer 19

• EXAMPLE. Consider a proposition p and its double negation ¬(¬p). Regardless of the truth value
  of the proposition p, the propositions p and ¬(¬p) have the same truth value.
• EXAMPLE. The biconditional proposition p ⇔ q is logically equivalent to the conjunction of the conditional propositions p ⇒ q and q ⇒ p.
• EXAMPLE. The conditional proposition p ⇒ q is logically
  equivalent to the proposition (¬p) ∨ q.
• EXAMPLE. The proposition ¬(p ∨ q) is logically equivalent to the proposition (¬p) ∧ (¬q).
• EXAMPLE. The proposition ¬(p∧q) is logically equivalent
  to the proposition (¬p) ∨ (¬q). The equivalence of these two propositions is known as de Morgan’s Laws.

Question 20

What is a predicate?

Answer 20

A predicate is a mathematical statement that depends on one or more variables.

• A simple example is given by the statement: n is an even number.
• This is a predicate that depends on a single variable n. For simplicity, let us assume that the variable n is an integer and let us denote this predicate by P(n). We can now construct propositions such as P(1), P(4) and P(21) whose truth values can be determined. P(1) is false, P(4) is true and P(21) is false.
• When n has a value then it becomes a proposition.

Question 21

Can you assign a truth value to a predicate before specifying the value of the variable?

Answer 21

We cannot assign a truth value to a predicate P(n) before we specify the value of the variable n. However, this does not exclude the possibility of constructing predicates whose truth values can be determined irrespectively of n.
- EXAMPLE. Let n be an integer, and consider the conditional statement ‘if n is even, then n+1 is odd’.

Question 22

What is an existential statement?

Answer 22

An existential statement is a statement that expresses the existence of at least one object of a certain kind that has a particular property.

• An existential statement can be written in the form ∃n[P(n)].
• In order to prove them, we simply need to find at least one real number n and at least one integer m with the required properties. In general, in order to prove that an existential statement is true, we just need to find an example.
• To disprove an existential statement we need to show that no integer values of n make P(n) true or equivalently that all integer values of n makes P(n) false.
• EXAMPLE. There exists a real number n such that n^2 = 17. There exists an integer m such that 3 < m < 12.
• EXAMPLE. The existential statement ‘there exists a real number n such that n^2 = 17’ can be written in the form ‘∃ real number n[n^2 = 17]’. Similarly, the existential statement ‘there exists an integer m such that 3 < m < 12’ can be written in the form ‘∃ integer m[3 < m < 12]’.

Question 23

What is the existential quantifier?

Answer 23

The symbol ∃ is called the existential quantifier and simply means ‘there exists. The property P(n) satisfied by n is enclosed in the square brackets ∃n[P(n)].

Question 24

What is a universal statement?

Answer 24

A universal statement is a statement that expresses the fact that all objects of a certain kind have a particular property.

• A universal statement can be written in the form ∀n[P(n)].
• To prove that a universal statement is true we need to show that all integer values of n make P(n) true or equvilantly, no integer value of n makes P(n) false.
• In general, in order to prove that a universal statement is false, we just need to find a counterexample.
• EXAMPLE. For all integers n, 2n is an even number. For all integers m, if m2 + m is even, then m is even.
• EXAMPLE. The universal statement ‘for all integers n, 2n is an even number’ can be written in the form ‘∀ integers n[2n is even]’. Similarly, the universal statement ‘for all integers m, if m2+m is even, then m is even’ can be written in the form ‘∀ integers m[(m^2+ m is even) ⇒ (m is even)]’.

Question 25

What is the universal quantifier?

Answer 25

The symbol ∀ is called the universal quantifier and simply means ‘for all’. The property P(n) satisfied by n is enclosed in the square brackets ∀n[P(n)].

Question 26

What is the negation of the existential statement ∃n[P(n)]?

Answer 26

The negation of the existential statement ∃n[P(n)] is the universal statement ∀n[¬P(n)].

Question 27

What is the negation of the existential statement ∀n[P(n)]?

Answer 27

The negation of the universal statement ∀n[P(n)] is the existential statement ∃n[¬P(n)].

Question 28

What is ∃n[P(n)]logically equivalent to?

Answer 28

Equivalently, we can say that ¬∃n[P(n)]is logically equivalent to ∀n[¬P(n)].

Question 29

What is ∀n[P(n)] logically equivalent to?

Answer 29

Equivalently, we can say that ¬∀n[P(n)] is logically equivalent to ∃n[¬P(n)].

Question 30

What is a direct proof?

Answer 30

A direct proof is the most straightforward method of proof where the truth or falsity of a given mathematical statement is established directly.
- EXAMPLE. Let us prove the universal statement ‘for all integers n, n 2 + n is an even number’.

Question 31

What is proof by contraposition?

Answer 31

A proof by contraposition is concerned with the proof of a conditional statement of the form p ⇒ q. The idea is to prove instead the logically equivalent contrapositive statement (¬q) ⇒ (¬p) which may happen to be easier to deal with.
- EXAMPLE. Let us prove the universal statement ‘for all integers n, if n^2 is even, then n is even’.

Question 32

What is proof by example or counterexample?

Answer 32

A proof by example or counterexample is a convenient method for either proving an existential statement ‘∃n[P(n)]’ or disproving a universal statement ‘∀n[P(n)]’. Disproving a universal statement ‘∀n[P(n)]’ amounts to proving the existential statement‘∃n[¬P(n)]’.

• EXAMPLE. Let us prove the existential statement ‘there exists an integer n such 2^n = n^2’. An example suffices: n = 2 is such an integer.
• EXAMPLE. Let us disprove the universal statement ‘for all integers n, 2^n /= n^2’. A counterexample suffices: n = 2.

Question 33

What is proof by contradiction?

Answer 33

Proof by contradiction is based on the following idea. Suppose that we want to prove that a statement s is true. Instead of showing directly that the truth value of s is T, we assume that s is false; in other words, we assume that ¬s is true. Our aim is to produce a valid mathematical argument based on the assumed truth of the premise ¬s which leads to some statement r that is false.
- EXAMPLE. Show that for all integers n, if n^2 is even, then n is even.