Prove that any formula built up from $¬$ and $→$ in which no propositional variable occurs more than once cannot be a tautology. 
Prove that any formula built up from $¬$ and $→$ in which no propositional
  variable occurs more than once cannot be a tautology.

If repeating propositional variable is allowed, then a tautology with a conditional would be easy; for $\psi\to\psi$ it will always be true regardless of $v(\psi)$. So if the question only concerns formulae built from $\to$ I can easily make up a truth assignment for, say, $\psi\to\theta$ such that it is false.
But the question concerns formulae built with both $\lnot$ and $\to$, and I cannot even think of a scenario where even repeating propositional variable would make any such formula a tautology. It seems natural to think that any such formula with no repeating propositional variable must be contingent, and cannot be a tautology. 
For example, say, $\lnot(\psi\to\theta)$, if $v(\psi)$=F and $v(\theta)$=T, then the formula would be false. This would already serve as a counterexample to the opposite of the claim, i.e. 'that any formula built up from $¬$ and $→$ in which no propositional variable occurs more than once CAN be a tautology.'
In other words, the question seems too easy. I must have misunderstood the question somewhere. Could anyone please help?
 A: To prove this claim, you actually want to prove the following stronger claim:
Claim Any formula built up from $¬$ and $→$ in which no propositional
variable occurs more than once is a contingent statement
(a  statement $\phi$ is contingent iff there exists some valuation $v_1$ such that $v_1(\phi)=True$ as well as some valuation $v_2$ such that $v_2(\phi)=False$)
This we can prove by structural induction:
Base: Suppose $\phi$ is an atomic statement. Since we can set any atomic statement to True by some valuation, and to False by some other valuation, $\phi$ is contingent. Check!
Step: Take some $\phi$ that is built up from $¬$ and $→$ and in which no propositional variable occurs more than once. If $\phi$ is not an atomic statement, then there are only two options:
I. $\phi = \neg \psi$ for some $\psi$. Given that $\phi$ is built up from $¬$ and $→$ and in which no propositional variable occurs more than once, it follows that $\psi$ is also built up from $¬$ and $→$ and in which no propositional variable occurs more than once. We can therefore apply our  inductive hypothesis that $\psi$ is a contingent statement. But, if $\psi$ is contingent, then clearly $\neg \psi$ is contingent as well, and hence $\phi$ is contingent.
II. $\phi = \phi_1 \rightarrow \phi_2$. Given that $\phi$ is built up from $¬$ and $→$ and in which no propositional variable occurs more than once, it follows that $\phi_1$ and $\phi_2$ are also built up from $¬$ and $→$ and in which no propositional variable occurs more than once. So we can apply our inductive hypothesis to $\phi_1$ and $\phi_2$, and conclude that they are both contingent.  In particular, there is some valuation $v_1$ such that $v_1(\phi_1)=True$, some valuation $v_2$ such that $v_2(\phi_1)=False$, some valuation $v_3$ such that $v_3(\phi_2)=True$, some valuation $v_4$ such that $v_4(\phi_2)=False$. 
Since no propositional variable occurs more than once in $\phi$, it follows that $\phi_1$ and $\phi_2$ do not share any variables. Hence, we can combine valuations $v_1$ and $v_3$ into one valuation $v_1 \cup v_3$, and it will be true that $$v_1 \cup v_3(\phi) = v_1 \cup v_3(\phi_1 \rightarrow \phi_2) = v_1 \cup v_3(\phi_1) \rightarrow v_1 \cup v_3(\phi_2) = True \rightarrow True = True$$
Likewise, $$v_1 \cup v_4(\phi) = v_1 \cup v_4(\phi_1 \rightarrow \phi_2) = v_1 \cup v_4(\phi_1) \rightarrow v_1 \cup v_4(\phi_2) = True \rightarrow False = False$$
Hence, $\phi$ is contingent.
This concludes the structural inductive proof of the Claim, and from this claim, your original statement to be proven immediately follows, for any statement that is a contingency is not a tautology.
A: First, to address your confusion, this is about negation and "strong negation". The negation of the statement "every googa is a plumbus" is "there is a googa which is not a plumbus". The "strong negation" would be "there is no googa which is a plumbus".
Here you made the switch from "every such and such sentence cannot be a tautology" to "every such and such sentence is a tautology". Of course, you contradicted the strong negation, the opposite if you will, but this is not a proof of the original statement.

Think of it this way, if $\varphi$ and $\psi$ are two propositions that have a disjoint set of propositional variables, then any assignment allows you to treat $\varphi$ and $\psi$ as a single propositional variable. Since their truth value is completely independent of one another.
This means that you can prove by induction on the structure of the proposition, that this is indeed the case.
A: I'll give you part of the algorithm, and see if you can fill in the $\dots$ :
$$F(E) = \begin{cases} 
\text{if } E \text{ is of the form } \ulcorner A \to B \lrcorner & \text{return } G(A) \cup F(B) \\
\text{if } E \text{ is of the form } \ulcorner \lnot A \lrcorner & \text{return } \dots \\
\text{if } E \text{ is a propositional variable } \ulcorner A \lrcorner & \text{return } \{\ulcorner A \lrcorner \text{ as False}\} \\
\end{cases}$$
$$G(E) = \begin{cases} 
\text{if } E \text{ is of the form } \ulcorner A \to B \lrcorner & \text{return } \dots \\
\text{if } E \text{ is of the form } \ulcorner \lnot A \lrcorner & \text{return } \dots \\
\text{if } E \text{ is a propositional variable } \ulcorner A \lrcorner & \text{return } \{\ulcorner A \lrcorner \text{ as True}\} \\
\end{cases}$$
Fill in the dots as necessary so that the variable assignment $F(E)$ makes $E$ false.
