Syntactic and Semantic Proof

Here we consider an example of a proof. The figure to the right provides the basis for our example. In this example we begin with a set of assertions stated in English. The first step is to identify the basic propositions that are contained in these assertions. These are shown below and will be referred to as f, s, m and c.    Next, we must determine the meaning of the connectives used in the English assertions in order to identify the complex propositions. These are shown as three premises in the next box and correspond to the first three sentences.    We wish to determine whether or not the negation of s follows from these premises. Or, another way of putting the question is shown in the last box. Here the entire set of English assertions are mapped to a single complex proposition. If this complex proposition is a tautology, then the negation of s is implied by the three premises. A tautology is a proposition that is true under all possible assignments of truth values to its constituent propositions. The complex proposition 'p or not p' is an example of a tautology. Conversely, a contradiction is a complex proposition that is false under all possible assignments of truth values. The complex proposition 'p and not p' is an example of a contradiction.

There are two basic ways in which to try to determine if a proposition deductively follows from a set of propositions. One way is to reason in the syntax of logical expressions and the other is to reason in the semantics of the expressions.

A Syntactic Proof

We first consider reasoning in the syntax of logical expressions. This is referred to as the proof theoretic approach. In this approach the logical expressions are manipulated in order to discover a deductive proof.    The figure to the right lists some of the better known rules of inference. The rule is shown on the left and the common name for the rule is shown on the right.

To read these as rules of inference you must do two things. First, think of the p, q, r, and so on as standing for any proposition. Thus, these are general rules and technically should probably be called inference schema. Second, find the –> that is not enclosed in any sort of parenthesis. Then the expression to the left of this implication is the premise and the expression to the right is the implication or deduction that is permitted from the premise. For example, the first rule which is called addition, says that if 'p' is true then you may infer that 'p or q' is true. And, of course, if you check out the truth table for this you would immediately see why this is valid. You would also note that this complex expression is a tautology.

The figure to the right shows the syntactic proof of our example. For each line of the proof I have written the basis for that line to the right. Thus, the first two lines are simply the first two premises. The conjunction of these premises provide the left side of the inference rule called hypothetical syllogism and the third line is the right hand side of this hypothetical syllogism. Thus, each line of this proof is justified, and of course the last line is the proposition that we set out to prove. This seems rather straightforward. But, there is a practical problem. The number of rules of inference that we might try at any point is usually quite large. And, in fact, finding a proof is simply a form of search....and one that we want to be exhaustive so that we will be sure to find a proof if one exists. Thus, the practical problem. These search spaces can get very large and their size increases very dramatically as we increase the number of premises that we are given.

A Semantic Proof

Perhaps, reasoning in the semantics will make life a bit simpler. Recall that the semantics of propositions is simply their truth value. Consequently, the first step is to consider all possible combinations of truth values that could be assigned to the basic propositions in our example. These are shown in the figure to the right. Notice that we have 4 basic propositions, each can be assigned two different truth values. In this case, there are 16, or 2 to the 4, possible unique combinations of truth values. And, in general, if there are n basic propositions, then we will need to consider 2 raised to the nth power of combinations of truth value assignments. The next step is to consider the truth value of the complex proposition of our example under all of these possible assignments of truth values to the basic propositions. This complex proposition is shown again here for ease of reference.

We can't determine the possible truth values of this complex proposition in a single step. We must build up the truth values of the propositions in this expression from the basic constituent propositions. We could do this in any order, but in this example we will proceed in a left to right fashion.

The first constituent is f or s. The figure to the right shows all of the truth value assignments for f and for s in the first two columns. The truth value for this complex expression, f or s, is obtained using the truth table for the logical connective 'or.' The third column lists the truth value that result.

The next step is to consider the complex proposition f or s implies m. The figure to the left shows the results obtained for this complex proposition. Note that the results that were obtained in the first step of this proof for the complex proposition f or s appear in the first column of this figure. These together with the possible truth value assignments to m are used to determine the truth value assignments shown in the third column.

Next , we consider the constituent m implies c. The figure to the right shows the resulting possible truth value assignments for this proposition.

The next figure on the left shows the resulting truth values that obtain for the conjunction of the two complex propositions shown in the first two columns.

And, the next figure on the right shows the possible truth values for the conjunction of the full set of three premises used in this example.

Finally, the figure to the left shows the result for the entire expression. And, it turns out that we have shown that this expression has the value T or true for all possible assignments of truth values to its constituents. Thus, not s or "stones don't sing" does indeed logically follow from these premises! We have proven this in the semantic model for these expressions. Again, the procedure is simple and straightforward. But, the procedure requires considerable memory and "computation" to obtain the result. And, remember that the combinations of truth values that must be considered grows exponentially with n.

	Knowledge Representation - Table of Contents
© Charles F. Schmidt