Logic and Set | NEB Class 11 Mathematics Notes

Chapter Overview

This unit bridges the deductive process of reasoning (Logic) with the foundational language of mathematics (Set Theory). Logic focuses on statements, their truth values, and logical connectives to form rigorous conclusions. Set Theory focuses on collections of objects, their relationships, and operations. Mastering these dual concepts enables you to write flawless mathematical proofs.

What this chapter covers

Statements and Truth ValuesLogical Connectives (AND, OR, NOT, Implication)Tautology and ContradictionSet Operations (Union, Intersection, Difference, Complement)Symmetric Difference & Power SetsDe Morgan's Laws for Logic and SetsAlgebraic Set ProofsTruth Table Proofs

Learning Objectives

1

Identify and distinguish between valid mathematical statements and non-statements (opinions, questions, open sentences).

2

Construct accurate truth tables for complex compound logical statements.

3

Understand and evaluate the precise truth conditions of Conditional (If-Then) and Biconditional statements.

4

Perform advanced operations on sets, including Difference, Complement, and Symmetric Difference.

5

Verify complex set identities using rigorous algebraic proofs and elements.

6

Recognise the mathematical harmony between Logic and Set Theory (e.g., AND mapping to Intersection, OR to Union).

The Bridge Between Logic and Sets

Key Insight

Logic and Set Theory are practically two different languages describing the exact same mathematical concepts. If you understand one, you automatically understand the other.

Logical AND ($\wedge$) behaves exactly like Set Intersection ($\cap$).
Logical OR ($\vee$) behaves exactly like Set Union ($\cup$).
Logical NOT ($\sim$) behaves exactly like Set Complement ($\overline{A}$).

Example: De Morgan's Law in Logic is $\sim(p \wedge q) \equiv \sim p \vee \sim q$. In Set Theory, the exact equivalent is $\overline{A \cap B} = \overline{A} \cup \overline{B}$. The structure is identical!

Key Definitions

Statement (Proposition)

A declarative sentence that is definitively either True or False. Questions, commands, and open sentences (like $x+2=5$) are not statements.

Tautology & Contradiction

A Tautology is a compound statement that is always True regardless of inputs. A Contradiction is always False.

Power Set ($P(A)$)

The set containing all possible subsets of a given set $A$, including the empty set $\phi$ and the set $A$ itself. If $A$ has $n$ elements, $P(A)$ has $2^n$ elements.

Symmetric Difference ($A \Delta B$)

The set of elements belonging to set $A$ or set $B$, but not both. Formula: $A \Delta B = (A-B) \cup (B-A)$.

Subset ($A \subseteq B$)

Set $A$ is a subset of $B$ if every single element of $A$ is also contained in $B$.

Logic vs. Set Theory Dictionary

Use this side-by-side dictionary to translate logical conditions into set operations seamlessly.

Logic Domain

$$Statements & Connectives$$

Conjunction ($p \wedge q$): True only if BOTH are true.

Disjunction ($p \vee q$): False only if BOTH are false.

Negation ($\sim p$): Inverts the truth value.

Implication ($p \Rightarrow q$): Broken (False) only if $T \Rightarrow F$.

Falsehood / Contradiction ($F$): Always false.

VS

Set Theory Domain

$$Sets & Operations$$

Intersection ($A \cap B$): Elements in BOTH sets.

Union ($A \cup B$): Elements in AT LEAST ONE set.

Complement ($\overline{A}$): Elements NOT in the set.

Subset ($A \subseteq B$): If an element is in A, then it is in B.

Empty Set ($\phi$): Contains no elements.

Memory trick: The symbol $\wedge$ looks like the 'A' in AND. The symbol $\cup$ looks like a 'U' for Union.

Formula Sheet & Proof Derivations

Implication Equivalence

(p \Rightarrow q) \equiv (\sim p \vee q)

Proves that an 'If... Then' statement is logically identical to 'Not p OR q'.

1Let us construct a truth table using KaTeX to compare both expressions.

2$$ \begin{array}{|c|c|c|c|c|} \hline p & q & \sim p & p \Rightarrow q & \sim p \vee q \\ \hline T & T & F & T & T \\ T & F & F & F & F \\ F & T & T & T & T \\ F & F & T & T & T \\ \hline \end{array} $$

3We observe that the columns for $(p \Rightarrow q)$ and $(\sim p \vee q)$ are absolutely identical (T, F, T, T). Therefore, they are logically equivalent.

De Morgan's Law (Sets)

\overline{A \cup B} = \overline{A} \cap \overline{B}

The complement of a union is the intersection of the complements.

1Let us prove this algebraically using the element method.

2Let $x$ be an arbitrary element such that $x \in \overline{A \cup B}$.

3This implies $x \notin (A \cup B)$.

4By definition of union, this means $x \notin A$ AND $x \notin B$.

5By definition of complement, $x \in \overline{A}$ AND $x \in \overline{B}$.

6By definition of intersection, $x \in (\overline{A} \cap \overline{B})$.

7Since this logic is completely reversible (using biconditionals), the sets are equal.

Symmetric Difference

A \Delta B = (A \cup B) - (A \cap B)

An alternative definition: Elements in exactly one of the sets, but not the intersection.

1The standard definition is $A \Delta B = (A - B) \cup (B - A)$.

2Let us expand this logically: it means elements that are strictly in A OR strictly in B.

3If we take all elements in $A \cup B$ (everything in both circles of a Venn diagram), and subtract the elements in $A \cap B$ (the overlapping middle part), we are left with exactly the outer moons.

4Therefore, $(A - B) \cup (B - A)$ is mathematically identical to $(A \cup B) - (A \cap B)$.

Choosing the Right Proof Method

When faced with a proof in the exam, follow this logic to choose your tool.

Does the question involve logical statements (p, q, symbols like \Rightarrow)?

Yes

Use a Truth Table. Create columns for every sub-expression and compare final columns.

No

Continue to next step ↓

Does the question ask to prove a Set Identity (A, B, \cup, \cap)?

Yes

Use the Element Method. Start with 'Let x \in LHS' and use logic words (AND/OR) to reach the RHS.

No

Continue to next step ↓

Is the question asking for Converse, Inverse, or Contrapositive?

Yes

Use Mechanical Swapping. Converse: Swap. Inverse: Negate. Contrapositive: Swap AND Negate.

No

Use Venn Diagrams if visual verification is explicitly requested.

The 'AND/OR' Translation Trick

Trick: When writing set theory proofs, translate set symbols directly into English logic words.

Steps to Remember:

Whenever you see $x \in A \cup B$, instantly translate it to: $x \in A$ OR $x \in B$.
Whenever you see $x \in A \cap B$, instantly translate it to: $x \in A$ AND $x \in B$.
Whenever you see $x \in A - B$, translate it to: $x \in A$ AND $x \notin B$.
Warning: When distributing a NOT ($\notin$), the words flip! $x \notin A \cup B$ becomes $x \notin A$ AND $x \notin B$.

Mnemonic: Union = OR. Intersection = AND. Difference = AND NOT.

Common Mistakes in NEB Exams

These conceptual errors account for the majority of lost marks in the Logic & Set theory section. Please review them carefully.

The F-Falsehood Trap (Logic): Students naturally assume that a false premise leading to a false conclusion ($F \Rightarrow F$) is False. Logically, it is True. Only $T \Rightarrow F$ breaks the rule.
Set Difference Confusion (Sets): Confusing $A-B$ with $B-A$. Remember, $A-B$ means you start with A and throw away anything that belongs to B. You NEVER include elements that are only in B.
Empty Set Inclusion (Sets): Forgetting that the empty set ($\phi$) is always a subset of every set. When making a Power Set, $\phi$ must always be the first element listed.
Improper Negation (Logic): Negating 'All men are honest' does not mean 'No men are honest'. The correct negation is 'Some men are not honest'. Always negate 'All' with 'Some... not'.

Solved Examples (Easy → Hard)

1

Find the truth table for $p \wedge \sim q$.

Easy

Solution

Let us systematically build the truth table. We need columns for $p$, $q$, $\sim q$, and finally the conjunction $p \wedge \sim q$.

$$ \begin{array}{|c|c|c|c|} \hline p & q & \sim q & p \wedge \sim q \\ \hline T & T & F & F \\ T & F & T & T \\ F & T & F & F \\ F & F & T & F \\ \hline \end{array} $$

We know that a conjunction is True only when both components are True. This only happens in the second row where $p=T$ and $\sim q=T$.

∴ Final column is F, T, F, F.

2

If $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$, calculate the Symmetric Difference $A \Delta B$.

Medium

Solution

Let us recall the definition of Symmetric Difference: $A \Delta B = (A - B) \cup (B - A)$.

First, let us find $A - B$. We take elements of $A$ and remove any that are in $B$. The number 3 is in $B$.
$A - B = \{1, 2\}$.

Next, we find $B - A$. We take elements of $B$ and remove any that are in $A$. The number 3 is in $A$.
$B - A = \{4, 5\}$.

Now, we take the union of these two results:
$\{1, 2\} \cup \{4, 5\} = \{1, 2, 4, 5\}$.

∴ A Δ B = {1, 2, 4, 5}

3

Prove algebraically that $A - (B \cup C) = (A - B) \cap (A - C)$.

Hard

Solution

Let us use the element method to prove this set identity.

Let $x \in A - (B \cup C)$.
By the definition of set difference, this implies:
$\iff x \in A$ AND $x \notin (B \cup C)$

Using De Morgan's logic for the NOT inclusion:
$\iff x \in A$ AND ($x \notin B$ AND $x \notin C$)

Using the distributive property of logical AND over AND (associativity):
$\iff (x \in A$ AND $x \notin B)$ AND $(x \in A$ AND $x \notin C)$

Translating back into set notation:
$\iff x \in (A - B)$ AND $x \in (A - C)$
$\iff x \in (A - B) \cap (A - C)$

Since the logical steps are perfectly reversible, the LHS is a subset of the RHS, and the RHS is a subset of the LHS. Therefore, the sets are exactly equal.

∴ Proved via the element method.

MCQ Practice

Mixed Level — MCQ

1

What is the logical negation of the conjunction $p \wedge q$?

Correct!

Incorrect. Correct: $\sim p \vee \sim q$

Solution

Let us recall De Morgan's Laws for logic. We know that when we distribute a negation $\sim$ into a bracket $(p \wedge q)$, it applies to both variables and flips the central operator. Thus, $\sim(p \wedge q) \equiv \sim p \vee \sim q$.

∴ $\sim p \vee \sim q$

2

If a set $A$ contains exactly 3 distinct elements, how many subsets exist in its Power Set $P(A)$?

Correct!

Incorrect. Correct: 8

Solution

Let us recall the fundamental theorem of power sets. We know that if a set has $n$ elements, the total number of possible subsets (including the empty set and the set itself) is $2^n$. Given $n = 3$, we calculate $2^3 = 2 \times 2 \times 2 = 8$.

∴ 8

3

Which of the following is logically equivalent to the implication $p \Rightarrow q$?

Correct!

Incorrect. Correct: $\sim p \vee q$

Solution

Let us rely on truth tables to verify this identity. We know that $p \Rightarrow q$ is only False when $p=T$ and $q=F$. If we test the expression $\sim p \vee q$ for the same inputs ($p=T, q=F$), $\sim p$ becomes $F$. Then $F \vee F$ equals False. In all other cases, it evaluates to True. Because they share the exact same truth table, they are equivalent.

∴ $\sim p \vee q$

4

If the intersection of two sets is the empty set ($A \cap B = \phi$), then sets A and B are strictly defined as:

Correct!

Incorrect. Correct: Disjoint sets

Solution

Let us consider the definition of intersection. We know that $A \cap B$ represents the elements that exist in both sets simultaneously. If this results in an empty set $\phi$, it means they share zero elements. By definition, sets with no common elements are called Disjoint Sets.

∴ Disjoint sets

5

A logical Tautology is defined as a compound statement that is:

Correct!

Incorrect. Correct: Always True

Solution

We know from our definitions that a Tautology represents absolute truth in logic. No matter what truth values are assigned to its individual variables (p, q, r), the final output of the expression will always evaluate to True (T).

∴ Always True

6

Which formula correctly defines the Symmetric Difference between two sets A and B ($A \Delta B$)?

Correct!

Incorrect. Correct: $(A - B) \cup (B - A)$

Solution

Let us visualize a Venn Diagram. We know that Symmetric Difference asks for elements that are in A OR in B, but strictly NOT in both. This consists of two separate 'moon' shapes: the part of A without B ($A - B$) and the part of B without A ($B - A$). Joining these two separate regions requires a Union operation, giving us $(A - B) \cup (B - A)$.

∴ $(A - B) \cup (B - A)$

7

Which of the following is considered a valid mathematical statement?

Correct!

Incorrect. Correct: 5 is a prime number.

Solution

Let us apply the rigid definition of a logical proposition. We know that a statement must declare a fact that is objectively True or False. Commands, questions, and emotional outbursts fail this test. Only the assertion that '5 is a prime number' is a declarative fact capable of being evaluated.

∴ 5 is a prime number.

8

According to the Distributive Law of Set Theory, the expression $A \cup (B \cap C)$ is equal to:

Correct!

Incorrect. Correct: $(A \cup B) \cap (A \cup C)$

Solution

Let us think of this just like basic algebra: $x(y + z) = xy + xz$. In set theory, the operator outside the brackets distributes to both terms inside the brackets, and the operator inside the brackets becomes the main link between the two new groups. Thus, $A \cup$ distributes to $B$ and $C$, resulting in $(A \cup B)$ and $(A \cup C)$, linked by the intersection $\cap$.

∴ $(A \cup B) \cap (A \cup C)$

9

The Law of Double Negation states that $\sim(\sim p)$ is logically equivalent to:

Correct!

Incorrect. Correct: $p$

Solution

Let us construct a quick mental truth table. If $p$ is True, then its negation $\sim p$ is False. If we apply another negation to that False, $\sim(\sim p)$ becomes True again. Because it perfectly returns to the original value of $p$ in all cases, $\sim(\sim p) \equiv p$.

∴ $p$

10

According to De Morgan's Law for sets, the complement of a union, $\overline{A \cup B}$, is equal to:

Correct!

Incorrect. Correct: $\overline{A} \cap \overline{B}$

Solution

Let us apply the structural rules of De Morgan. We know that an overline (complement) extending over a bracket must be distributed to everything inside. The set $A$ becomes $\overline{A}$, the set $B$ becomes $\overline{B}$, and crucially, the union $\cup$ flips upside down into an intersection $\cap$. Thus, $\overline{A \cup B} = \overline{A} \cap \overline{B}$.

∴ $\overline{A} \cap \overline{B}$

Short Questions (2 Marks Each)

1

Is the sentence 'Mathematics is a difficult subject' a valid logical statement? Justify your answer.

[2 marks]

Solution

Let us evaluate the sentence against the mathematical definition of a proposition. We know that a valid statement must be an objective fact that is definitively True or False for everyone.

The difficulty of mathematics is a subjective opinion. It may be true for one person and false for another. Because it lacks universal objective truth, it fails the definition.
Answer: No, it is not a statement because it is a subjective opinion, not a definitive True/False fact.

∴ No, it is a subjective opinion.

2

Given the set $A = \{a, b\}$, write down its complete Power Set $P(A)$.

[2 marks]

Solution

Let us recall that a Power Set $P(A)$ is the set containing all possible subsets of $A$.

First, we know the number of subsets will be $2^n$. Here $n=2$, so there will be $2^2 = 4$ subsets.
We must list them methodically:
1. The empty set (always a subset): $\phi$
2. Subsets with one element: $\{a\}$, $\{b\}$
3. Subsets with two elements (the set itself): $\{a, b\}$

Now, we group them all inside one large set bracket.
Answer: $P(A) = \{\phi, \{a\}, \{b\}, \{a, b\}\}$

