2. A Small Propositional System

The examples from the previous chapter suggest a way to test the difference.

Can we find a case in which all the premises are true and the conclusion is false?

In other words, can we find a case allowed by the premises in which the conclusion fails?

If we can, the conclusion does not follow from those premises.

If no such case remains, we will call the inference valid.

That criterion will guide the construction.

Our first example was:

15 is even or 15 is divisible by 3.
15 is not even.

Thus: 15 is divisible by 3.

To examine more closely if it is valid, we will construct a small formal system in which the relation between premises and conclusion can be inspected directly.

If the model itself becomes convincing, and if it can show either that a counterexample remains or that none is available, then it may tell us something about where the constraint comes from.

What should be the main objects of our formal system?

15 is not true or false.

Even is not true or false.

That means they cannot be our primary objects.

The claims we make about them can be true or false however.

"15 is even" can be true or false. So can "15 is divisible by 3". And so can "15 is even or 15 is divisible by 3".

Claims that can be true or false will be our basic objects. We will call them propositions.

Some claims are uncertain for us, or difficult to classify, even if they are in fact either true or false and we simply do not know which. Other claims are vague or context-dependent in ways that make it less clear whether treating them as having exactly one of two truth values is an adequate representation.

Both cases raise further problems, but we do not need to settle them here. We are not trying to build a system for every kind of claim. We are trying to construct one small setting in which a source of logical constraint can be made visible. We deliberately restrict ourselves to propositions that we treat as having one of two truth values.

That gives us objects suitable for the criterion we started with.

Now take the proposition "15 is even or 15 is divisible by 3."

We can split it into two smaller claims:

"15 is even."

"15 is divisible by 3."

Each of those can still be true or false on its own.

The word "or" tells us how the two claims have been combined into a larger proposition.

The same happens with:

"15 is even or 15 is divisible by 3."

Again we have two propositions, joined in a particular way.

Now compare:

"15 is even."

We cannot split this in the same way into smaller parts that are themselves propositions and whose combination gives us the original claim.

For the present system, we will call propositions of the latter kind simple propositions.

We will use letters such as $A$ and $B$ to stand for simple propositions. At this stage, what the propositions are about does not matter to the formal structure. What matters is whether each is true or false.

For our case let:

$A$ = "15 is even"

and:

$B$ = "15 is divisible by 3".

Then $A\ and\ B$ represents "15 is even and 15 is divisible by 3."

If we want to build larger propositions formally, we need somewhere to start.

Our simple propositions provide that starting point. Symbols such as $A$, $B$ or $C$ will count as propositions in the system.

We then need rules that tell us how further propositions can be built from ones we already have.

Otherwise any sequence of symbols would be allowed, including expressions for which we would not know what proposition they represent or how their truth value should be determined.

We will call expressions constructed according to these rules well-formed formulas.

The rules introduce the connectives we need and make the construction of larger formulas traceable.

If $P$ is a proposition, then $\neg (P)$ is a proposition. It represents "not $P$".

If $P$ and $Q$ are propositions, then $(P)\land(Q)$ is a proposition. It represents "$P$ and $Q$".

If $P$ and $Q$ are propositions, then $(P)\lor(Q)$ is a proposition. It represents "$P$ or $Q$".

If $P$ and $Q$ are propositions, then $(P)\to(Q)$ is a proposition. It represents "if $P$, then $Q$".

The formation rules let us recover how a proposition was constructed.

The parentheses help preserve the order of the construction.

Every complex expression can in this way be taken apart into simpler expressions until we reach the original variables.

That trace will matter when we assign truth values, because the truth value of a complex proposition will depend on the truth values of the propositions from which it was built.

What We Have Constructed

We now have a small formal language.

Its basic objects are propositions that we treat as either true or false, and connectives. "Connective" is inherited terminology here and applies also to negation.

We have created formation rules that let us build complex propositions from simpler ones while preserving how they were constructed.

Now we need a way to find out which propositions must be true when others are true.

We have made the structure of the propositions explicit enough that their construction can be followed step by step.

If the truth value of a complex proposition can be determined from the truth values of the propositions from which it was built, then we may be able to inspect the whole process rather than simply accept the result.

What is still missing is exactly that connection.

We know how formulas can be constructed. We have not yet defined how their truth values depend on the truth values of their parts.

Fixing The Mappings

We now have expressions, but how do we make use of them?

For that we define mappings from the truth values of the simpler parts to the truth value of the whole.

Each connective operates on one or two propositions.

For two variables, there are four possible assignments:

There are no other combinations if each variable has two possible truth values.

We can look at how it was created systematically: to each truth value of A, the two truth values of B have been attached.

On the basis of complete enumeration of all cases we can now define our connectives.

We can be sure that we have not overlooked a case. That will matter for showing that there can be no counterexample.

The first column of the first table, and the first two columns of the second table give us all possible truth value combinations of the simpler propositions $A$ and $B$.

The later columns fix the truth value of the complex proposition combining them using each connective.

Once the truth values of $A$ and $B$ are given, the truth value of each more complex expression is no longer separately chosen. If $A=\text{true}$ and $B=\text{false}$, then under the definitions above $A\land B=\text{false}$, $A\lor B=\text{true}$, and $A\to B=\text{false}$.

The convincing force here is conditional. Nothing about the symbols themselves forces us to use these definitions. We have adopted them, but once we do, and once the truth values of the simpler expressions are fixed, the mappings determine the truth values of the more complex expressions in a definite way.

Why These Definitions?

The table fixes how the connectives behave inside our formal system.

As we will see now, they catch many intuitions about how connectives work in natural language. But at the same time they exclude some quite natural readings. Those readings require more complicated constructions. We gain simplicity and inspectability, but some natural-language claims become harder to translate.

Take $A\land B$.

If it represents "$A$ and $B$", then it should be true exactly when both $A$ and $B$ are true.

That is the basic intuition behind "and" in natural language.

But what we lose are the fine differences between "Peter felt sick and Peter took the medicine" and "Peter took the medicine and Peter felt sick".

There is no temporal or causal meaning hidden in the logical "and".

It is true when both components are true, and false otherwise, and no other meaning is preserved.

For $A\lor B$, we use the inclusive sense of "or": "$A$, or $B$, or both". It is false only when both $A$ and $B$ are false.

The exclusive sense of "or" gets lost, like in "We can go to the movies, or we can stay home."

If we want to express it, we need to resort to something like $(A \lor B) \land (\neg A \lor \neg B)$.

Negation is rather simple.

If $A$ is true, then $\neg A$ is false.

If $A$ is false, $\neg A$ is true.

Nothing worth mentioning seems lost here.

For $A\to B$ the case we need to exclude is the one in which $A$ is true and $B$ is false. That is exactly the shape of the counterexample we used to test whether a conclusion follows from its premises.

So we define $A\to B$ as false in that case, and true in the other three.

Treating every other combination as true makes the connective very simple to handle, but it has consequences that may seem strange.

Suppose we have:

Cats are plants.
Trees are plants.
Cats are animals.

Under the ordinary interpretation, "Trees are plants" is true. So is "Cats are animals". "Cats are plants" is false.

According to the mapping we defined for $A\to B$, both of these come out true:

"If cats are plants, then trees are plants."

If the premise is false, the whole proposition is true. We were only forbidding the case that the premise is true and the consequence is false. That is not the case here.

"If cats are animals, then trees are plants."

Because premise and consequence are true, the whole proposition is true, too. The formal system is not telling us that being a cat has anything to do with trees being plants. It is preserving only this condition: $A\to B$ is false when $A$ is true and $B$ is false. If $B$ is already true, that forbidden case cannot occur.

These consequences have long been recognized as peculiarities of the so-called material implication $\rarr$. The connective preserves only a narrow condition: the antecedent cannot be true while the consequent is false. It contains no causal or other connection between what the two propositions say. That is exactly the part of the conditional relation we want this system to preserve.

Once the representation and the mappings remain in place, the truth values of the more complex propositions are no longer settled separately. They follow from the truth values of their parts according to rules we can inspect directly.

Testing The Inference

How can we use this to check if inferences are valid?

Let's assume we have the following premises. They can either be our first example from the last chapter, or any other inference that fits this pattern:

$A \lor B$

$\neg A.$

$B.$

We can combine them into one expression (we drop the first pair of brackets; it does not change anything in the reading):

$(A \lor B) \land \neg A.$

Now compare that expression with the proposed conclusion:

$$ B. $$

How do we find the truth value of a complex proposition?

We can follow the way the proposition was constructed.

Our proposition is

$$ (A\lor B)\land\neg A $$

We begin with its simple propositions, $A$ and $B$, and list every possible assignment of truth values:

Then we look for the simplest parts whose truth value is not yet in the table.

Here these are $\neg A$ and $A\lor B$.

Their truth value depends only on $A$ and $B$, so we can add a column for each of them:

Now the truth values of both parts of the larger proposition are available:

$$ (A\lor B)\land\neg A. $$

