基础知识

逻辑符号

原子命题

$p,\, q,\, r,\, \ldots$ 表示原子命题（简单命题）

1 表示命题的真值为真

0 表示命题的真值为假

联结词

否定联结词

$\neg$ 称为否定联结词

$\neg p$ 称为 $p$ 的否定式

$p$ $\neg p$
0 1
1 0
合取联结词

$\wedge$ 称为合取联结词（AND）

$p\, \wedge\, q$ 称为 $p$ 与 $q$ 的合取式

$p$ $q$ $p\, \wedge\, q$
0 0 0
0 1 0
1 0 0
1 1 1

可以将 $p\, \wedge\, q$ 理解为 $p \cdot q$

析取联结词

$\vee$ 称为析取联结词（OR）

$p\, \vee\, q$ 称为 $p$ 与 $q$ 的析取式

$p$ $q$ $p\, \vee\, q$
0 0 0
0 1 1
1 0 1
1 1 1

可以将 $p\, \vee\, q$ 理解为 $p + q$

蕴涵联结词

$\rightarrow$ 称为蕴涵联结词

$p\, \rightarrow\, q$ 称为 $p$ 与 $q$ 的蕴含式

$p$ $q$ $p\, \rightarrow\, q$
0 0 1
0 1 1
1 0 0
1 1 1

可以将 $p\, \rightarrow\, q$ 理解为 $p \leq q$

等价联结词

$\leftrightarrow$ 称为等价联结词

$p\, \leftrightarrow\, q$ 称为 $p$ 与 $q$ 的等价式

$p$ $q$ $p\, \leftrightarrow\, q$
0 0 1
0 1 0
1 0 0
1 1 1

可以将 $p\, \leftrightarrow\, q$ 理解为 $p = q$

优先级

分别是 $\neg$, $\wedge$ $\vee$, $\rightarrow$ $\leftrightarrow$

逻辑公式

命题公式

• 单个命题变元（常元）是命题公式
• 若 $A$ 是命题公式，则 $\neg A$ 也是
• 若 $A,\, B$ 是命题公式，则 $A \wedge B$、$A \vee B$、$A \rightarrow B$ 和 $A \leftrightarrow B$ 也是
• 只有有限次应用上述三个方式形成的字符串才是

真值表

$p$ $q$ $p \rightarrow q$ $p \wedge \neg p$ $p \wedge (p \vee q) \leftrightarrow p$
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 0 1

等值式

等值式 $A \Leftrightarrow B$ 表示 $A \leftrightarrow B$ 是永真式

$p$ $q$ $p \rightarrow q$ $\neg p \vee q$ $(p \rightarrow q) \leftrightarrow (\neg p \vee q)$
0 0 1 1 1
0 1 1 1 1
1 0 0 0 1
1 1 1 1 1

$\therefore p \rightarrow q \Leftrightarrow \neg p \vee q$

对偶原理

$\vee$ 和 $\wedge$ 互换，0 和 1 互换之后，等值式仍然成立

推理定律

推理定律 $A \Rightarrow B$ 表示 $A \rightarrow B$ 是永真式

BigData