Questions and Answers Section

Question 1

Construct the truth table for the statement $(p \implies q) \land (q \implies p)$, which is $p \iff q$.

Explanation: A truth table systematically evaluates a logical expression for all possible combinations of truth values of its simple propositions.

1. Columns Setup: We need columns for our basic propositions, $p$ and $q$. We also need intermediate columns for each part of the expression, $p \implies q$ and $q \implies p$, and a final column for the complete expression.
2. Evaluating Implications: An implication $A \implies B$ is only False when $A$ is True and $B$ is False. Otherwise, it is True.
3. Evaluating Conjunction (AND): The final expression $(p \implies q) \land (q \implies p)$ is a conjunction (AND). It is only True when both of its parts are True.

Truth Table:

$p$	$q$	$p \implies q$	$q \implies p$	$(p \implies q) \land (q \implies p)$
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

Observation: The final column, which represents the biconditional statement $p \iff q$, is True only when $p$ and $q$ have the same truth value (both True or both False).

Question 2

Show that the statement $(p \land q) \implies p$ is a tautology.

Explanation: A tautology is a compound statement that is always True, regardless of the truth values of the individual propositions. We can prove this using a truth table.

1. Columns Setup: We need columns for $p$, $q$, the hypothesis $(p \land q)$, and the final implication.
2. Evaluating the Hypothesis: The column for $p \land q$ is True only when both $p$ and $q$ are True.
3. Evaluating the Implication: The final column for $(p \land q) \implies p$ is evaluated. Remember that an implication is only False if the hypothesis is True and the conclusion is False.

Truth Table:

$p$	$q$	$p \land q$ (Hypothesis)	$(p \land q) \implies p$
T	T	T	T $\implies$ T = T
T	F	F	F $\implies$ T = T
F	T	F	F $\implies$ F = T
F	F	F	F $\implies$ F = T

Conclusion: Since every entry in the final column is True, the statement is a tautology. This logical rule is known as the Law of Simplification, as it states that if a conjunction is true, then each of its components must be true.

Question 3

Write the converse, inverse, and contrapositive of the statement: "If a number is a multiple of 9, then it is a multiple of 3."

Explanation: First, let's define our propositions and the original statement's form.

• Let $p$: "a number is a multiple of 9."
• Let $q$: "a number is a multiple of 3."
• The original statement is an implication: $p \implies q$.

For any implication $p \implies q$, we can define three related implications:

1. Converse (Form: $q \implies p$): We swap the hypothesis and the conclusion.

   • In Words: "If a number is a multiple of 3, then it is a multiple of 9."
   • (Note: This statement is false. For example, 6 is a multiple of 3 but not of 9.)

2. Inverse (Form: $\sim p \implies \sim q$): We negate both the hypothesis and the conclusion.

   • In Words: "If a number is not a multiple of 9, then it is not a multiple of 3."
   • (Note: This is also false. The number 6 is not a multiple of 9, but it is a multiple of 3.)

3. Contrapositive (Form: $\sim q \implies \sim p$): We negate both propositions and swap their order.

   • In Words: "If a number is not a multiple of 3, then it is not a multiple of 9."
   • (Note: This statement is true and is logically equivalent to the original statement.)

Question 4

Use a truth table to prove De Morgan's Law: $\sim(p \land q) \equiv \sim p \lor \sim q$.

Explanation: To prove that two logical expressions are equivalent, we can construct a truth table and show that their corresponding columns are identical for all possible truth value combinations.

1. Identify LHS and RHS:

   • Left-Hand Side (LHS): $\sim(p \land q)$
   • Right-Hand Side (RHS): $\sim p \lor \sim q$

2. Construct the Table: We will build the table by first evaluating the expressions inside the parentheses and the negations, then combining them.

Truth Table:

$p$	$q$	$p \land q$	LHS: $\sim(p \land q)$	$\sim p$	$\sim q$	RHS: $\sim p \lor \sim q$
T	T	T	F	F	F	F $\lor$ F = F
T	F	F	T	F	T	F $\lor$ T = T
F	T	F	T	T	F	T $\lor$ F = T
F	F	F	T	T	T	T $\lor$ T = T

Conclusion: The column for the LHS, $\sim(p \land q)$, is identical to the column for the RHS, $\sim p \lor \sim q$. Since they have the same truth value in every case, the two statements are logically equivalent.

Question 5

Negate the statement: "There exists a real number $x$ such that for all real numbers $y$, $xy=1$."

Explanation: This problem involves negating a statement with multiple quantifiers.

1. Translate to Symbolic Form:

   • "There exists" is the existential quantifier, $\exists$.
   • "for all" is the universal quantifier, $\forall$.
   • The predicate (the property) is $(xy=1)$. The statement is: $\exists x \in R, \forall y \in R, (xy=1)$.

2. Apply the Rule for Negating Quantifiers: To negate a sequence of quantifiers, you flip each quantifier and negate the predicate at the end. The rule is $\sim (\exists x, \forall y, P(x,y)) \equiv \forall x, \exists y, \sim P(x,y)$.

   • The first quantifier $\exists$ flips to $\forall$.
   • The second quantifier $\forall$ flips to $\exists$.
   • The predicate $(xy=1)$ is negated to $(xy \neq 1)$.

3. Write the Negated Symbolic Form: The negation is: $\forall x \in R, \exists y \in R, (xy \neq 1)$.

4. Translate Back to English: Translating the negated symbols back into words gives us: "For all real numbers $x$, there exists a real number $y$ such that $xy \neq 1$."

Question 6

Use a proof by contradiction to show that if $5n+3$ is an even integer, then $n$ must be an odd integer.

Explanation: A proof by contradiction works by assuming the opposite of what you want to prove and showing that this assumption leads to a logical impossibility (a contradiction).

1. State the Original Statement: Let $p$: "$5n+3$ is even" and $q$: "$n$ is odd". We want to prove $p \implies q$.

2. Set up the Assumption for Contradiction: We assume that the statement $p \implies q$ is false. This happens only when $p$ is true and $q$ is false. So, we assume that $5n+3$ is even AND $n$ is not odd (i.e., $n$ is even).

3. Derive Consequences from the Assumption: Since we assumed $n$ is even, by definition, $n$ can be written as $n = 2k$ for some integer $k$.

4. Reach a Contradiction: Now, substitute this into the expression $5n+3$: $5n+3 = 5(2k) + 3 = 10k+3$. We can rewrite this as: $10k+2+1 = 2(5k+1)+1$. Let $m = 5k+1$. Since $k$ is an integer, $m$ is also an integer. The expression is of the form $2m+1$, which is the definition of an odd number. This means that if $n$ is even, then $5n+3$ must be odd. This contradicts our initial premise that $5n+3$ is even.

5. Conclusion: Our assumption led to a contradiction, so the assumption must be false. Therefore, the original statement "if $5n+3$ is even, then $n$ is odd" must be true.

Question 7

Check whether the statement $(p \implies q) \lor (q \implies p)$ is a tautology, contradiction, or contingency.

Explanation: We can determine the nature of the statement by constructing a truth table to see if it's always true (tautology), always false (contradiction), or sometimes true and sometimes false (contingency).

1. Columns Setup: We need columns for $p$, $q$, the two implications $p \implies q$ and $q \implies p$, and the final disjunction (OR) of these two.
2. Evaluating the Implications: An implication is only False when T $\implies$ F.
3. Evaluating the Disjunction (OR): The final column is True if at least one of the two implications is True.

Truth Table:

$p$	$q$	$p \implies q$	$q \implies p$	$(p \implies q) \lor (q \implies p)$
T	T	T	T	T $\lor$ T = T
T	F	F	T	F $\lor$ T = T
F	T	T	F	T $\lor$ F = T
F	F	T	T	T $\lor$ T = T

Conclusion: Since every entry in the final column is True, the statement is a tautology.

Question 8

Write the contrapositive of the inverse of the statement: "If it rains, then I will not go to school."

Explanation: This is a multi-step transformation. Let's break it down.

1. Symbolic Form of Original Statement:

   • Let $p$: "it rains."
   • Let $q$: "I will not go to school."
   • The statement is $p \implies q$.

2. Step 1: Find the Inverse:

   • The inverse of an implication $A \implies B$ is $\sim A \implies \sim B$.
   • Applying this to our statement, the inverse is $\sim p \implies \sim q$.
   • In words: "If it does not rain, then I will go to school."

3. Step 2: Find the Contrapositive of the Result from Step 1:

   • Now, we need to find the contrapositive of the inverse statement, $\sim p \implies \sim q$.
   • The contrapositive of an implication $A \implies B$ is $\sim B \implies \sim A$.
   • Here, $A = \sim p$ and $B = \sim q$.
   • The contrapositive is $\sim (\sim q) \implies \sim (\sim p)$.

4. Simplify and Translate:

   • Using the double negation law ($\sim(\sim A) \equiv A$), the expression simplifies to $q \implies p$.
   • This form, $q \implies p$, is the converse of the original statement.
   • Translating $q \implies p$ back to words: "If I will not go to school, then it rains."

Question 9

