Generating Secure PDF Link
Discrete Structure Chapter 1 Ex 1.1 Solved Notes & Quiz
Please Wait
10
seconds remaining...
Discrete Structure Chapter 1 Ex 1.1 Solved Notes & Quiz
In discrete mathematics and formal logic, a proposition is a declarative statement that is either strictly True ($T$) or False ($F$), but not both. Logical operators (connectives) are used to combine atomic propositions into compound propositions.
| $p$ | $q$ | $\neg p$ | $p \land q$ | $p \lor q$ | $p \to q$ | $p \leftrightarrow q$ |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Question 1 (Part i): Construct a truth table for the compound proposition $p \lor \neg q$.
Solution:
We systematically evaluate each row for combinations of $p$ and $q$:
| $p$ | $q$ | $\neg q$ | $p \lor \neg q$ |
|---|---|---|---|
| T | T | F | T |
| T | F | T | T |
| F | T | F | F |
| F | F | T | T |
Answer: The truth values for $p \lor \neg q$ are $$\text{T}, \text{T}, \text{F}, \text{T}$$
Question 1 (Part ii): Construct a truth table for the compound proposition $\neg(p \land q)$.
Solution:
First construct $p \land q$, then apply the negation operator $\neg$:
| $p$ | $q$ | $p \land q$ | $\neg(p \land q)$ |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
Answer: The truth values for $\neg(p \land q)$ are $$\text{F}, \text{T}, \text{T}, \text{T}$$
Question 2 (Part i): Use a truth table to prove De Morgan's Law: $\neg(p \lor q) \equiv \neg p \land \neg q$.
Solution:
We construct truth tables for both sides of the logical equivalence and compare corresponding columns:
| $p$ | $q$ | $p \lor q$ | $\neg(p \lor q)$ | $\neg p$ | $\neg q$ | $\neg p \land \neg q$ |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Comparing Column 4 ($\neg(p \lor q)$) and Column 7 ($\neg p \land \neg q$), the truth values match identically row-by-row ($\text{F}, \text{F}, \text{F}, \text{T}$). Hence, the statement is proved.
Answer: $$\neg(p \lor q) \equiv \neg p \land \neg q \quad \text{(Proved)}$$
Question 2 (Part ii): Prove the logical equivalence $p \to q \equiv \neg p \lor q$ using a truth table.
Solution:
Evaluate the truth values of $p \to q$ and $\neg p \lor q$ for all possible truth assignments:
| $p$ | $q$ | $p \to q$ | $\neg p$ | $\neg p \lor q$ |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Column 3 ($p \to q$) is identical to Column 5 ($\neg p \lor q$) for every row ($\text{T}, \text{F}, \text{T}, \text{T}$).
Answer: $$p \to q \equiv \neg p \lor q \quad \text{(Proved)}$$
Question 3 (Part i): Determine whether the statement $(p \to q) \leftrightarrow (\neg q \to \neg p)$ is a tautology, a contradiction, or a contingency.
Solution:
Construct a truth table for the given statement:
| $p$ | $q$ | $p \to q$ | $\neg q$ | $\neg p$ | $\neg q \to \neg p$ | $(p \to q) \leftrightarrow (\neg q \to \neg p)$ |
|---|---|---|---|---|---|---|
| T | T | T | F | F | T | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | T |
| F | F | T | T | T | T | T |
Since the final column evaluated to True ($\text{T}$) in every possible row, the proposition is logically valid under all interpretations.
Answer: $$\text{The proposition is a Tautology.}$$
Question 3 (Part ii): Determine whether the statement $(p \land \neg p)$ is a tautology, a contradiction, or a contingency.
Solution:
Construct the truth table:
| $p$ | $\neg p$ | $p \land \neg p$ |
|---|---|---|
| T | F | F |
| F | T | F |
Since the output column contains only False ($\text{F}$) values for all inputs, the statement is always false.
Answer: $$\text{The proposition is a Contradiction.}$$
Question 4 (Part i): Translate the English sentence into propositional logic: "If it rains, then the ground is wet."
Solution:
Let $p$ represent the proposition: "It rains."
Let $q$ represent the proposition: "The ground is wet."
The sentence structure is a conditional statement "If $p$, then $q$". Symbolically, this is expressed using the conditional operator $\to$.
Answer: $$p \to q$$
Question 4 (Part ii): Translate the English sentence into propositional logic: "You can access the portal only if you are enrolled."
Solution:
Let $a$ represent: "You can access the portal."
Let $e$ represent: "You are enrolled."
Note that "$a$ only if $e$" means that being enrolled is a necessary condition for accessing the portal. Thus, if $a$ occurs, $e$ must hold. Symbolically, this translates to $a \to e$.
Answer: $$a \to e$$
Question 5 (Part i): Given truth valuations $p = \text{True}$ and $q = \text{False}$, evaluate the truth value of $(p \land q) \to (p \lor q)$.
Solution:
Substitute the valuations into the statement:
1. Evaluate antecedent: $p \land q = \text{True} \land \text{False} = \text{False}$.
2. Evaluate consequent: $p \lor q = \text{True} \lor \text{False} = \text{True}$.
3. Evaluate full implication: $\text{False} \to \text{True} = \text{True}$.
Answer: $$\text{True}$$
Question 5 (Part ii): Given truth valuations $p = \text{False}$ and $q = \text{False}$, evaluate the truth value of $(p \leftrightarrow q) \land \neg p$.
Solution:
Substitute the given truth values into the expression:
1. Evaluate $p \leftrightarrow q$: $\text{False} \leftrightarrow \text{False} = \text{True}$.
2. Evaluate $\neg p$: $\neg(\text{False}) = \text{True}$.
3. Evaluate conjunction: $\text{True} \land \text{True} = \text{True}$.
Answer: $$\text{True}$$
Question 6 (Part i): State the converse, inverse, and contrapositive for the implication: "If $n$ is an even integer, then $n^2$ is an even integer."
Solution:
Let $p$: "$n$ is an even integer" and $q$: "$n^2$ is an even integer". Original implication: $p \to q$.
- Converse ($q \to p$): "If $n^2$ is an even integer, then $n$ is an even integer."
- Inverse ($\neg p \to \neg q$): "If $n$ is not an even integer, then $n^2$ is not an even integer."
- Contrapositive ($\neg q \to \neg p$): "If $n^2$ is not an even integer, then $n$ is not an even integer."
Answer:
$$\text{Converse: If } n^2 \text{ is even, then } n \text{ is even.}$$
$$\text{Inverse: If } n \text{ is odd, then } n^2 \text{ is odd.}$$
$$\text{Contrapositive: If } n^2 \text{ is odd, then } n \text{ is odd.}$$
Question 6 (Part ii): State the converse, inverse, and contrapositive for the implication: "If $x + 2 = 5$, then $x = 3$."
Solution:
Let $p$: "$x + 2 = 5$" and $q$: "$x = 3$". Original implication: $p \to q$.
- Converse ($q \to p$): "If $x = 3$, then $x + 2 = 5$."
- Inverse ($\neg p \to \neg q$): "If $x + 2 \neq 5$, then $x \neq 3$."
- Contrapositive ($\neg q \to \neg p$): "If $x \neq 3$, then $x + 2 \neq 5$."
Answer:
$$\text{Converse: If } x = 3, \text{ then } x + 2 = 5.$$
$$\text{Inverse: If } x + 2 \neq 5, \text{ then } x \neq 3.$$
$$\text{Contrapositive: If } x \neq 3, \text{ then } x + 2 \neq 5.$$
Q1: What is the logical equivalence of the negation of an implication, $\neg(p \to q)$?
Q2: How many rows are required in a truth table for a compound proposition with $n$ distinct variables?
Q3: Which statement is logically equivalent to the conditional $p \to q$?
Q4: A compound proposition that is always True under all truth valuations is called a:
Q5: What is the truth value of $p \to q$ when $p$ is False and $q$ is False?
Q6: The biconditional statement $p \leftrightarrow q$ is True when: