Discrete Mathematics: One Mark Questions, Book Back Answers and Notes

About Discrete Mathematics

Medium ~210 min study

Discrete mathematics deals with objects that take separate, countable values rather than values that change smoothly. In this unit the textbook looks at two such topics. The first is binary operations: rules like addition or multiplication that take two elements of a set and give one element back. The second is mathematical logic, where sentences are treated like algebraic symbols that can be true or false.

In the first part you check whether a given rule is a binary operation on a set and which properties it has. For example, subtraction is a binary operation on \(\mathbb{Z}\) but not on \(\mathbb{N}\), because \(2 - 5\) is not a natural number. You also work with finite systems such as \(\mathbb{Z}_5\) under addition modulo 5, and with matrices whose entries are only 0 and 1.

In the second part you write statements in symbols using \(\neg\), \(\wedge\), \(\vee\), \(\rightarrow\) and \(\leftrightarrow\), and build truth tables to decide their truth values. Book back MCQs here are usually direct: count the rows of a truth table, spot a tautology, find an identity element, or pick the contrapositive of a statement. Learn the truth tables of the five connectives by heart; most of these questions reduce to reading one of them.

What you'll learn

• Check whether a given rule is a binary operation on a set by testing closure.
• Test commutative and associative properties and find the identity element and inverses where they exist.
• Compute sums and products modulo n and use Cayley tables for these operations.
• Build truth tables for compound statements involving all five connectives.
• Classify a statement as a tautology, contradiction or contingency.
• Use the laws of logical equivalence, including De Morgan's laws, to simplify statements.

Before you start

• Sets and the number systems N, Z, Q and R.
• Properties of ordinary addition and multiplication.
• Matrix notation and operations from Unit 1.

Discrete Mathematics explained

Binary Operations and Mathematical Logic

Binary Operations

A binary operation \(*\) on a non-empty set \(S\) is a rule that assigns to each ordered pair \((a, b)\) of elements of \(S\) a unique element \(a * b\) that is also in \(S\). The last condition is the closure property, and it is the first thing to check. Addition is a binary operation on \(\mathbb{N}\), but subtraction is not, and division is not a binary operation even on \(\mathbb{R}\), because division by zero is undefined. Once closure holds, you test the other properties. The operation is commutative if \(a * b = b * a\) and associative if \((a * b) * c = a * (b * c)\) for all elements. An identity \(e\) satisfies \(a * e = e * a = a\), and when it exists it is unique. An inverse of \(a\) is an element \(a'\) with \(a * a' = a' * a = e\). You can only talk about inverses after you have found the identity.

Modular Arithmetic and Boolean Matrices

Addition modulo \(n\), written \(+_n\), adds two integers and keeps the remainder on division by \(n\). Multiplication modulo \(n\), written \(\times_n\), does the same with the product. In \(\mathbb{Z}_5\), \(3 +_5 4 = 2\) and \(3 \times_5 4 = 2\). The identity for \(+_n\) is 0 and the identity for \(\times_n\) is 1. Cayley tables for these operations make it easy to read off identities and inverses. A Boolean matrix has only 0 and 1 as entries. The join \(A \vee B\) takes the larger of the corresponding entries and the meet \(A \wedge B\) takes the smaller. Both operations are commutative and associative on the set of Boolean matrices of a fixed order.

Statements and Truth Tables

A statement (proposition) is a sentence that is either true or false, but not both. Questions, commands and exclamations are not statements. A simple statement cannot be broken into smaller statements; a compound statement is built from simple ones using connectives. Negation \(\neg p\) reverses the truth value. The conjunction \(p \wedge q\) is true only when both parts are true. The disjunction \(p \vee q\) is false only when both parts are false. A truth table lists every combination of truth values of the simple statements, so with \(n\) simple statements the table has \(2^n\) rows.

Conditional and Biconditional Statements

The conditional \(p \rightarrow q\) reads "if \(p\) then \(q\)". It is false only when \(p\) is true and \(q\) is false; in every other row it is true, including when \(p\) is false. The biconditional \(p \leftrightarrow q\) reads "\(p\) if and only if \(q\)" and is true exactly when \(p\) and \(q\) have the same truth value. From \(p \rightarrow q\) we form the converse \(q \rightarrow p\), the inverse \(\neg p \rightarrow \neg q\) and the contrapositive \(\neg q \rightarrow \neg p\). The statement and its contrapositive are logically equivalent. The converse and the inverse are equivalent to each other, but not to the original statement.

Tautologies, Duality and Logical Equivalence

A compound statement is a tautology if the last column of its truth table is all T, a contradiction if it is all F, and a contingency otherwise. For example, \(p \vee \neg p\) is a tautology and \(p \wedge \neg p\) is a contradiction. The dual of a statement is obtained by swapping \(\wedge\) with \(\vee\) and T with F. Two statements are logically equivalent, written \(p \equiv q\), when they have identical truth values in every row. The standard laws include the idempotent, commutative, associative, distributive, identity, complement, absorption and De Morgan's laws, such as \(\neg(p \wedge q) \equiv \neg p \vee \neg q\). A useful one to remember is \(p \rightarrow q \equiv \neg p \vee q\). With these laws you can simplify an expression step by step instead of drawing a full truth table.

Common mistakes to avoid

• Calling an operation binary without checking closure, for example subtraction on N, where 2 − 5 leaves the set.
• Treating p → q as false when p is false. The conditional is false only when p is true and q is false.
• Writing the contrapositive of p → q as ¬p → ¬q. That is the inverse; the contrapositive is ¬q → ¬p.
• Applying De Morgan's laws without switching the connective: ¬(p ∧ q) is ¬p ∨ ¬q, not ¬p ∧ ¬q.
• Looking for inverses before finding the identity element, or checking a ∗ e = a on one side only.

Test yourself on these with the practice test, then check the worked reasoning in the solved MCQs.

Frequently asked questions

What is the difference between a simple and compound statement?

A simple statement expresses one fact and cannot be split into smaller statements, like '5 is a prime number'. A compound statement joins simple statements using connectives such as 'and', 'or', 'if then', or uses 'not'. Its truth value depends on the truth values of its parts.

How do you prove an operation is commutative?

Take two arbitrary elements a and b of the set and show that a ∗ b = b ∗ a. It is not enough to check one or two pairs; the equality must hold for every pair. To show an operation is not commutative, a single counterexample is enough.

What defines a tautology in logic?

A tautology is a compound statement that is true for every possible combination of truth values of its simple statements. The last column of its truth table contains only T. The simplest example is p ∨ ¬p.

What is the role of the identity element?

The identity element e leaves every element unchanged under the operation: a ∗ e = e ∗ a = a. For addition on Z the identity is 0, and for multiplication it is 1. If an identity exists it is unique, and inverses are defined with respect to it.

How does modular arithmetic differ from regular arithmetic?

In arithmetic modulo n you do the usual addition or multiplication and then keep only the remainder after dividing by n. So the answers always lie in {0, 1, ..., n − 1}. For example, 4 ×₆ 5 = 20 leaves remainder 2, so the answer is 2.

Why is the contrapositive useful in mathematics?

The contrapositive of p → q is ¬q → ¬p, and the two are logically equivalent. So proving the contrapositive proves the original statement. Sometimes it is easier, for example showing 'if n² is even then n is even' by proving 'if n is odd then n² is odd'.