逻辑和证明--命题等价式

发布时间:2019-07-15 作者:大扑棱蛾子 阅读次数:
版权声明:未经允许不得转载至微信公众号,转载至个人博客请注明出处。 阅读原文

命题等价式

一个真值永远是真的符合命题(无论其中出现的命题变元的真值时什么),称为永真式(tautology),也称为重言式。一个真值永远为假的复合命题称为矛盾式(contradiction)。既不是永真式又不是矛盾式的复合命题称为可能式(contingency)

pp ¬p\lnot p p¬pp\lor \lnot p p¬pp\land \lnot p
TT FF TT FF
FF TT TT FF

逻辑等价式

逻辑等价
如果pqp\harr{q}是永真式,则复合命题p\:p\:q\:q\:称为是逻辑等价的。用记号pqp\equiv{q}表示p\:p\:q\:q\:是逻辑等价的。

符号\equiv不是逻辑联结词,pqp\equiv{q}不是一个复合命题,而是代表“pqp\harr{q}是永真式”这一语句。有时候用符号\Harr来代替\equiv表示逻辑等价。

复合命题p\:p\:q\:q\:是等价的当且仅当对应他们的真值的两列完全一致。

德·摩根律

  • ¬(pq)=¬p¬\lnot(p\land q) = \lnot{p}\lor\lnot
  • ¬(pq)=¬p¬\lnot(p\lor q) = \lnot{p}\land\lnot

逻辑等价式

等价式1 等价式2 名称
pTpp\land T\equiv p pFpp\lor F \equiv p 恒等律
pTTp\lor T\equiv T pFFp\land F\equiv F 支配律
pppp\lor p\equiv p pppp\land p \equiv p 幂等律
¬(¬p)p\lnot(\lnot p)\equiv p 双重否定律
pqqpp\lor q\equiv q\lor p pqqpp\land q\equiv q\land p 交换律
(pq)rq(pr)(p\lor{q})\lor r\equiv q\lor(p\lor r) (pq)rq(pr)(p\land q)\land r\equiv q\land(p\land r) 结合律
p(qr)(pq)(pr)p\lor(q\land{r})\equiv(p\lor{q})\land(p\lor{r}) p(qr)(pq)(pr)p\land(q\lor r)\equiv(p\land q)\lor(p\land r) 分配律
¬(pq)¬p¬q\lnot(p\land q)\equiv\lnot p\lor\lnot q ¬(pq)¬p¬q\lnot(p\lor q)\equiv\lnot p\land\lnot q 德·摩根律
p(pq)pp\lor(p\land q)\equiv p p(pq)pp\land(p\lor q)\equiv p 吸收律
p¬pTp\lor\lnot p\equiv T p¬pFp\land\lnot p\equiv F 否定律

条件命题的逻辑等价式

  • pq¬pqp\to q \equiv \lnot p \lor q
  • pq¬q¬pp\to q \equiv \lnot q \to \lnot p
  • pq¬pqp\lor{q}\equiv\lnot{p}\to q
  • pq¬(p¬q)p\land{q}\equiv\lnot({p}\to\lnot{q})
  • ¬(pq)p¬q\lnot(p \to q)\equiv p \land\lnot q
  • (pq)(pr)p(qr)(p\to{q})\land(p\to{r})\equiv{p\to(q\land{r})}
  • (pq)(pr)p(qr)(p\to{q})\lor(p\to{r})\equiv{p\to(q\lor{r})}
  • (pr)(qr)pqr(p\to{r})\land(q\to{r})\equiv{p\lor{q}}\to r
  • (pr)(qr)pqr(p\to{r})\lor(q\to{r})\equiv{p\land{q}}\to r

双条件命题的逻辑等价式

  • pq(pq)(qp)p\harr{q}\equiv(p\to{q})\land(q\to{p})
  • pq¬p¬qp\harr{q}\equiv\lnot{p}\harr\lnot q
  • pq(pq)(¬p¬q)p\harr{q}\equiv(p\land{q})\lor(\lnot{p}\land\lnot{q})
  • ¬(pq)p¬q\lnot(p\harr{q})\equiv p\harr\lnot q

德·摩根律可以扩展为

¬(p1p2pn)=¬p1¬p2¬pn¬(p1p2pn)=¬p1¬p2¬pn\lnot(p_1\lor p_2\lor \dots \lor p_n)=\lnot{p_1} \land \lnot{p_2}\land\dots\land\lnot{p_n}\\ \lnot(p_1\land p_2\land \dots \land p_n)=\lnot{p_1} \lor \lnot{p_2}\lor\dots\lor\lnot{p_n}\\

逻辑等价式证明

分配率: p(qr)(pq)(pr)p\lor(q\land{r})\equiv(p\lor{q})\land(p\lor{r})\:p(qr)(pq)(pr)\:p\land(q\lor{r})\equiv(p\land{q})\lor(p\land{r})

