Discrete Mathematics

by Rafał Jaworski
based on materials prepared by Joanna Pomianowska

Basic mathematical logic

Propositional calculus

Logic is the systematic study of the form of valid inference, and the most general laws of truth.
(Gottlob Frege)

Inference is a process of obtaining a conclusion from a set of premises. Logic is concerned with
inferring true statements from other statements.

Propositional calculus is a formal system that deals with propositions in a mathematical way.
Proposition is expressed by a declarative logical sentence and can either be true or false. For every
proposition It must be possible to determine whether it is true or false regardless of any
circumstances or external conditions. That is to say that a proposition must either always be true or
always be false.

Examples of propositions:

✓ Warsaw was the capital of Poland in 2018.

✓ Earth orbits around the sun.
✓ Every odd number is divisable by 2. (this proposition is always false).
✓ It is not true that 𝑥 ≥ 3 for every natural x.

Examples of sentences which do not express a proposition

✓ Come to the blackboard!

✓ Do you own a dog?
✓ Lawyers are rich.
✓ 𝑥−𝑦 =𝑦−𝑥

Propositions in logic are typically denoted with lowercase letters p,q,r. We will be joining them
together with standard operators:

~ negation
∨ disjunction (or)
∧ conjunction (and)
→ implication (if.. then…)
↔ equivalence „…if and only if…”
⊕ exclusive disjunction XOR
| Sheffer stroke NAND
↓ Pierce’s arrow NOR

1
 Discrete Mathematics
by Rafał Jaworski
based on materials prepared by Joanna Pomianowska

Table for the operators

negation disjunction conjunction implication equivalence exclusive Sheffer Pierce’s

or stroke arrow

NO OR AND If…then… ..if an only if.. NAND NOR

𝑝 𝑞 ∼𝑝 𝑝∨𝑞 𝑝∧𝑞 𝑝→𝑞 𝑝↔𝑞 𝑝⨁𝑞 𝑝|𝑞 𝑝↓𝑞

0 0 1 0 0 1 1 0 1 1

0 1 1 1 0 1 0 1 1 0

1 0 0 1 0 0 0 1 1 0

1 1 0 1 1 1 1 0 0 0

An converse proposition for the conditional statement 𝑝 → 𝑞 is 𝑞 → 𝑝.

An inverse proposition for the conditional statement 𝑝 → 𝑞 is ~𝑝 → ~𝑞.

A contrapositive of the conditional statement 𝑝 → 𝑞 is (~𝑞) → (~𝑝).

Logical matrix of a complex sentence built from simple propositions p,q,r, .. is a table of all possible
logical values of the sentences calculated from the values of the propositions.

Example 1
Sentence (𝑝 → 𝑞) ∧ (𝑞 → 𝑝)
𝑝 𝑞 𝑝→𝑞 ∧ 𝑞→𝑝
0 0 1 1 1
0 1 1 0 0
1 0 0 0 1
1 1 1 1 1
is equivalent to 𝑝 ↔ 𝑞.
Example 2
Logical matrix of (𝑝 → 𝑞) ∧ [(𝑞 → ~𝑟) → (𝑝 ∨ 𝑟)]
𝑝 𝑞 𝑟 𝑝→𝑞 ∧ [(𝑞 → ~𝑟) → (𝑝 ∨ 𝑟)]
0 0 0 1 0 1 1 0 0
0 0 1 1 1 1 0 1 1
0 1 0 1 0 1 1 0 0
0 1 1 1 1 0 0 1 1
1 0 0 0 0 1 1 1 1
1 0 1 0 0 1 0 1 1
1 1 0 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1
Tautology is a sentence which is always true for every value of the p, q, r, .. variables.

Conversely, a sentence which is always false is a contradiction.

Negation of any tautology is a contradiction.

2
 Discrete Mathematics
by Rafał Jaworski
based on materials prepared by Joanna Pomianowska

Equivalent sentences (laws of logic)

1. double negation
(~~𝑝) ⟺ 𝑝

2. laws of commutation
(𝑝 ∨ 𝑞) ⟺ (𝑞 ∨ 𝑝)

(𝑝 ∧ 𝑞) ⟺ (𝑞 ∧ 𝑝)

(𝑝 ↔ 𝑞) ⟺ (𝑞 ↔ 𝑝)