Disprove the following statement by finding a counterexample: "For all real numbers $x$, if $x^2 > 4$, then $x > 2$."

Explanation: To disprove a universal statement (a statement that claims to be true "for all" numbers), we only need to find a single instance where it is false. This instance is called a counterexample.

1. Analyze the Statement: The statement is an implication $p \implies q$, where:

   • Hypothesis ($p$): $x^2 > 4$
   • Conclusion ($q$): $x > 2$

2. Condition for a Counterexample: A counterexample is a value of $x$ that makes the implication false. An implication $p \implies q$ is false only when the hypothesis ($p$) is True and the conclusion ($q$) is False.

3. Find a Suitable Value for x:

   • We need $x^2 > 4$ to be True. This is true for $x > 2$ or $x < -2$.
   • We need $x > 2$ to be False. This is true for $x \le 2$. We must find an $x$ that satisfies both conditions simultaneously. Looking at the ranges, any number $x < -2$ will work.

4. Test a Counterexample: Let's choose $x = -3$.

   • Check the hypothesis: Is $(-3)^2 > 4$? Yes, $9 > 4$ is True.
   • Check the conclusion: Is $-3 > 2$? No, this is False.

Conclusion: Since $x = -3$ makes the hypothesis true and the conclusion false, it is a valid counterexample that disproves the statement.

Question 10

Translate the statement "The square of any even integer is divisible by 4" into symbolic form using quantifiers.

Explanation: Symbolic translation helps clarify the logical structure of a statement.

1. Identify the Universe: The statement is about integers. The set of all integers is denoted by $Z$.

2. Identify the Quantifier: The phrase "any" (or "all", "every") implies the universal quantifier, $\forall$ (For all).

3. Identify the Logical Structure: The statement has an "if-then" structure.

   • Hypothesis ($P(n)$): "$n$ is an even integer."
   • Conclusion ($Q(n)$): "$n^2$ is divisible by 4." The structure is $P(n) \implies Q(n)$.

4. Combine the Parts: We combine the quantifier, the universe, and the implication to form the complete symbolic statement.

   "For all integers n, if n is even, then n² is divisible by 4."

   In symbolic form, this is: $\forall n \in Z, (n \text{ is even} \implies n^2 \text{ is divisible by 4})$

   If we define $P(n)$ and $Q(n)$ as above, the more compact form is: $\forall n \in Z, (P(n) \implies Q(n))$.

Question 11

Prove that $\sim(p \iff q)$ is logically equivalent to $p \iff \sim q$.

Explanation: To prove logical equivalence, we can show that both statements have identical truth tables.

1. Identify LHS and RHS:

   • Left-Hand Side (LHS): $\sim(p \iff q)$
   • Right-Hand Side (RHS): $p \iff \sim q$

2. Rule for Biconditional ($\iff$): A biconditional statement is True only when its two components have the same truth value.

3. Construct the Truth Table:

$p$	$q$	$p \iff q$	LHS: $\sim(p \iff q)$	$\sim q$	RHS: $p \iff \sim q$
T	T	T	F	F	T $\iff$ F is F
T	F	F	T	T	T $\iff$ T is T
F	T	F	T	F	F $\iff$ F is T
F	F	T	F	T	F $\iff$ T is F

Conclusion: The final column for the LHS is (F, T, T, F). The final column for the RHS is also (F, T, T, F). Since the columns are identical, the two statements are logically equivalent. This means that the negation of a biconditional is equivalent to one part being biconditionally related to the negation of the other part.

Question 12

Provide a direct proof for the statement: "The product of two odd integers is an odd integer."

Explanation: A direct proof is a method where we assume the hypothesis is true and use definitions, axioms, and logical steps to directly show that the conclusion must also be true.

1. State the Hypothesis: Let $m$ and $n$ be two arbitrary odd integers.

2. Use the Definition of an Odd Integer: By definition, an integer is odd if it can be written in the form $2k+1$ for some integer $k$. Since $m$ and $n$ are odd, we can write:

   • $m = 2k+1$, for some integer $k$.
   • $n = 2j+1$, for some integer $j$.

3. Perform the Algebraic Manipulation: We want to show that their product, $mn$, is also odd. Let's calculate the product: $mn = (2k+1)(2j+1)$ $mn = 4kj + 2k + 2j + 1$

4. Show the Result Fits the Definition: To show that $mn$ is odd, we need to express it in the form $2(\text{integer})+1$. We can factor out a 2 from the first three terms: $mn = 2(2kj + k + j) + 1$ Since $k$ and $j$ are integers, the term $(2kj + k + j)$ is also an integer. Let's call this integer $p$. Then, $mn = 2p+1$.

5. Conclusion: Since the product $mn$ can be written in the form $2p+1$, by definition, the product of two odd integers is an odd integer.

Question 13

Write the negation of the statement: "If I study, then I will pass the exam."

Explanation: It's a common mistake to think the negation of "If P, then Q" is "If P, then not Q". The correct method is to use logical equivalences.

1. Translate to Symbolic Form:

   • Let $p$: "I study."
   • Let $q$: "I will pass the exam."
   • The statement is an implication: $p \implies q$.

2. Use the Implication Equivalence: An implication is logically equivalent to a disjunction: $p \implies q \equiv \sim p \lor q$.

3. Negate the Equivalent Form: We need to find the negation of the original statement, which is $\sim(p \implies q)$. This is the same as finding the negation of the equivalent form: $\sim (\sim p \lor q)$.

4. Apply De Morgan's Law: De Morgan's Law states that $\sim(A \lor B) \equiv \sim A \land \sim B$. Applying this: $\sim(\sim p) \land (\sim q)$

5. Simplify and Translate Back to English: Using the double negation law, $\sim(\sim p) \equiv p$. The final symbolic form is $p \land \sim q$. Translating this back to words:

   • $p$: "I study"
   • $\land$: "and"
   • $\sim q$: "I will not pass the exam"

   The final negated statement is: "I study and I will not pass the exam."

Question 14

Check if the statement $(\sim p \land p) \implies (p \lor q)$ is a tautology.

Explanation: A tautology is a statement that is always true.

1. Analyze the Hypothesis: The hypothesis of the implication is the expression $(\sim p \land p)$. This is the Law of Non-Contradiction. It states that a proposition and its negation cannot be true at the same time. Therefore, the statement $(\sim p \land p)$ is a contradiction, meaning it is always False (F).

2. Analyze the Implication with a False Hypothesis: The full statement is of the form $H \implies C$, where $H$ is the hypothesis and $C$ is the conclusion. We have determined that the hypothesis $H$ is always False. Let's recall the truth table for an implication:

   • T $\implies$ T is True
   • T $\implies$ F is False
   • F $\implies$ T is True
   • F $\implies$ F is True

   An implication with a false hypothesis is always True, regardless of the truth value of the conclusion. This principle is sometimes called the "Principle of Vacuous Truth."

3. Conclusion: Since the hypothesis $(\sim p \land p)$ is always False, the entire implication $(\sim p \land p) \implies (p \lor q)$ is always True. Therefore, the statement is a tautology.

Question 15

Write the inverse of the converse of the statement: "If the weather is good, we will have a picnic."

Explanation: This is a multi-step transformation. Let's break it down.

1. Symbolic Form of Original Statement:

   • Let $p$: "the weather is good."
   • Let $q$: "we will have a picnic."
   • The original statement is $p \implies q$.

2. Step 1: Find the Converse:

   • The converse of an implication $A \implies B$ is $B \implies A$.
   • Applying this to our statement, the converse is $q \implies p$.
   • In words: "If we will have a picnic, then the weather is good."

3. Step 2: Find the Inverse of the Result from Step 1:

   • Now, we need to find the inverse of the converse statement, $q \implies p$.
   • The inverse of an implication $A \implies B$ is $\sim A \implies \sim B$.
   • Here, $A = q$ and $B = p$.
   • The inverse is $\sim q \implies \sim p$.

4. Simplify and Translate:

   • The resulting form, $\sim q \implies \sim p$, is the contrapositive of the original statement ($p \implies q$).
   • Translating $\sim q \implies \sim p$ back to words: "If we will not have a picnic, then the weather is not good."

Question 16

What can you say about the truth value of $p \iff q$ if the statement $(p \lor q) \land (\sim p)$ is true?

Explanation: We are given a compound statement and told that it is true. We can use this information to deduce the individual truth values of $p$ and $q$.

1. Analyze the Given True Statement: The statement is $(p \lor q) \land (\sim p)$. This is a conjunction (AND). For a conjunction to be true, both of its parts must be true.

   • Part 1: $(\sim p)$ must be True.
   • Part 2: $(p \lor q)$ must be True.

2. Deduce the Truth Value of p: From Part 1, if $(\sim p)$ is True, then $p$ must be False (F).

3. Deduce the Truth Value of q: Now we use the fact that $p$ is False in Part 2. The statement $(p \lor q)$ must be True. Substituting the value of $p$: $(F \lor q)$ is True. A disjunction (OR) is true if at least one of its parts is true. Since the first part is False, the second part, $q$, must be True (T).