So we add one more column:

This gives us a general procedure.

Start with the simple propositions and enumerate all possible assignments to them. Then add the complex parts one by one, beginning with those whose own parts already have truth values in the table. Continue until the whole proposition has a column.

Because our formation rules let us take every complex proposition apart into smaller propositions, we can repeat this procedure for propositions of any finite complexity.

We can now shorten the table to $A$, $B$, the premise and the conclusion:

The first two columns give us every possible assignment to $A$ and $B$. In that way we make sure we have every case covered.

The third column tells us which assignments make both premises true.

Only one does.

In that same row $B$ is true.

There is no row in which $(A\lor B)\land\neg A$ is true while $B$ is false.

Thus the inference is valid in the sense we fixed at the beginning of the chapter.

If someone wants to reject the conclusion while keeping both premises, we can ask what assignment would make that possible.

The table contains every assignment allowed by the system.

None works.

The attempted denial requires a counterexample that is not available under the conditions stipulated here.

That matters because we took care at two earlier points.

First, the first two columns contain every possible combination of truth values for $A$ and $B$ in this system.

Second, the formal expressions are meant to preserve the parts of the natural-language claims that matter for the inference.

If that representation remains convincing, and if the mappings we defined remain in place, then the table leaves no case in which the premises are true and the conclusion false.

Under those conditions, the inference is valid.

An Inference That Fails

We can now return to the first inference from the previous chapter that did not seem convincing:

15 is not even or 15 is divisible by 3.
15 is not even.

Thus: 15 is divisible by 3.

Using the same representation gives $\neg A \lor B$ and $\neg A$.

The proposed conclusion is now $B$.

Again, we can combine the premises and inspect every possible assignment:

This time two assignments make both premises true.

In one of them $B$ is false:

That means the premises can be true, while the conclusion is false.

The constraint that held in the earlier inference is absent here.

And the table gives us the counterexample directly.

Translated back into ordinary language, the premises do not exclude this situation:

15 is not even or 15 is divisible by 3.
15 is not even.
15 is not divisible by 3.

The last sentence is false in fact as a statement about arithmetic. But if we want it to enter the inference and make the counterexample go away, we need to add it as a premise. The premises we have do not force the conclusion. And that is the only question we are asking here: whether the inference is valid.

For the validity of an inference, it does not matter whether the conclusion happens to be true for some other reason than following from the premises. An inference cannot use facts that have not entered the representation.

We can see this more easily by changing the example:

17 is not even or 17 is divisible by 3.
17 is not even.
17 is divisible by 3.

Here the same inference form would lead to a false conclusion.

On the other hand this is a valid inference, even though one premise is false:

17 is even or 17 is divisible by 3.
17 is not even.

Thus: 17 is divisible by 3.

Our small formal system does both kinds of work we wanted from it, provided that we handle the translation into the system with care.

It shows, within the representation we constructed, why one inference satisfies our criterion of validity and why the other does not.

And it can do that because the relevant possibilities have all been made explicit.

What This Construction Shows

We can now separate two things that were easy to run together at the beginning.

First, we can see where the constraint inside the formal system comes from.

For a finite number of simple propositions, we can enumerate every possible assignment of truth values. The mappings then determine the truth values of the more complex propositions for each assignment.

To test an inference, we inspect every case in which the premises are true.

If none of those cases leaves the conclusion false, then there is no counterexample within the system. We can be sure of that. The conclusion is not another choice left open after the premises, mappings, and possible assignments have been fixed.

Several things contribute to the constraint: complete enumeration of the relevant possibilities, fixed mappings between simpler and more complex propositions, and a construction that remains open to inspection.

They also make mistakes easier to locate. If something seems wrong, we can ask whether a case was omitted, a mapping was applied incorrectly, a formula was constructed incorrectly, or the original problem was represented badly.

That combination seems to be the source of how this constraint becomes so widely convincing.

But this alone does not show that the formal system is convincing as an appropriate representation of a particular inference.

In our examples, we were interested only in whether the premises could be true while the conclusion was false. We therefore represented the claims as propositions with two truth values and chose mappings that preserve the distinctions needed for that test.

This deliberately leaves other things out. The system does not preserve temporal order, causal connection, uncertainty, vagueness, or every feature of ordinary conditionals.

The choice of mappings can be questioned, as can the decision to treat the claims as simply true or false, the translation of the ordinary-language claims into propositions, and whether something left out by the representation matters to the problem.

If those choices remain convincing for the case at hand, then the absence of a counterexample inside the system can carry convincing force in the inquiry.