How to prove that a function is not pseudorandom? I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I'm struggling with the exercies which ask for proofs, like the following one: 


  Let G(k) be a PRG with |k| = n, and G'(k) the output of G(k) truncated to the first n bits. Prove that $F_k(x) = G'(k) \oplus x$ is not pseudorandom. 


The only thing I can say is that $F_k()$ has a very specific structure, not chosen randomly from $1/2^n$.

Any hints?
Before answering the actual question, I will offer some general advice.


It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this case it has one which is conceptually identical to the one you have given here (where $G'(k)$ is replaced by $k$).
It is crucial to know and understand your definitions. Here, you want to show that a certain family of functions is not pseudorandom (i.e., does not satisfy the definition of a pseudorandom family of functions), but it is not clear that you understand what this means (you do not articulate it in your question). You must understand this definition if you want to be able to show that a certain construction does or does not satisfy it.
Broadly speaking, you seem to lack what is commonly known as mathematical maturity, which is not knowledge of any specific mathematics, but rather the ability to see how to connect the dots in a mathematical argument between the hypotheses and the conclusion. Indeed, a telltale sign of someone who is not "mathematically mature" is that they balk at the mere sight of the word "proof" and seem unable to make any progress beyond stating the hypotheses. Unfortunately, cryptography is not the best of places to "get your feet wet" in writing proofs because it is a very complicated business (most results in cryptography aim to prove that it is impossible to do something), and you can feel overwhelmed pretty quickly. For this reason, abstract algebra or real analysis are better training grounds, even if you have no intention of studying them for their on sake.




To turn to the main question, we first need to know and undertand the definition of a pseudorandom family of functions. We consider a function $F$ which maps each pair of strings $(k,x)$ of equal length to a third string $y$ of the same length as $k$ and $x$. For any string $k$ of length $n$, we note $F_k$ the function which maps the $n$-bit string $x$ to the $n$-bit string $y$ (i.e., $F_k(x) = F(k,x)$. The string $k$ is called the key. I only state the definition of a pseudorandom function without a lengthy discussion (which can be found in the book).


  The function $F$ defined above is pseudorandom if it satisfies the following two conditions.
  
  
  Easy to compute. There is a deterministic polynomial-time algorithm $C$ such that $C(k,x) = F_k(x)$ for any strings $k$ and $x$ of equal length.
  Pseudorandom. For every probabilistic polynomial-time algorithm $D$, every polynomial $p$ and all sufficiently large $n$, we have
  $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] -
          \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right|
&lt; \frac{1}{p(n)}.$$
  


My notation is as follows:


$\{0,1\}^n$ is the set of all strings of length $n$.
$\mathrm{Func}_n$ is the set of all functions from $\{0,1\}^n$ to itself.
$k \gets X$, where $X$ is a finite set, means that $k$ is randomly and uniformly chosen from $X$.
$D^f$ denotes the algorithm $D$ when given oracle access to the function $f$. That is, $D^f$ can obtain $f(x)$, for any $x$ of its choice, at the cost of only one operation.
$\mathrm{Pr}[A : P(x)]$ denotes the probability that $P(x)$ holds after the execution of $A$.


Here, you want to prove that the given function is not pseudorandom, meaning that it does not satisfy the definition above. In other words, that it satisfies its logical negation. Since the logical negation of the definition is not entirely trivial, it is best stated explicitly. Typically, the "easy to compute" condition will be satisfied, so we only give the negation of the pseudorandomness condition.


  A function $F$ as above which is easy to compute is not pseudorandom if there exists a probabilistic polynomial-time algorithm $D$ and a polynomial $p$ such that for infinitely many $n$, we have
  $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] -
          \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right|
\ge \frac{1}{p(n)}.$$


We can finally define the algorithm $D$ (we denote by $\mathcal{O}$ the function computed by the oracle). On input $1^n$, it proceeds as follows.


Compute $y_0 = \mathcal{O}(0^n)$.
Compute $y_1 = \mathcal{O}(1^n)$.
If $y_0 \oplus y_1 = 1^n$, output $1$. Otherwise, output $0$.


We must determine the probability that $D$ outputs $1$ in each case: when $\mathcal{O}$ is $F_k$ for a uniformly chosen $k$, and when it is a uniformly chosen $f$.


In the first case, regardless of what $k$ is, we have $y_0 = G'(k) \oplus 0^n = G'(K)$ and $y_1 = G'(K) \oplus 1^n$. Hence we have $y_0 \oplus y_1 = G'(k) \oplus G'(k) \oplus 1^n = 1^n$, and $D$ ouputs $1$ with probability $1$.
For the second case, we note that $D$ outputs $1$ if and only if $y_1 = y_0 \oplus 1^n$. If $f$ is a totally random function, $y_1$ is chosen among all $2^n$ strings of length $n$ uniformly and independently of $y_0$, and so it will equal $y_0 \oplus 1^n$ with probability $1/2^n$.


Hence finally we see that for all $n$, the value of the big probability expression in the definition equals $1-\frac{1}{2^n}$. If $n &gt; 0$ this is at least $\frac{1}{2}$, and so we can take $p$ to be the constant polynomial $2$.