Ch 3. Logic and Proofs
3.3 Arguments and Rules of Inference
In logic, deductive reasoning starts with general rules or principles and applies them to a specific case to reach a necessary conclusion. This form of reasoning is foundational in mathematics, programming, and business decision-making, where conclusions must follow logically from known facts.
A deductive argument consists of one or more premises (also called hypotheses) and a conclusion. The goal is to determine whether the conclusion logically follows from the premises.
An argument is said to be valid if, whenever all the premises are true, the conclusion must also be true. Validity is about the structure of the argument, not the actual truth of the premises.
In propositional logic, an argument is a sequence of propositions, such as
[latex]p_{1}, p_{2}, \dots p_{n} \Rightarrow q[/latex]
This means: If all the premises [latex]p_{1}[/latex] through [latex]p_{n}[/latex] are true, then the conclusion [latex]q[/latex] must also be true. The symbol [latex]\Rightarrow[/latex] means “therefore.”
Example 3.12
Let [latex]p[/latex] be the proposition "The server is online", [latex]q[/latex] be the proposition "The database is accessible", and [latex]r[/latex] be the proposition "The system is operational". The premises are [latex]p \rightarrow q[/latex] and [latex]q \rightarrow r[/latex]. The conclusion is [latex]p \rightarrow r[/latex].
We want to determine if this argument is valid, which can be done with a truth table.
| [latex]p[/latex] | [latex]q[/latex] | [latex]r[/latex] | [latex]p \rightarrow q[/latex] | [latex]q \rightarrow r[/latex] | [latex]p \rightarrow r[/latex] |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | T | F | T | F | F |
| T | F | T | F | T | T |
| T | F | F | F | T | F |
| F | T | T | T | T | T |
| F | T | F | T | F | T |
| F | F | T | T | T | T |
| F | F | F | T | T | T |
We observe that whenever both premises ([latex]p \rightarrow q[/latex] and [latex]q \rightarrow r[/latex]) are true, the conclusion [latex]p \rightarrow r[/latex] is also true. Therefore, the argument is valid.
Rules of Inference for Propositions:
| Rule Name | Form | Description |
|---|---|---|
| Modus Ponens | [latex]p \rightarrow q, p \Rightarrow q[/latex] | If [latex]p[/latex], then [latex]q[/latex] and [latex]p[/latex] is true, then [latex]q[/latex] is true |
| Modus Tollens | [latex]p \rightarrow q, \neg q \Rightarrow \neg p[/latex] | If [latex]p[/latex], then [latex]q[/latex] and [latex]q[/latex] is false, then [latex]p[/latex] is false |
| Hypothetical Syllogism | [latex]p \rightarrow q, q \rightarrow r \Rightarrow p \rightarrow r[/latex] | If [latex]p[/latex], then [latex]q[/latex] and if [latex]q[/latex], then [latex]r[/latex], then if [latex]p[/latex], then [latex]r[/latex] |
| Disjunctive Syllogism | [latex]p \lor q, \neg p \Rightarrow q[/latex] | If [latex]p[/latex] or [latex]q[/latex] is true and [latex]p[/latex] is false, then [latex]q[/latex] is true |
| Addition | [latex]p \Rightarrow p \lor q[/latex] | If [latex]p[/latex] is true, then [latex]p[/latex] or [latex]q[/latex] is true |
| Simplification | [latex]p \land q \Rightarrow p[/latex] | If [latex]p[/latex] and [latex]q[/latex] is true, then [latex]p[/latex] is true |
| Conjunction | [latex]p, q \Rightarrow p \land q[/latex] | If [latex]p[/latex] is true and [latex]q[/latex] is true, then [latex]p[/latex] and [latex]q[/latex] is true |
Example 3.13
Let [latex]p[/latex] be the proposition "The user is authenticated" and [latex]q[/latex] be the proposition "The user can access the dashboard". It is given that [latex]p \rightarrow q[/latex] and [latex]p[/latex].
Using Modus Ponens, we conclude that [latex]q[/latex]: "The user can access the dashboard."
A common logical error is the fallacy of affirming the conclusion, which assumes that if [latex]p \rightarrow q[/latex] and [latex]q[/latex] is true, then [latex]p[/latex] must also be true. This is not valid.
Example 3.14
If a user is an admin, then they can access the settings panel. ([latex]p \rightarrow q[/latex])
The user can access the settings panel. ([latex]q[/latex])
Therefore, the user is an admin. ([latex]p[/latex]) Invalid reasoning
The user might have access for another reason (e.g., they are a developer). The conclusion does not necessarily follow.
Real-World Example 3.3: IT Security Policy
A company has the following policy:
If an employee is on the internal network, then they can access the file server. ([latex]p \rightarrow q[/latex])
Aiden is on the internal network. ([latex]p[/latex])
Using Modus Ponens, we conclude that Aiden can access the file server. ([latex]q[/latex])