∴ { φ, {a}, {b}, {a, b} }

3

Write the Contrapositive of the symbolic statement $p \Rightarrow q$.

[2 marks]

Solution

Let us apply the mechanical rule for forming a contrapositive. We know that to construct it, we must do exactly two things to the original conditional statement.

1. We swap the positions of the hypothesis and the conclusion ($q \Rightarrow p$).
2. We apply a negation to both of those components.

Combining these steps mathematically gives us our result.
Answer: $\sim q \Rightarrow \sim p$

∴ $\sim q \Rightarrow \sim p$

4

Evaluate the intersection of any set A with the empty set: $A \cap \phi$.

[2 marks]

Solution

Let us think about the definition of an intersection. We know that $A \cap B$ represents only the elements that exist in BOTH sets simultaneously.

Since the empty set $\phi$ contains absolutely zero elements, it is impossible for it to share any elements with set $A$. Therefore, the overlap between them contains nothing.
Answer: $A \cap \phi = \phi$

∴ \phi (The empty set)

5

Find the strict logical negation of the mathematical inequality '1 < 2'.

[2 marks]

Solution

Let us carefully consider what negating a mathematical inequality means. We know that 'less than' ($<$) claims a specific relationship. The logical opposite must cover every other possible relationship in mathematics.

If 1 is NOT strictly less than 2, then 1 must be either greater than 2 OR equal to 2. Therefore, the negation symbol flips the inequality and adds the 'equal to' condition.
Answer: $1 \geq 2$

∴ $1 \geq 2$

6

Define the Symmetric Difference of two sets A and B, and provide its mathematical formula.

[2 marks]

Solution

Let us explain the concept logically. We know that the symmetric difference focuses on exclusivity. It represents the collection of elements that belong to set A, or belong to set B, but strictly exclude elements that belong to both.

Mathematically, we take the elements exclusively in A ($A-B$) and unite them with elements exclusively in B ($B-A$).
Answer: The symmetric difference is the set of elements in exactly one of the sets. Formula: $A \Delta B = (A - B) \cup (B - A)$.

∴ Elements in A or B, but not both. A Δ B = (A - B) ∪ (B - A).

7

Evaluate the truth value of the logical expression $T \wedge (F \vee T)$.

[2 marks]

Solution

Let us evaluate the expression step by step, solving the brackets first according to the order of operations.

First, evaluate the bracket $(F \vee T)$. We know that a disjunction (OR) is True if at least one component is True. Thus, $F \vee T$ resolves to $T$.
Now substitute this back into the main expression: $T \wedge T$.
We know that a conjunction (AND) is True only when both sides are True. Thus, $T \wedge T$ resolves to True.
Answer: True.

∴ True

8

If $A = \{x: x^2 - 5x + 6 = 0\}$ and $B = \{2, 3\}$, determine whether these sets are Equal Sets. Justify your reasoning.

[2 marks]

Solution

Let us translate set A from set-builder notation into roster form by solving the quadratic equation.

Given equation: $x^2 - 5x + 6 = 0$
Factorizing: $x^2 - 3x - 2x + 6 = 0$
$x(x - 3) - 2(x - 3) = 0$
$(x - 2)(x - 3) = 0$
Thus, the roots are $x = 2$ and $x = 3$.

Therefore, the elements of Set A are $\{2, 3\}$. Since Set B is also $\{2, 3\}$, they contain the exact same elements.
Answer: Yes, they are Equal Sets.

∴ Yes, solving the quadratic gives {2,3}, which matches B perfectly.

9

Define a 'Contradiction' in mathematical logic, and provide a simple symbolic example.

[2 marks]

Solution

Let us recall the categorization of truth tables. We know that if a compound logical statement evaluates to False in every possible theoretical scenario, it represents an impossible reality.

This absolute falsehood is called a contradiction.
A classic example is asserting that a fact is both true and false simultaneously: $p \wedge \sim p$ ('It is raining AND it is not raining').
Answer: A contradiction is a statement that is always False. Example: $p \wedge \sim p$.