4. Evaluate the Target Expression: We have found that $p$ is False and $q$ is True. The question asks for the truth value of the biconditional $p \iff q$. A biconditional is true only when both parts have the same truth value. We are evaluating $F \iff T$. Since the truth values are different, the statement $p \iff q$ is False.

Question 17

Prove by contrapositive: "For integers $a$ and $b$, if $ab$ is even, then at least one of $a$ or $b$ is even."

Explanation: Proving by contrapositive involves proving the logically equivalent statement $\sim Q \implies \sim P$ instead of the original $P \implies Q$.

1. Identify P and Q:

   • $P$: "$ab$ is even."
   • $Q$: "at least one of $a$ or $b$ is even." The original statement is $P \implies Q$.

2. Form the Contrapositive ($\sim Q \implies \sim P$):

   • $\sim Q$: The negation of "at least one of $a$ or $b$ is even" is "neither $a$ nor $b$ is even," which means "both $a$ and $b$ are odd."
   • $\sim P$: The negation of "$ab$ is even" is "$ab$ is odd." The contrapositive statement to prove is: "If both $a$ and $b$ are odd, then $ab$ is odd."

3. Prove the Contrapositive using a Direct Proof:

   • Assume hypothesis is true: Let $a$ and $b$ be odd integers.
   • Use definition: By definition of an odd integer, we can write $a = 2k+1$ and $b = 2m+1$ for some integers $k$ and $m$.
   • Logical deduction: Calculate their product: $ab = (2k+1)(2m+1) = 4km + 2k + 2m + 1$.
   • Show conclusion is true: Factor out a 2 from the first three terms: $ab = 2(2km+k+m)+1$. Let $p = 2km+k+m$. Since $k$ and $m$ are integers, $p$ is an integer. The product $ab$ is of the form $2p+1$, which is the definition of an odd integer.

4. Conclusion: We have successfully proven the contrapositive statement. Since the contrapositive is logically equivalent to the original statement, we have also proven that "if $ab$ is even, then at least one of $a$ or $b$ is even."

Question 18

Write the negation of the statement: "All students have paid their fees and some students have received their books."

Explanation: This problem involves negating a compound statement containing quantifiers.

1. Translate to Symbolic Form:

   • Let $P(x)$: "student $x$ has paid their fees."
   • Let $Q(x)$: "student $x$ has received their books."
   • "All students have paid their fees" translates to $\forall x, P(x)$.
   • "some students have received their books" translates to $\exists y, Q(y)$. The full statement is: $(\forall x, P(x)) \land (\exists y, Q(y))$.

2. Apply De Morgan's Law: We need to negate the entire expression: $\sim [(\forall x, P(x)) \land (\exists y, Q(y))]$. Let $A = (\forall x, P(x))$ and $B = (\exists y, Q(y))$. We are finding $\sim(A \land B)$. By De Morgan's Law, this is equivalent to $\sim A \lor \sim B$.

3. Negate the Quantified Parts:

   • $\sim A = \sim(\forall x, P(x)) \equiv \exists x, \sim P(x)$. In words: "There exists a student who has not paid their fees," or "Some students have not paid their fees."
   • $\sim B = \sim(\exists y, Q(y)) \equiv \forall y, \sim Q(y)$. In words: "For all students, they have not received their books," or "All students have not received their books."

4. Combine and Translate Back to English: The negated statement is $\sim A \lor \sim B$. Combining the English translations gives: "Some students have not paid their fees or all students have not received their books."

Question 19

Construct a truth table for $(p \implies q) \iff (\sim p \lor q)$ and determine if it is a tautology.

Explanation: This question asks us to verify the fundamental logical equivalence for an implication using a truth table. A tautology is a statement that is always true.

1. Identify LHS and RHS:

   • Left-Hand Side (LHS): $p \implies q$
   • Right-Hand Side (RHS): $\sim p \lor q$ We want to check if $LHS \iff RHS$ is always true.

2. Construct the Table: We will build the table step-by-step.

$p$	$q$	LHS: $p \implies q$	$\sim p$	RHS: $\sim p \lor q$	$(p \implies q) \iff (\sim p \lor q)$
T	T	T	F	F $\lor$ T = T	T $\iff$ T = T
T	F	F	F	F $\lor$ F = F	F $\iff$ F = T
F	T	T	T	T $\lor$ T = T	T $\iff$ T = T
F	F	T	T	T $\lor$ F = T	T $\iff$ T = T

Conclusion: First, we observe that the column for the LHS ($p \implies q$) is identical to the column for the RHS ($\sim p \lor q$). This proves they are logically equivalent. Second, the final column evaluates the biconditional between these two equivalent statements. Since they are always the same, the biconditional is always true. Therefore, the statement is a tautology.

