※間違い等ありましたらコメント頂けると助かります.
タイトルのような命題の証明を背理法で考える際に混乱しまくっていたので, 同じ事で悩む人々のために共有しようと思います. なお基本的に同じ操作ですので, ここでは∃は扱わずに∀のみを扱います.
①:∀x[P(x)→Q(x)]を背理法で示す
ここで, xはある対象領域D上の変数です. また, P(x), Q(x)はそれぞれ, Dから{真, 偽}への写像で、命題関数もしくは述語と言います. 例えば, P(a)やQ(b)はそれぞれ「aはPである」「bはQである」という命題を意味し, それぞれ真か偽のどちらかの値をとります. これらは, 命題を抽象的に表すための記号だと考えてください.
背理法である命題を示すには, 示したい命題の否定をとって矛盾を導く訳ですが, 上の命題の否定はどうなるでしょうか.
一般に（命題論理における）任意の命題P, Qについて, P→Qという命題は¬P∨Qという命題と同値です（真理値表を書いてみましょう. 同じ真理値の振り分けになるはずです. 厳密な証明は参考文献1を参照）. よって上の命題は
∀x[¬P(x)∨Q(x)]
と置き換えられます（ここ少しごまかしがあります）（同値な命題が置き換え可能である事は, 置換定理によって保証されます. 参考文献1参照）.
この命題の否定を取ると, 二重否定の法則およびDe Morganの法則より
∃x[P(x)∧¬Q(x)]
となります.
よって, P(x)が真かつ¬Q(x)が真であるようなxが存在する事を仮定して矛盾を導けばよいという事になります.
注意すべきは,「P(x)が真であるxを任意にとって, かつ¬Q(x)を仮定し矛盾を導く」という方針は誤りとはいかないまでも不正確だという事です. 私見ですが P(x)が真かつ¬Q(x)が真であるxをきちんと取れる保証がない事が一つの理由でしょう（実際, 示したい命題が真であれば, そうしたxは存在しません）. そもそもそうしたxが存在しなければ, それ以降の議論は無意味なものになってしまいます（空集合に対する議論になってしまいます）.
なお, 「P(x)が真かつ¬Q(x)が真であるようなxが存在する事を仮定して, P(x)であるxを任意にとり, かつ¬Q(x)を仮定し矛盾を導く」という方針は全く問題ありません.
②:∀xP(x)→Qを背理法で示す
ではこの命題はどうでしょうか. ∀xという束縛がP(x)にしかかかっていない事に注意してください. よく見るとこの命題は, P→Qという命題論理における命題と実質的に変わらない事になります（Pを∀xP(x)と置けばよいのです）.
P→Qという命題は¬P∨Qという命題と同値でしたから, この命題は
¬[∀xP(x)]∨Q
と同値であり, その否定は
∀xP(x)∧¬Q
となります.
よって, すべてのxについてP(x)が真であると仮定し, さらに¬Qが真であると仮定して矛盾を導くことになります. ①の場合とよく見比べてみましょう. ∀が残されている点に注意してください. ∀がどこまで束縛しているかで, 用いるべき仮定が大きく異なります.
③: P→∀xQ(x)を背理法で示す
そろそろ慣れてきたでしょうか. ∀xという束縛はQ(x)にしかかかっていません. この命題は, 命題論理におけるP→Qという命題のQを∀xQ(x)としたものに他なりません.
よってこの命題は
¬P∨∀xQ(x)
と同値であり, その否定は
P∧∃x[¬Q(x)]
となります.
よって, Pが真と仮定し, さらに¬Q(x)が真であるようなxが存在する事を仮定して矛盾を導きます.
④: ∀x[P(x)]→∀y[Q(y)]を背理法で示す
ここで, yはある対象領域D'上の変数です. ∀x[P(x)]→∀x[Q(x)]という命題は, 上の命題においてD=D'とした特別な場合に対応します.
さて, この命題はP→QのPを∀xP(x), またQを∀yQ(y)とした命題に他なりません.
よって, この命題は
¬[∀xP(x)] ∨ ∀yQ(y)
と同値であり, その否定は
∀xP(x) ∧ ∃y[¬Q(y)]
となります. よって, すべてのxについてP(x)が真であると仮定し, かつ¬Q(y)が真であるyが存在する事を仮定して矛盾を導きます.
おわりに
重要な事は, 自分の示したい命題が, ①から④のどれに対応するのか正確に把握する事です（当たり前ですが）. さもなければ, 間違いに気づかぬまま「証明のように見える何か」を書いて満足してしまう事になります.
ただし, 実際の命題はここで扱ったような抽象化された命題よりも複雑ですし, 背理法を使おうとすると訳分からなくなる事が多いです（実際訳分からなくなったのでここで整理しました）. 身もふたもないのですが, 背理法を使わずに証明が書けるならばそれに越したことはなく, 背理法という高等な技術はなるべく使わないようにするのが現実的だと思います.
参考文献
1. 前原昭二『記号論理入門（新装版）』日本評論社, 2005.
2. 前原昭二『復刊 数理論理学序説』共立出版株式会社, 2010.