∴ A statement that is always False. Example: p ∧ ~p.

10

If you are given that $A \subseteq B$ and simultaneously $B \subseteq A$, what specific mathematical conclusion can you draw about these two sets?

[2 marks]

Solution

Let us interpret the definitions of subsets logically.

The first premise, $A \subseteq B$, tells us that every single element of A exists inside B. There is nothing in A that B does not have.
The second premise, $B \subseteq A$, tells us that every single element of B exists inside A. There is nothing in B that A does not have.

If neither set possesses elements unique to itself, they must contain the exact same collection of elements.
Answer: The sets are equal, meaning $A = B$.

∴ The sets are equal (A = B).

Long Questions (3-4 Marks Each)

1

Prove using a comprehensive truth table that the conditional statement $p \Rightarrow q$ is logically equivalent to its contrapositive $\sim q \Rightarrow \sim p$.

[4 marks]

Solution

Let us construct a full truth table to evaluate all four possible scenarios for $p$ and $q$, and compare the outputs of both expressions.

$$ \begin{array}{|c|c|c|c|c|c|} \hline p & q & \sim p & \sim q & p \Rightarrow q & \sim q \Rightarrow \sim p \\ \hline T & T & F & F & T & T \\ T & F & F & T & F & F \\ F & T & T & F & T & T \\ F & F & T & T & T & T \\ \hline \end{array} $$

We know that a conditional statement ($p \Rightarrow q$) evaluates to False only when the premise is True and the conclusion is False (Row 2). Evaluating the contrapositive ($\sim q \Rightarrow \sim p$), it also encounters $T \Rightarrow F$ only in Row 2. Because the final columns for both expressions mirror each other exactly as (T, F, T, T), we have successfully proven their logical equivalence.

∴ Proved using Truth Table. Final columns match perfectly.

2

Prove algebraically De Morgan's Law for Set Theory: $\overline{A \cup B} = \overline{A} \cap \overline{B}$.

[4 marks]

Solution

Let us prove this identity using the element method, translating set operations into logical statements.

Let $x$ be an arbitrary element belonging to the left-hand side:
$x \in \overline{A \cup B}$
By the fundamental definition of a complement, this means:
$\iff x \notin (A \cup B)$
By De Morgan's logic regarding the 'NOT' distribution over a union (OR), we state:
$\iff x \notin A$ AND $x \notin B$
By the definition of a complement, replacing NOT IN with IN COMPLEMENT:
$\iff x \in \overline{A}$ AND $x \in \overline{B}$
Finally, by the definition of an intersection (AND maps to $\cap$):
$\iff x \in (\overline{A} \cap \overline{B})$

Since every logical step we took involves a biconditional ($\iff$), the logic works flawlessly in reverse as well. Therefore, the two sets are completely equal.

∴ Proved algebraically using the element method and biconditionals.

3

Show that the logical statement $(p \wedge q) \Rightarrow (p \vee q)$ is a tautology by constructing a truth table.

[3 marks]

Solution

Let us systematically build a truth table resolving the inner brackets first before tackling the main implication.

$$ \begin{array}{|c|c|c|c|c|} \hline p & q & p \wedge q & p \vee q & (p \wedge q) \Rightarrow (p \vee q) \\ \hline T & T & T & T & T \\ T & F & F & T & T \\ F & T & F & T & T \\ F & F & F & F & T \\ \hline \end{array} $$

We know that an implication only resolves to False when a True premise leads to a False conclusion. In Row 1, we have $T \Rightarrow T$, which is True. In Rows 2, 3, and 4, the premise $(p \wedge q)$ is False. Any implication starting with a False premise is automatically True. Because the entire final column evaluates to T, the statement is a proven Tautology.

∴ Proved. Final column consists entirely of 'T'.

4

Prove algebraically that $A - (B \cup C) = (A - B) \cap (A - C)$.

[4 marks]

Solution

Let us employ the element method, converting the set difference into logical AND NOT structures.

