Download as:
Rating : ⭐⭐⭐⭐⭐
Price: $10.99
Language:EN
Pages: 51

Amy glenschool engineering information technology murdoch university

Proving and Testing the Validity of Arguments (ctd.)

MAS162 – Foundations of Discrete Maths
1

Chapter 7: Propositional Logic (continued)

MAS162 – Foundations of Discrete Maths
2
MAS162 – Foundations of Discrete Maths
3
MAS162 – Foundations of Discrete Maths
3

Hn

C
MAS162 – Foundations of Discrete Maths
3

Recall: Logical Arguments/Inferences

...

Hn

H1, H2, . . . , Hn.

Recall: Logical Arguments/Inferences

...

Hn

C

H1, H2, . . . , Hn.

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

MAS162 – Foundations of Discrete Maths
3

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.

MAS162 – Foundations of Discrete Maths
4

Example: using rules of inference

Example: using rules of inference

Write the following argument in symbolic form & prove that it is logically valid.

Example: using rules of inference

Write the following argument in symbolic form & prove that it is logically valid.

¬m
¬v
(w ∨ ¬i) h



w
¬i
¬h

Let h denote “I am healthy”

m ∧ v
5

⇔ ¬w ∧ i . . . (1)

⇒ ¬w . . . (2)

i ∧ (¬v → ¬i)

⇒ ¬(¬v)

MAS162 – Foundations of Discrete Maths
6

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

is a tautology P := (H1 ∧ H2 ∧ · · · ∧ Hn) → C
MAS162 – Foundations of Discrete Maths
7
MAS162 – Foundations of Discrete Maths
7

▶ 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.

MAS162 – Foundations of Discrete Maths
7

▶ 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.

MAS162 – Foundations of Discrete Maths
7

▶ 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.

MAS162 – Foundations of Discrete Maths
7

▶ 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.

Dr Amy Glen (Murdoch University) MAS162 – Foundations of Discrete Maths Lecture 26 – S1 2017 9
MAS162 – Foundations of Discrete Maths
10
MAS162 – Foundations of Discrete Maths
10

▶ 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.

MAS162 – Foundations of Discrete Maths
10

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

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”

¬i ℓ

→→→

s
¬s i
b
11
MAS162 – Foundations of Discrete Maths
12

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.

( b 1

1t)

0s
1 1
b
MAS162 – Foundations of Discrete Maths
12

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.

1

1 ( b
1
0¬

1t)

0 i 1 b

MAS162 – Foundations of Discrete Maths
12

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.

Dr Amy Glen (Murdoch University) MAS162 – Foundations of Discrete Maths Lecture 26 – S1 2017 12

Test the validity of the following inference. If it is valid, give a proof using the rules of inference, and if it is invalid, give a counterexample.

p
¬q
p

¬r
q

MAS162 – Foundations of Discrete Maths
13

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.

1q
MAS162 – Foundations of Discrete Maths
14

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 . . .

0q

∴ 0r

▶ 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.

MAS162 – Foundations of Discrete Maths
14
Copyright © 2009-2023 UrgentHomework.com, All right reserved.