Amy glenschool engineering information technology murdoch university

Proving and Testing the Validity of Arguments (ctd.)

Chapter 7: Propositional Logic (continued)

Hn

Recall: Logical Arguments/Inferences

...

Hn

H1, H2, . . . , Hn.

Recall: Logical Arguments/Inferences

...

Hn

H1, H2, . . . , Hn.

Otherwise the inference is said to be invalid or a fallacy.

H2

...

Hn are true), in which case we say that C is a logical consequence of the hypotheses

H1, H2, . . . , Hn.

Recall: Rules of Inference
Some valid inferences tend to arise very frequently, and it is convenient to use them over and over again instead of having to draw up a truth table each time we use them.

Recall: Rules of Inference
Some valid inferences tend to arise very frequently, and it is convenient to use them over and over again instead of having to draw up a truth table each time we use them.

To do this it is not necessary to examine the entire truth table. It is sufficient to show that Q is true whenever P is true.

Example: using rules of inference

Example: using rules of inference

Example: using rules of inference

Testing Validity of Inferences
▶ Recall that a proposition C is a valid conclusion from the hypotheses H1, H2, . . . , Hn if and only if the compound proposition

▶ Recall that a proposition C is a valid conclusion from the hypotheses H1, H2, . . . , Hn if and only if the compound proposition

P := (H1 ∧ H2 ∧ · · · ∧ Hn) → C
is a tautology, i.e., the conclusion C is true whenever all of the hypothesis H1, H2, . . . , Hn are true.

▶ So we can always determine the validity or otherwise of an inference simply by computing a truth table.

▶ But this can be quite long and tedious if we are forced to do it by hand.

▶ But this can be quite long and tedious if we are forced to do it by hand.

▶ As we have just seen, rules of logical implication can also be used to prove that a given inference is valid.

▶ But this can be quite long and tedious if we are forced to do it by hand.

▶ As we have just seen, rules of logical implication can also be used to prove that a given inference is valid.

▶ Suppose you were not told in advance that a given inference is valid, but instead were asked to determine its validity.

▶ How would you go about doing this without computing the truth table?

This will work fine if the inference happens to be valid, but if it is invalid, then you’ll just keep arriving at dead ends, never knowing whether you are missing some clever step in the “proof”.

▶ Suppose you were not told in advance that a given inference is valid, but instead were asked to determine its validity.

▶ Suppose you were not told in advance that a given inference is valid, but instead were asked to determine its validity.

▶ How would you go about doing this without computing the truth table?

▶ Remember that we are trying to discover whether the compound proposition
P := (H1 ∧ H2 ∧ · · · ∧ Hn) → C
is a tautology or not.

▶ Remember that we are trying to discover whether the compound proposition
P := (H1 ∧ H2 ∧ · · · ∧ Hn) → C
is a tautology or not.

▶ Remember that we are trying to discover whether the compound proposition
P := (H1 ∧ H2 ∧ · · · ∧ Hn) → C
is a tautology or not.

▶ If P is a tautology, then it always has the value 1, no matter what values we substitute in for its variables p1, p2, . . . .

▶ On the other hand, if P is not a tautology, then there is an
assignment of values to the variables p1, p2, . . . that makes P have the value 0.

▶ The method we use is to try to find such an assignment of values.

▶ The method we use is to try to find such an assignment of values.

▶ If we succeed, then P is not a tautology and as a result of our working we have a counterexample to show why.

▶ Note: P := H → C where H := H1 ∧ H2 ∧ · · · ∧ Hn.

▶ Since P is false only when H is true and C is false, it follows that P is not a tautology if and only if we are able to choose values for the variables so that H is true and C is false.

I have specified the initial conditions and the program begins. So I must have included an infinite loop.

Example

Let i denote “I specify initial conditions”Let b denote “The program begins”
Let ℓ denote “I included an infinite loop”Let t denote “The program terminates”Let s denote “The program succeeds”

Example

Solution

We try to falsify the inference by making each of the hypotheses true but the conclusion false. This is indicated by the 1’s and 0’s in the following working.

Solution

We try to falsify the inference by making each of the hypotheses true but the conclusion false. This is indicated by the 1’s and 0’s in the following working.

We try to falsify the inference by making each of the hypotheses true but the conclusion false. This is indicated by the 1’s and 0’s in the following working.

Example . . .

But when trying to do such an assignment, we reach a conflict between H1 (with q = 0) and H3 (with q = 1), for instance.

Example . . .

But when trying to do such an assignment, we reach a conflict between H1 (with q = 0) and H3 (with q = 1), for instance.

▶ Since we have failed to assign values to the variables so that all three hypothesis are true but the conclusion is false, there is no
counterexample and the inference is valid.

Example . . .

▶ Since we have failed to assign values to the variables so that all three hypothesis are true but the conclusion is false, there is no
counterexample and the inference is valid.