Just recently, I’ve been reading a beautiful book written by Charles Petzold titled Code: I’m still at chapter eleven “Gates (not Bill)”, but just the chapter before, namely “Logic and Switches” had an intriguing problem described:
$\eqref{eq:dcb6}$ All philosophers are logical; and $\eqref{eq:e6e9}$ an illogical man is always obstinate (stubborn).
Well, these are two premises, but what would the conclusion be? According to Charles it is:
$\eqref{eq:e1c5}$ Some obstinate people are not philosophers.
This is quite counter-intuitive, isn’t it? Well, I wanted see the proof! So I sat down, and translated all statements into predicate logic. Well, the first premise goes like this:
$$\begin{equation}\label{eq:dcb6} \forall{p}\in\mathbb{P}:\textbf{logical}(p) \end{equation} $$You can read the above statement $\eqref{eq:dcb6}$ like this: “For all $p$ in $\mathbb{P}$ it holds that $p$ is logical”, where $p$ stands for a single philosopher and $\mathbb{P}$ stands for the set of all philosophers. This means we can read the whole thing more naturally like this: “For each philosopher, it holds that he (or she) is logical”, or shorter: “All philosophers are logical.”
Now, let’s have a look at the second premise:
$$\begin{equation}\label{eq:e6e9} \forall{m}\in\mathbb{M}:\neg\textbf{logical}(m) \implies\textbf{obstinate}(m) \end{equation} $$So, let’s read it again: For all $m$ in $\mathbb{M}$ it holds, that if $m$ is illogical, then $m$ is obstinate, simply meaning that “all illogical men are always obstinate.” Now, let’s translate the conclusion:
$$\begin{equation}\label{eq:e1c5} \neg\forall{m}\in\mathbb{M}:\textbf{obstinate}(m) \land m\not\in\mathbb{P} \end{equation} $$which means that “not for all $m$ among all men $\mathbb{M}$, it holds that $m$ is obstinate and $m$ does not belong to the set of philosophers $\mathbb{P}$”. This rather very complicated statement can be simplified to: “Some obstinate men are not philosophers!”
Good, now that we have translated perfectly understandable English into completely incomprehensible predicate logic, let’s do some magic to derive from the premises $\eqref{eq:dcb6}$ and $\eqref{eq:e6e9}$ the conclusion $\eqref{eq:e1c5}$. But before that we need to state another rather obvious fact, namely that “all philosophers are men, but not all men are philosophers:”
$$\begin{align}\label{eq:49fe} \mathbb{P}\subset\mathbb{M}\tag{$\star$} \end{align} $$Above, we say that the set of philosophers $\mathbb{P}$ is a subset of all men $\mathbb{M}$, which is the same as declaring that all philosophers are men (but not necessarily the other way around).
Derivation of the conclusion
Based on the premises $\eqref{eq:49fe}$ that all philosophers are men, and $\eqref{eq:dcb6}$ that they are logical, we can deduce that there are some men who are not philosophers, hence illogical (where we assume based on $\eqref{eq:dcb6}$ that only philosophers can be logical):
$$\begin{equation}\label{eq:95af} \exists{m}\in\mathbb{M}:m\not\in\mathbb{P} \vdash \neg\textbf{logical}(m) \end{equation} $$Further, since all illogical men tend to be obstinate, we can derive that there exists also an illogical one, who is indeed obstinate:
$$\begin{equation}\label{eq:aa48} \exists{m}\in\mathbb{M}:\neg\textbf{logical}(m) \implies\textbf{obstinate}(m) \end{equation} $$which we can reformulate by using the fact, that “$\neg{a}$ implying $b$” ($\neg{a}\implies{b}$) is equivalent to “$a$ or $b$” ($a\lor{b}$):
$$\begin{equation}\label{eq:1c8c} \exists{m}\in\mathbb{M}:\textbf{logical}(m) \lor\textbf{obstinate}(m) \end{equation} $$Hence apparently, there is a man who is logical or obstinate! Now, if we combine $\eqref{eq:95af}$ and $\eqref{eq:1c8c}$ we get:
$$\begin{equation}\label{eq:a4ba} \exists{m}\in\mathbb{M}:\neg\textbf{logical}(m)\land\bigg{(} \textbf{logical}(m)\lor\textbf{obstinate}(m)\bigg{)} \end{equation} $$which is equal to — derived by pulling the left hand side into the parentheses and then simplifying $\neg\textbf{logical}(m)\land\textbf{logical}(m)$ to $\bot$, namely false:
$$\begin{equation}\label{eq:c038} \exists{m}\in\mathbb{M}:\bot\lor\bigg{(} \neg\textbf{logical}(m)\land\textbf{obstinate}(m)\bigg{)} \end{equation} $$which is equal to — derived by dropping $\bot$ in the or statement:
$$\begin{equation}\label{eq:8a48} \exists{m}\in\mathbb{M}: \neg\textbf{logical}(m)\land\textbf{obstinate}(m) \end{equation} $$which is equal to — according to $\eqref{eq:dcb6}$:
$$\begin{equation}\label{eq:b3b1} \exists{m}\in\mathbb{M}: \textbf{obstinate}(m)\land m\not\in\mathbb{P} \end{equation} $$So $\eqref{eq:b3b1}$ means that “some obstinate man are not philosophers!” Quod erat demonstrandum. $\blacksquare$
No comments:
Post a Comment