Logic, relations and functions

Maths · Sets, functions and groups. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Maths topics

The idea

A proposition is a statement that is either true (T) or false (F), never both. Propositions p and q are joined by connectives, and a truth table lists the result for every combination of T and F.

A tautology is true in every row of its truth table; a contradiction (absurdity) is false in every row.

A relation from A to B is any set of ordered pairs (a, b) with a in A and b in B. It is a function from A to B when its domain is the whole of A and each element of A has exactly one image in B. The range is the set of images.

Rules to remember

Negation ∼p reverses the truth value. Conjunction p ∧ q is true only when both are true. Disjunction p ∨ q is false only when both are false.
Conditional p → q is false only when p is true and q is false. Biconditional p ↔ q is true when p and q have the same truth value.
For p → q: converse is q → p, inverse is ∼p → ∼q, contrapositive is ∼q → ∼p.
A conditional and its contrapositive are logically equivalent; so are the converse and the inverse.
Onto (surjective): range = B. Into: range ≠ B. One-one (injective): different elements have different images. Bijective: one-one and onto.
Only a bijective function has an inverse function. To find f⁻¹(x), write y = f(x), solve for x, then interchange x and y.
Domain of a real function: leave out values that make a denominator zero or put a negative number under a square root.

Common mistake

Students mark p → q as false whenever p is false. It is the opposite: when p is false the conditional is always true, and the only false case is p true with q false.

Worked example

Show that (p ∧ q) → p is a tautology.

p = T, q = T: p ∧ q = T, and T → T is T.
p = T, q = F: p ∧ q = F, and F → T is T.
p = F, q = T: p ∧ q = F, and F → F is T.
p = F, q = F: p ∧ q = F, and F → F is T.

Answer: The statement is true in all four rows, so it is a tautology.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Sets and set operations Binary operations and groups →Take a Maths test