Some fundamental concepts of logic

If you encountered propositional logic before, you may know that there are three large classes of formulas one may distinguish. Usually, these are called contingent, tautology, and contradiction. In our semantics, all this means is the following:

Now one thing to note at the beginning is that atomic formulas are all contingent. That is, for each atomic formula $P$, there is a structure $\mathbf{S}$ such that $\mathbf{S} \models P$, and there is a structure $\mathbf{S}'$ such that $\mathbf{S}' \not\models P$. On the other hand, some complex formulas are contingent, some are tautologies, and some are contradictions.

What makes a formula a tautology or a contradiction? It is the way the connectives work. Notice that by definition, each connective must obey some specific rules in any structure regarding the truth-values of the formulas on which it operates. For example, $X \wedge Y$ is true in any $\mathbf{S}$ iff $X$ and $Y$ are both true individually in $\mathbf{S}$. However, some formulas may say things that go against these rules. This means that they won’t be true in any structure $\mathsf{S}$, since again, every structure must abide by these rules, while the formula says otherwise.

Let’s take the simplest example: $X \wedge \neg X$. In fact, this is not a formula of the language, but a class of formulas of form $X \wedge \neg X$. But as it turns out, no matter what formula you take for $X$, it will always be the case that for any structure $\mathbf{S}$, $\mathbf{S} \not\models X \wedge \neg X$. In other words, this formula schema cannot have a true instance.

Now again, the reason for this is the way structures are defined. In particular, in every structure $\mathbf{S}$, either $\mathbf{S} \models X$, or $\mathbf{S} \not\models X$. This is sometimes called the Law of Excluded Middle, and it falls out of our definition of a structure. What this means is that every formula $X$ is either true in a structure, or false in a structure, and not a third thing (the ‘excluded middle’).

We also have that it is never the case that $\mathbf{S} \models X$ and $\mathbf{S} \not\models X$. This is sometimes called the Law of Non-contradiction. Again, this falls out of our definition of what it means for something to be a structure. Now adding these two laws together, you simply get that every formula $X$ is either true or false, and not both or neither in a structure.

So take $X \wedge \neg X$. By the above, either $\mathbf{S} \models X$, or $\mathbf{S} \models \neg X$. Those are the only two options we have. We can consider each of them in turn:

1. Suppose $\mathbf{S} \models X$. Then, by definition of $\neg$, $\mathbf{S} \not\models X$. But $\mathbf{S} \models X \wedge \neg X$ iff $\mathbf{S} \models X$, and $\mathbf{S} \models \neg X$, by definition of $\wedge$. So since the latter half fails, $\mathbf{S} \not\models X \wedge \neg X$.

2. Suppose $\mathbf{S} \not\models X$. Then, by definition of $\neg$, $\mathbf{S} \models \neg X$ in this case. But again, $\mathbf{S} \models X \wedge \neg X$ iff $\mathbf{S} \models X$, and $\mathbf{S} \models \neg X$, by definition of $\wedge$. Moreover, in this case, we already assumed that $\mathbf{S} \not\models X$. So once again, $\mathbf{S} \not\models X \wedge \neg X$.

This means that there is no structure $\mathbf{S}$ in which $X \wedge \neg X$ is true. So every instance of $X \wedge \neg X$ is false in every structure, no matter what you take $X$ to be.

At first, this type of talk might be confusing, but all we did was precisely represent what is usually illustrated by the following truth table:

In particular, a formula is contradictory, as represented in a truth table, if all values in the column underneath the formula are false. Again, the truth table rows just represent two large (jointly exhaustive) classes of structures, one in which $X$ is true, the other in which $X$ is false, and then show that neither of these classes make $X \wedge \neg X$ true.

It will be important in what’s to come that every contradictory formula hides a claim of the form $X \wedge \neg X$ for some formula $X$. In fact, every contradictory formula hides a claim of the form $P \wedge \neg P$, for some atomic formula $P$. In other words, the only contradictory formulas are those that try to say that something both is and is not the case (though not necessarily in exactly those words).

On the other hand, we may find formulas of the form $X \vee \neg X$, which are not contradictory, but the exact opposite, tautological. Again, the reason is because of how the connectives are defined in a structure. Again, in every structure, we have that either $\mathbf{S} \models X$, or $\mathbf{S} \not\models X$. So:

1. If $\mathbf{S} \models X$, then $\mathbf{S} \models X \vee \neg X$, since by definition of $\vee$, $S \models X \vee \neg X$ iff it models either $X$ or $\neg X$.

2. If $\mathbf{S} \not \models X$, then by definition of $\neg$, $\mathbf{S} \models \neg X$, so by definition of $\vee$, $\mathbf{S} \models X \vee \neg X$ (because of the latter half of the disjunction now).

Thus, $X \vee \neg X$ must be true in every structure $\mathbf{S}$, no matter which formula we take for the variable $X$. And again, this is just an explanation of the following truth-table:

As you can see, unlike with contradictions, tautologies have all values as true in the column underneath them.

Now we can formulate one of the most significant connections between tautologies and contradictions. As such, we will give it the proper form of a theorem.

As before, inverting this biconditional by negating both sides also gets us a true biconditional. Thus:

Here is an additional proposition that may help here:

Now given the above two propositions, we can see that if a formula $X$ of $\mathcal{L}_0$ is not a tautology, then $\neg X$ is not a contradiction, because if $X$ is not a tautology, it is either a contradiction or contingent, so $\neg X$ will either be a tautology (hence not a contradiction), or contingent (hence not a contradiction). And similarly the other way around.

In fact, the following also follows:

Some of what the above propositions tell us is summarized in Table 5.1.

Here is another thing that will be relevant presently. Suppose you have a formula $X$, and it is not a tautology (so it is either a contradiction or contingent). Then, its negation $\neg X$ will not be a contradiction (it will either be a tautology or contingent). Thus, if $X$ is not a tautology, there is at least one structure $\mathbf{S}$ such that $\mathbf{S} \models \neg X$, and vice versa. This is usually what is called a counterexample. In other words: