逻辑:命题逻辑,语义后承,和转化规则

命题逻辑和语义后承

最近在自己学逻辑, 逻辑是计算机的一个重要基础学科.然而本人自己找的教材资料是德语英语中文各个语言,在此做出整理.可能存在错误,欢迎指正.

逻辑学起源于古希腊. 当时“雄辩“(Rhetorik)时常用”演绎推论法”(Deduktion). 由前提(Prämissen)和结论(Konklusionen)构成.

命题逻辑的语法(Syntax der Aussagenlogik)

命题逻辑由 原子公式(占位符,命题字母,命题变量) 和 逻辑运算符 组成.

而这样的一个式子(Formel)通常会用一个希腊字母表示.(在此文档中如此, 中文资料也见过使用拉丁字母abc的)

这样的陈述可能很难想象出式子,那么在这里附上一个式子:

$\alpha=((\lnot A \land B)\lor C)$

原子公式(Aussagenlogische Atome)

原子公式也叫占位符,命题字母,命题变量(Aussagenlogische Atome, Elementaraussagen, aussagenlogische Variablen)
由带或不带下标的大写字母构成, 比如:
A,B,X_i
如上面例子中的ABC.

运算符(Junktoren)

这里目前列出一些基本的运算符.

符号记忆很简单, 我是觉得or比较容易true,贱贱的笑笑$\lor$. and比较刁难,不容易true, 摆脸色了$\land$.

其中的和, 或, 非, 不难理解.
and很明显从自然语言语义上就是”两者都成立才行”, or就是两个随便哪个行就ok, not 就是取反.等价是两者同为True或同为False才是True,也不难理解.

而蕴涵则可以理解为一个条件.

比如: P为人活着, Q为有水源:
那么$P/rightarrow Q$真值表可以解释为如下

人活着就要有水源. True
人没活着, 但是有水源, True
人没活着, 没有水源. True
人活着, 但是没有水源. False(这不可能)

此时, 有水源就是人活着的必要条件. 也就是说, 人活着(P)是有水源(Q)情况的子集.
同样充分条件也可以用蕴含关系表达.

而等价可以当作”充分必要条件理解”
能被2整除的自然数是偶数, 自然数偶数能被2整除. 逻辑真值表等价.

运算符号优先级

Bindungsregeln dienen der Ersparnis von Klammern

$\lnot > \land > \lor$
也不难记,小学牛津英语的神回答:not at all(not and or)

此外我接触过的大多数编程语言,php, python, C(++), java, javascript都遵从这个运算规定.

真值表(Wahrheitstafel)

我个人觉得没啥好做笔记的

一些基本概念(Grundbegriffe)

先设一个集合$V$,是某式子所有原子公式(上面的A,B,C那样的变量)的集合

一个函数$l()$存在映射$V\to \left{ True, False \right}$ (解释,Interpretation)

假设存在一个$\alpha$:

• Erfüllbar(可满足): 至少存在一个赋值方法可以让$l(\alpha) = True$ 比如$A\lor\lnot B$ 当 $A=True,B =True$
• Tautologie(重言,永真): 无论如何赋值$l(\alpha) = True$ 比如$A\lor \lnot A$
• Widerspruchsvoll(矛盾): 无论如何赋值$l(\alpha) = False$ 比如 $A \land \lnot A$
• Falsifizierbar(可证伪): 至少存在一种赋值,让$l(\alpha) = False$ 比如 $A \lor B$ 当 $A,B = False$

这里有一个结论,一个”矛盾”的$\alpha$,在其取not时$\lnot \alpha$是重言的

因为$\alpha$是”矛盾的”,所以根据定义,$l(\alpha) = False$, 所以无论定义域$V$中如何取值(alpha中变量如何取值),都不影响这个结论. 同样的当$l(\lnot \alpha)$时,无论定义域如何取值也不会影响$l(\lnot \alpha) = True$.

语义后承(语义蕴涵,Semantische Folgerung)

如果我们假设M为非空集合, 存在$\alpha_1, \dots,\alpha_n$使$M={\alpha_1, \dots,\alpha_n}$(也可写做$\alpha_1 \land \dots \land \alpha_n$)当存在$\beta$,当解释$l(M)=True$时同样$l(\beta) =True$, 那么可以认为此为语义后承. 写做$M\models \beta$

(说白了就是Alpha是真的时候beta也是真)

如果此时集合M里只有一个$\alpha$那么可以写作$\alpha\models\beta$, 若M是空集,存在$\models\beta$那么意味着$\beta$重言(Tautologie).这是一种特殊的语义后承.

一些推论:

• $\alpha \models \beta$: $\models \alpha \rightarrow \beta$, $\models \lnot \alpha \lor \beta$
• $\alpha \models \beta$: $\alpha \land \lnot \beta$ 是矛盾(Widerspruchsvoll)
• 如果$\alpha$是矛盾的(永为False)那么$\alpha \models \beta$ 此处$\beta$可以为任意式子.
• 如果$\alpha$是矛盾的(永为False)那么存在$\alpha \models (A \land \lnot A)$

语义后承的一些重要规则

这些规则在后面的归结(Resolution)中会有用

• $\alpha, \; \alpha \to \beta \models \beta$(Modus Ponens(拉丁语,肯定前件))
• $\alpha \to \beta,\; \beta \to \sigma \models \alpha \to \sigma$(Kettenregel,链式法则(?))
• $(\alpha \lor \beta),(\lnot \beta \lor \sigma) \models (\alpha \lor \sigma)$

逻辑等价(Logische Äquivalenz)

如果两个式子$l(\alpha) = l(\beta)$成立即等价. 写做$\alpha\approx\beta$(国内资料也有很多使用=表示)

此时也存在$\alpha \models \beta,\beta\models\alpha$

逻辑转换化规则(Umformungsregeln)

此处偷了懒, 等价用了等于号.

• Negation(对合律): $\lnot \lnot a = a$
• Idempotenz(幂等律): $a \lor a = a,\;a \land a = a$
• Neutrales Element(互补律的一种用法): $(\alpha \land \lnot \alpha)\lor \beta = \beta,\;(\alpha \lor \lnot \alpha) \land \beta = \beta$

• Kotradiktion/Tautologie: $(\alpha \land \lnot \alpha) \land \beta= \alpha \land \lnot \alpha,\;(\alpha \lor \lnot \alpha)\lor \beta= \alpha \lor \lnot \alpha$

• Kommutativität(交换律): $\alpha \lor \beta = \beta \lor \alpha,\;\alpha \land \beta = \beta \land \alpha$

• Assoziativtät(结合律): $(\alpha\lor\beta) \lor \gamma = \alpha \lor (\beta \lor \gamma),\;(\alpha\land\beta)\lor\gamma = \alpha\land(\beta \land \gamma)$
• Distributivität(分配率): $(\alpha \land \beta)\lor \gamma = (\alpha \lor \gamma) \land (\beta \lor \gamma),\;(\alpha\lor\beta)\land \gamma = (\alpha\land \gamma) \lor (\beta \land \gamma)$
• De Morgan(德摩根定律): $\lnot(\alpha \land \beta) = \lnot \alpha \lor \lnot \beta,\;\lnot(\alpha\lor \beta) = \lnot \alpha \land \lnot \beta$
• Absorption(吸收率): $\alpha\land(\alpha \lor \beta) = \alpha,\; \alpha \lor(\alpha \land \beta) = \alpha$