Question 20

Is the following argument valid? "If you have a password, then you can log on. You have a password. Therefore, you can log on."

Explanation: An argument is valid if the conclusion logically follows from the premises. This means that if all the premises are true, the conclusion must also be true. We can check this by seeing if the argument form is a tautology.

1. Translate to Symbolic Form:

   • Let $p$: "you have a password."
   • Let $q$: "you can log on."

2. Identify the Argument Structure:

   • Premise 1: $p \implies q$
   • Premise 2: $p$
   • Conclusion: $q$

3. Form the Corresponding Implication: The entire argument can be written as a single logical statement: $[(p \implies q) \land p] \implies q$. The argument is valid if and only if this statement is a tautology.

4. Check for Tautology (using a truth table):

$p$	$q$	$p \implies q$	$(p \implies q) \land p$	$[(p \implies q) \land p] \implies q$
T	T	T	T $\land$ T = T	T $\implies$ T = T
T	F	F	F $\land$ T = F	F $\implies$ F = T
F	T	T	T $\land$ F = F	F $\implies$ T = T
F	F	T	T $\land$ F = F	F $\implies$ F = T

Conclusion: Since the final column is always True, the statement is a tautology. This confirms that the argument is valid. This specific, valid argument form is one of the most important in logic and is known as Modus Ponens.

Question 21

Find a counterexample to the statement: "For any real number $x$, $x < x^2$."

Explanation: A counterexample is a specific example that proves a general statement ("for any" or "for all") is false. We need to find a single real number $x$ for which the condition $x < x^2$ is not true.

1. Negate the Condition: The opposite of $x < x^2$ is $x \ge x^2$. We are looking for a number $x$ that satisfies $x \ge x^2$.

2. Test Different Types of Numbers:

   • Large positive numbers: If $x=10$, $10 < 100$. True. The statement holds.
   • Negative numbers: If $x=-2$, $-2 < 4$. True. The statement holds.
   • Zero: If $x=0$, is $0 < 0^2$? No, $0 < 0$ is false. So $x=0$ is a counterexample.
   • One: If $x=1$, is $1 < 1^2$? No, $1 < 1$ is false. So $x=1$ is a counterexample.
   • Fractions between 0 and 1: Let's try $x=0.5$. Is $0.5 < (0.5)^2$? Is $0.5 < 0.25$? This is False.

Conclusion: We have found several values for which the statement is false. For example, when $x=0.5$, the condition $x < x^2$ becomes $0.5 < 0.25$, which is not true. Therefore, $x=0.5$ is a valid counterexample. Any number $x$ in the interval $[0, 1]$ would also work.

Question 22

Write the converse, inverse, and contrapositive of: "If $x$ is a real number such that $x^2=9$, then $x=3$."

Explanation: First, let's analyze and symbolize the original statement.

• Let $p$: "$x^2=9$."
• Let $q$: "$x=3$."
• The original statement is $p \implies q$.

(Note: The original statement itself is false. A counterexample is $x=-3$, where the hypothesis $p$ is true but the conclusion $q$ is false.)

1. Converse (Form: $q \implies p$): Swap the hypothesis and conclusion.

   • In Words: "If $x=3$, then $x^2=9$."
   • (This statement is true.)

2. Inverse (Form: $\sim p \implies \sim q$): Negate both the hypothesis and the conclusion.

   • $\sim p$: "$x^2 \neq 9$."
   • $\sim q$: "$x \neq 3$."
   • In Words: "If $x^2 \neq 9$, then $x \neq 3$."
   • (This statement is true.)

3. Contrapositive (Form: $\sim q \implies \sim p$): Negate both propositions and swap their order.

   • In Words: "If $x \neq 3$, then $x^2 \neq 9$."
   • (This statement is false, and has the same truth value as the original. The same counterexample, $x=-3$, applies. Here, $x \neq 3$ is true, but $x^2 \neq 9$ is false.)

Question 23

Simplify the logical expression: $(p \lor q) \land \sim (\sim p \land q)$.

Explanation: We will simplify the expression using the standard laws of logical equivalence.

1. Initial Expression: $(p \lor q) \land \sim (\sim p \land q)$

2. Apply De Morgan's Law: Focus on the second part, $\sim (\sim p \land q)$. According to De Morgan's Law, $\sim(A \land B) \equiv \sim A \lor \sim B$. $\sim (\sim p \land q) \equiv \sim(\sim p) \lor (\sim q)$

3. Apply Double Negation Law: The law $\sim(\sim A) \equiv A$ simplifies $\sim(\sim p)$ to $p$. The second part becomes: $p \lor \sim q$.

