TN 12th Maths — Learn, Visualize, Practice

1. What discrete mathematics studies

Continuous mathematics deals with the real line, where between any two numbers there are uncountably many more. Discrete mathematics instead works with sets whose elements are separated — finite sets, or countably infinite ones like $\mathbb{N} = \{1, 2, 3, \dots\}$ . Its elements can be listed as a sequence with gaps between them, which is exactly why it underpins computer science and logic.

This chapter covers two pillars of discrete mathematics: binary operations (the abstract study of "combining two things to get a third") and mathematical logic (the abstract study of true/false reasoning).

2. Binary operations and closure

Addition, subtraction and multiplication all share a common shape: you feed in two elements of a set and get back a single element. Discrete mathematics makes this idea precise with the notion of a binary operation.

DefinitionBinary operation (Definition 12.1)

A binary operation $*$ on a non-empty set $S$ is a rule $* : S \times S \to S$ that assigns to every ordered pair $(a, b)$ with $a, b \in S$ exactly one element $a * b$ , and crucially that result again lies in $S$ .

The requirement that $a * b$ stays inside $S$ is called closure. It is built into the definition — if the output ever escapes $S$ , then $*$ is simply not a binary operation on $S$ . So the very first thing to check is always: does the output land back in the set?

Which usual operations are binary on which sets

$+$ and $\times$ are binary on $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ — sums and products never leave these sets.
$-$ is binary on $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$ but NOT on $\mathbb{N}$ : $2 - 5 = -3 \notin \mathbb{N}$ .
$\div$ is NOT binary on $\mathbb{Z}$ (e.g. $1 \div 2 = \tfrac12 \notin \mathbb{Z}$ ); it is binary on $\mathbb{Q}\setminus\{0\}$ , since dividing by $0$ is undefined.
Matrix addition and multiplication are binary on the set of all $2 \times 2$ real matrices.

Watch out: To prove something is NOT a binary operation, you only need ONE counterexample where the output leaves the set. To prove it IS, you must argue the output stays in the set for every pair.

ExampleClosure on the integers

Is

a * b = a + b - ab

a binary operation on

\mathbb{Z}

?

ExampleA quotient operation — watch the denominator

Is

a * b = \dfrac{a-1}{b-1}

a binary operation on

\mathbb{Q}

?

ExampleExponentiation on the naturals

Is

a * b = a^{b}

a binary operation on

\mathbb{N}

?

3. Commutative and associative properties

Once $*$ is a binary operation on $S$ , we ask what algebraic laws it obeys. The first two are about the order and grouping of the inputs.

DefinitionCommutative property

$*$ is commutative if $a * b = b * a$ for all $a, b \in S$ — the order of the two inputs does not matter.

DefinitionAssociative property

$*$ is associative if $(a * b) * c = a * (b * c)$ for all $a, b, c \in S$ — when combining three elements, how you bracket them does not matter.

Note: These are separate questions. Subtraction on $\mathbb{Z}$ is neither: $3 - 5 \ne 5 - 3$, and $(8 - 3) - 2 = 3$ while $8 - (3 - 2) = 7$. One counterexample is enough to kill either property.

ExampleTesting commutativity

On

\mathbb{R}

define

a * b = a + b - ab

. Is

*

commutative?

ExampleTesting associativity

On

\mathbb{R}

define

a * b = a + b + ab

. Is

*

associative?

ExampleA quick disproof by counterexample

Show that

a * b = a^{b}

on

\mathbb{N}

is neither commutative nor associative.

4. Identity and inverse elements

The next two properties are about special elements — one that does nothing, and, for each element, one that undoes it.

DefinitionIdentity element

An element $e \in S$ is an identity for $*$ if $a * e = e * a = a$ for every $a \in S$ . For example $0$ is the identity for $+$ and $1$ is the identity for $\times$ .

DefinitionInverse element

