Problem 28 - Discrete Mathematics with Applications

Question

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$p \wedge q \equiv q \wedge p$$

Step-by-Step Solution

Answer

The statement \(p \wedge q = q \wedge p\) is True, as both sides are equal for all possible combinations of truth values for \(p\) and \(q\).

Step 1: Create a Truth Table

First, we will create a truth table that includes all possible combinations of truth values for \(p\) and \(q\). There are 2 possible truth values (True, False) for each of the two statements, and hence there will be 4 rows in our truth table.

Step 2: Evaluate the LHS

Now, we will evaluate the left-hand side of the equation, \(p \wedge q\). In the truth table, we will write the truth values of the conjunction of \(p\) and \(q\).

Step 3: Evaluate the RHS

Next, we will evaluate the right-hand side of the equation, \(q \wedge p\). In the truth table, we will write the truth values of the conjunction of \(q\) and \(p\).

Step 4: Compare LHS and RHS

Finally, we will compare the truth values of LHS and RHS of the equation for each row of the truth table to determine if they are equal. Here is the complete truth table: | \(p\) | \(q\) | \(p \wedge q\) (LHS) | \(q \wedge p\) (RHS) | |-------|-------|----------------------|----------------------| | T | T | T | T | | T | F | F | F | | F | T | F | F | | F | F | F | F | As we can see from the truth table, for each possible combination of truth values for \(p\) and \(q\), the left-hand side and the right-hand side of the equation are equal. Therefore, the statement \(p \wedge q = q \wedge p\) is True.

Key Concepts

Truth Table

The truth table is a helpful tool in discrete mathematics that allows us to explore the truth values of logical statements. Its purpose is to list all possible combinations of truth values for given propositions.

• In our example, we have two statements, \(p\) and \(q\), each of which can be true (T) or false (F).
• This results in four possible sets of truth values: both true, one true and one false, and both false.

A truth table provides a systematic way to organize these combinations so that we can easily explore their implications in logical expressions. By calculating the truth values for \(p \wedge q\) and \(q \wedge p\), we can see that these expressions have the same truth values in every possible scenario. This demonstration shows that the statement \(p \wedge q = q \wedge p\) is true, illustrating a fundamental property of logical conjunction.

Logical Conjunction

Logical conjunction is a fundamental concept in logic where two statements are combined using the "and" operator, symbolized by \( \wedge \). This operation only results in a true outcome when both constituent statements are true.

• For example, the statement \(p \wedge q\) means "\(p\) and \(q\)."
• This will be true if and only if both \(p\) and \(q\) are true.

This property is evident in the truth table: when both \(p\) and \(q\) are true, \(p \wedge q\) is true, otherwise, it is false. The equality \(p \wedge q = q \wedge p\) demonstrates the commutative property of conjugation, much like addition in arithmetic, where the order of terms does not affect the result.

Tautology

In logic, a tautology is a statement that is always true, regardless of the truth values of its components. Tautologies are significant in mathematical proofs and logical reasoning because they provide universal truths.

• An example of a tautology is the statement \(p \lor eg p\), which reads: "\(p\) or not \(p\)."
• This is true in any scenario because either a statement or its negation must be true.

Tautologies are the backbone of logical reasoning, ensuring that certain conclusions hold under all interpretations. While our exercise example, \(p \wedge q = q \wedge p\), is not a tautology in form, it does emphasize the commutative nature of conjunction, being true for all truth values of \(p\) and \(q\). This is subtly linked to the broader concept of tautology in maintaining logical consistency.

Contradiction

A contradiction is the opposite of a tautology in logic. It is a statement that is invariably false, no matter what the truth values of its components are. Contradictions highlight the impossibility of certain propositions.

• An example is \(p \land eg p\) — "\(p\) and not \(p\)" — which can never be true.
• In this case, since \(p\) and its negation cannot both be true at the same time, the statement is always false.

Contradictions are useful in logical proofs, particularly in methods like proof by contradiction, where assuming a contradiction leads to a logical impossibility, thereby proving the opposite assertion. In our specific example, while testing \(p \wedge q = q \wedge p\), the comparison lends itself to confirming equality rather than highlighting contradiction. However, understanding contradiction ensures one sees why \(p \wedge q = eg (p \wedge q)\) would always be false.