Perhaps the simplest formal system for zeroeth order logic is the Nicod system. As its language it uses the subset of our language for zeroeth order logic consisting of those lists where \({ ⊼ }\), whose truth table is
| P | Q | ( P ⊼ Q ) |
|---|---|---|
| F | F | T |
| F | T | T |
| T | F | T |
| T | T | F |
is the only logical operator appearing. There’s no loss of expressiveness involved in this restriction since we can write \({ ( P ∧ Q ) }\) as \({ [ ( P ⊼ Q ) ⊼ ( P ⊼ Q ) ] }\), \({ ( P ∨ Q ) }\) as \({ [ ( P ⊼ P ) ⊼ ( Q ⊼ Q ) ] }\), and \({ ( ¬ P ) }\) as \({ ( P ⊼ P ) }\). All the other operators were expressed in terms of \({ ∧ }\), \({ ∨ }\) and \({ ¬ }\) so they can be expressed by first converting the expression into one involving those three operators and then converting them as above.
The Nicod system has a single axiom, \[ ( ( p ⊼ ( q ⊼ r ) ) ⊼ ( ( s ⊼ ( s ⊼ s ) ) ⊼ ( ( u ⊼ q ) ⊼ ( ( p ⊼ u ) ⊼ ( p ⊼ u ) ) ) ) ) . \] There are two rules of inference. The first is the rule of substitution discussed earlier. More explicitly, from any statement we can derive another statement by replacing each occurence of one of the variables with an expression. In fact we can do this for each variable in the statement. The second is that from two statements of the form \({ P }\) and \({ [ P ⊼ ( Q ⊼ R ) ] }\) we can derive the statement \({ R }\).
We can use truth table method to show that, no matter which of the 32 possible ways of assigning truth values to the variables \({ p }\), \({ q }\), \({ r }\), \({ s }\), and \({ u }\) we choose, the statement \[ ( ( p ⊼ ( q ⊼ r ) ) ⊼ ( ( s ⊼ ( s ⊼ s ) ) ⊼ ( ( u ⊼ q ) ⊼ ( ( p ⊼ u ) ⊼ ( p ⊼ u ) ) ) ) ) . \] will always evaluate to true, i.e. that it is a tautology.
It is also possible to show that the two rules of inference of the system have the property that if applied to tautologies they lead to a tautology. In fact the first is, as discussed earlier, a general property of zeroeth order logic and the second follows from the truth table
| P | Q | R | ( Q ⊼ R ) | [ P ⊼ ( Q ⊼ R ) ] |
|---|---|---|---|---|
| F | F | F | T | T |
| F | F | T | T | T |
| F | T | F | T | T |
| F | T | T | F | T |
| T | F | F | T | F |
| T | F | T | T | F |
| T | T | F | T | F |
| T | T | T | F | F |
There is only one case in which both \({ P }\) and \({ [ P ⊼ ( Q ⊼ R ) ] }\) are true and in that case \({ R }\) is also true.
It follows that any theorem must be a tautology, since we start from an axiom which is true in any interpretation which assigns to the operator ⊼ the meaning described by its truth table given earlier and the rules of inference can only produce true statements from true statements. In other words any interpretation which assigns to the operator ⊼ the meaning described by the truth table above and assigns any truth values whatever to its variables is a sound interpretation of the Nicod system. We say that a system is “sound” if the intended interpretation or interpretations are sound. The Nicod system is sound in this sense.
We just saw that the Nicod system is sound, which in this case means that every theorem is a tautology. It’s also complete, in the sense that every tautology is a theorem. As you might imagine, proving this is rather painful. The fact that we have only one axiom and two rules of inference made proving soundness relatively easy but it makes proving completeness very hard. We won’t even attempt it.
It’s important to note that soundness and completeness are properties of the system and its interpretation. They express, respectively, the fact that every provable statement is true and every true statement is provable. Provability is a concept within the system, but truth depends on the interpretation given to statements, which is not part of the system.