Problem 7 - A Gentle Introduction to the Art of Mathematics

Question

Find the disjunctive normal form of \((A \triangle B) \triangle C\).

Step-by-Step Solution

Answer

Disjunctive normal form is \( (A \land \eg B \land \eg C) \lor (\eg A \land B \land \eg C) \lor (\eg A \land B \land C) \lor (A \land \eg B \land C) \)

Step 1 - Understand the Symmetric Difference

The symmetric difference of two logical statements, denoted by \(A \triangle B\), is true when either A or B is true, but not both. It is equivalent to \((A \land \eg B) \lor (\eg A \land B)\).

Step 2 - Apply Symmetric Difference Definition

Apply the definition of symmetric difference to \(A \triangle B\). \(A \triangle B = (A \land \eg B) \lor (\eg A \land B)\).

Step 3 - Substitute Back into the Original Expression

Substitute \(A \triangle B\) into the original expression: \((A \triangle B) \triangle C = ((A \land \eg B) \lor (\eg A \land B)) \triangle C\).

Step 4 - Redistribute Symmetric Difference

Replace \((x \triangle C)\) using the symmetric difference properties: \(P \triangle Q = (P \land \eg Q) \lor (\eg P \land Q)\): \[ ((A \land \eg B) \triangle C) \lor ((\eg A \land B) \triangle C) \rightarrow (((A \land \eg B) \land \eg C) \lor (\eg (A \land \eg B) \land C)) \lor (((\eg A \land B) \land \eg C) \lor (\eg (\eg A \land B) \land C)) \]

Step 5 - Apply De Morgan's Law

Apply De Morgan's Law and simplify: \[ = ((A \land \eg B \land \eg C) \lor (\eg A \lor B \lor C)) \lor ((\eg A \land B \land \eg C) \lor (A \lor \eg B \lor C)) \]

Step 6 - Combine All Terms and Simplify

Combine all terms and simplify: \[ = (A \land \eg B \land \eg C) \lor (\eg A \land B \land \eg C) \lor (\eg A \land B \land C) \lor (A \land \eg B \land C)\]

Key Concepts

Symmetric Difference

To start with, let's understand the concept of symmetric difference. The symmetric difference of two sets (or logical statements) is denoted by \(A \triangle B\). It means the elements that are in either of the sets but not in their intersection. In other words, it is true if one, and only one, of the statements is true. This is represented as:
\[ A \triangle B = (A \land \eg B) \lor (\eg A \land B) \].
Here’s how to break it down:

• \(A \land \eg B\): This is true when A is true, and B is false.
• \(\eg A \land B\): This is true when A is false, and B is true.

De Morgan's Laws

Next, let's dive into De Morgan's Laws. These laws help in transforming complex logical expressions into simpler ones. They are:
\[ \eg (A \land B) = \eg A \lor \eg B \] \[ \eg (A \lor B) = \eg A \land \eg B \]
By applying these laws, we can simplify expressions by breaking down negations that are applied to entire conditions. Let’s take an example:
\( \eg (A \land B) \rightarrow \eg A \lor \eg B \).
Instead of dealing with a complicated expression, we now have two simpler terms combined with a logical OR operator (<\lor>).
These laws are critical when simplifying and converting logical statements into a form that’s easier to analyze.

Logical Statements Simplification

Finally, let’s discuss simplifying logical statements. Simplification involves reducing a complex expression to its simplest form. We use logical equivalence and properties like distribution, associative, commutative, and De Morgan's laws to achieve this.
In our example, the expression \[ (A \triangle B) \triangle C \] first transforms into: \[ ((A \land \eg B) \lor (\eg A \land B)) \triangle C \].
Then substitute by breaking down further into:
\[ (((A \land \eg B) \land \eg C) \lor (\eg (A \land \eg B) \land C)) \lor (((\eg A \land B) \land \eg C) \lor (\eg (\eg A \land B) \land C)) \]
Simplify using De Morgan's laws:
\[ = ((A \land \eg B \land \eg C) \lor (\eg A \lor B \lor C)) \lor ((\eg A \land B \land \eg C) \lor (A \lor \eg B \lor C)) \]
Combine terms to get the final simplified form:
\[ (A \land \eg B \land \eg C) \lor (\eg A \land B \land \eg C) \lor (\eg A \land B \land C) \lor (A \land \eg B \land C) \].
Simplifying logical statements helps in making the analysis and computation more efficient.