Assume an element $x \in A - (B \cup C)$.
By definition of set difference, this translates to:
$\iff x \in A$ AND $x \notin (B \cup C)$
Applying De Morgan's rule to the union negation:
$\iff x \in A$ AND ($x \notin B$ AND $x \notin C$)
Now, we use the Distributive Law of Logic to distribute '$x \in A$ AND' across the brackets:
$\iff (x \in A$ AND $x \notin B)$ AND $(x \in A$ AND $x \notin C)$
Converting these logical phrases back into set difference notation:
$\iff x \in (A - B)$ AND $x \in (A - C)$
Finally, converting the central AND into an intersection:
$\iff x \in (A - B) \cap (A - C)$

Because all steps use equivalence ($\iff$), the equality holds.

∴ Proved using the element method and logical distribution.

5

Prove using a truth table that the negation of an implication is equivalent to a conjunction: $\sim(p \Rightarrow q) \equiv p \wedge \sim q$.

[3 marks]

Solution

Let us construct a comparative truth table to evaluate both sides of the equivalence equation.

$$ \begin{array}{|c|c|c|c|c|c|} \hline p & q & p \Rightarrow q & \sim(p \Rightarrow q) & \sim q & p \wedge \sim q \\ \hline T & T & T & F & F & F \\ T & F & F & T & T & T \\ F & T & T & F & F & F \\ F & F & T & F & T & F \\ \hline \end{array} $$

We know that two compound statements are equivalent if their final output columns are identical. The 4th column representing the left-hand side evaluates to (F, T, F, F). The 6th column representing the right-hand side also evaluates exactly to (F, T, F, F). Therefore, we have successfully verified the equivalence.

∴ Proved using Truth Table comparisons.

6

Prove the Distributive Law of sets: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

[4 marks]

Solution

Let us use the element method to prove this identity by translating Set Theory into formal Logic.

Let $x \in A \cup (B \cap C)$.
By definition of union and intersection, this means:
$\iff x \in A$ OR ($x \in B$ AND $x \in C$)
We know from the logical distributive laws that OR distributes over AND:
$\iff (x \in A$ OR $x \in B)$ AND $(x \in A$ OR $x \in C)$
Translating the OR statements back into unions:
$\iff x \in (A \cup B)$ AND $x \in (A \cup C)$
Translating the central AND statement back into an intersection:
$\iff x \in (A \cup B) \cap (A \cup C)$

As every step relies on fundamental biconditional equivalence, the LHS and RHS denote the exact same set.

∴ Proved using element method and logical distribution of OR over AND.

7

Prove that the compound statement $(p \wedge q) \wedge \sim(p \vee q)$ constitutes a logical contradiction.

[3 marks]

Solution

Let us build a truth table, computing the inner parentheses first to reach the final conjunction.

$$ \begin{array}{|c|c|c|c|c|c|} \hline p & q & p \wedge q & p \vee q & \sim(p \vee q) & (p \wedge q) \wedge \sim(p \vee q) \\ \hline T & T & T & T & F & F \\ T & F & F & T & F & F \\ F & T & F & T & F & F \\ F & F & F & F & T & F \\ \hline \end{array} $$

We know that a logical statement is categorized as a contradiction if it evaluates to False in all possible theoretical realities. Observing the 6th column, which represents the full statement, we see that it results in (F, F, F, F). Because it is impossible for this statement to ever be True, it is firmly proven to be a contradiction.

∴ Proved. Final column consists entirely of 'F'.

8

Prove algebraically that $(A \cap B) \cup (A \cap \overline{B}) = A$.

[4 marks]

Solution

Let us simplify the left-hand side of the equation using the established algebraic laws of Set Theory.

LHS = $(A \cap B) \cup (A \cap \overline{B})$
We can see that the term '$A \cap$' is common to both brackets. We will use the reverse Distributive Law (factoring it out):
$= A \cap (B \cup \overline{B})$

We know from the Complement Law that the union of a set with its own complement results in the Universal Set ($U$):
$= A \cap U$

We know from the Identity Law that the intersection of any set with the Universal Set simply returns the set itself:
$= A$

Since LHS simplifies directly to $A$, which is the RHS, the proof is complete.

