命题逻辑

应用一套形式化规则对以符号表示的描述性陈述进行推理的系统

基本概念

• 断言：一个陈述句
• 命题：具有真假意义的断言
  • 一个命题不能同时既为真又为假
  • 一个命题可在一定条件下为真，而在另一条件下为假
• 论域（个体域）：由所讨论对象的全体构成的集合，其中的元素称为个体
• 命题常量：某个具体命题
• 命题变量：指代任何具体命题
• 原子命题（简单命题）：不能分成更简单的陈述句的命题
• 复杂命题：由若干个原子命题通过逻辑运算符构成的命题

命题联结词

名称	符号	说明
否定	$\neg p$	非p
合取	$p\wedge q$	p且q
析取	$p\vee q$	p或q
蕴含	$p\rightarrow q$	如果p则q
等价	$p\leftrightarrow q$	p当且仅当q

范式

可以进行两个命题的等价判定

• 析取范式：由有限个简单合取式构成的析取式
  • 设$\alpha_i$为简单的合取式，则$\alpha = \alpha_1 \vee \alpha_2 \vee ··· \vee \alpha_k$为析取范式
  • 一个析取范式是不成立的，当且仅当它的每个简单合取式都不成立
• 合取范式：由有限个简单析取式构成的合取式
  • 设$\alpha_i$为简单的析取式，则$\alpha = \alpha_1 \wedge \alpha_2 \wedge ··· \wedge \alpha_k$为析取范式
  • 一个合取范式是成立的，当且仅当它的每个简单析取式都是成立的
• 任一命题公式都存在与之等值的析取范式与合取范式（不是唯一的）