If $p \to q$ and if $r \to s$, can we say that if $p \land r$ then $q \land s$?
$p,q,r,s$ are logical statements. How can I prove it?
Asked
Active
Viewed 80 times
1
-
Have you tried building truth tables for the two and comparing? – Oct 29 '16 at 18:52
-
yes :), but this is the only way? i mean in this case there is 2^4 combination of true and false for each statement, i worry about the generalization of this thing because of this i am searching another way – Yassin Rany Oct 29 '16 at 18:56
-
As far as I'm aware, that is the only way to do it, but hopefully someone else can comment on that. As for the 2⁴ combinations, that is not that big of a number; you can easily build such a table in half a piece of paper. However, I don't understand your worries, so perhaps you could restate the last few words of your last sentence, please? Also - if you aren't convinced, try to plug some specific statements for p, q, r and s and see how it unfolds for each implication. – Oct 29 '16 at 19:05
-
Thank you for the help. I meant with the last sentence if i need to prove it to 4 propositions for example, then there are 2^8 possibilities that should be analized, this was my worry haha,what we do then? we can easy reach one millions of cases... – Yassin Rany Oct 30 '16 at 19:19
3 Answers
2
In the worst case scenario, you unfortunately have $2^n$ cases to consider, no matter what method you use. But, here is a method that, on average, will be quicker than the full truth table method: the short truth table method.
In the short truth table method, you simply try and consider what it would take for the implying statements to be true, and the implied statement to be false. Put a different way: you try and come up with a counterexample to the argument.
In this case, let's first focus on the implied statement. For $(p \wedge r) \rightarrow (q \wedge s)$ to be false, $p \wedge r$ needs to be true, and $q \wedge s$ false. So, $p$ and $r$ are both true, and $q$ and $s$ are not both true.
Now let's focus on the implying statement $(p \rightarrow q) \wedge (r \rightarrow s)$. For this to be true, you need $p \rightarrow q$ to be true as well as $r \rightarrow s$. Since we already knew that $p$ had to be true in order to get our counterexample, that means that $q$ has to be true as well given the first conditional, and given that $r$ needed to be true, the second conditional forces $s$ to be true as well.
But wait! Now we have that $q$ and $s$ are both true, and yet earlier we saw they couldn't both be true. So, we have reached a contradiction! From what? From the assumption that we could make the implying statement true and the implied statement false (or: from the asumption that there is a counterexample to the argument). So: there is no counterexample possible. So, the argument is indeed valid.
So, the whole idea behind the short truth-table method is that you immediately try to generate the kind of row that you would nomally be looking for in a full truth table to obtain you answer, and often you can do this much more quickly than doing the whiole truth table.
Unfortunately, sometimes you get stuck when using this method, and nothing gets forced. So then you will have to consider multiple ways to make certain statements true or false. And that is exactly what the tree method does ... But that is for another day.
Bram28
- 100,612
- 6
- 70
- 118
2
The premises are
$$p \to q \qquad \qquad \qquad r \to s$$
Assume $p \land r$. Use conjunction elimination twice, then use modus ponens twice, and then use conjunction introduction once. Lastly, using implication introduction, we conclude
$$p \land r \to q \land s$$
1
We only need to check when the $p$ and $r$ is true, as otherwise the implication is trivially true. When $p$ and $r$ is true that means that both $p$ and $r$ are true (separately). But using the condition we have that this implies that both $q$ and $s$ are true (separately). So we have that $q$ and $s$ is true. Therefore the implication $p \text{ and } r \implies q \text{ and } s$ is true.
Stefan4024
- 35,843