逻辑和证明--命题逻辑

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

命题逻辑

命题

命题
命题是一个陈述预计(即陈述事实的语句),它或真或假,但不能既真又假。

我们用字母来表示命题变元,它是代表命题的变量。习惯上用字母p,q,r,s,p,\enspace q,\enspace r,\enspace s,\enspace \dots表示命题。如果一个命题是真命题,它的真值为真,用TT表示;如果它是假命题,其真值为假,用FF表示。

涉及命题的逻辑领域称为命题演算命题逻辑。许多数学陈述都是有一个或多个命题组合而来。称为复合命题的新命题是由已知命题用逻辑运算符组合而来。

p\:p\:为一个命题,则p\:p\:的否定记作¬p\:\lnot p\:(也可记作p\:\overline{p}\:),指“不是p\:p\:所指的情形”。命题¬p\:\lnot p\:读作“非p\:p\:”。p\:p\:的否定¬p\:\lnot p\:的真值和p\:{p}\:的真值相反。

命题之否定的真值表

pp ¬p\lnot p
TT FF
FF TT
合取(and)
p\:p\:q\:q\:为命题。p\:p\:q\:q\:的合取即命题“p\:p\:并且q\:q\:”,记作pq\:p\land{q}\:。当p\:p\:q\:q\:都是真时pq\:p\land{q}\:命题为真,否则为假
析取(or)
p\:p\:q\:q\:为命题。p\:p\:q\:q\:的析取即命题“p\:p\:q\:q\:”,记作pq\:p\lor{q}\:。当p\:p\:q\:q\:均为假时,pq\:p\lor{q}\:命题为假,否则为真。
异或
p\:p\:q\:q\:为命题。p\:p\:q\:q\:的异或(记作pqp\oplus q)是这样一个命题: 当p\:p\:q\:q\:中恰好只有一个为真命题时为真,否则为假。
蕴含
p\:p\:q\:q\:为命题条件语句pqp \to q是命题“如果pp,则qq”。当pp为真而qq为假时,条件语句pqp \to q为假,否则为真。在条件语句pqp \to q中,pp称为假设(前件、前提),qq称为结论(后件)。
pp qq pqp\land q pqp\lor q pqp\oplus q pqp \to q
TT TT TT TT FF TT
TT FF FF TT TT FF
FF TT FF TT TT TT
FF FF FF FF FF TT

条件语句

语句pqp \to q称为条件语句,因为pqp \to q可以断定在条件pp成立的时候qq为真。条件语句也称为蕴含pqp \to q,则ppqq的必要条件。

充分条件、必要条件、充分必要条件

  • 充分条件: 如果A能推出B,那么A就是B的充分条件。其中A为B的子集,即属于A的一定属于B,而属于B的不一定属于A,具体的说若存在元素属于B的不属于A,则A为B的真子集;若属于B的也属于A,则A与B相等。
  • 必要条件: 必要条件是数学中的一种关系形式。如果没有A,则必然没有B;如果有A而未必有B,则A就是B的必要条件,记作BAB→A,读作“B含于A”。数学上简单来说就是如果由结果B能推导出条件A,我们就说A是B的必要条件。
  • 充分必要条件: 也称充要条件 如果p\:p\:q\:q\:的充要条件,则通过p\:p\:可以推导出q\:q\:,通过q\:q\:也可以推导出p\:p\:pqp \leftrightarrow q。当且仅当即指充要条件。

pp仅当qq”和“qq除非¬p\lnot p

  • pp仅当qq”,表达了“如果pp,则qq”同样的意思。
  • qq除非¬p\lnot p”,与pqp \to q拥有相同的真值。可以做下转换,qq除非¬p\lnot p”,也就是说“如果非¬p\lnot pqq”即¬¬pq=pq\lnot\lnot p \to q= p \to q
逆命题、逆否命题与反命题
由条件语句pqp \to q可以构成一些新的条件语句。特别是三个常见的相关条件语句还拥有特殊的名称。命题qpq\to{p}称为pqp\to{q}逆命题,而pqp\to{q}逆否命题是命题¬q¬p\lnot{q} \to \lnot{p}。命题¬p¬q\lnot{p} \to \lnot{q}称为pqp\to{q}的反命题。三个由pqp \to q衍生出来的条件语句中,只有逆否命题总是和pqp \to q具有相同的真值。

当两个复合命题具有相同的真值时,我们称它们是等价的。前提为真,结论为假时才为假。

pp qq pqp\to q qpq\to p ¬q¬p\lnot q\to\lnot p ¬p¬q\lnot p\to\lnot q
TT TT TT TT=TT \to T = T ¬T¬T=FF=T\lnot{T} \to \lnot{T} = F \to F = T ¬T¬T=FF=T\lnot{T} \to \lnot{T} = F \to F = T
TT FF FF FT=TF \to T = T ¬F¬T=TF=F\lnot{F} \to \lnot{T} = T \to F = F ¬T¬F=FT=T\lnot{T} \to \lnot{F} = F \to T = T
FF TT TT TF=FT \to F = F ¬T¬F=FT=T\lnot{T} \to \lnot{F} = F \to T = T ¬F¬T=TF=F\lnot{F} \to \lnot{T} = T \to F = F
FF FF TT FF=TF \to F = T ¬F¬F=TT=T\lnot{F} \to \lnot{F} = T \to T = T ¬F¬F=TT=T\lnot{F} \to \lnot{F} = T \to T = T
双条件语句
p\:p\:q\:q\:为命题。双条件语句pq\:p \harr q\:是命题“p\:p\:当且仅当q\:q\:”。当p\:p\:q\:q\:有同样的真值时,双条件语句为真,否则为假(即同为真或同为假)。双条件语句也称为双向蕴含。
pp qq pqp\harr q
TT TT TT
TT FF FF
FF TT FF
FF FF TT

pqp \harr{q}(pqqp)(p\to{q}\land{q}\to{p})有完全相同的真值。

条件的隐式使用

~

复合命题的真值表

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

逻辑运算符的优先级

¬,,,,\lnot,\land,\lor,\to,\harr

运算符 优先级
¬\lnot 1
\land 2
\lor 3
\to 4
\harr 5

逻辑运算和位运算

真值
TT 1
FF 0

计算机的位运算对应于逻辑联结词(,,\land,\lor,\oplus\quad对应与、或、异或 )。

xx yy xyx\lor y xyx\land y xqx\oplus q
00 00 00 00 00
00 11 11 00 11
11 00 11 00 11
11 11 11 11 00

评论

Your browser is out-of-date!

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

×