In: Computer Science
Use rules of inference to show that the hypotheses p → q, r → s, and ¬q ∨ ¬s implies ¬p ∨ ¬r
We want to show that,pq,r
s
and
q
s
implies
p
r.
Inorder to prove this hypothesis,we can simply uses conjunction and destructive dilemma.By using material implication which is a valid rule of replacement ,transpostion which is a valid rule of replacement and hypothetical syllogism which belongs to rule of inference can also used to prove this.Here we shows the proof to solve this hypotheses by this two way.
FIRST METHOD:
conjunction p
q
p
q
Destructive syllogism pq
r
s
q
s
p
r
The table below shows the steps to prove the given hypotheses.
1 | p![]() |
Given |
2 | r![]() |
Given |
3 | ![]() ![]() ![]() |
Given |
4 | (p![]() ![]() ![]() |
Conjunction on 1 and 2 |
5 | ![]() ![]() ![]() |
Destructive dilemma on 4 and 3 |
SECOND METHOD:
Material implication (pq)
(
p
q)
Transposition (pq)
(
q
p)
Hypothetical syllogism pq
qr
p
r
The table below shows the steps to prove the given hypotheses.
1 | p![]() |
Given |
2 | r![]() |
Given |
3 | ![]() ![]() ![]() |
Given |
4 | q![]() ![]() |
Material implication on 3 |
5 | ![]() ![]() ![]() |
Transposition rule on 2 |
6 | q![]() ![]() |
Hypothetical syllogism on 4 and 5 |
7 | p![]() ![]() |
Hypothetical syllogism on 1 and 6 |
8 | ![]() ![]() ![]() |
Material implication on 7 |