Are deduction rules just truth tables?

Question

What is the difference between a deduction rule and a truth table? In what sense are they axioms?

The notes I am studying give the following deduction rules

$1. P\implies(Q\implies P) \\ 2. [P\implies(Q\implies R)]\implies [(P\implies Q) \implies (P\implies R)] \\ 3.\neg\neg P\implies P $

It also gives the 'modus ponens' deduction rule, that from P and $P\implies Q$ we can deduce Q.

Take the first axiom as an example. If P is a tautology on a set of elementary propositions, then $Q\implies P$ is a tautology. Drawing my truth table, that's because we never have $Q \land \neg P$ being true, as P is always true! Or for $\neg \neg P \implies P$ I again draw my truth table and find that P is a tautology if $\neg \neg P$ is a tautology.

Or perhaps I am already using these axioms when drawing up my truth tables, but haven't realised it?

Thank you!

Answer 1

A deduction rule is not the same as a truth-table.

In general, deduction rules are used for proofs, which are sequences of statements, starting with some givens (premises, assumptions, definitions, axioms), and conclude with some conclusion (theorem). A deduction rule says that "If you already have one or more statements of the form [such-and-so], then you can write down a new statement of the form [this-and-that]"

Axioms can be seen as a special kind of deduction rule. They basically say: "At any point in the proof, you can write down a statement of the form [bla bla]"

Now, technically a deduction rule can be anything. That is, I could define a deduction rule that says:

\begin{array}{c} \cfrac{}{\varphi} \end{array}

I call this the 'Hokus Ponens' rule: it says that at any point, I am allowded to write down any statement I want!

But, obviously, this is not a valid (sound) inference rule! So, actual proof systems will ensure that their deduction rules are in fact valid. And, how do we know they are valid? Well, for that we can use a truth-table, as a truth-table is a tool that allows us to investigate the truth-conditions of the statements involved.

Indeed, this is basically what you yourself did: when you put the axioms on a truth-table, and found them all to be tautologies, you effectively verified that these axioms (as special inference rules) are in fact valid.

Answer 2

The first three things are usually called axioms rather than rules cause they are templates for statements you are allowed to assume. (But we can think of axioms as simple cases of rules... a rule that just says “_ holds” rather than something like “if _ holds then _ holds.”

With regard to your example about the first axiom, you are thinking about it slightly wrong. The most pertinent fact is not that if $P$ is a tautology then $Q\to P$ is a tautology, though that is true. It is that if $P$ is true then $Q\to P$ is true. In other words that $P\to(Q\to P)$ is a tautology.

In fact all three axioms are tautologies, as you can verify by truth tables. And the modus ponens rule has the property that if the premises are true, then the conclusion is. This guarantees that anything we can derive in this deductive system will be a tautology.

You aren’t using the axioms at all when you are drawing up the truth tables. You are talking about the axioms and studying their semantic properties, not using them.

The point of the deductive system is that we have simple reasoning rules that always produce tautologies (and in fact they are capable of deriving any tautology, although that’s harder to prove). This may seem just an unnecessarily counterintuitive way of going about things since checking a tautology is already simple via a truth table (though natural deduction systems are much more intuitive than Hilbert systems like the one here). However when you move along to first order logic, the semantics becomes less concrete and is no longer decidable, and the value of deductive systems becomes more apparent.

(Also I shouldn’t discount the value of deductive systems as an interesting object of study in their own right, rather than just as a more concrete way of arguing for something’s validity.)

Answer 3

The examples you give do not count, rigorously, as examples of deduction rules.

P --> ( P --> Q) is a proposition ( a sentence that , in principle, can be true or false).

It happens that this proposition is always true ( true in all possible cases, as it is shown by its truth table). Therefore , it is a law of logic or a logical truth.

Corresponding to this law, there is an inference rule. A rule is not a proposition, it is neither true or false, since it is an order, a command, an " imperative" This corresponding rule is :

From P, infer (P --> Q).

Each law of logic whose main operator is a conditional has a corresponding rule.

For example the "modus ponens law" : [(A--> B) & A] --> B

has a corresponding rule of inference, the "modus ponens rule" :

" from (A-->B) and A , infer B" .

The distinction between laws and rules amounts to the distinction between semantics and syntax.