中科院讲义-分布式操作系统-Peterson和Dekker算法证明教学课件

中科院讲义分布式操作系统Peterson和Dekker算法证明常用逻辑运算符叫否定(Negation)-P读作非P∧叫合取(Conjunction)P∧Q读作P与Qv叫析取(Disjunction)PvQ读作P或Q→叫条件(Condition)P→Q读作如果P,则→叫双条件(Bicondition)PQ读作P当且仅当Q①逻辑运算符优先级从高到低为②同级逻辑运算符从左到右③最外层括号可以去掉。真值表非」合取」析取异或」条件双条件NOTANDORXORCONDITIONBICONDITIONPQ-PPAQIPVQP⊕QP→QP(>QFFTFFFTFTTTFFTFFTFF-(PAQ)-(P+>Q)PvQ(P→→Q∧(Q>P常用逻辑公式等价(Equivalance)公式1交换律:P∧Q≡Q∧P,PQ≡QvP,P4Q≡Q<P2结合律P∧(Q∧R)≡(PAQ)∧R),Pv(QvR)≡(PvQR,P(QR)≡(PQR3分配律:P∧(QvR)≡(PAQV(P∧R),Pv(Q∧R)≡(PvQ∧(PvR),P→(Q→R)≡(P→Q→(P→R)常用逻辑公式4双重否定律:~~P≡P5DeMogen定律:~(P∧Q≡~PV~Q,(PvQ≡~P∧~Q6否定深入:(P分Q≡~P4Q≡P~QP→~Q≡Q→PP4>-Q≡Q4P常用逻辑公式7变量等同P∧P≡P,PVP≡P,P∧~P≡F,P~P≡T,P→P≡T,P→~P≡~P,P→P≡P,P>P≡T,P4>~P≡F8.常量与变量的逻辑T∧P≡P,F∧P≡F,TvP≡T,FVP≡P,T→P≡P,F→P≡T,P→T≡T,P→F≡~PT<>P≡P,F<)P≡~P常用逻辑公式9.逻辑词归化:P∧Q≡~(PV~Q),PVQ≡~(~P∧~Q),P→Q≡~PVQP分Q≡(P→Q)∧(Q→P)P>Q≡(PAQV(~P∧~Q10.量词分配律:彐x(A(x)VB(x))≡3A(x)v彐B(x√x(A(x)AB(x)≡VxA(x)∧VxB(x)常用逻辑公式11量词转换律:Vx4(x)≡3A(x),~彐A(x)≡Vx~A(x)12量词辖域扩张及收缩律:VxA(x)∧P≡Vx(A(x)∧P),VA(XVP=V(A(x)vP),彐A(x)∧P≡彐x(A(x)∧P)彐A(x)VP≡彐(A(x)P)常用逻辑公式13量词其他等价公式:VxA(x)→>B≡VxA(x)→B),A→VB(X)≡VxA→B(x),彐xA(x)→>B≡彐(A(x)→>B),A→彐B(x)≡彐(A→B(x)彐x(A(x)→>B(X)≡Vx4(x)→>彐B(x),14量词次序交换:xyA(x,y)≡VVA(x,y)彐彐A(x,y)≡彐彐xA(x,y)常用逻辑公式蕴涵式(Implication):1.化简式:P∧Q→P,P∧Q→Q2附加式:P→PvQ,Q→PvQ3~P→P>Q,Q→P→Q,(P→Q→P,~(P→Q→~Q4.P,Q→P∧Q常用逻辑公式5析取三段论:~P,PvQ→Q6假言推论(modusponens简记MP):P,P→Q→Q7拒取式:-Q,P→Q→-P8假言三段论:P→Q,Q→R→P→R9.二难推论:PvQ,P>R,Q→R→R0(P→Q→(RP→RvQ,(P→Q)→(R∧P→R∧Q)36、自己的鞋子，自己知道紧在哪里。——西班牙

37、我们唯一不会改正的缺点是软弱。——拉罗什福科

38、我这个人走得很慢，但是我从不后退。——亚伯拉罕·