xP(x)∨¬xQ(x)求前束范式过程
时间: 2023-08-10 07:04:41 浏览: 56
过程如下:
1. 将析取符号转化为蕴含符号:xP(x) ∨ ¬xQ(x) = ¬(xP(x)) → xQ(x)
2. 对于∀和∃量词,使用以下公式进行变换(其中P(x)和Q(x)是谓词,x是变量):
- ∃x(P(x) ∧ Q(x)) = P(y) ∧ Q(y) (y是新的代替x的变量)
- ∃x(P(x) ∨ Q(x)) = P(y) ∨ Q(y) (y是新的代替x的变量)
- ∀x(P(x) ∧ Q(x)) = P(x) ∧ Q(x)
- ∀x(P(x) ∨ Q(x)) = P(x) ∨ Q(x)
3. 将公式变为前束范式(即量词出现在公式的最前面):
¬(xP(x)) → xQ(x) = ∀x(¬(xP(x)) → xQ(x)) (将变量x量化,使用全称量词)
= ∀x(¬xP(x) ∨ xQ(x)) (蕴含符号的否定是析取符号,应用De Morgan定律)
= ∀x(¬P(x) ∨ Q(x)) (去掉量词内的变量前缀x)
相关问题
(p→((¬r∧s)∨(r∧¬s)))∧(¬r∧q)∨(r∧¬q)∧(r→¬s)求主析取范式的详细过程
首先,我们需要将条件式转化为合取范式,即将它们转换为逻辑与的形式。具体步骤如下:
1. 将条件式中的蕴含符号转换为逻辑或和非运算的组合形式,即 p→q 转换为 ¬p∨q。
(p→((¬r∧s)∨(r∧¬s)))∧(¬r∧q)∨(r∧¬q)∧(r→¬s)
= (¬p∨((¬r∧s)∨(r∧¬s)))∧(¬r∧q)∨(r∧¬q)∧(¬r∨¬s)
2. 将条件式中的合取符号转换为逻辑或和非运算的组合形式,即 p∧q 转换为 ¬(¬p∨¬q)。
= ((¬¬p∧¬(¬r∧s)∧¬(r∧¬s))∨(¬¬p∧(¬r∧s)∨¬¬p∧(r∧¬s)))∧(¬¬r∨¬q)∨(r∧¬q)∧(¬¬r∨¬¬s)
3. 对条件式中的每个逻辑非运算符号应用德·摩根定律,并将条件式中的双重否定符号去除,即 ¬¬p 转换为 p。
= ((p∨(r∨¬s))∧(p∨(¬r∨s)))∧(r∨q)∧(¬r∨¬q)∧(r∨¬q)∧(¬r∨s)
4. 对条件式中的每个逻辑与运算符号应用分配律。
= ((p∧p)∨(p∧¬r)∨(p∧s)∨(r∧p)∨(r∧¬r)∨(r∧s))∧(r∨q)∧(¬r∨¬q)∧(r∨¬q)∧(¬r∨s)
5. 将条件式中的逻辑或运算符号转换为主析取范式,即将它们转换为逻辑或的形式。
= (p∧¬r∧s)∨(p∧r∧¬s)∨(r∧q)∨(¬r∧¬q∧r)∨(r∧¬q∧¬r)∨(¬r∧s)
因此,主析取范式为 (p∧¬r∧s)∨(p∧r∧¬s)∨(r∧q)∨(¬r∧¬q∧r)∨(r∧¬q∧¬r)∨(¬r∧s)。
求下列命题公式的主析取范式和主合取范式并写出过程,(1)(¬P∧Q)→R (2)¬ (P∨¬Q)∧(S→T)
对于问题,我可以回答。对于第一个命题公式,其主析取范式为 (¬P∨R)∨(¬Q∨R),主合取范式为 (P∧¬Q∧¬R)∨(P∧¬Q∧R)∨(P∧Q∧¬R)∨(Q∧¬R)。具体过程如下:
(1) (¬P∧Q)→R
= ¬(¬P∧Q)∨R
= (P∨¬Q)∨R
= ¬(P∨¬Q)→R
主析取范式为 (¬P∨R)∨(¬Q∨R)
主合取范式为 (P∧¬Q∧¬R)∨(P∧¬Q∧R)∨(P∧Q∧¬R)∨(Q∧¬R)
(2) ¬ (P∨¬Q)∧(S→T)
= (¬P∧Q)∧(S→T)
= (¬P∧Q∧¬S)∨(¬P∧Q∧T)∨(P∧Q∧¬S)∨(P∧Q∧T)
= (¬P∨Q∨T)∧(¬P∨Q∨¬S)∧(P∨Q∨T)∧(P∨Q∨¬S)
= (¬P∨Q∨T)∧(¬P∨Q∨¬S)∧(P∨Q∨T)∧(P∨Q∨¬S)∧(¬P∨Q)∧(¬Q∨¬S∨T)∧(Q∨¬S∨T)
主析取范式为 (¬P∨Q∨T)∧(¬P∨Q∨¬S)∧(P∨Q∨T)∧(P∨Q∨¬S)∧(¬P∨Q)∧(¬Q∨¬S∨T)∧(Q∨¬S∨T)
主合取范式为 (¬P∧¬Q∧¬S∧T)∨(¬P∧¬Q∧S∧¬T)∨(¬P∧Q∧¬S∧T)∨(¬P∧Q∧S∧¬T)∨(P∧¬Q∧¬S∧T)∨(P∧¬Q∧S∧¬T)∨(P∧Q∧¬S∧T)