Logical Entailment - Propositional Logic - by Michael Genesereth

Validit, validity, satisfiability, and unsatisfiability, are properties of individual sentences. In logical reasoning, we are not so much concerned with individual sentences, as we are with the relationships between sentences. In particular, we would like to know, given some sentences, whether other sentences are or are not logical conclusions. This relative property is known as logical entailment. When we're speaking about propositional logic, we sometimes use the phrase propositional entailment. By definition; a set of sentences, delta, logically entails a sentence fee. If in only in every truth assignment that satisfies delta also satisfies fee. In what come, follows, we will use this notation shown here, where we write delta then what's called a double turnstile, a vertical bar followed by an equal sign, and phi, as our way of notating the statement that a set of premises delta logically entails phi. As an example of this concept we can say that the sentence fee P logically entails the sentence P or Q. Since the disjunction is true, whenever one of its disjuncts is true, then P or Q must be true whenever P is true. On the other hand, the sentence P does not logically entail P and Q. The conjunction is true if and only if both of its conjuncts are true, and Q might be false. Of course any sentence containing, set of sentences containing both P and Q must logically entail the single sentence P and Q. Note the relationship of logical entailment is a logical one even if the premises of a problem do not logically entail a conclusion this does not mean that the conclusion is necessarily false even if the premises are true. It just means that it's possible that the conclusion is false. Note also that logical entailment is not the same as logical equivalence. The sentence P logically entails P or Q, but P or Q does not necessarily entail, does not logically entail P. Logical entailment is not so much analogous with arithmetic equality as it is with arithmetic inequality. One way of determining whether or not a set o f premises logically entails a possible conclusion is to check the truth table for the proposition constants in the language. This is called the truth table method. First we form a truth table for the proposition constants and add a column for the premises and a column for the conclusion. We then evaluate the premises. We evaluate the conclusion, and we compare the results. If every row that satisfies the premises also satisfies the conclusion, then the premises logically entail the conclusion. Otherwise, they don't. As an example, let's use this method to show that P logically entails P or Q. We've set up our truth table, and add columns for our premises and the conclusion. In this case, the premise is just P, and so evaluation is straightforward. We just copy the col-, first column. The conclusion is true if and only P is true or Q is true. Finally we notice that every row that satisfies the premise also satisfies the conclusion. Hence P logically entails P or Q. Now let's do the same for the premise P and the conclusion P and Q. We set up our table as before and evaluate our premise. In this case there is only one row that satisfies our conclusion. Finally we notice that the assignment in the second row satisfies our premise but does not satisfy our conclusion, So logical entailment does not hold in this case. Finally let's look at the problem of determining whether a set of premises consisting of the sentence P as well as the sentence Q logically entails the sentence P and Q. Here we set up our table as before but this time we have two premises to satisfy. Only one truth assignment satisfies both premises and this truth assignment also satisfies the conclusion, and so in this case logical entailment does hold. As a final example, let's return to the love life of a fickle Mary. Here is a slightly simplified version of the problem from the course introduction. We know P implies Q. This is, if Mary loves Pat, then Mary loves Quincy. We know N implies P or R. That is, if it's Monday, then Mary loves Pat or Quinc Y. And let's say we know that it is Monday. Let's show that Mary loves Quincy. To make this determination we formed the truth table for our language. We evaluate each of our premises and we evaluate our conclusion. Finally we check that the conclusion is satisfied in every row that satisfies the premises. Hence in this case we can say that Mary loves Quincy is a logical conclusion from the premises. You know, the logical entailment and satisfied ability have an interesting relationship to each other. In particular, if a set of delta of sentences logically entails a sentence fee then delta together with [inaudible] of fee must be unsatisfiable. The reverse is also true. If delta with [inaudible] of fee is unsatisfiable then delta must logically entail fee. This is guaranteed by meta-theorem called the unsatisfiability theorem shown here with a small proof that it's correct. An interesting consequence of this is that we can determine logical entailment simply by checking for unsatisfiability.