Mathematical Proofs: A Complex Scenario

Sarmad’s pet

Let’s take a more complex scenario as follows:

Scenario

Sarmad has a pet, or he has a motorcycle. If he has a motorcycle, then he is tired. If Sarmad does not have a motorcycle, (then) he uses a taxi. If Sarmad is not tired, then he is in the kitchen.

If Sarmad has a pet, then the pet is in the kitchen. If Sarmad and his pet are in the kitchen, (then) he offers tuna to his pet. If Sarmad offers tuna to his pet, (then) his pet is a cat. If Sarmad does not have a pet, then he is lonely.

Given that:

Sarmad is not lonely, or he is not using a taxi.

And Sarmad is not tired.

Can we conclude from this information that, Sarmad’s pet is a cat, and the pet is in the kitchen, and Sarmad offers tuna to his pet?

Formalization

Let’s represent different propositions in the given scenario as follows:

$q_1$ : Sarmad has a pet.
$q_2$ : Sarmad’s pet is a cat.
$q_3$ : Sarmad has a motorcycle.
$q_4$ : Sarmad is tired.
$q_5$ : Sarmad uses a taxi.
$q_6$ : Sarmad is in the kitchen.
$q_7$ : The pet is in the kitchen.
$q_8$ : Sarmad offers tuna to his pet.
$q_9$ : Sarmad is lonely.

Hypotheses

$\begin{aligned}{} H_1 :&\; q_1 \lor q_3 &:& \text{ Sarmad has a pet, or he has a motorcycle.}\\ H_2 :&\; q_3 \Rightarrow q_4 &: &\text{ If Sarmad has a motorcycle, then he is tired.}\\ H_3:&\; \neg q_3 \Rightarrow q_5 &: &\text{ If Sarmad does not have a motorcycle, (then) he uses a taxi.}\\ H_4:&\; \neg q_4 \Rightarrow q_6 &:& \text{ If Sarmad is not tired, then he is in the kitchen.}\\ H_5:&\; q_1 \Rightarrow q_7 &:& \text{ If Sarmad has a pet, then the pet is in the kitchen.}\\ H_6:&\; (q_6 \land q_7)\Rightarrow q_8 &:& \text{ If Sarmad and his pet are in the kitchen, (then) he offers tuna to his pet.}\\ H_7:&\; q_8 \Rightarrow q_2 &:& \text{ If Sarmad offers tuna to his pet, (then) his pet is a cat.}\\ H_8:&\; \neg q_1 \Rightarrow q_9 &:& \text{ If Sarmad does not have a pet, then he is lonely.}\\ H_9:&\; \neg q_9 \lor \neg q_5 &:& \text{ Sarmad is not lonely, or he is not using a taxi.}\\ H_{10}:&\; \neg q_4 &:& \text{ Sarmad is not tired.} \end{aligned}$

Conclusion

$C:\;\;\; q_2 \land q_7 \land q_8 \;\;\;:$ Sarmad’s pet is a cat, and the pet is in the kitchen, and Sarmad offers tuna to his pet.

We first apply the conjunction rule on $H_3$ and $H_8$ to conclude $C_1$ .

$C_1: \;\;\; (\neg q_3 \Rightarrow q_5) \land (\neg q_1 \Rightarrow q_9).$

If we apply destructive dilemma using $C_1$ and $H_9$ , we can conclude; $\neg(\neg q_3)\lor \neg(\neg q_1).$ Which is equivalent to, $q_3\lor q_1.$

$C_2: \;\;\; q_3\lor q_1.$

Using modus ponens, we can conclude $q_6$ from $H_4$ and $H_{10}.$

$C_3: \;\;\; q_6.$

Using modus tollens, we can conclude $\neg q_3$ from $H_2$ and $H_{10}.$

$C_4: \;\;\; \neg q_3.$

Applying disjunctive syllogism on $C_2$ and $C_4$ , we conclude $q_1$ .

$C_5: \;\;\; q_1.$

Using modus ponens, we can conclude $q_7$ from $C_5$ and $H_5.$