4. Substitute Back into the Main Expression: The entire expression is now: $(p \lor q) \land (p \lor \sim q)$

5. Apply the Distributive Law (in reverse): This matches the form $(A \lor B) \land (A \lor C) \equiv A \lor (B \land C)$. Here, $A=p$, $B=q$, and $C=\sim q$. Applying the law, we get: $p \lor (q \land \sim q)$.

6. Apply the Law of Non-Contradiction: The expression $(q \land \sim q)$ is a contradiction, which is always False (F). Our expression becomes: $p \lor F$.

7. Apply the Identity Law: Any statement OR False is equivalent to the statement itself ($A \lor F \equiv A$). Therefore, the final simplified expression is $p$.

Question 24

Negate the statement: "Some students are hardworking and all students are intelligent."

Explanation: This problem involves negating a compound statement containing quantifiers.

1. Translate to Symbolic Form:

   • Let $H(x)$: "student $x$ is hardworking."
   • Let $I(x)$: "student $x$ is intelligent."
   • "Some students are hardworking" translates to $\exists x, H(x)$.
   • "all students are intelligent" translates to $\forall y, I(y)$. The full statement is: $(\exists x, H(x)) \land (\forall y, I(y))$.

2. Apply De Morgan's Law: We need to negate the entire expression: $\sim [(\exists x, H(x)) \land (\forall y, I(y))]$. Let $A = (\exists x, H(x))$ and $B = (\forall y, I(y))$. We are finding $\sim(A \land B)$. By De Morgan's Law, this is equivalent to $\sim A \lor \sim B$.

3. Negate the Quantified Parts:

   • $\sim A = \sim(\exists x, H(x)) \equiv \forall x, \sim H(x)$. In words: "For all students, they are not hardworking," or "All students are not hardworking."
   • $\sim B = \sim(\forall y, I(y)) \equiv \exists y, \sim I(y)$. In words: "There exists a student who is not intelligent," or "Some students are not intelligent."

4. Combine and Translate Back to English: The negated statement is $\sim A \lor \sim B$. Combining the English translations gives: "All students are not hardworking or some students are not intelligent."

Question 25

Is the statement "It is necessary for a number to be divisible by 3 for it to be divisible by 12" true or false?

Explanation:

1. Translate the Language: The phrasing "Q is necessary for P" translates to the logical implication $P \implies Q$. It means that if P is true, Q must also be true.

2. Identify P and Q:

   • $P$: "a number is divisible by 12."
   • $Q$: "a number is divisible by 3."

3. Form the Implication: The statement is equivalent to: "If a number is divisible by 12, then it is divisible by 3."

4. Test the Implication's Validity: To prove this, we can use a direct proof.

   • Let $n$ be an integer that is divisible by 12 (assume the hypothesis is true).
   • By definition, this means $n = 12k$ for some integer $k$.
   • We want to show that $n$ is also divisible by 3. We can rewrite the expression for $n$ as: $n = 3 \cdot (4k)$.
   • Since $k$ is an integer, $4k$ is also an integer. Let's call it $m$. So, $n = 3m$.
   • This shows that $n$ is a multiple of 3.

5. Conclusion: Since assuming the hypothesis (divisible by 12) directly leads to the conclusion (divisible by 3), the implication is True.

Question 26

Use a truth table to determine if $(p \implies q)$ is equivalent to $(\sim q \implies \sim p)$.

Explanation: This question asks us to verify the equivalence between an implication and its contrapositive. Two statements are logically equivalent if they have the same truth value for all possible inputs.

1. Identify LHS and RHS:

   • Left-Hand Side (LHS): $p \implies q$ (The original implication)
   • Right-Hand Side (RHS): $\sim q \implies \sim p$ (The contrapositive)

2. Construct the Truth Table: We will build the table with columns for the basic propositions, their negations, and then the two implications.

$p$	$q$	LHS: $p \implies q$	$\sim q$	$\sim p$	RHS: $\sim q \implies \sim p$
T	T	T	F	F	F $\implies$ F = T
T	F	F	T	F	T $\implies$ F = F
F	T	T	F	T	F $\implies$ T = T
F	F	T	T	T	T $\implies$ T = T

Conclusion: The column for the LHS and the column for the RHS are identical (T, F, T, T). Since they have the same truth values in every case, the statement $(p \implies q)$ is logically equivalent to its contrapositive $(\sim q \implies \sim p)$.

Question 27

Prove by contradiction that there is no largest integer.

Explanation: A proof by contradiction begins by assuming the opposite of the statement you want to prove.

1. Statement to Prove: There is no largest integer.

