1.设公式α为：∀x（P（x）∨p）→∀x P（x）∨p.证明：α是逻辑有效的.问：经过如下的代入得到的公式是否还是逻辑有效的？

（1）以（p∧γ）代换p，得公式

∀x（P（x）∨（p∧γ））→∀x P（x）∨（p∧γ）；

（2）以∃y P（y）代换p，得公式

∀x（P（x）∨∃y P（y））→∀x P（x）∨∃y P（y）；

（3）以∃x P（x）代换p，得公式

∀x（P（x）∨∃x P（x））→∀x P（x）∨∃x P（x）；

（4）以P（y）代换p，得公式

∀x（P（x）∨P（y））→∀x P（x）∨P（y）；

（5）以Q（x）代换p，得公式

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

2.求下面公式联立代入的结果：

（1）（P（v1）∨R（v0，v2））（v2/v1，v1/v0，v0/v2）；

（2）（∀v0 R（v0，v1，v2））（v4/v0，v2/v1）；

（3）（∃v0 R（v0，v1，v2））（v1/v0，v0/v2，v2/v1）；(www.daowen.com)

（4）（∀v0 P（v0，v3）∨∃v1 R（v0，v1，v2））（v4/v0，v2/v1，v1/v2，v3/v3）.

3.设公式α为：∀x∃y R（x，y）→∃y R（z，y），用个体变项y代换α中的个体变项z，结果公式α（y/z）为：

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

问：代入后的公式是否逻辑有效？

4.证明逻辑等值的性质（1）～（4）.

5.求下列公式的前束范式：

（1）∀z（⇁⇁∀y P（y，z）→⇁⇁∃x Q（x，y，z））；

（2）∀y（P（y）→⇁（∀x Q（x，y）→∀z⇁P（z）））；

（3）P（x）∨⇁∀y P（y）；

（4）∃x P（x，y，z）↔∀y Q（x，y，z）；

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

（6）∃x∀y Q（x，y）→∀y∃x Q（x，y）；

（7）∃x（p→P（x））→（p→∃x P（x））；

（8）∀x∃y（（P（x）→Q（y））→R（z））→（∃x∀z（（P（y）→Q（x））→R（z）））.