If an identity $e$ exists, then $b \in S$ is an inverse of $a$ when $a * b = b * a = e$ , written $b = a^{-1}$ . Under $+$ the inverse of $a$ is $-a$ ; under $\times$ the inverse of $a \ne 0$ is $\tfrac{1}{a}$ .

Note: Two useful theorems: in any algebraic structure the identity element, if it exists, is unique; and the inverse of an element, if it exists, is unique. Read $a^{-1}$ as "the inverse of $a$", NOT as $\tfrac{1}{a}$ — the meaning depends on the operation.

ExampleFinding identity and inverse

On

\mathbb{Z}

define

m * n = m + n - mn

. Find the identity, then the inverse of a general element.

ExampleThe five-property checklist for a familiar operation

Verify closure, commutativity, associativity, identity and inverse for

+

on

\mathbb{Z}

.

5. Operation tables and modular arithmetic

When a set is finite, a binary operation can be displayed completely as a Cayley table (operation table): the entry in row $a$ , column $b$ is $a * b$ . The table lets us read off every property by eye.

DefinitionModular arithmetic

Fix a modulus $n > 1$ . We write $a \equiv b \ (\text{mod } n)$ when $a - b$ is a multiple of $n$ ; here $b$ is the remainder when $a$ is divided by $n$ . On $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$ define $a +_n b$ as the remainder of $a + b$ on division by $n$ .

For example, $25 \equiv 4 \ (\text{mod } 7)$ and $15 \equiv 0 \ (\text{mod } 5)$ . Here is the full Cayley table for $+_5$ on $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ :

+₅	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

ExampleReading properties off the table

Using the

+_5

table, verify closure, commutativity, identity, and find the inverse of

2

.

ExampleMultiplication modulo n

Compute

4 \times_{11} 5

and

9 \times_{11} 3

under multiplication modulo

11

.

6. Mathematical logic: statements

Logic studies reasoning through symbols. Its atoms are statements (also called propositions).

DefinitionStatement (proposition)

A statement is a declarative sentence that is either true or false, but not both. Its truth value is $T$ (true) or $F$ (false).

Statement or not?

" $2 + 3 = 5$ " is a statement (true). " $7$ is even" is a statement (false).
"Chennai is in Tamil Nadu" is a statement (true). "Peacock is our national bird" is a statement (true).
"Close the door." (a command), "What time is it?" (a question) and " $x + 1 = 4$ " (depends on $x$ ) are NOT statements.

A statement built from a single idea is a simple statement; combining simple statements with connectives gives a compound statement. We name simple statements with propositional variables $p, q, r, \dots$

7. Logical connectives and their truth tables

Connectives let us build every compound statement, and each is defined completely by a truth table listing the output for every combination of inputs. A formula with $n$ variables needs $2^n$ rows.

Negation $\neg p$ ("not $p$ ") — reverses the truth value.
Conjunction $p \wedge q$ (" $p$ and $q$ ") — true only when both are true.
Disjunction $p \vee q$ (" $p$ or $q$ ") — false only when both are false (inclusive or).
Conditional $p \to q$ ("if $p$ then $q$ ") — false only when $p$ is true and $q$ is false.
Biconditional $p \leftrightarrow q$ (" $p$ if and only if $q$ ") — true exactly when $p$ and $q$ have the same truth value.
Exclusive or $p \veebar q$ — true when exactly one of $p, q$ is true (not both).

Watch out: The conditional $p \to q$ trips students up: whenever the hypothesis $p$ is false, the whole statement is automatically true ("vacuously true"). Only a true $p$ with a false $q$ makes $p \to q$ false. Also, $p \to q$ does NOT require $p$ and $q$ to be related in meaning.

Key idea: Open the Visualize tab to build these truth tables yourself — pick any compound expression and watch the result column fill in row by row, and compare two expressions side by side to test equivalence.

8. Constructing truth tables for compound statements

To evaluate a compound statement, add one column per sub-expression, working outward from the innermost pieces, and fill each column using the connective definitions.

ExampleA three-column build

