1.在QC中，证明下列定理：

（1）⇁（∃x P（x）∧Q（y））→（∃x P（x）→⇁Q（y））；

（2）（∀x（⇁P（x）→Q（x））∧∀x⇁Q（x））→P（y）；

（3）∀x（P（x）→Q（x））∧∀x（Q（x）→R（x））→（P（y）→R（y））；

（4）∀x（P（x）∨Q（x））∧（∀x⇁P（x））→∃x Q（x）；

（5）∀x（P（x）∨Q（x））∧（∀x⇁P（x））→∀x Q（x）；

（6）⇁∀x（P（x）∨Q（x））∧（∀x⇁P（x））→⇁∀x Q（x）.

2.在QC中证明下列定理：

（1）∀x（p∨P（x））→p∨∀x P（x）；

（2）p∨∀x P（x）→∀x（p∨P（x））；

（3）∀x（p∨P（x））↔p∨∀x P（x）；

（4）∀x（p∧P（x））→p∧∀x P（x）；

（5）p∧∀x P（x）→∀x（p∧P（x））；

（6）∀x（p∧P（x））↔p∧∀x P（x）；

（7）∀x（p→P（x））↔（p→∀x P（x））；

（8）∀x（P（x）→p）↔（∃x P（x）→p）；

（9）∃x（p→P（x））↔（p→∃x P（x））；

（10）∃x（P（x）→p）↔（∀x P（x）→p）；

（11）∃x（P（x）→p）↔（∀x P（x）→p）；

（12）∃x（p∨P（x））↔p∨∃x P（x）；

（13）∀x P（x）∧∃x Q（x）→∃x（P（x）∧Q（x））；

（14）∀x∀y（P（x，y）→Q（x，y））→（∀x∀y P（x，y）→∀x∀y Q（x，y））；

（15）∀x∃y（P（x，y）→Q（x，y））→（∃x∀y P（x，y）→∃x∃y Q（x，y））；(www.daowen.com)

（16）∀x∃y（P（x，y）→Q（x，y））→（∀x∀y P（x，y）→∀x∃y Q（x，y））.

3.谓词演算的求否定规则为：设α为一阶公式，其中→和↔不出现，α的否定式α-可用下面的方法直接求得：

（1）∨被代以∧，∧被代以∨；

（2）∀Δ被代以∃Δ，∃Δ被代以∀Δ；

（3）⇁π被代以π，⇁ρ（Δ1，Δ2，…，Δn）被代以ρ（Δ1，Δ2，…，Δn）；

（4）不出现于部分公式⇁π中的π被代以⇁π，不出现于部分公式⇁ρ中的ρ（Δ1，Δ2，…，Δn）被代以⇁ρ（Δ1，Δ2，…，Δn），其中Δ表示任意的x，y，…，ρ表示任意的谓词，并且，从α→β可得β-→α-，从α↔β，可得α-↔β-.

求下面公式的否定式：

①p∧⇁∀x∃y（P（x）∧Q（y））；

②∀x（P（x）↔Q（x））；

③∃x（P（x）∧∀y（⇁Q（y）→R（x，y）））；

④∀x P（x）→∀x Q（x）.

4.谓词演算的求对偶规则为：设α为一阶公式，其中→和↔不出现，α的对偶公式α*可用下面的方法求得：

（1）把∧和∨互换；

（2）把∀Δ和∃Δ互换；并且，从α→β可得β*→α*，从α↔β可得α*↔β*.

利用对偶规则证明下面的定理：

①∃x（P（x）∨Q（x））↔∃x P（x）∨∃x Q（x）；

②∀x（P（x）∧Q（x））↔∀x P（x）∧∀x Q（x）；

③∃x（p∧P（x））↔p∧∃x P（x）；

④∃x（p∨P（x））↔p∨∃x P（x）；

⑤∃x∃y R（x，y）↔∃y∃x R（x，y）；

⑥∃x R（x，y）→∃x∃y R（x，y）.