pp qq rr qrq\land r p(qr)p\lor(q\land{r}) (pq)(pr)(p\lor{q})\land(p\lor{r}) qq\lor p(qr)p\land(q\lor{r}) (pq)(pr)(p\land{q})\lor(p\land{r})
TT TT TT TT TT TT=TT\land{T}=T TT TT TT=TT\lor{T}=T
TT TT FF FF TT TT=TT\land{T}=T TT TT TF=TT\lor{F}=T
TT FF TT FF TT TT=TT\land{T}=T TT TT FT=TF\lor{T}=T
TT FF FF FF TT TT=TT\land{T}=T FF FF FF=FF\lor{F}=F
FF TT TT TT TT TT=TT\land{T}=T TT FF FF=FF\lor{F}=F
FF TT FF FF FF TF=FT\land{F}=F TT FF FF=FF\lor{F}=F
FF FF TT FF FF FT=FF\land{T}=F TT FF FF=FF\lor{F}=F
FF FF FF FF FF FF=FF\land{F}=F FF FF FF=FF\lor{F}=F

德·摩根律:¬(pq)¬p¬q\lnot(p\land{q})\equiv\lnot{p}\lor\lnot{q}¬(pq)¬p¬q\lnot(p\lor{q})\equiv\lnot{p}\land\lnot q

pp qq ¬p\lnot p ¬q\lnot q pqp\land q pqp\lor q ¬(pq)\lnot(p\land{q}) ¬p¬q\lnot{p}\lor\lnot q ¬(pq)\lnot(p\lor{q}) ¬p¬q\lnot{p}\land\lnot q
TT TT FF FF TT TT FF FF FF FF
TT FF FF TT FF TT TT TT FF FF
FF TT TT FF FF TT TT TT FF FF
FF FF TT TT FF FF TT TT TT TT

吸收律 p(pq)pp\lor(p\land{q})\equiv{p}\:p(pq)p\:p\land(p\lor{q})\equiv p

  • (a) 证明:p(pq)pp\lor(p\land{q})\equiv{p}\:
    p=Tp=T时,无论pqp\land{q}为何真值,p(pq)p\lor(p\land{q})都为TT
    p=Fp=F时,无论qq为何真值,pqp\land{q}总为FFFF=FF\lor{F} = F
    所以,p(pq)p\lor(p\land{q})qq的真值无关,所以p(pq)p\lor(p\land{q})\equiv
  • (b)证明:p(pq)pp\land(p\lor{q})\equiv{p}
    p=Tp=T时,无论qq为何真值,pqp\lor{q}总为TTTT=TT\land{T} = T
    p=Fp=F时,无论pqp\land{q}为何真值,p(pq)p\land(p\lor{q})都为FF
    所以,p(pq)p\land(p\lor{q})qq的真值无关,所以(pq)p\land(p\lor{q})\equiv p

构造新的逻辑等价式

例1: 证明pqr(pr)(qr)p\lor{q} \to r \equiv (p \to r)\land(q \to r)

pqr¬(pq)r(¬p¬q)r(¬pr)(¬qr)(pr)(qr)\begin{array}{ll} p\lor{q} \to r &\equiv \lnot(p\lor{q})\lor{r} \\ &\equiv(\lnot{p}\land\lnot{q})\lor{r}\\ &\equiv(\lnot{p}\lor{r})\land(\lnot{q}\lor{r})\\ &\equiv(p\to{r})\land(q\to{r}) \end{array}

例2: 证明¬(pq)\lnot(p\to{q})p¬qp\land\lnot{q}是逻辑等价的。

¬(pq)¬(¬pq)¬¬p¬qp¬q\begin{array}{ll} \lnot(p\to{q}) &\equiv \lnot(\lnot{p}\lor{q}) \\ &\equiv \lnot\lnot{p}\land\lnot{q}\\ &\equiv p\land\lnot{q} \end{array}

例3: 证明(pq)(pq)(p\land{q})\to(p\lor{q})为永真式。

(pq)(pq)¬(pq)(pq)¬p¬q(pq)(¬pp)(¬qq)TTT\begin{array}{ll} (p\land{q})\to(p\lor{q}) &\equiv \lnot(p\land{q})\lor(p\lor{q})\\ &\equiv\lnot{p}\lor\lnot{q}\lor(p\lor{q})\\ &\equiv(\lnot{p}\lor{p})\lor(\lnot{q}\lor{q})\\ &\equiv T\lor{T}\\ &\equiv T \end{array}

其他

一个只含逻辑运算符\lor\land¬\lnot的复合命题的对偶式是通过将该命题中的每个\lor\land代替、每个\land\lor代替,每个TTFF代替,每个FFTT代替而得到的命题。命题s\:s\:的对偶式用s\:s^*\:表示。

NANDNAND(与非)和NORNOR(或非)
命题pNANDqp\enspace NAND\enspace qppqq或两者均为假时为真,而当ppqq为真是为假。命题pNORqp\enspace NOR\enspace q只在ppqq均为假时为真,否则为真。命题pNANDqp\enspace NAND\enspace qpNORqp\enspace NOR\enspace q分别表示为pqp\:|\:qpqp\:\darr\:q
pp qq pqp\:\mid\:q (pq)(p\land q) ¬(pq)\lnot(p\land q) pqp\:\darr\:q pqp\lor q ¬(pq)\lnot(p\lor{q})
TT TT FF TT FF FF TT FF
TT FF TT FF TT FF TT FF
FF TT TT FF TT FF TT FF
FF FF TT FF TT TT FF TT
  • pq¬(pq)p\:\mid\:q\equiv\lnot(p\land{q})
  • pq¬(pq)p\:\darr\:q\equiv\lnot(p\lor{q})

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×