Construct the truth table for

(p \vee q) \wedge (p \vee \neg q)

and classify it.

ExampleCounting the rows first

How many rows does the truth table of

(p \wedge q) \vee (\neg r \vee \neg s) \wedge (\neg t \wedge v)

need?

9. Conditional: converse, inverse, contrapositive

From a conditional $p \to q$ we derive three related statements. Only one of them is always logically equivalent to the original.

Converse: $q \to p$ (swap hypothesis and conclusion).
Inverse: $\neg p \to \neg q$ (negate both).
Contrapositive: $\neg q \to \neg p$ (swap AND negate) — this one is equivalent to $p \to q$ .

p \to q \;\equiv\; \neg q \to \neg p \qquad\text{but}\qquad p \to q \;\not\equiv\; q \to p

ExampleWriting all three

For "If

x = y

, then

x^2 = y^2

", write the converse, inverse and contrapositive.

10. Tautology, contradiction, contingency

Look at the final column of a compound statement's truth table. Exactly three cases can occur.

DefinitionTautology

True for every assignment of truth values — the whole final column is $T$ . Denoted $\mathbb{T}$ . Example: $p \vee \neg p$ .

DefinitionContradiction

False for every assignment — the whole final column is $F$ . Denoted $\mathbb{F}$ . Example: $p \wedge \neg p$ .

DefinitionContingency

Neither a tautology nor a contradiction — the final column mixes $T$ and $F$ . Example: $p \wedge q$ .

Note: The negation of a tautology is a contradiction and vice versa. For any statement $p$: $p \vee \neg p$ is a tautology (law of the excluded middle) and $p \wedge \neg p$ is a contradiction.

ExampleIdentifying a tautology

Show that

p \vee \neg p

is a tautology.

ExampleClassifying without guessing

Is

(p \wedge q) \wedge \neg(p \vee q)

a tautology, contradiction or contingency?

11. Logical equivalences and De Morgan's laws

DefinitionLogically equivalent

Two statements are logically equivalent, written $\equiv$ , when their truth-table columns are identical in every row. Equivalently, $A \equiv B$ means $A \leftrightarrow B$ is a tautology.

The equivalences worth memorising:

De Morgan's laws

\neg(p \wedge q) \equiv \neg p \vee \neg q, \qquad \neg(p \vee q) \equiv \neg p \wedge \neg q

Conditional as disjunction

p \to q \equiv \neg p \vee q

Distributive laws

p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r), \quad p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)

Double negation

\neg(\neg p) \equiv p

Note: De Morgan's laws say "not (both)" is the same as "at least one not", and "not (either)" is the same as "neither". They turn the negation of a compound statement into a compound of negations.

ExampleVerifying a De Morgan law by truth table

Verify

\neg(p \wedge q) \equiv \neg p \vee \neg q

.

ExampleProving p → q ≡ ¬p ∨ q

Show the conditional equals a disjunction:

p \to q \equiv \neg p \vee q

.

12. The duality principle

Many logical equivalences come in mirror-image pairs. The duality principle explains why.

DefinitionDual of a statement (Definition 12.19)

The dual of a compound statement is obtained by interchanging $\wedge$ with $\vee$ , and $\mathbb{T}$ with $\mathbb{F}$ , while leaving negations $\neg$ and the variables unchanged.

Principle: if two statements are logically equivalent, then so are their duals. This is exactly why De Morgan's two laws, and the two distributive laws, always appear together — each is the dual of the other. Also, the dual of a dual returns the original statement.

Dual pairs

The dual of $p \wedge (q \vee r)$ is $p \vee (q \wedge r)$ .
The dual of $p \vee \mathbb{F} \equiv p$ is $p \wedge \mathbb{T} \equiv p$ .
The dual of $\neg(p \vee q) \vee [p \vee (p \wedge \neg r)]$ is $\neg(p \wedge q) \wedge [p \wedge (p \vee \neg r)]$ — note $\neg$ is untouched.