Logic and Proofs
Sinethemba Funani
Department of Mathematics,
University of Fort Hare, South Africa
February 11, 2025
1 / 12
Inductive vs Deductive Reasoning
Inductive Reasoning:
I Observing specific cases or patterns.
I Generalizing to form conjectures or hypotheses.
Example: The sum of the first ”n” natural numbers follows
the formula n(n+1)
2 .
I May lead to false conclusions if not proven.
Deductive Reasoning:
I Starting with accepted premises or axioms.
I Drawing logical conclusions that are proven to be true.
Example: Proving the sum of angles in a triangle equals 180°.
I Provides certainty and validity when assumptions are true.
2 / 12
Basic Definitions
Statement
A statement is a sentence expressed in words that is either true or
false.
I Statements do not include exclamations, questions, or orders.
I They can be true or false at the same time, though it can be
true or false considering different contexts.
I A statement is simple when it cannot be broken down into
other statements, i.e It will rain.
I A compound statement is a statement that can contain
several simple statements. connected by words such as and,
or, thus, then, therefore, because, for, moreover.
3 / 12
Basic Definitions...
Definition
A definition is a statement of the precise meaning of a word or
phrase, a mathematical symbol or concept.
Theorem
A theorem is a mathematical statement that can be proved by a
chain of logical reasoning on the by a chain of logical reasoning on
the basis of certain assumptions that are given or implied in the
theorem.
Lemma
A lemma is an auxiliary theorem proved beforehand to be used in
the proof of another theorem.
Corollary
A corollary is a theorem that is a natural consequence, that is, it
follows logically from something else.
4 / 12
Propositions and Paradoxes
A proposition is a sentence that is either true or false. Thus a
proposition has exactly one truth value: true which is denoted by
T, or false which is denoted by F.
Some examples of propositions are;
√
1. 2 is irrational
2. 1 + 1 = 5
Here are some sentences that are not Propositions
1. What did you say?
2. x 2 = 36
3. This sentence is false.
Statement (3) is an example of a sentence that is neither true or
false, and is referred to as a paradox.
5 / 12
Propositions and Paradoxes (contd)
Proposition (1) and (2) are simple in the sense that they do not
have any other propositions as components. Compound
propositions can be formed by using logical connectives with simple
propositions.
Definition
Given Propositions P and Q:
The conjunction of P and Q, denoted by P ∧ Q, is the proposition
”P and Q”. P ∧ Q is exactly True if both P and Q are true.
The disjunction of P and Q, denoted by P ∨ Q, is the proposition
”P or Q”. P ∨ Q is True exactly when at least one of P or Q is
true.
The negation of P, denoted ~P, is the proposition ”not P”. ~P is
true exactly when P is false.
6 / 12
Propositions and Paradoxes (contd)
I If P is ”1 6= 3” AND Q is ”7 is odd” then P ∧ Q is ”1 6= 3
and 7 is odd”
I For P ∨ Q is ”1 6= 3 OR 7 is odd”
I ~Q is ”It is not the case that 7 is odd”
I For P ∧ Q, both P and Q are true, then P ∧ Q is true, P ∨ Q
is also true
7 / 12
Propositions and Paradoxes (contd)
The following truth table of a compound
P Q P ∧Q P ∨Q
T T T T
T F F T
F T F T
F F F F
Compound Propositions are propositions with more than two
components
Example
Find all the possible values of (P ∧ Q) ∨ ~R
8 / 12
Proposition and Paradoxes (contd)
Solution
I For 3 components (P, Q, R), we have 3 propositions, and
each can be independently be true or false.
I So for each of the 3 components, there are 2 choices (True or
False)
I Therefore the total number of choices is 23 = 8
now,
P Q R ¬R (P ∧Q) (P ∧Q) ∨¬R
T T T F T T
T T F T T T
T F T F F F
T F F T F T
F T T F F F
F T F T F T
F F T T F T
F F F T F T
9 / 12
Propositions
I Two propositions are equivalent if and only if they have the
same truth value
I The proposition ”1 + 1 = 2” and "6 < 10" are equivalent
because both are true
For example P ∨ (Q ∧ P) and P are equivalent,
Proof.
P Q Q ∧P P ∨(Q ∧P) P
T T T T T
T F F T T
F T F F F
F F F F F
I Any proposition P is equivalent to itself
I Also, the propositional forms P and ¬(¬P) are equivalent.
Their truth table is as follows,
10 / 12
Propositions
Definition
A denial of a proposition S is any proposition equivalent to ¬S
I By definition, the negation ¬P is a denial of the proposition
P, but a denial need not be the negation.
I A proposition has only one negation but may have several
denials
Example
The proposition P: ”π is rational” has a negation ¬P: ”It is not
the case that π is rational”
Some useful denials
I π is irrational
I π is a quotient of two integers
I The decimal expansion of π is not repeating
Note: Since P is false, all denials are true
11 / 12
Propositions
I Tautologies are propositional forms that are true for every
assignment of truth values to their components
I Tautologies will have the value true regardless of what
proposition(s) we select for the components.
P ¬P P ∨ ¬P
T F T
F T T
I A contradiction is the negation of a tautology thus ¬(P ∨ ¬P)
12 / 12