2. Assumption for Contradiction: Assume the opposite is true: There exists a largest integer. Let's call this integer $N$.

3. Definition of 'Largest': If $N$ is the largest integer, it means that for any integer $m$, the inequality $m \le N$ must hold.

4. Derive a Contradiction: Let's construct a new number. Consider the number $M = N + 1$.

   • Since $N$ is an integer and $1$ is an integer, their sum, $M$, must also be an integer.
   • By the properties of numbers, we know that $N+1 > N$, which means $M > N$.

5. Identify the Contradiction: We have constructed an integer $M$ such that $M > N$. This directly contradicts our assumption that $N$ is the largest integer (because we just found a larger one).

6. Conclusion: Since our initial assumption led to a logical contradiction, the assumption must be false. Therefore, the original statement is true: there is no largest integer.

Question 28

Write the converse of the contrapositive of the statement: "If $x>y$, then $x-y > 0$."

Explanation: This is a multi-step transformation. Let's track the changes to the implication.

1. Symbolic Form of Original Statement:

   • Let $p$: "$x > y$."
   • Let $q$: "$x-y > 0$."
   • The original statement is $p \implies q$.

2. Step 1: Find the Contrapositive:

   • The contrapositive of an implication $A \implies B$ is $\sim B \implies \sim A$.
   • Applying this to our statement, the contrapositive is $\sim q \implies \sim p$.
   • In words: "If $x-y \le 0$, then $x \le y$."

3. Step 2: Find the Converse of the Result from Step 1:

   • Now, we need to find the converse of the contrapositive statement, $\sim q \implies \sim p$.
   • The converse of an implication $A \implies B$ is $B \implies A$.
   • Here, $A = \sim q$ and $B = \sim p$.
   • The converse is $\sim p \implies \sim q$.

4. Simplify and Translate:

   • The resulting form, $\sim p \implies \sim q$, is the inverse of the original statement ($p \implies q$).
   • Translating $\sim p \implies \sim q$ back to words: "If $x \le y$, then $x-y \le 0$."

Question 29

Given that $p \implies q$ is False, determine the truth value of $(p \land q) \implies (p \lor q)$.

Explanation:

1. Deduce the values of p and q: We are given that the implication $p \implies q$ is False. An implication is only false in one specific scenario: when the hypothesis is True and the conclusion is False. Therefore, we can definitively conclude:

   • $p$ is True (T).
   • $q$ is False (F).

2. Evaluate the Target Expression's Hypothesis: The hypothesis of the target expression is $(p \land q)$. Substitute the truth values we found: $(T \land F)$. The result of a conjunction (AND) is True only if both parts are True. So, $(T \land F)$ is False (F).

3. Evaluate the Target Expression's Conclusion: The conclusion of the target expression is $(p \lor q)$. Substitute the truth values: $(T \lor F)$. The result of a disjunction (OR) is True if at least one part is True. So, $(T \lor F)$ is True (T).

4. Evaluate the Final Implication: The full expression is now reduced to: $(p \land q) \implies (p \lor q)$ $F \implies T$ An implication with a False hypothesis is always True.

Answer: The truth value of the statement is True.

Question 30

Is the following argument valid? "If it is a holiday, the office is closed. The office is closed. Therefore, it is a holiday."

Explanation: An argument is valid if the conclusion must be true whenever all the premises are true. If we can find even one situation (a counterexample) where the premises are true but the conclusion is false, the argument is invalid.

1. Translate to Symbolic Form:

   • Let $p$: "it is a holiday."
   • Let $q$: "the office is closed."

2. Identify the Argument Structure:

   • Premise 1: $p \implies q$ (If it is a holiday, the office is closed.)
   • Premise 2: $q$ (The office is closed.)
   • Conclusion: $p$ (Therefore, it is a holiday.)

3. Search for a Counterexample: We need to find a scenario where the premises are true but the conclusion is false.

   • Premise 1 ($p \implies q$) must be True.
   • Premise 2 ($q$) must be True.
   • Conclusion ($p$) must be False.

   Let's try to create such a scenario:

   • Set $p$ to be False: "It is not a holiday."
   • Set $q$ to be True: "The office is closed."

   Now, let's check the premises with these values:

   • Premise 1: $p \implies q$ becomes $F \implies T$, which is True.
   • Premise 2: $q$ is True.

   So, we have a situation where both premises are true. What is the conclusion in this situation? The conclusion is $p$, which we set to be False.

4. Conclusion: We have successfully found a situation (e.g., a Sunday, when the office is closed but it's not an official holiday) where the premises are true but the conclusion is false. Therefore, the argument is invalid. This famous logical error is known as the Fallacy of Affirming the Consequent.