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.

A question has appeared in our Informatics Olympiad which there is a lot of discussion over it. the problem states:

Below are 5 statements. At most how many of them can be true together?

a) if b is true then this statement is false.

b) if number of the true statements is greater than $2$, then one of them is c.

c) at least one of a and d is false.

d) b and c are both true or both false.

e) b is true or false.

many say this number is $3$, by statements a,d,e being true and the rest false, and many other say this number is $4$, a being false and the rest being true. what is your opinion? which group say the truth?

EDIT. I made a mistake and typed ''wrong'' in statement c instead of ''false''. now it's correct.

share|improve this question
    
If b is true and a is false, then a is true; you cannot have a false and b true, so "many other" is wrong. –  Arturo Magidin Feb 27 '12 at 4:45
    
statement a is self-refential. Normaly in propositional logic you do not admit self-reference because it leads to antinomies. –  magma Feb 27 '12 at 11:43
    
when and where will it be possible to see the official answer to this question? –  magma Feb 27 '12 at 13:21
    
@magma: I doubt if there will be any official solution, since it appeared in a multiple choice exam, but if there was one, I'll inform you. –  Goodarz Mehr Feb 27 '12 at 17:02
add comment

2 Answers 2

a cannot be false: for a to be false you need b to be true and a to not be false; that is, b and a must both be true. That means that $$\mathbf{a}\text{ false}\Rightarrow \mathbf{a}\text{ true}.$$ That means that a will be true, since $(\neg P\to P)\to P$ is a tautology.

In particular, it is impossible for a to be false and all other statements to be true.

Also, e is always true. So at least a and e are always true.

Corrected (misread b in my first pass).

Since a is true, by contrapositive it follows that b is false. So we must have that there are more than two true statements, but c is false. Since b and c are both false, then d is true (which is our third true statement).

So the answer is 3 statements.


No longer applicable:

If, as magma suggests, "wrong" should not be taken as a synonym for "false", but rather as saying something like "ill-formed", "self-referential", "cannot be assigned a truth-value", etc., then you could make a case for saying that a is self-referential, hence "wrong", while the other four statements are true. But if that is the case, then the answer you quote, "a false and the rest true" would also be incorrect, since the conclusion is not that "a is false", but rather that "a is wrong".

share|improve this answer
1  
The fact that at least a and e are true doesn’t make the antecedent of b true: $2\not>2$. However, you know from the truth of a that b is false and hence that its antecedent must be true. –  Brian M. Scott Feb 27 '12 at 5:07
    
@Brian: Oops; misread that. Thanks. –  Arturo Magidin Feb 27 '12 at 5:10
    
@Arturo a cannot be true. If a is true, then the consequent in a ("this statement is false") must be true, so a must be false ("this" refers to a). At the same time a cannot be false, by a similar reasoning. So a is neither true nor false, it is wrong (self-referential, ill formatted). Please see my answer. –  magma Feb 27 '12 at 13:14
    
@magma: An implication is true when either the consequent is true, or the antecedent is false. You are asserting, inter alia, that for the implication in a to be true, the consequent must be true; that does not follow. –  Arturo Magidin Feb 27 '12 at 15:57
    
I'v edited my post. thanks. –  Goodarz Mehr Feb 27 '12 at 17:04
show 5 more comments

statement a is self-referential. Normally in propositional logic you do not admit self-reference because it leads to antinomies. The statement "this statement is false" is neither true nor false. It is wrong. So c is true (since a is wrong). Since c is true, the consequent in b ("one of them is c") is true, so b is true. So d is also true and.... e is true.

Answer: b,c,d and e are true, a is wrong

Please note: a is not false, it is wrong. This is what the judges wanted the competitors to realize, as you see in the wording of c

share|improve this answer
    
There are two problems with this. The first is that, while you are correct that this doesn't have a direct formulation into higher-order logic, that does not mean we cannot make sense of it as is. Also, it's clear enough how to formulate it indirectly in HOL. The second problem is that "wrong" is a synonym for false -- I have never seen it used to refer to things like "ill-formed" or "not a proposition". To the contrary, the phrase I hear for similar things is "not even wrong". –  Hurkyl Feb 27 '12 at 12:30
    
your comment is "not even wrong"."Wrong" is not a synonym for false.At least not in the context of this question.Don't you see that all statements use the words true and false except c.Do you think it is by chance or for literary reasons?.Of course not.The examiners distinguish true, false and wrong (in the sense of ill-formed).You may learn something about self-reference here: en.wikipedia.org/wiki/Self-reference but I would recommend above all Quine's methods of logic where he deals explicitly with these kind of sentences. amazon.com/Methods-Logic-W-V-Quine/dp/0674571762 –  magma Feb 27 '12 at 13:04
2  
@magma: Apparently, the reason (c) used "wrong" and the rest used "false" was that the OP mistakenly used a different word when translating from Persian; he reports that the same persian word was used in the original in all the parts, so that suggests that you were misled by this inadvertent change to put a lot of meaning into what was indeed merely accidental. –  Arturo Magidin Feb 27 '12 at 18:00
    
@magma: Yes, I know about self reference. But it's easy enough to encode the problem in ordinary first-order logic. While you do not have self-reference, the notion of implicit definition works just fine in logic as it does anywhere else. Or, you can just encode the whole thing as a predicate on five variables: $(a \Leftrightarrow (b \implies \not a)) \wedge \cdots$ –  Hurkyl Feb 28 '12 at 10:01
    
@Hurkyl in light of the new/revised statement of the problem - as supplied by the OP - I concur with you. I am working on a modified answer. –  magma Feb 28 '12 at 10:21
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.