3. laws of association
[(𝑝 ∨ 𝑞) ∨ 𝑟] ⟺ [𝑝 ∨ (𝑞 ∨ 𝑟)]

[(𝑝 ∧ 𝑞) ∧ 𝑟] ⟺ [𝑝 ∧ (𝑞 ∧ 𝑟)]

4. laws of distribution
[𝑝 ∨ (𝑞 ∧ 𝑟)] ⟺ [(𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)]

[𝑝 ∧ (𝑞 ∨ 𝑟)] ⟺ [(𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)]

5. laws of idempotence
(𝑝 ∨ 𝑝) ⟺ 𝑝

(𝑝 ∧ 𝑝) ⟺ 𝑝

6. laws of identity
(𝑝 ∨ 0) ⟺ 𝑝
(𝑝 ∨ 1) ⟺ 1
(𝑝 ∧ 0) ⟺ 0

7. law of excluded middle

(𝑝 ∨ ~𝑝) ⟺ 1
(𝑝 ∧ ~𝑝) ⟺ 0

8. De Morgan laws for negation

~(𝑝 ∨ 𝑞) ⟺ (~𝑝 ∧ ~𝑞)
~(𝑝 ∧ 𝑞) ⟺ (~𝑝 ∨ ~𝑞)
(𝑝 ∨ 𝑞) ⟺ ~(~𝑝 ∧ ~𝑞)
(𝑝 ∧ 𝑞) ⟺ ~(~𝑝 ∨ ~𝑞)

9. law of contraposition (transposition)

(𝑝 → 𝑞) ⟺ (~𝑞 → ~𝑝)

10. reformulating implication with alternative or conjunction

(𝑝 → 𝑞) ⟺ (~𝑝 ∨ 𝑞)
(𝑝 → 𝑞) ⟺ ~(𝑝 ∧ ~𝑞)

3
 Discrete Mathematics
by Rafał Jaworski
based on materials prepared by Joanna Pomianowska

11. (𝑝 ∨ 𝑞) ⟺ (~𝑝 → 𝑞)
(𝑝 ∧ 𝑞) ⟺ ~(𝑝 → ~𝑞)

12. [(𝑝 → 𝑟) ∧ (𝑞 → 𝑟)] ⟺ [(𝑝 ∨ 𝑞) → 𝑟]

[(𝑝 → 𝑞) ∧ (𝑝 → 𝑟)] ⟺ [𝑝 → (𝑞 ∧ 𝑟)]

13. definition of equivalence

(𝑝 ↔ 𝑞) ⟺ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝)

14. exportation law

[(𝑝 ∧ 𝑞) → 𝑟] ⟺ [𝑝 → (𝑞 → 𝑟)]

15. reductio ad absurdum

(𝑝 → 𝑞) ⟺ [(𝑝 ∧ ~𝑞) → 0]

Two logical sentences P and Q are logically equivalent if they assume the same logical values for every set of
values of their propositions p,q,r...

We denote two logically equivalent sentences with 𝑃 ⟺ 𝑄.

𝑃 ⟺ 𝑄 if and only if 𝑃 ↔ 𝑄 is a tautology.

Sentence P implies Q when Q always has the value 1 when P has the value 1. We denote 𝑃 ⇒ 𝑄.
𝑃 ⇒ 𝑄 if and only if 𝑃 → 𝑄 is a tautology.

Logical implications

16. 𝑝 ⇒ (𝑝 ∨ 𝑞) introduction of alternative

17. (𝑝 ∧ 𝑞) ⇒ 𝑝 omitting conjunction

18. (𝑝 → 0) ⇒ ~𝑝 reductio ad absurdum

19. [𝑝 ∧ (𝑝 → 𝑞)] ⇒ 𝑞 modus ponendo ponens

20. [(𝑝 → 𝑞) ∧ ~𝑞] ⇒ ~𝑝 modus tollendo tollens

21. [(𝑝 ∨ 𝑞) ∧ ~𝑝] ⇒ 𝑞 modus ponendo tollens

22. 𝑝 ⇒ [𝑞 → (𝑝 ∧ 𝑞)]

23. [(𝑝 ↔ 𝑞) ∧ (𝑞 ↔ 𝑟)] ⇒ (𝑝 ↔ 𝑟) transitivity of ↔

24. [(𝑝 → 𝑞) ∧ (𝑞 → 𝑟)] ⇒ (𝑝 → 𝑟) transitivity of →