$C_6: \;\;\; q_7.$

We can use the conjunction rule on $C_3$ and $C_6$ to get the following conclusion.

$C_7:\;\;\; q_6 \land q_7.$

Using modus ponens, we can conclude $q_8$ from $H_6$ and $C_7$

$C_8:\;\;\; q_8.$

Now, we get $q_2$ from $C_8$ and $H_7$ using modus ponens.

$C_9 :\;\;\; q_2.$

We can use conjunction on $C_9$ and $C_6$ and then take the conjunction with $C_8$ to reach the following conclusion:

$C :\;\;\; q_2 \land q_7 \land q_8.$

$\begin{aligned}{} &\;\;\;\;H_3:\;\;\; \neg q_3 \Rightarrow q_5\\ &\;\;\;\;H_8:\;\;\; \neg q_1 \Rightarrow q_9\\ &\rule[0 pt]{150 pt}{0.5 pt}\\ &\therefore C_1:\;\;\;(\neg q_3 \Rightarrow q_5)\land (\neg q_1 \Rightarrow q_9) \end{aligned}$

$\begin{aligned}{} &\;\;\;\;C_1:\;\;\;(\neg q_3 \Rightarrow q_5)\land (\neg q_1 \Rightarrow q_9)\\ &\;\;\;\;H_9:\;\;\; \neg q_9 \lor \neg q_5\\ &\rule[0 pt]{150 pt}{0.5 pt}\\ &\therefore C_2:\;\;\;\neg(\neg q_3) \lor \neg ( \neg q_1) \end{aligned}$

$\begin{aligned}{} &\;\;\;\;H_4:\;\;\; \neg q_4 \Rightarrow q_6\\ &\;\;\;H_{10}:\;\;\; \neg q_4 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_3:\;\;\;q_6 \end{aligned}$

$\begin{aligned}{} &\;\;\;\;H_2:\;\;\; q_3 \Rightarrow q_4\\ &\;\;\;H_{10}:\;\;\; \neg q_4 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_4:\;\;\; \neg q_3 \end{aligned}$

$\begin{aligned}{} &\;\;\;\;C_2:\;\;\; q_3 \lor q_1\\ &\;\;\;\;C_4:\;\;\; \neg q_3 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_5:\;\;\;q_1 \end{aligned}$

$\begin{aligned}{} &\;\;\;\;H_5:\;\;\; q_1 \Rightarrow q_7\\ &\;\;\;\;C_5:\;\;\; q_1 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_6:\;\;\;q_7 \end{aligned}$

$\begin{aligned}{} &\;\;\;\;C_3:\;\;\; q_6\\ &\;\;\;\;C_6:\;\;\; q_7 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_7:\;\;\;q_6 \land q_7 \end{aligned}$

$\begin{aligned}{} &\;\;\;\;H_6:\;\;\; (q_6 \land q_7) \Rightarrow q_8\\ &\;\;\;\;C_7:\;\;\; q_6 \land q_7 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_8:\;\;\;q_8 \end{aligned}$

$\begin{aligned}{} &\;\;\;\;H_7:\;\;\; q_8 \Rightarrow q_2\\ &\;\;\;\;C_8:\;\;\; q_8 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_9:\;\;\;q_2 \end{aligned}$

$\begin{aligned}{} &\;\;\;\;C_9:\;\;\; q_2\\ &\;\;\;\;C_6:\;\;\; q_7 \\ &\;\;\;\;C_8:\;\;\; q_8 \\ &\rule[0 pt]{85 pt}{0.5 pt}\\ &\therefore C_9:\;\;\;q_2 \land q_7 \land q_8 \end{aligned}$

Introduction

Propositional Logic

Basic Operations

Assessment-I

Propositional Toolkit

Assessment-II

Logical Reasoning

Assessment-III

Quantifiers and First Order Logic

Assessment-IV

Quantified Logical Reasoning

Assessment-V

Proving Theorems

Assessment-VI

Conclusion

Sarmad’s pet