Connecting propositional logic and mathematical proofs

logicproof-writing

I am a bit confused about the connection between propositional logic and mathematical proofs. The goal of a proof of the statement $(P{\implies}Q)$ is to show that it is always true, so it's a Tautology. Is this correct?

For example, I want to prove this:

If $x$ is divisible by $6$, it is also divisble by $3$.

In propositional logic, we have

  • Statement $P$: $\quad x$ is divisible by $6$
  • Statement $Q$: $\quad x$ is divisible by $3$

The truth table for implications has the form

\begin{array}{cc|c@{}ccc@{}c}
P&Q&(&P&\rightarrow&Q&)\\\hline
1&1&&1&\mathbf{1}&1&\\
1&0&&1&\mathbf{0}&0&\\
0&1&&0&\mathbf{1}&1&\\
0&0&&0&\mathbf{1}&0&
\end{array}

Because the implication is always true if $P$ is false, it is sufficient to just show that $Q$ is true if $P$ is true, like in the below, right ?

  • Proof:

    $x\text{ is divisible by }6\\
    \implies x= 6 \times k\\
    \implies x= (3\times 2)\times k\\
    \implies x= (2\times k)\times 3\\
    \implies x= m\times 3\\
    \implies x\text{ is divisible by }3.$

Best Answer

Yes, your argument is correct.

I will also address your more general question about

the connection of propositional logic and mathematical proofs

For the most part, everyday mathematics is written in English (or other natural language) with a few symbols. So your proof is essentially

If $6$ divides $x$ then $x = 6k = 3(2k)$ for some integer $k$. That shows $x$ is also a multiple of $3$.

The formal argument with the truth table for implication is called for only if that's what your instructor requires at this stage of you education.

Related Question