Mathematics for Computing – Discrete Mathematics
1
Lecturer: Dr Nguyen Hieu Thao
Email: [Link]@[Link]
Lecture Notes: Logic and Math Proofs
(Week 2)1
Propositions
A proposition is a declarative sentence that is either true or false, but not both. We use
variables, such as p, q and r, to represent propositions. We may write ‘p : 1 + 1 = 1’ to indicate
that the proposition represented by p is ‘1 + 1 = 1’.
Let p and q be propositions.
(a) The negation of proposition p, denoted by ¬p, is the proposition ‘not p’.
(b) The conjunction of p and q, denoted by p ∧ q, is the proposition ‘p and q’.
(c) The disjunction (or inclusive-or) of p and q, denoted by p ∨ q, is the proposition ‘p or q’.
(d) The exclusive-or of p and q, denoted by p ⊕ q, is the proposition ‘p or q but not both’.
(e) De Morgan’s Laws for logic: ¬(p ∨ q) ≡ ¬p ∧ ¬q, ¬(p ∧ q) ≡ ¬p ∨ ¬q.
Let p and q be propositions.
(a) The proposition ‘if p then q’ is a conditional proposition and is denoted by p → q, where
p is the hypothesis and q is the conclusion.
(b) The proposition ‘p if and only if q’ is a biconditional proposition and is denoted by p ↔ q.
It is true when both p and q have the same truth value.
(c) The converse of the proposition p → q is the proposition q → p.
(d) The contrapositive of the conditional proposition p → q is ¬q → ¬p.
(e) The negation of the conditional proposition p → q is characterized by
¬(p → q) ≡ p ∧ ¬q.
Thus, ¬(p → q) means that p is true while q is false.
1 Most of the content of this document is taken from the book [1].
2
Operator precedence. Without parentheses, the order is: ¬, ∧, ∨, and →.
Truth tables of (conditional) propositions are below.
p q ¬p p∧q p∨q p exor q p→q p↔q ¬q → ¬p
T T F T T F T T T
T F F F T T F F F
F T T F T T T F T
F F T F F F T T T
Table 1: Truth tables for common logical connectives and conditional statements.
Suppose compound propositions P and Q are constructed from simpler propositions p1 , p2 , . . . , pn .
Then P and Q are logically equivalent, denoted by P ≡ Q, if they have the same truth values
for all possible truth assignments.
Let P (x) be a statement involving the variable x and let D be a set. Then P is a proposi-
tional function on the domain D if for each x ∈ D, P (x) is a proposition.
Let P be a propositional function with domain D.
(a) The statement ‘P (x) for every x’ (symbolically, ∀x P (x)) is a universally quantified state-
ment. The universal quantifier ∀ means ‘for every’ or ‘for all’ or ‘for any’. It is false if
P (x) is false for at least one x ∈ D.
(b) The statement ‘there exists x, P (x)’ (symbolically, ∃x P (x)) is an existentially quantified
statement. The existential quantifier ∃ means ‘there exists’ or ‘there is’ or ‘for some’ or
‘for at least one’. It is true if P (x) is true for at least one x ∈ D.
(c) Generalized De Morgan’s Laws. Let P be a propositional function with variable x.
(i) ¬(∀x P (x)) ≡ ∃x ¬P (x).
(ii) ¬(∃x P (x)) ≡ ∀x ¬P (x).
These express how negation interacts with quantifiers, similar to the logical De Morgan’s
laws.
p
∴q
is valid.
FIRST SOLUTION We construct a truth table for all the propositions involved:
3
p q p→q p q
Nested quantifiers
T T T T T
Consider the domain of discourse XT× YF. F T F
F T T F T
F x ∈F X andT y ∈
(a) ∀x ∀y P (x, y) is true if, for every YF, P (x,
F y) is true. It is false if there exist
x ∈ X and y ∈ Y such that P (x, y) is false.
We observe that whenever the hypotheses p → q and p are true, the conclusion q is also
true;
(b) ∀xtherefore,
∃y P (x, y) the argument
is true is valid.
if, for every x ∈ X, there exists y ∈ Y such that P (x, y) is true. It is
false if there
SECOND exists x ∈ X
SOLUTION Wesuch
canthat P (x,
avoid y) is false
writing the for every
truth .
y ∈byY directly
table verifying that
whenever the hypotheses are true, the conclusion is also true.
(c) ∃x ∀y P (x, y) is true if, there exists x ∈ X such that P (x, y) is true for every y ∈ Y . It is
Suppose that p → q and p are true. Then q must be true, for otherwise p → q
falsebe
would if for every
false. x ∈ X, there
Therefore, exists y ∈ Y
the argument such that P (x, y) is false.
is valid.
❦
(d) ∃x ∃y P (x, y) is true if, there exist x ∈ X and y ∈ Y such that P (x, y) is true. It is false if
The argument in Example 1.4.2 is used extensively and is known as the modus
for every
ponens rulex of
∈X and y ∈ Yor, Plaw
inference of isdetachment.
(x, y) false. Several useful rules of inference for
propositions, which may be verified using truth tables (see Exercises 33–38), are listed
in Table 1.4.1.
Mathematical proofs
TABLE 1.4.1 ■ Rules of Inference for Propositions
Rule of Inference Name Rule of Inference Name
p→q p
p q
∴q Modus ponens ∴p∧q Conjunction
p→q p→q
¬q q→r Hypothetical
∴ ¬p Modus tollens ∴p→r syllogism
p∨q
p ¬p Disjunctive
∴p∨q Addition ∴q syllogism
p∧q
∴p Simplification
mple 1.4.3 Table 2: is
Which rule of inference Standard
used in rules of inference
the following in propositional logic.
argument?
If the computer has one gigabyte of memory, then it can run “Blast ’em.” If the
computer can run “Blast ’em,” then the sonics will be impressive. Therefore, if the com-
puter has one gigabyte of memory, then the sonics will be impressive.
❦
4
An argument is a sequence of propositions written
p1 , p2 , . . . , pn ∴ q.
The symbol ∴ is read ‘therefore’. The propositions p1 , p2 , . . . , pn are the hypotheses and
the proposition q is the conclusion. An argument is valid provided that if p1 , p2 , . . . , pn are all
true, then q must also be true.
(a) A direct proof of a statement p → q assumes that p is true and then, using p and other
known facts shows directly that q is true. This is the most common and straightforward
method.
(b) To disprove a universally quantified statement ∀x P (x), we need to find one element x in
D such that P (x) is false. Such an element x is a counterexample.
(c) A proof by contrapositive of a statement p → q proves its contrapositive statement
¬q → ¬p since they are logically equivalent, symbolically,
p → q ≡ ¬q → ¬p.
This is often easier when the negation of q has a simple form.
(d) To prove a statement p → q by contradiction, we assume p and ¬q and show this leads to
a contradiction (!). That is,
(p ∧ ¬q → ! ) =⇒ p → q.
References
1. Johnsonbaugh, R.: Discrete Mathematics - Eighth Edition. Pearson Education, New York
(2018).