Week 5 Problems

标签：Week land 等值 neg Problems lor 演算 rightarrow

T5

判断对错：任意命题合式公式可以等价转化为复杂度不超过二的形式

T6

(2)今有一命题逻辑合式公式\(F_2\)为

\[(P\rightarrow R)\rightarrow ((Q\rightarrow R) \rightarrow (P\lor Q)\land \neg R) \]

根据Week1T1(1)中真值表写出\(F_2\)的主析取范式与主合取范式

T7

设命题逻辑合式公式\(F\)中有\(n\)个命题逻辑变量、\(m\)个联结词，

试设计一个时间复杂度为\(\mathcal O\big(2^n(n+m-1)\big)\)的算法统计\(F\)的

1. 主析取范式中有几个极小项

2. 主合取范式中有几个极大项

写出伪代码即可

写在等值演算题目前

1. 等值演算应该使用\(\Leftrightarrow\)连接前后两步，不应该使用\(=\)连接，更不应该不连接。尽管课本第一章提到可以使用\(=\)代替\(\Leftrightarrow\)，但这样做容易造成与指派函数运算的概念混淆，因此不推荐这样做。

2. 有先后顺序的两步等值演算不能二合一跳步骤，否则无法区分你究竟是没写步骤还是推到一半不会了索性写个结论装样子。

3. \(\lor\)先于\(\land\)计算时要加括号。

T8

使用等值演算把

\[(Q\rightarrow R)\rightarrow ((Q\rightarrow \neg R)\rightarrow \neg Q ) \]

等价转化到

\[Q\rightarrow (R\rightarrow Q ) \]

T9

使用等值演算证明\((P\lor \neg Q)\land (P \lor Q) \land (\neg P \lor \neg Q) \Leftrightarrow \neg(\neg P \lor Q)\)

T10

使用等值演算证明公式 \((P\rightarrow Q) \land (Q\rightarrow R) \land \neg(P\rightarrow R)\) 是永假式

Hint.

可能有同学在化简\((P\lor \neg Q) \land Q\)型中间结果时，会「在跳步骤的过程中」发生错误。

T11

使用等值演算证明\(P\rightarrow (Q \rightarrow P) \Leftrightarrow \neg P \rightarrow (P\rightarrow Q)\)

标签：Week,land,等值,neg,Problems,lor,演算,rightarrow
From： https://www.cnblogs.com/fallqs/p/18096289