Ch 3. Logic and Proofs
3.2 Conditional Propositions and Logical Equivalence
Consider a proposition that states that “whenever [latex]p[/latex] is true, [latex]q[/latex] must also be true”, that is, “if [latex]p[/latex], then [latex]q[/latex]”. A logical statement of this form is a conditional proposition and is written symbolically as [latex]p \rightarrow q[/latex].
Example 3.5
If a customer spends over $100, then they receive free shipping.
Let [latex]p[/latex]: "Customer spends over $100."
Let [latex]q[/latex]: "Customer receives free shipping."
Then: [latex]p \rightarrow q[/latex]
Truth Table for [latex]p \rightarrow q[/latex]
| [latex]p[/latex] | [latex]q[/latex] | [latex]p \rightarrow q[/latex] |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The second row of this table shows that a conditional proposition [latex]p \rightarrow q[/latex] can only be false when [latex]p[/latex] is true, and [latex]q[/latex] is false.
If the condition of a proposition ([latex]q[/latex]) never occurs, then the implication ([latex]p \rightarrow q[/latex]) can’t be violated. This is shown in the third and fourth rows of this table, where [latex]p[/latex] is false, no matter the truth value of [latex]q[/latex]. In this situation, the conditional proposition [latex]p \rightarrow q[/latex] is vacuously true.
Example 3.6
"If a user logs in with the wrong password, then they access the dashboard."
If no user logs in with the wrong password ([latex]p[/latex] is false), the statement is vacuously true, even if the dashboard is inaccessible!
Why is this true? Think of it like a promise:
“If I win the lottery, I’ll buy you a car.”
If I never win the lottery ([latex]p[/latex] is false), I haven’t broken my promise – so the statement is still considered true. Similarly, if no user logs in with the wrong password, the system never has a chance to violate the rule, so the condition holds by default.
Imagine a system rule that says:
“If a customer enters an invalid promo code, then they receive a discount.”
If no customer ever enters an invalid code, the system never has to enforce the rule. Logically, the rule is still considered valid, even if it never applies.
It’s important in logic to understand whether one condition guarantees another (a sufficient condition) or if it is required for it to occur (a necessary condition). These concepts can be written using symbols as follows:
[latex]p[/latex] is a sufficient condition for [latex]q[/latex] if [latex]p \rightarrow q[/latex].
[latex]q[/latex] is a necessary condition for [latex]p[/latex] if [latex]p \rightarrow q[/latex].
Example 3.7
Consider the following conditional proposition: "If a file is encrypted, then it is secure."
Logically, this means that encryption is sufficient> for security. It also means that security is necessary> for encryption.
A biconditional is a statement of the form [latex]p \leftrightarrow q[/latex], meaning [latex]p[/latex] if and only if [latex]q[/latex]. It is true when [latex]p[/latex] and [latex]q[/latex] are both true or both false.
Example 3.8
"A user is authenticated if and only if they provide valid credentials."
This means both conditions must match in truth value.
If two statements always have the same truth value, then we say they are logically equivalent. The symbol [latex]\equiv[/latex] is used to represent this.
Example 3.9
The two statements [latex]p \rightarrow q[/latex] and [latex]\neg p \lor q[/latex] are logically equivalent. This can be shown by using a truth table.
| [latex]p[/latex] | [latex]q[/latex] | [latex]p \rightarrow q[/latex] | [latex]\neg p[/latex] | [latex]\neg p \lor q[/latex] |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
De Morgan’s Laws relate the negation of conjunctions and disjunctions:
[latex]\neg (p \land q) \equiv \neg p \lor \neg q \quad[/latex] (3.1)
[latex]\neg (p \lor q) \equiv \neg p \land \neg q \quad[/latex] (3.2)
Example 3.10
The statement "It is not true that the user is logged in and has admin rights" is equivalent to the statement "The user is not logged in or does not have admin rights".
Programming Example 3.4 (Pseudocode)
# Original condition
IF NOT (user_is_logged_in AND user_is_admin) THEN
DISPLAY "Access denied."
# Equivalent using De Morgan's Law
IF NOT user_is_logged_in OR NOT user_is_admin THEN
DISPLAY "Access denied."
For the conditional proposition [latex]p \rightarrow q[/latex], its logical equivalence [latex]\neg q \rightarrow \neg p[/latex] is its contrapositive.
Example 3.11
The contrapositive of the conditional proposition "If a system is secure, then it has a firewall" is "If a system does not have a firewall, then it is not secure."
Theorem 3.1: Law of Contraposition
For any propositions [latex]p[/latex] and [latex]q[/latex],
[latex]p \rightarrow q \equiv \neg q \rightarrow \neg p[/latex]
Proof
| [latex]p[/latex] | [latex]q[/latex] | [latex]p \rightarrow q[/latex] | [latex]\neg q[/latex] | [latex]\neg p[/latex] | [latex]\neg q \rightarrow \neg p[/latex] |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Since the columns for [latex]p \rightarrow q[/latex] and [latex]\neg q \rightarrow \neg p[/latex] are identical, they are logically equivalent.
[latex]\square[/latex]
Real-World Example 3.2: E-Commerce Checkout Logic
In an e-commerce platform, a business rule might state:
"If a customer is a member, then they receive a 10% discount."
Let p be the proposition "The customer is a member," and q be the proposition "The customer receives a 10% discount". This rule can be written as the conditional proposition [latex]p \rightarrow q[/latex].
| [latex]p[/latex] | [latex]q[/latex] | [latex]p \rightarrow q[/latex] | Explanation | Rule Violated |
|---|---|---|---|---|
| T | T | T | A customer is a member and receives the discount. | No |
| T | F | F | A customer is a member but does not receive the discount. | Yes |
| F | T | T | A customer is not a member but still receives the discount. | No |
| F | F | T | A customer is not a member and does not receive the discount. | No |
Programming Logic (Pseudocode)
IF is_member AND NOT received_discount THEN
DISPLAY "Policy violation: Member did not receive discount."
ELSE
DISPLAY "Policy condition satisfied."
