Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying for an entrance exam. Now I am stuck on this question:

Suppose that P, Q are propositions such that "P or Q" is true. For each proposition (1), (2) and (3) which of the following is logically appropriate? "The proposition is true", "The proposition is false", "Our assumption is not sufficient to determine truth of the proposition". Answer with a short proof.
(1) "P and Q"
(2) "P implies Q"
(3) "'Not P' implies Q"

First I looked at the truth-tables and tried to find a connection somehow.
For (1) I think it is "not sufficient" because either P or Q could be false.
For (2) I think it is "false" because if P is true and Q is false there would be a contradiction.
For (3) I think it is "true" because the truth tables are the same.

Are my answers correct? If so, what would be a short proof for them? If not, where is my mistake?

I hope some knowledgeable people can help out. Best regards

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

As pointed out by others, it seems difficult to say what the question here means by "proof".

The following I hope helps you write explanations of your own.

For (1) I would say to suppose p true, and q false, which makes "p or q" true as required. Then, we also have "p and q" false. So, "p and q" might come as false, given "p or q" as true. But also, suppose p true and q true. Then we have "p or q" as true as required, and also "p and q" true. So, "p and q" might also come out true if "p or q" is true. So, "Our assumption is not sufficient to determine truth of the proposition" comes as most appropriate here.

For (2) suppose p true and q false. We then have "p or q" true, and "p implies q" false. But this doesn't make "p implies q" false, since we don't know the actually truth values of p and q. We only know "p or q" true. So, does there exist a case where "p or q" holds true, while "p implies q" also holds true? Well, suppose p true and q true. Again, we have "p or q" true, and now we also have "p implies q" true. So, as above, "p or q" is not sufficient to determine the truth of "p implies q".

Your answer for (3) seems to work well, I would guess, as long as you show the truth tables. That said, the entire truth tables seem a little more information than you actually need though (this isn't to say that writing the entire truth tables out would come as an incorrect "proof"). You only need to look at the rows of the truth tables where "p or q" holds true, and make sure that those rows also come out true for "'not p' implies q".

share|improve this answer
    
Thank you! Your explanation helped a lot. (2) became clear to me now and I think I can answer upcoming problems in a similar way. –  entrance_exam Sep 5 '11 at 8:59
add comment

Doesn't the exam specify what it means by a "proof"? Your remark on the first proposition is probably what along the lines of what would be required of you (assuming you are working with standard semantics of predicate logic e.t.c. which from the circumstances I think I can assume you are). As is suggested in another answer, and a remark on a somewhat embarrassing error in mine, you can apply the same reasoning for the second proposition, you since you can find two situations (both satisfying $P$ and $Q$), one where it is true and one where it is false. The answer would, thus, be that not information is given (more formally you would say that the statement is neither provable nor disprovable from your assumption $P$ and $Q$).

In the third case I suspect, as another answer has already pointed out, that stating that the truth tables are equivalent is probably what they want you to do. Such a proof is not a "formal proof" (that is not to say it isn't rigorous) in the technical sense of the word though, since it is a proof on the standard semantics of propositional logic, rather than a proof within some proof system.

So in case you are familiar with any of the usual formal proof system for propositional logic you can prove the third statement by applying or-elimination, basically meaning you split the assumption of $P$ or $Q$ into two cases, one where $P$ is true, and another where $Q$ is true.

In the first case you have a contradiction (since you have now assumed $\lnot P$ and $P$) which by the principle of explosion (anything follows from a contradiction) means you can conclude $Q$.

In the second case you can trivally conclude $Q$, since you assumed it. or-elimination now states that since you could conclude $Q$ from both these cases, you can conclude $Q$ from their disjunction (their disjunction meaning the statement $P$ or $Q$).

As I already said, unless they have said something about formal proofs somewhere I doubt this is what they expect, but I figured it might be worth noting for completeness :).

share|improve this answer
    
Your answer seems close, but what he wrote about (2) isn't quite correct as you suggest. –  Doug Spoonwood Aug 20 '11 at 13:58
    
You are quite right, I didn't read things properly and just read it as a question asking which propositions were provable from the assumption, I will correct this :) –  Tilo Wiklund Aug 20 '11 at 16:20
    
Thank you! The exam didn't specify what it exactly means by a proof. Thank you for explaining about general proof techniques. I wish I could mark 2 answers as accepted! I decided to pick the one who answered first and helped me but yours is also appreciated! –  entrance_exam Sep 5 '11 at 9:01
add comment

Surely your reasoning for (1) applies equally well for (2).

Truth tables seem to me to be as good as anything by way of a proof for (3). And I think what you've written for (1) also amounts to a proof.

share|improve this answer
1  
No, (2) isn't "false" as his answer says. –  Doug Spoonwood Aug 20 '11 at 13:58
1  
Sorry, your answer here actually is correct. Why can't I change me vote? His reasoning for (1) applies equally well for (2) making the assumption insufficient to determine anything about the proposition in those cases. I read Tilo's comment first, than uncarefully read yours, and since he referred to your comment I misread it as he did. My error and apologies. –  Doug Spoonwood Aug 20 '11 at 14:17
    
@Doug, I think the rules are that you can't change a vote until there has been a change (that is, an edit) in the answer. Don't worry about it, just resolve to read with care. –  Gerry Myerson Aug 20 '11 at 23:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.