[离散数学]命题逻辑P_3：命题符号化及其应用
[离散数学]命题逻辑P_3：命题符号化及其应用
前言1. 命题联结词的总结命题联结词命题联结词的真值表例子
2. 命题联结词的优先级优先级顺序例子
3. 复合命题符号化例子
4. 联结词应用开关电路逻辑电路网页检索位运算
总结
前言
第三讲：命题符号化及其应用
数理逻辑，就是用数学的方法研究逻辑推理的规律。
把一个自然语句的(复合)命题写成一个由命题标识符，联结词和圆括号所组成的命题公式，并且这一命题公式在相应的指派下所得到的命题与原自然语句表达相同的逻辑关系。这一过程叫做命题符号化。
一般命题符号化采用以下几个步骤： (1)确认自然语句是个命题。 (2)将自然语句中包含的一些原子命题分离出来，并将它们符号化。 (3)根据自然语句中的逻辑关系，选用适当的联结词，再将整个句子符号化。
本文命题符号化及其应用是命题逻辑的第三部分。
1. 命题联结词的总结
命题联结词
联结词记号复合命题读法记法真值结果否定
¬
\lnot
¬
P
P
P的否定非
P
P
P
¬
P
\lnot P
¬P
¬
P
\lnot P
¬P的真值为“真”当且仅当
P
P
P的真值为“假”合取
∧
\land
∧
P
P
P并且
Q
Q
Q
P
P
P合取
Q
Q
Q
P
∧
Q
P\land Q
P∧Q
P
∧
Q
P\land Q
P∧Q的真值为“真”当且仅当
P
、
Q
P、Q
P、Q的真值同为“真”析取
∨
\lor
∨
P
P
P或者
Q
Q
Q
P
P
P析取
Q
Q
Q
P
∨
Q
P\lor Q
P∨Q
P
∨
Q
P\lor Q
P∨Q的真值为“真”当且仅当
P
、
Q
P、Q
P、Q的真值至少一个为“真”蕴涵
→
\rightarrow
→若
P
P
P，则
Q
Q
Q
P
P
P蕴涵
Q
Q
Q
P
→
Q
P\rightarrow Q
P→Q
P
→
Q
P\rightarrow Q
P→Q的真值为“假”当且仅当
P
P
P的真值为“真”、
Q
Q
Q的真值为“假”等价
↔
\leftrightarrow
↔
P
P
P当且仅当
Q
Q
Q
P
P
P等价于
Q
Q
Q
P
↔
Q
P\leftrightarrow Q
P↔Q
P
↔
Q
P\leftrightarrow Q
P↔Q的真值为“真”当且仅当
P
、
Q
P、Q
P、Q的真值同为“真”或同为“假”
命题联结词“
∧
\land
∧”、“
∨
\lor
∨”、“
↔
\leftrightarrow
↔”具有对称性，而“
¬
\lnot
¬”、“
→
\rightarrow
→”没有。
命题联结词的真值表
P
P
P
Q
Q
Q
¬
P
\lnot P
¬P
P
∧
Q
P\land Q
P∧Q
P
∨
Q
P\lor Q
P∨Q
P
→
Q
P\rightarrow Q
P→Q
P
↔
Q
P\leftrightarrow Q
P↔Q0010011011011010001001101111
重要！！
联结词是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题的真值只取决于构成他们的各简单命题的真值，而与它们的内容无关，与二者之间是否有关系无关。
例子
命题1：雪是白的当且仅当北京是中国的首都。
两个真命题用等价联结词连接 - 命题为真
命题2：如果2是偶数，则天上可以掉馅饼。
蕴涵联结词的前件为真命题，后件为假命题 - 命题为假
尽管两个简单命题内容之间无关联，但二者均为合法命题，且具有确定的真值。
2. 命题联结词的优先级
优先级顺序
所有五个联结词的优先顺序为：否定，合取，析取，蕴涵，等价；同级的联结词，按其出现的先后次序（从左到右）；若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最高优先级。
类似加减乘除，先乘除后加减，违反优先顺序时使用括号
例子
¬
P
∨
¬
Q
→
R
∧
S
↔
T
\lnot P\lor \lnot Q\rightarrow R\land S\leftrightarrow T
¬P∨¬Q→R∧S↔T的运算步骤是如何呢？
先算
¬
P
\lnot P
¬P和
¬
Q
\lnot Q
¬Q，再算
R
∧
S
R\land S
R∧S，然后算
∨
\lor
∨，接着算“
→
\rightarrow
→”，最后算“
↔
\leftrightarrow
↔”
¬
P
∨
(
¬
Q
→
R
)
∧
S
↔
T
\lnot P\lor \left( \lnot Q\rightarrow R \right) \land S\leftrightarrow T
¬P∨(¬Q→R)∧S↔T的运算步骤又是如何？
使用括号后，先算
¬
P
\lnot P
¬P和
¬
Q
\lnot Q
¬Q，再算
(
¬
Q
→
R
)
\left( \lnot Q\rightarrow R \right)
(¬Q→R)，然后算
∧
\land
∧，接着算“
∨
\lor
∨”，最后算“
↔
\leftrightarrow
↔”
3. 复合命题符号化
例子
设命题：
P
P
P：你陪伴我；
Q
Q
Q：你代我叫车子；
R
R
R：我将出去. 符号化下属语句：
如果你陪伴我并且代我叫辆车子，则我将出去。 符号化为：（
P
∧
2
Q
P\land ^2 Q
P∧2Q）
→
1
\rightarrow ^1
→1
R
R
R
P
P
P合取
Q
Q
Q，蕴涵
R
R
R（括号可省略）
如果你不陪伴我或不代我叫辆车子，我将不出去。 符号化为：（
¬
P
∨
2
¬
Q
\lnot P\lor ^2 \lnot Q
¬P∨2¬Q）
→
1
\rightarrow ^1
→1
¬
R
\lnot R
¬R
除非你陪伴我或代我叫车子，否则我将不出去。 符号化为：
R
→
(
P
∨
Q
)
R\rightarrow \left( P\lor Q \right)
R→(P∨Q)或
(
¬
P
∧
¬
Q
)
→
¬
R
\left( \lnot P\land \lnot Q \right) \rightarrow \lnot R
(¬P∧¬Q)→¬R
否则 - 蕴涵前件的否定；除非 - 后件
剥洋葱 - 从外层向内层进行分析 - 分析顺序用数字序号标出
4. 联结词应用
开关电路
对于串联电路，需要两个开关同时闭合，灯泡才能亮起 - 合取；对于并联电路，至少需要一个开关闭合，灯泡才能亮起 - 析取；开关断开，灯泡不亮。
设命题
P
P
P；开关
S
1
S_1
S1闭合；命题
Q
Q
Q；开关
S
2
S_2
S2闭合。则用复合命题表示：
（图1）开关电路的“串联”：
P
∧
Q
P\land Q
P∧Q（图2）开关电路的“并联”：
P
∨
Q
P\lor Q
P∨Q（图3）开关电路的“断开”：
¬
P
\lnot P
¬P
逻辑电路
命题联结词“
∧
\land
∧”、“
∨
\lor
∨”、“
¬
\lnot
¬”对应于与门、或门和非门电路，从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。 与门 - 输入
P
、
Q
P、Q
P、Q都是高电平时，输出高电平；有一个是低电平时，输出低电平，即“合取联结词”。 或门 - 输入
P
、
Q
P、Q
P、Q中有一个是高电平时，输出高电平，即“析取联结词”。 非门 - 输入
P
P
P是高电平时，输出低电平；输入低电平时，输出高电平，即“否定联结词”。 输入
P
、
Q
、
R
P、Q、R
P、Q、R，其中
P
、
Q
P、Q
P、Q经过一个与门然后输入或门，
Q
、
R
Q、R
Q、R经过一个与非门然后输入或门。
符号化为：
(
P
∧
Q
)
∨
¬
(
Q
∧
R
)
\left( P\land Q \right) \lor \lnot \left( Q\land R \right)
(P∧Q)∨¬(Q∧R)
逻辑电路可以用复合命题表示，显然可以利用命题逻辑的研究工具对逻辑电路进行研究和分析。
网页检索
布尔检索
在布尔检索中，联接词“
∧
\land
∧”（一般用AND表示）用于匹配包含两个检索项的记录，联接词“
∨
\lor
∨”（一般用OR表示）用于匹配包含两个检索项至少一个的记录，而联接词“
¬
\lnot
¬”（一般用NOT表示）用于排除某个特定的检索项。
New AND Mexico AND universities： 检索新墨西哥州各大学的网页。(New AND Mexico OR Arizona) AND universities： 检索新墨西哥州或亚利桑那州各大学的网页。
位运算
计算机中的信息采用二进制的方式来表达。每个二进制位只能是1或0，可对应于某一个布尔变量的真值。当我们需要判断该布尔变量的真值时，就可以利用按位与（bitwise AND）或按位或（bitwise OR）以及按位取反（bitwise NOT）等来操作。
这是TCP/IP网络协议栈中的IP报头的基本格式，考虑：如何获取版本号？
从版本号和头长的8字节中提取出版本号。
i
p
d
a
t
a
[
0
]
&
0
×
F
0
>
>
4
ipdata\left[ 0 \right] \&0\times F0>>4
ipdata[0]&0×F0>>4
i
p
d
a
t
a
[
0
]
ipdata\left[ 0 \right]
ipdata[0]：表示第一个字节
&
0
×
F
0
\&0\times F0
&0×F0：十六进制11110000 - 即版本号用1进行与；头长用0进行与。 与 - 合取； 用1合取 - 不改变值； 用0合取 - 结果为0。 去掉头长的内容，保留版本号的内容。
>
>
4
>>4
>>4：右移四位，方便判断等于4还是等于6。
总结
本文介绍了命题逻辑中的命题符号化及其应用部分，对命题逻辑有更深的了解。