∴ Proved algebraically using Distributive, Complement, and Identity Laws.

9

Prove by truth table that the biconditional is logically equivalent to a two-way conditional statement: $(p \Leftrightarrow q) \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)$.

[4 marks]

Solution

Let us construct a comprehensive truth table to verify that an 'If and only if' statement operates identically to two implications meeting via conjunction.

$$ \begin{array}{|c|c|c|c|c|c|} \hline p & q & p \Leftrightarrow q & p \Rightarrow q & q \Rightarrow p & (p \Rightarrow q) \wedge (q \Rightarrow p) \\ \hline T & T & T & T & T & T \\ T & F & F & F & T & F \\ F & T & F & T & F & F \\ F & F & T & T & T & T \\ \hline \end{array} $$

We know that a biconditional $p \Leftrightarrow q$ requires both sides to perfectly match to be True (Row 1 and Row 4), giving us (T, F, F, T). Evaluating the right-hand expression, the conjunction evaluates to True only when both individual implications are True, which also results in (T, F, F, T). Since the columns are identical, the equivalence is proven.

∴ Proved using Truth Table. Columns match perfectly.

10

Given the Universal set $U=\{1,2,3,4,5,6,7,8,9,10\}$, $A=\{1,2,3\}$, and $B=\{3,4,5\}$. Find the Symmetric Difference $A \Delta B$, and then verify your answer using the alternate formula $(A \cup B) - (A \cap B)$.

[4 marks]

Solution

Let us solve this systematically in two separate parts to verify the formulas match.

Part 1: Using the standard definition $A \Delta B = (A - B) \cup (B - A)$
First, find $A - B$ (elements strictly in A). The element 3 is in B, so we remove it: $\{1, 2\}$.
Next, find $B - A$ (elements strictly in B). The element 3 is in A, so we remove it: $\{4, 5\}$.
Union them together: $\{1, 2\} \cup \{4, 5\} = \{1, 2, 4, 5\}$.

Part 2: Using the alternate formula $(A \cup B) - (A \cap B)$
First, find the total union $A \cup B$: $\{1, 2, 3, 4, 5\}$.
Next, find the intersection $A \cap B$: $\{3\}$.
Now subtract the intersection from the union: $\{1, 2, 3, 4, 5\} - \{3\} = \{1, 2, 4, 5\}$.

Since both methods yield exactly $\{1, 2, 4, 5\}$, we have successfully found and verified the symmetric difference.

∴ A Δ B = {1, 2, 4, 5}. Verified by both methods.

One-Page Revision Cheat Sheet

1

Proposition strictness: Logical sentences must be exclusively True or False. Unknown variables (x=2), questions, and commands are disqualified.

2

Implication Trap ($p \Rightarrow q$): The most tested connective. It evaluates to FALSE only when $T \Rightarrow F$. A false premise ($F \Rightarrow F$) evaluates to TRUE.

3

De Morgan's Trick: Distributing a negation ($\sim$ or complement bar) forces the inner operator to flip. AND becomes OR. $\cup$ becomes $\cap$.

4

Contrapositive rules: $\sim q \Rightarrow \sim p$ is mathematically identical to the original $p \Rightarrow q$. The converse ($q \Rightarrow p$) is a totally different statement.

5

Tautology vs Contradiction: A truth table full of 'T's is a Tautology. A table full of 'F's is a Contradiction.

6

AND vs Intersection: $p \wedge q$ behaves exactly like $A \cap B$. Both demand strict inclusivity.

7

OR vs Union: $p \vee q$ behaves exactly like $A \cup B$. Both are lenient and inclusive.

8

Symmetric Difference: The exclusive 'OR'. It demands elements that are in A or B, but rigidly NOT in both. $A \Delta B = (A-B) \cup (B-A)$.

9

Power Set Math: A set with $n$ elements will always spawn exactly $2^n$ subsets in its power set. Never forget the empty set $\phi$!

10

Proof Strategies: Use truth tables for logical $p/q$ symbols. Use 'Let $x \in$ LHS' with AND/OR word translations for Set Theory proofs.