Highlight text to annotate itX
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.