The problem goes as such: politicians never tell the truth and non politicians always tell the truth. A stranger meets 3 natives and asks the first of them "Are you a politician?" And he answers. The second native then reports that the first native denied being a politician. The third native says that the first native is a politician. How many of these 3 are politicians?
I'm essentially confused on how to solve this problem without knowing what the 1st native said.
On
Let's write $\;P(x)\;$ for "$\;x\;$ is a politician". We are told that, when $\;x\;$ says $\;\phi\;$, then $\;\phi\;$ is true if and only if $\;x\;$ is not a politician. That is, $$ \lnot P(x) \equiv \underline{\phi} $$ (where I've underlined $\;x\;$'s statement for clarity, this line does not have any formal meaning).
Naming the politicians $\;A,B,C\;$ in order, the second's statement translates to $$ \tag{1} \lnot P(B) \equiv \underline{(\lnot P(A) \equiv \underline{\lnot P(A)})} $$ Now simplify the right hand side, and the conclusion about $\;B\;$ is...?
For the third, we get $$ \lnot P(C) \equiv \underline{P(A)} $$ What does this tell us about the combination of $\;A\;$ and $\;C\;$?
Add up those sub-answers and you get your answer.
The nice thing about this style of proof is that there is no need for any case analysis, which (in my opinion) makes the argument clearer.
Case 1: No. 1 is a liar.
"Are you a liar?"
No. 1 think. "Hmm, I am but I better lie" and says "No, I'm not". That's a lie.
No. 2 says "No. 1 denied it". That's true.
No. 3 says "No. 1 is a liar". That's true.
You have one liar.
Case 2: No. 1 is not a liar.
"Are you a liar?"
No.1 thinks "No. I'm not and I better tell the truth" and says "No, I'm not". That's true.
No. 2 says "No. 1 denied it". That's true.
No. 3 says "No. 1 is a liar". That's a lie.
You have 1 liar.
So... You have one liar. Either 1 is a liar and 3 is a truther. Or 1 is a truther and 3 is a liar. 2 is definitely a truther.