这份笔记还处于实验和编写阶段. 可能很多内容会大改, 并且正确性不能够保证, 仅做预览使用.

这份讲义大部分照抄了南京大学魏恒峰老师的离散数学课件和NJU问题求解课程编写组提供的课件和补充资料. 在这里为他们辛苦的准备讲稿以及无私地开源供外校学生学习表达感谢以及敬佩!

请参看Github的源代码仓库 https://github.com/shzaiz/dx-public/blob/main/TeXify/pypsolve/pypsolve-main.pdf.

Part I
计算的核心

计算机为什么能够帮助我们这么多? 这一部分我们来简单给出一些答案. 具体地, 我们将会了解计算思维最核心的概念了解计算的基本方法与局限; 同时接受基本的形式化训练掌握抽象数学证明的基本方法.

Chapter 1
程序设计语言基础回顾[P]

心智的活动, 除了尽力产生各种简单的认识之外, 主要表现在如下三个方面:

(1) 将若干简单认识组合为一个复杂认识, 由此产生出各种复杂的认识.

(2) 将两个认识放在一起对照, 不管它们如何简单或者复杂, 在这样做时并不将它们合而为一. 由此得到有关它们的相互关系的认识.

(3) 将有关认识与那些在实际中和它们同在的所有其他认识隔离开, 这就是抽象, 所有具有普遍性的认识都是这样得到的.

–John Locke 有关人类理解的随笔, 1960

1.1 问题的提出: 通过程序, 可以求解的问题

电脑之所以叫“电脑”, 就是因为它能替代部分人类的思维活动. 回忆每个班上都有一个笔记和草稿纸都工工整整的Ta, 比如布置了一个很繁琐的任务, Ta总是认认真真默默画完. 很显然, 工整的笔记可以启发思维, 但是当问题范围更加大的时候非常困难继续进行.

学过编程的我们如果有良好的计算思维的时候, 就可能有这样的感慨:

烦死了! 劳资不干了! 玩更有趣的东西去了! –一名具有良好计算思维的同学

这就是计算思维: 写个程序 (如model checker) 来代替我们一部分的机械的思维活动. 任何机械的思维活动都可以用计算机替代, Al还可以替代启发式/经验式的决策.

1.2 程序设计的语法与语义

我们在学习英语的时候很重要的一部分是语法(grammar): 也就是什么样的语言是可以被接受(acceptable)的. 比如下面这个英文句子是没有语法错误的:

Fuhai Zhu said that this test is only a small test, so don’t panic.

但是这句话不同人有不同的理解方式, 这就是这句话的语义(schematics).

• 我们可以推断朱富海老师在安抚准备参加小测试学生们的情绪
• 但是南京大学数学系的同学知道这是一个有名的梗: 上学期教高等代数的朱富海老师把线上期中考叫做“小测验”, 并在同学询问考试范围的时候微笑的答道:“从小学学的都考.”

简而言之(不严谨) , 现在我们有一个由一堆字符串和推导规则组成的形式系统(formal system), 语法决定了这个形式系统能生存什么样的字符串, 而至于这些字符串有什么样的含义则是语义的范畴.

语法类似材料, 语义类似与材料组成的各种建筑物, 我们可以通过语法研究语义层面的推导, 同时也可以从语义层面捕获语法中内涵的结构, 其实语法和语义是相互区别又紧密联系, 即从范畴论的角度看语法和语义是伴随的(其实不同的人做数学证明可以有不同的风格: 偏语法和偏语义, 不过大部分数学家更喜欢语义风格的证明, 可能因为更直观, 更容易被人脑接受. )

选自 https://www.zhihu.com/question/31347357/answer/892133941

1.3 Python代码执行可视化: 一个网站

1for i in range(10): 
2    print(i**2)

通过观察可以发现, 代码按照行数执行, 一次执行一行, 每一次执行计算机内部结构的状态(右侧的面板). 下面我们化繁为简, 来看一看一个系统(数学意义上)能够完成任何人类完成的操作需要的最小可能的操作是什么.

1.4 可以“程序化”执行命令的最小指令集

如果我们说, 写出来一个可以计算“我们想要计算的任何理论上能够计算的东西”并不难, 你会不会认为这件事情是无稽之谈? 毕竟计算问题多种多样, 有一些内容涉及到很复杂的判断. 但是, 我们可以用一个很小的指令的集合来描述“我们可以计算的一切事物”. 我们不妨从日常生活中找一点灵感.

我们需要找一些东西来具象化我们脑子中的“红绿灯的状态(state)”, “现在在做作业的题目编号”, 这些内容, 因此我们就希望把这些抽象出来. 因此我们有了变量(variable)的概念, 也就是值存在的空间.

把上面的三个内容转化成伪代码(不唯一)就是:

1------ GO THROUGH CONJUNCTION ------ 
2if traffic light’s color is green: 
3    go pass by 
4else 
5    wait 
6 
7------ DO HOMEWORK ------ 
8range = [a..b] 
9working on problem = a 
10while working on problem <= b: 
11    finished this problem or can’t work out 
12    working on problem = working on problem+1 
13 
14------ SORT EXAM SCORE ------ 
15list = get the source table 
16result = empty(for now) 
17while list is not empty 
18    k= get the max element of list 
19    write k to the next line of result 
20show result

其实要是能够构造出任何程序的“原材料”(也就是我们的指令集)并不复杂. 无非就是变量(variable)的赋值(assign), 判断(judgement), 跳转(jump), 终止(terminate). 也就是, 如果你能声称有一套系统可以自动化的解决这四个内容, 那么这个系统就具有机械化地做任何人类做的事情. 换句话说, 你可以用这个工具创造整个世界.

其实用“机械化”的方法代替人力这样的想法是在计算机诞生之前就是人们孜孜以求的问题. Alan Turing 在1936年就提出了这样的设想. 他就是由只一条(无限长)的纸带和一根笔(可以改纸带的内容, 并且查看纸带的内容并据此做判断), 并且有一个程序(墙上的表格), 指示下一步要往哪转移. 只要能够移动读写头, 写纸带的某一个格子, 读纸带的某一个格子, 跳转, 以及终止. 根据计算领域里的证明, 可以得到这个机器就和我们人类的计算能力等价.

这是最早的图灵机的原型.

下面我们来看一看为什么说可以用Python语言的计算能力和他们是等价的. 在这之前, 我们先来了解一下如何获取帮助和得到通俗易懂的教程.

所以, 请认真阅读并实践(无论是在脑子还是在交互器(interactive shell)里面)官方帮助文档(可以在 https://docs.python.org/zh-cn/3/tutorial/introduction.html找到)¹ 的内容. 可以让你了解更多易于理解的东西. 如果文章中有描述C和Pascal的句子, 忽略它就可以. 毕竟文档是给各个不同层次和水平的人看的, 有一些看不懂以后再说.

1.4.1 Python中的整个世界

下面的内容其实不用单独记忆, 只要明确有哪些语句, 这些语句造成的效果是什么就行了. 如果看到有任何的问题, 如果是关于英语单词的, 可以搜索字典; 如果是对于程序报错有疑问, 可以搜索文档里面关于报错的信息; 如果有其他创造性的问题, 则可以询问周围的同学和老师.

下面会有两个术语(term), 分别是表达式(expression)和过程(procedure), 表达式可以暂且认为是形如x+12, [2]*3这样的可以进行计算的内容, 过程就是一系列执行的过程, 不一定要能得到值. 我们用一个例子感受一下.

def InsertionSort(A):                            

    for j in range(1, len(A)):                   #Proc

        key = A[j]    #A[j],key are expr #Proc   #|

        i = j - 1     #j-1,i are an expr #v      #|

        while (i >=0) and (A[i] > key):          #|   

        #    <-expr->    <----expr----->         #|   

        #    <-----------expr----------->        #|   

            A[i+1] = A[i] #A[i]is expr   #Proc   #|

            i = i - 1     #i-1 is expr   #v      #|

        A[i+1] =    key                          #v

       <-expr->  <-expr->

其实上面的Proc表示过程, 然后右边的是一个字符画, 表示↓, <-expr->其实表示的意思是_expr这一段是表达式.

重要的是, 把示例代码放到上面提到的可视化网站里面看一看就会很清楚, 很多概念都是不用记忆的.

变量的定义与赋值

语义: 看看有没有叫变量名的盒子, 如果有, 就把右边的内容计算出来重新把新东西替换进原来的盒子里; 否则, 就创建一个新盒子, 把右边算出来的东西丢进去.

下面我们给出注解:

• 在不加修饰的情况下, 变量的名称只在当前的缩进块内有效
• 命名是用来指代对象的. 这就是为什么有时候可视化工具里面Frames后面有一个箭头指着Objects.
• 如果用一个变量=另一个变量, 大多数情况是现计算出来右手边表达式的值之后给左手边的变量. 有时候一些文章里面写作lhs ←rhs.

b=114514

a=b+1 #执行完本句之后a=114515

b = b+1 # 执行完本句之后b=114515, a=114515不变

a = b+1 # 执行完本句之后a=114515, b=114516

• 在Python中, 变量的值的类型可以是任意的. 因为Python声明变量的时候没有说明类型.

a=”Fuhai Zhu teached Advanced Algebra” # a现在是字符串

a=1 # a现在是整数

a=None # None是一个关键字, 表示什么都没有.

• 如果没有定义(也就是没有找到叫这个名字的盒子)就使用了一个变量(就是想要从这个名字的盒子里面拿东西), 通常就会有如下的报错:

print(a+1)

      ^

Traceback (most recent call last):   File "<stdin>", line 1, in <module> 

NameError: name ’n’ is not defined

(命名错误: 名称’n’没有定义)

可以把什么东西放到盒子里面呢? 数字、字符串、列表. 当然这份回答相当不全面. 这时候可以参看官方文档 https://docs.python.org/zh-cn/3/tutorial/introduction.html来继续.

控制语句: 判断与循环

语义: 它通过逐个计算表达式, 直到发现一个表达式为真, 并且执行使表达式为真的这个过程(完成后不执行或计算if语句的其他部分的判断表达式) . 如果所有表达式都为false, 如果存在else下方语句块的过程.

下面我们同样给出注记和例子.

• 什么是真? 什么是假? 这个问题就比较深刻了. 不过先可以认为非0数字和True是真, 0和False和None是假.

if "AK":

    print("AK") # 会输出AK, 这是怎么判断的?(后续会回答)

• 可以用逻辑运算符 and(且) or(或) not(非) 进行逻辑表达, 比如

zgw = 0

kertz = 1

ak = 1

cmo = 1

if kertz and ak and cmo :

    print(“Zixuan Yuan got full mark in CMO”)

elif zgw and ak and cmo:

    print(“zgw got full mark in CMO”)

else:

    print(“zgw is such a noob”)

# 会输出Kertz got full mark in CMO, 由于已经找到了一个表达式的值为真的

# 表达式, 所以执行完print(“Zixuan Yuan got full mark in CMO”)之后就

# 会跳转到这个语句块的尾部了. 不会执行print(“zgw is such a noob”).

# (为自己菜爆的数学基础做了一个掩盖(大雾))

• 如果结构不完整, 或者在else之后还有elif, 那么就触发形如这样的错误:

例子1.py-------------

if True:

print("Err")

----

File "main.py", line 3

    print("Err")

    ^ IndentationError: expected an indented block

(缩进(indent)错误: 我预期有一个带着缩进的语句块, 但是没有)

例子2.py---------------

if False:

    print(1)

else:

    print(2)

elif True:

    print(3)

---

  File "main.py", line 5

    elif True:

    ^ SyntaxError: invalid syntax

(语法错误: 无效的语法)

语义: 这样反复测试表达式, 如果为真, 则执行过程1如果表达式为假(这可能是第一次测试) , 则执行else子句的过程2(如果存在的话) , 然后循环终止. 在过程1中执行的break语句会终止循环, 且不执行else子句的过程2. 在过程1中执行的continue语句跳过过程1的continue语句之后的其余部分, 然后立刻回到测试表达式语句.

有了循环(loop), 我们就可以解读这个东西:

def InsertionSort(A):

    j=1

    while(j<len(A)):

        key = A[j]

        i = j - 1

        while (i >=0) and (A[i] > key):

            A[i+1] = A[i]

            i = i - 1

        A[i+1] = key

        j=j+1

    return A

InsertionSort([1,1,4,5,1,4])

这个程序做的事情就和排序成绩类似. 输入一个列表A, 它就可以把A进行排序.

程序的终止

因此, 我们就得到了最小的可以(理论上)执行任何与人类计算能力等价的模型

这些内容看上去十分的平凡, 但是通过一些过程的复合, 我们就能看到更多的魔力.

1.4.2 函数: 整合相似过程

我们可以把相似的过程写在一起, 为了简洁和可维护.

下面, 可以阅读https://docs.python.org/zh-cn/3/tutorial/controlflow.html#defining-functions 的4.7, 4.8.1-4.8.6节的内容, 把所有代码是怎么执行的放在pythontutor里面模拟着看一遍. 文字可以不用看, 但是代码一定要执行一遍.

递归(recursion)过程和栈帧(stack frame)

观察下面的代码, 可能难以想象是怎么执行的:

def fib(n):

    if(n==1):

         return 1

    if(n==2):

         return 1

    else:

         return fib(n-1) + \

                fib(n-2)

fib(5)

像这样用自己调用自己的函数调用通常叫做递归. 一个关于递归的有趣定义是:

事实上, 我们可以把它放在pythontutor里面执行一下, 发现如下的规则:

• 原来的程序就像是一张纸, 上面标注着当前执行到的行数;
• 每次函数调用的时候, 就会在一张新的纸片上抄下来调用的内容, 并且代换传进来的参数;
• 把这个内容放在原来纸片上面, 然后从第一行开始执行;
• 执行完的纸片扔掉.

看上去就像是:

• 你在晚自习上看课外书(执行原来的函数)
• 老师来了, 让你写作业(函数调用)
• 你把作业叠放在课外书上, 开始做作业 (执行函数)
• 做完作业之后你把作业扔了继续看课外书(回到原来的函数)

像羽毛球球桶那样, 只能从一个方向插入, 弹出的内容的东西叫做“栈(stack)”, 由于这些内容通常都是一些数据, 由此我们用术语数据结构(data structure)来描述. 能被取出来的那个元素是栈顶(top of the stack), 在这个可视化工具里面用蓝色标示出来了.

Traceback就是出错之后, Python顺着栈一层一层找的结果. Trace是跟踪, back是返回, 意思可能就是说堆栈的回溯(traceback).

1.5 一些小例子

下面我们来看一些基础的例子, 来体会上一节中的一些思考:

片段1. 热身练习

1def getpercent(chinese, math, english): 
2    return (chinese+math+english)/(150+150+150) 
3 
4print(getpercent(100, 120, 135))

片段2. 计算钱数之和

1money = [10, 14, 13, 10] 
2int total = 0 
3for i in money: 
4    total = total + i 
5 
6print(money)

这里的for i in ...只是for u in range(len(money)), i=money[u]的简称罢了. 对我们的实际程序没有太多的障碍. 还是逃脱不了循环的大框架. 我们在前面说的最小指令集还是起作用的.

片段3. 求一个数是不是素数

1def isprime(x): 
2    flag = 1 
3    d=2 
4    while d<x: 
5        if x%d == 0: 
6            flag = 0 
7        d = d+1 
8    if flag: 
9        return 1 
10    else: 
11        return 0

在这个程序片段中, flag 代表了什么? 是不是有些像现实世界中的信息传递方式? 因为我们无法跨越循环次序改变程序的行为, 我们只好使用变量flag来记录, 并且让程序的控制流通过flag来进行判断与执行.

事实上, 数学上的定义是∀x,¬∃p,s.t.p|x. 我们的程序看上去并不是像数学那样简洁. 其实, 程序设计家族也有其他成员可以写起来比较优美.

1  (defun quadratic-roots-2 (A B C) 
2  (cond ((= A 0) (string "Not a quadratic equation.")) 
3    (t 
4    (let ((D (- (* B B) (* 4 A C)))) 
5      (cond ((= D 0) (concatenate ’string "x = " (write-to-string (/ (+ (- B) (sqrt D)) (* 2 A))))) 
6        (t 
7        (values (concatenate ’string "x1 = " (write-to-string (/ (+ (- B) (sqrt D)) (* 2 A)))) 
8                (concatenate ’string "x2 = " (write-to-string (/ (- (- B) (sqrt D)) (* 2 A)))))))))))

1ancestor(A, B) :- 
2    parent(A, C), 
3    ancestor(C, B). 
4  

片段4. Perfect数

1def is_perfect(n): 
2    sum=0 
3    for i in range(1,n): 
4        if n%i==0: 
5            sum=sum+i 
6    return sum==n

其中range现在可以认为是生成[1,n)的列表. 并且每一次循环就取列表的下一个元素. 比如for i in range(1,5)每次循环i的值会是1 2 3 4.

在这个实例中, 逻辑关系体现的如何?

片段5. 求3和5的因数个数

1def multiples_of_3_and_5(n): 
2    sum=0 
3    for i in range(1, n): 
4        if i%3==0 or i%5==0: 
5            sum=sum+i 
6    return sum    

可以注意我们的逻辑在Python里面是如何表达的? 还有哪些逻辑表达关系? 事实上, 这也是后续离散数学部分要学的命题逻辑–我们需要对于以前的逻辑有一个比较确切的定义.

普通的高中毕业生基本是无法回答这个问题的. 因为课本的知识完全没有提及类似的问题. 这就导致我们的高中数学看上去更像是民科学习的数学. 同时轻松地毁掉了高中与大学的衔接过程.

片段6. 一定范围内勾股数的个数

1def integer_right_triangles(p): 
2    #  a^2+b^2=c^2    a+b+c=p   c is the longest 
3    count=0 
4    for a in range(1,p): 
5        for b in range(a,p-a): 
6            c=p-a-b 
7            if a+b+c==p and a**2+b**2==c**2: 
8                count+=1 
9                print(a,b,c) 
10    return count

这个例子对于数学的关系好像更加清晰了. 比如直角三角形数对有兴致a² + b² = c². 于是剩下的就比较像自然的“数数”一样了.

片段7: 递归的力量

1def fib(n): 
2    if(n==1): 
3        return 1 
4    if(n==2): 
5        return 1 
6    else: 
7        return fib(n-1) + \ 
8               fib(n-2) 
9 
10fib(5)

这个内容也在前方的例子中有提及, 这样我们自然的就得出了“栈”的定义. 这也是我们这里接触的第一个数据结构–栈.

如果自己曾经动手写过一点代码的话, 我们就会发现把代码调试对是一件很不容易的事情. 下面我们给出一些小提示:

(1) 阅读程序的报错信息. 我们发现很多同学会对于红色的Syntax Error如临大敌, 见到就跑. 下面, 我来举一个例子来说明为什么这是对的:

为什么会出现这样的情况? 这就是因为没有知道什么东西是“错的”. 请观看真理元素的《你能解决这一问题吗》视频, 思考一下为什么错误也是很重要的. 这位UP在B站上的官方中文翻译视频链接是 https://www.bilibili.com/video/BV1Hx41157jV.

(2) 程序出现难以预料的行为时, 在脑子里面模拟执行一遍程序. 告诉自己“程序就是状态机”. 看一看逻辑设计的是不是出错了.

(3) 善于使用调试器. 观察程序在哪一个地方与你预期的执行不相符. 这时候, 往往就意味着可以提问了.

很多问题都可以通过查资料解答. 其中, 有一个很好的途径就是先看一看官方文档. 通常官方文档都有非常详细的解释.

1.1_____________________________________________________________________________     

• 请用Python写一段代码, 它可以模拟图灵机的行为(内存大小不是无限的, 输入输出格式自定).

1.6 C语言引导

一个很好玩的事情是, C语言程序设计的基本语法比Python更加的基础. 而且C基本代码的语义的确定的掌握要花费的精力是远远小于Python的. 它更简单、包袱更少也没有很庞大的工具链。虽然说这相当于 “把你的手脚捆起来编程”但我们通常不需要很复杂的数据结构和代码逻辑因此现代语言特性的好处在大部分时候并不显著。而且用 C 语言还有一些额外的好处

和其他编程语言相比,C 语言特性更容易真正掌握和深入理解.如果你没有学好,用几周的时间补上应该也没问题 C 是一种 “高级的汇编语言”, 你不难在大脑里把 C 出代码翻译成指令序列; 但对于现代语言来说, 这要困难得多. 透过对 C 语言的深入理解, 可以更好地理解现代编程语言的设计动机和实现方法.

–蒋炎岩, 操作系统课程自救指南

所以, 不用惊慌. 我们会来简单介绍一下. 我们会用几个例子来说明一下C语言里面, 一些规则. 但是不用试图记忆, 最好能够跟着敲一遍. 一个比较完好的编译器会在你犯错误的时候(通常情况下犯错是很正常的)给出你提示. 这时候查一查字典就可以解决大多数的情形.

1.6.1 作为不太好用的计算器

作为计算机, 一个很重要的事情是: 如何使用计算机进行比较复杂的算术运算?

比如下面的程序可以告诉我们1+1的值, 并且输出到屏幕.

1#include <cstdio.h> 
2int main(){ 
3  printf("%d\n", 1+1); 
4  return 0; 
5}

这里的“%d”是输出的占位符, 会输出整数. d是digit的简称. 因为整数是由一位一位的数码构成的.

我们来看一看有没有什么有趣的实验:

和Python不同, C会默认地把1.6转化成整数. 这是为什么?

对于实数, 我们可以使用%f输出. f是float的简称, 用来表示这是一个浮点数(也就是实数, 因为小数点会“浮动”).

如果我们在程序的开头加上#include <math.h>, 就可以得到更加多样的数学运算. 如: 要计算1 + 2 _ 5−0.1, 我们就可以在main()里面替换上

1  printf("%.2f\n", 1+2*sqrt(3)/(5-0.1));

1.6.2 变量的引入

我们上面已经可以计算东西了, 可是还是不够劲啊! 如果我们能够从键盘读取输入就更加不错了! 那我们就需要用到scanf了.

输入的东西放在哪里呢? 可以放在小盒子里面. 和Python的“小盒子”不是很相同, 小盒子必须指定变量, 并且指定了之后不能修改盒子的类型. 这也是历史上的因素导致的.

我们来试一试: 比如最简单的a + b问题: 输入两个数, 用程序把它求和, 结果输出出来.

1#include <cstdio.h> 
2int main(){ 
3  int a, b; 
4  scanf("%d%d", &a, &b); 
5  printf("%d\n", a+b); 
6  return 0; 
7}

这时候, 代换的方法仍然起作用. 我们就可以通过交互的情况下得到输入与输出了!

回忆一下小学的时候, 我们总是被要求计算(有点无聊的)圆柱体的表面积. 如果有一个小程序可以帮助当时的我们, 输入半径和高, 自动为我们输出答案, 那样自己就很好了. 于是我们有:

1#include <stdio.h> 
2#include <math.h> 
3int main(){ 
4  const double pi = 3.14; 
5  double r, h, s1, s2, s; 
6  scanf("%lf%lf", &r, &h); 
7  s1 = pi*r*r; 
8  s2 = 2*pi*r*h; 
9  s = s1*2.0 + s2; 
10  printf("Area = %.3f\n", s); 
11  return 0; 
12} 

1.6.3 顺序执行的程序

上面我们编写了很多行的代码, 一个问题是我们的程序是怎样被执行的? 事实上, 这点和Python区别不大–在没有控制执行的情形下都是顺序–从上到下一行一行执行的. 我们可以使用调试器来证明这一点.

例子: 交换变量

我一直一来是不太赞成初学的时候使用Python的语法特性a, b = b, a来做交换变量的. 其原因是可能会让一部分关键的直觉和感受丢失. 比如, 如果我们在C中希望交换两个变量, 怎么办?

如果我们还想像Python那样, 看一看会得到什么:

1$ vim tmp.c 
2 
3#include <bits/stdc++.h> 
4int main(){ 
5    int a = 1, b=2; 
6    a, b = b, a; 
7    printf("a=%d, b=%d", a, b); 
8    return 0; 
9} 
10 
11:!gcc %.c 
12 
13warning: left operand of comma operator has no effect [-Wunused-val 
14ue] 
15    a, b = b, a; 
16    ^ 
17tmp.cpp:4:15: warning: expression result unused [-Wunused-value] 
18    a, b = b, a; 
19              ^ 
202 warnings generated.

哦, 出警报了, 我们看一看运行之后会有什么效果:

1:!./a.out 
2a=1, b=2

诶, 完全没有效果了! 我们回顾上面的警告说这句话没有任何的作用. 这样就解释了这件事. 所以我们要用更加底层的方法来完成.

我们现在有哪些工具呢? (1) 创建一个带有类型的盒子; (2) 为这个盒子装/修改东西; (3) 输入, 输出; (4) 新增一行(句)代码.

1.6.4 循环结构

我们刚刚对于所有的东西这样描述不够劲啊, 毕竟我们还是只是一个一个地完成步骤的说明. 有没有方法完成自动的重复呢? 我们可以用while循环.

那么如果我们希望在某一个地方就不用继续循环下去了, 可以用break; 如果在某一个地方跳过下面的语句继续循环, 那么可以用continue.

与while相仿, 我们还可以用for循环. for的语法比较像∑ . 同样也有break和continue.

1.6.5 方便地创建多个变量: 数组

如果我们想要创建100个变量, 我们可以不用声明a0, a1,a2,... . 我们有可以自动给一个“空间”, 就像int a[100];, 这样就给我们了100个变量的int类型的空间. 如果我们想访问其中的一个(比如第14个), 我们就可以用a[14]来访问. 注意: 数组从0开始编号, 访问a[100]虽然不会有报错信息, 但是这是未定义行为.

我们可以用重复的方法来走遍一个数组里面的所有的部分. 可以和上面的for很方便的对应起来.

当然我们还可以创建多个方括号, 简称为“维度”. 比如b[100][100就可以让我们在一个100 ×100的平面上面读取数据. 比如想访问第二行(从0计数)第三列(从0计数)的就可以写成b[2][3] 当然, 这个维度可以是任意多个的–只要不超出内存限制就没问题.

这证明了一个普遍规则程序帮你写的代码会比你自己手写的更正 确、更可靠。如果改进了生成器例如能生成更好的代码那么每个人 都会受益相反对手写程序的改进并不能改善其他程序。像Yacc和 Lex这样的工具是这一规则的极好例子Unix也提供了许多其他工具。 编写程序的程序总是值得尝试。就像道格·麦基尔罗伊所言“任何你必 须重复做的事都有待自动化。” – Unix传奇: 历史与回忆

Chapter 2
简单数理逻辑[M]

“有两种推广一种没有什么价值, 另一种则是有价值的没什么思想、仅凭唬人的专人术语做推广是很容易做到的颇为困难的是从若干好的素材中提取出一份精致凝练的精品.” —- George Polya

2.1 问题的提出: 为什么要研究简单的数理逻辑

事实上, 很多同学是在学习数学中体会到逻辑的. 但是, 我们当中的很多人会发现: 数学仅仅是为了对付高考这样的考试. 那么希望在这一节以及以后的生活中, 慢慢体会数学带给我们的潜移默化的影响.

这一部分我们建议参看教科书《Reading, Writing, and Proving A Closer Look at Mathematics》的第一章. 我们会在这一章主要概括一下它的主要意思. 由于是为了本科生写的数学课本, 所以句子十分的容易懂. 就当做一个小练习吧.

我们在生活中经常看到这样的对话:

再后来, 我们发现所有的数学问题都可以通过一种“程序化”的手段来解决. 比如, 我们在上一学期学习的Gram-Schmidt正交化矩阵向量的基、解其次线性方程组、求导数等等这样的操作, 都有一系列的明确的步骤.

那么数学仅仅是局限于此吗? 我们来看一看那些伟大的数学家的思想是什么样的:

伟大的数学家、教育学家George Polya专门出了一本书叫做“如何解题”. 于是, 学习数学一个很重要的目的可能就是教会我们:

(1) 如何解决一个问题;

(2) 为什么这样做是对的;

(3) 这个方法什么时候是对的.

在我们遇到一个难以解答的数学问题的时候, 还是回过头来看看George Polya为我们总结的How to solve it的一个list吧.

在解答完这些问题之后, 我们往往会感到满足. 很多时候这也是我们去学习数学的一个很重要的原因.

同样, 顺着南京大学的问题求解课程, 我们同样找到了一本很有趣的书: 《Mathematics: A Discrete Introduction, Second Edition. Edward R. Scheinerman》. 这本书里面详细讲述了我们为什么要学习数学, 以及数学学习带来的享受.

我们先来看存在于大学数学课本的很多重要的元素和栏目.

定义(definition).

定义的结构通常形如: X是一个具有性质Y的东西. 其实, 很多情形下, 我们对于定义的理解是很需要时间的, 一般地, 我们需要关注:

命题(proposition).

命题是我们关于数学对象的一些陈述性的性质. 那些陈述性的性质, 如果命题是真的, 我们就称为真命题(有些难以得到的也称作“定理”); 不知道是不是真的命题一般来称为猜想; 错误的命题通常就称为“错误”.

数学中的命题和物理里面的命题有什么不同点? 比如, 我们说Galileo的速度变换公式在低速的情形下是成立的, 当速度接近光速c的时候, 这个公式就不灵了. 换言之, 我们只是使用了一个近似的表达结果. 但是, 数学的逻辑世界中这样的事情是不会发生的. 我们如果认为一个“命题”是真的, 那么在给定公理体系下, 无论什么情形下, 都是对的.

通常描述一个命题的时候, 我们使用的是若p则q的形式来完成表述. 那么什么叫做“若...则...”呢? 其实它的意思是对于任何一个真的p, q一定是真的. 具体的关系可以参看表格2.1.

关于逻辑连接词, 我们会在后面专门讨论. 下面再来看几个名词. 从上述参考资料中直接摘录了部分结果.

• 结果(result): A modest, generic word for a theorem. There is an air of humility in calling your theorem merely a "result." Both important and unimportant theorems can be called results.
• 事实(fact): A very minor theorem. The statement "6 + 3 = 9" is a fact.
• 命题(proposition): A minor theorem. A proposition is more important or more general than a fact but not as prestigious as a theorem.
• 引理(lemma): A theorem whose main purpose is to help prove another, more important theorem. Some theorems have complicated proofs. Often one can break the job of proving a complicated theorem down into smaller parts. The lemmas are the parts, or tools, used to build the more complicated proof.
• 推论(corollary): A result with a short proof whose main step is the use of another, previously proved theorem.

证明(proof).

这个用的就比较多了. 我们曾经学过很多的方法, 比如反证法, 数学归纳法等.

2.2 开始行动: 符号化逻辑

2.2.1 命题, 真值表和指派

从高中开始, 我们似乎就开始处理各种各样的命题. 下面我们加一层抽象, 这样, 我们就可以把一些繁琐的内容交给计算机完成, 并且在探索的过程中对“什么是有效的推理”有一个更深的理解.

相仿地, 我们试图像第一章探求的“最小的指令集合”一样, 问一问: 我们表达的逻辑, 有没有一些基础的组成部分?

其实命名的关键在于描述中的“和”和“析”. 我们可以查询古汉语字典来获取他们的意思. 并且从中找到一些合理性.

下面, 不妨用Python语言为例, 来看一看这些内容是如何在语言中有所设计的. 需要注意的是, 上表格中的后两个记号并不是新的. 只是我们经常用他们, 于是就变成了一个独立的记号.

如果p那么q的意思是: 如果p是对的, 那么q一定是对的, 如果p是错的, 那么q的真假性不确定. 因此, 我们可以把p →q表示为¬p ∨q–意味着要么p不成立, 要么当p成立的时候q是对的–命题只有对和错, 所以我们就很干净的进行了一次分类讨论.

当且仅当的表示就是“若p则q, 且若q则p”. 本质上还是命题符号之间的“非”, “或”, “与”之间的连接.

1    a=True, b=False, c=True 
2    var = a and b or not c 
3    print(var) 
4  

既然我们规定了符号, 自然要研究一下他们的运算律和运算关系. 什么是运算律?

那么我们说的命题的真假是怎么界定的呢? 通常情况下, 我们需要分类讨论每一个需要讨论的命题的真假, 最后看一看根据公式表达的真假性就行了. 所以, 我们很多时候希望“假定”这些命题的真假, 来考察最终结论的真假, 并且希望从中找到一点规律. 这样做其实有一个更专业的名字叫“真值指派”. 这样我们就可以对于“这句话永远是对的”有一个更加深刻的定义.

像上面的例子, 我们通常会对命题的一些内容的真假进行预先假定, 即: 对于命题进行真值指派.

2.2.4 (真值指派 (v)). 令 S 为一个命题符号的集合. S 上的一个真值指派 v 是一个从 S 到真假值的映射

具体的, 我们可以“指派”命题符号中的各个变量的值, 然后映射到真或假两种情况.

我们可以借助这个想法为我们上面定义的为我们上面的逻辑连接词做一个精确的数学定义. 叫做“真值表”.

比如, 我们有“非”的真值表(表2.3)、“和”的真值表(表2.4)、“或”真值表(表2.5)、“若,则”真值表((表2.6)以及“当且仅当”的真值表(表2.7)

事实上, 我们在小学很可能通过列举的方法完成求解. 但是现在我们可以用真值表列举. 甚至可以把公式写出来进行推演!

比如一个命题的否定的否定还是原命题本身一样, 我们可以定义一些“公式”. 比如

p̸与p等价.首先我们定义一下什么叫“满足′′,“蕴含′′或者“等价′′.

很多时候一些逻辑表达式看上去就是废话. 比如“如果我后天知道了考试的成绩, 那我明天就知道了”. 数学上面对这类问题有一个定义叫做“重言蕴含”.

反之, 就是永远都不能成立的矛盾的形式.

我们可以认为是语义上的, ⊢是 偏向语法上的推演.

对于命题公式而言, 如果对于相同的变量输入, 外部观测的结果的真假相同, 我们就称为命题的等价.

根据上面的定义, 我们可以证明:

2.2.2 命题逻辑的化简

在上面我们发现了有很多的“废话”, 但是, 当看上去是“废话”的东西堆多堆复杂的时候, 那么它就不是显然的. 这就需要一些推理规律来帮助我们联通看上去毫不相干的逻辑符号.

经过我们的探讨, 我们就希望把一些最基本的规律写出来:

利用这些内容我们可以构造一些等价的命题:

这些为什么有用呢? 考虑有一天你在求解一个数学问题, 其中你想把一个命题否定掉, 比如

其中一个很重要的手段就是通过上面的这些重言式的替换. 就像在学习三角函数的时候使用三角恒等式替换一样.

下面我们来看一个比较有趣的逻辑代数推演的例子:

: 我们可以将上述条件用以下逻辑表达式来表示:

先看前两个括号(上述式子红色的部分), 以连接两个式子中间的∧展开(下式红色符号), 我们有

根据已知条件, p₁ ∧p₄,p₂ ∧p₄,p₁ ∧p₃均为假的, 所以上述式子是

与后面的((p₅ ∧¬p₆) ∨(¬p₅ ∧p₆))进行∧操作, 也就是有

所以我们知道: p₂,p₃,p₆是对的. #

事实上, 我们能这样做是因为有带入定理帮助我们.

2.2.3 化简的“目标”之一: 范式

范式的意思是“规范的形式”. 那么, 这些内容化简到最后有没有一个目标呢? 其实是有的. 任何一个命题都可以写成“合取范式(CNF)”或者“析取范式(DNF)”的形式. 下面给出形如这样的式子的定义:

2.2.12 (合取范式 (Conjunctive Normal Form)). 我们称公式 α 是合取范式, 如果它形如

其中, 每个 β_i 都形如

并且 β_ij 或是一个命题符号, 或者命题符号的否定.

2.2.13 (析取范式 (Disjunctive Normal Form)). 我们称公式 α 是析取范式, 如果它形如

其中, 每个 β_i 都形如

并且 β_ij 或是一个命题符号, 或者命题符号的否定.

. (Copied from https://planetmath.org/everypropositionisequivalenttoapropositionindnf ) Any two propositions are equivalent if and only if they determine the same truth function. Therefore, if one can exhibit a mapping which assigns to a given truth function a proposition in disjunctive normal form such that the truth function f of this proposition is f, the theorem follows immediately.

Let n denote the number of arguments f takes. Define

For every X ∈{T,F}, define L_i(x) = {T,F}ⁿ →{T,F} as follows:

Then, we claim that

On the one hand, suppose that f(Y ) = T for a certain Y ∈{T,F}ⁿ, By definition of V (f), we have Y ∈V (f). By definition of L_i, we have

In either case, L_i(Y )(Y ) = T, since a conjunction equals T if each term of the conjunction equals T, it follows that∨ _i=1ⁿL _i(Y )(Y ) = T, Finally, since a disjunction equals T if and only if there exists a term which equals T, it follows the right hand side equals equals T when the left-hand side equals T.

On the one hand, suppose that V (Y ) + F for a certain Y ∈{T,F}. Let X be any element of V (f). Since Y V (f), there must exist an index i such that X_i≠Y _i. For this choice of i, Y _i = ¬X_i, Then we have

In either case,L_i(X)(Y ) = F, Since a conjunction equals F if and only if there exists a term which evaluates to F, it follows that ∨ _i=1ⁿ = F for all X ∈V (f). Since a disjunction equals if and only if each term of the conjunction equals F, it follows that the right hand side equals equals Fwhen the left-hand side equals F. □

上面的只是给了我们一个正确性证明, 但是并没有告诉我们如何把一个式子化为合取范式或者析取范式. 一般的, 我们有如下的方法:

(1)用¬,∧,∨代替→,↔;

(2)用双重否定律, 消去律去掉多余的否定连接词, 运用De Morgan律将否定连接词内移.

(3) 利用分配率, 结合律, 幂等律整理得到.

实际上, 在上面的三个人从哪里来的例子中, 我们就用到了这样的想法.

下面的这个回答来源于StackExchange上面的回答[?], 简要概括如下:

逻辑公式中的变量输入可以以复杂的方式混在一起. 如果公式采用CNF或DNF变量就更加分离从而更容易看出表达式何时成立. 比如, 要检查CNF是否成立只需逐个检查每个子句有一个是假的整个都是假的. DNF也类似: 逐个检查子句并在找到一个为真的子句时停止, 整个句子都是真的.

很多时候真值表会带来很多的麻烦: 意味着穷举和非常麻烦的事情. 有了CNF与DNF以后, 我们不必从真值表开始枚举, 可以通过操作表达式来形式地构造标准形式. 在某些情况下可能可以更方便一些.

下面我们来看一看合取范式与析取范式的一些性质.

我们发现, 在合取范式中, 只要有一个条件是假的, 那么整个命题都是假的. 在析取范式中, 只要有一个条件是真的, 那么这个命题是真的. 特别地, 如果每个命题变元或其否定恰好只有一个出现过并且只出现了一次, 那么我们说这个合取范式为极小项(析取范式为极大项). 比如我们有两个变量, 那么就可以有如下的四个逻辑表达式:

这样就保证了我们除了枚举输入的命题之外, 我们还可以枚举极小项, 极大项, 从两方面来观察命题的真假. 比如. 还是上面的两个命题符号的情形, 对于合取范式和析取范式, 分别有表2.2.3 以及表2.2.3的情形.

我们发现每一个赋值对应一个取值为的极项, 每个极项的赋值是唯一的. 并且没有等价的两个极项, 任何两个不同的极项取必为真, 极的否定是极, 所有的极项的取为永假公式.

如果我们把合取范式和析取范式里面的内容都变为极小项/极大项的时候, 我们就可以得到更标准, 更易于处理的内容. 通常称为主合(析)取范式.

2.1_____________________________________________________________________________     

1. 

符号化下列命题:

i. 虽然他的程序编写得很短小但运行效率不高.

ii. 控制台打字机既可作为输入设备, 又可作为输出设备.

iii. 如果你不多刷算法题且刷题时不讲方法 那么面试时可能难于通过能力测试.

iv. 若a和b是偶数, 则a + b是偶数.

v. 停机的原因在于语法错误或程序逻辑错误.

vi. 如果公用事业费用增加或者增加基金的要求被否定, 那么, 当且仅当现有计算机设备不适用, 才需购买一台新计算机.

vii. 1 is the factorial of 0, and u is the factorial of x+1 if v is the factorial of x and u is v times.

2. 

设 P: 数理逻辑很有趣; Q: 作业很难; R: 这门课程使人喜欢. 将下列句子符号化:

i. 数理逻辑很有趣, 并且作业很难.

ii. 数理逻辑无趣, 作业也不难, 那么这门课程就不会使人喜欢.

iii. 数理逻辑很有趣, 作业也不难, 那么这门课程就会使人喜欢.

iv. 数理逻辑无趣, 作业也不难, 而且这门课程也不使人喜欢.

v. 数理逻辑很有趣意味着作业很难, 反之亦然.

vi. 或者数理逻辑很有趣, 或者作业很难, 并且两者恰具其一.

3. 

构造如下命题公式真值表并判断其类型:

i. ((P →Q) ∧(Q →R)) →(P →R).

ii. (P →Q) ↔(Q →P).

iii. (P ∨Q) ∧(¬P ∨Q) ∧(P ∧¬Q) ∧(¬P ∧¬Q).

iv. (P ∨Q) ∨(¬P ∨Q) ∨(P ∧¬Q) ∨(¬P ∧¬Q).

2.3 命题推演的真象: 命题的推演

我们发现, 蕴含词的逻辑永真式和我们经常所做的推理有很好的联系. 具体地, 如果α →β, 那么如果α成立, 可以推导出β为真.

同样的, 如果假设α成立, 只要经过合理的推导可以推导出β为真, 那么这个规则就是成立的.

我们在推理时多半用“因为...所以...”, 那么前面的什么概念能起关键作用呢?

一般而言, 逻辑推理有一系列的假设前提A₁,A₂,,A_n, 有一个结论B, 什么是正确的推理呢? 形式化地, 对前提与结论所涉及的逻辑变量任意赋值, 如果任意的A_i均为这真, 它们的合取式的值当然也为真, 那么B必为真.

形式化的, 我们就说: 这样的推理是正确的.

需要注意的是, ⇒是一个关系, 这是一个不可计算的公式.

所以这就解释了我们为什么经常使用的因为...所以...是合理的了. 比如(p ∧(p ∧q)) →q是永真的, 那么就可以有三段论这样的合理的推理过程了.

我们经常对于知识研究一些规律. 比如在逻辑公式很长的时候, 逐个枚举是十分低效率的. 比如, 如果有200个命题符号的逻辑公式, 用计算机枚举则需要2²⁰⁰种情况. 用Python的强大的计算器可以知道, 需要核验的情况是一个61位数.

既然要推理, 我们就要有推理的定律和推理的推理的规则. 正如前面说的程序语言的语法和语义类似.

经过总结归纳, 我们有如下的推理定律:

一个学习的很好的方法是举一些例子. 我们可以用上面的符号翻译成具体的例子. 不用太过于拘束.

以最后一个例子为例, 有:

推理规则可以使用真值表验证. 除此之外, 我们还需要推理定律: 也就是需要完成什么样的变换. 我们有三条规则.

(1) Premise规则: 前提引用. 如果推理的时候引入了前提集合中的一个前提, 那么称为使用了P规则;

(2) Transformation规则: 逻辑结果引用的规则. 在推理过程中, 如果引入推理过程中某个产生的中间结果, 那么称使用了T规则;

(3) Conclusion premise规则: 附加前提规则. 在推理过程中, 如果逻辑结果为一个含有蕴含→的式子, 那么把它的前提条件作为假设引入, 就是用了CP规则. 所有引入的假设最终必须被“释放” (discharged) 所谓释放, 其实就是在使用假设α作为假设的前提下推出了β, 最后要写成α →β的形式. 这就是假设的释放.

我们来推导一下I₆.

对于I₉, 我们可以先把G是对的引入集合, 然后最后推理得到I的时候, 为了说明它的正确性, 就需要使用CP规则.

在上面我们做的研究中, 我们会发现很多东西相当的机械化. 于是, 在有机械化的内容出现的时候, 计算机就有用了. 所以, 我们希望找到一种方法, 使得计算机可以自动地推理我们的命题. 在1965年, J.A. Robinson发现了消解原理: 它的原理是规则I₇. 具体的有:

我们经过消解的方法, 立即可以得到一个很有“自动化”意思的定理:

2.2_____________________________________________________________________________     

1. 

请写一个Python程序, 输入一个命题公式(形式自己指定), 输出一个填写好的真值表的填写(形式同样自己指定). 提示: 一开始不要搞得太复杂. 比如只接受五个逻辑连接词的某两个, 然后慢慢扩展.

2. 

请写出一个Python程序, 使得我们可以把一个命题问题化为合取范式.

2.4 变得更加严谨: 形式化推理系统

经过我们前面的一些探索, 我们就有资本忘记以前学过的所有的东西了. 现在, 让我们来形式化这一切–用公理和原则来进行推演. 以前的内容带来的直觉会对我们在形式系统里面操作产生引导的作用. 下面我们来看一些规则:

如下是若干个可以完成任何规则的: 其中像分数线一样的上方表示的是前提, 下方表示的是结论. 有时候我们可以把它写成一行就成了{前提}⊢结论.

• Conjunction: ;
• Simplification: and ;
• Addition: and ;
• Disjunctive Syllogism: and ;
• Modus Pones: ;
• Conditional Proof: ;
• Double Negation: ;
• Contradiction: ;
• Indirect proof:

我们只用上面的一些内容就可以得到更加复杂的推理规则: 比如我们有前提A →B,¬A →A, 尝试推出结论B. 我们可以用上面的推理规则这样推理:

Modus Tollens: mode that denies

Proof by cases

Hypothetical Syllogism

Constructive Dilemma

2.5 表达更丰富的内容: 谓词 部分与整体的关系

我们发现命题逻辑无法表达部分与整体的关系. 例如:

我们发现以前学过的东西仅仅能应对很基本的内容. 比如任意, 存在无法表示. 下面我们形式化的先来说说什么是任意和存在. 这些是对于一类类似于变元的内容的性质的总体描述. 因此, 我们首先定义什么是谓词

很多时候, 我们会泛指一些很笼统的概念, 比如“人”. 也有时候我们会举一些明确的个体, 比如“蒋炎岩老师(图2.3)”. 这时候我们就需要区分“个体变量”(通常是泛指)和“个体常量”(通常是特指).

这样子, 我们就可以更加方便的定义量词(qualifier)了.

上面的内容一个很重要的地方在于引入了变元. 例如, 在函数符号和谓词符号中, 变元的引入使得我们要讨论的事情变得更加多了.

这下子, 我们就可以定义谓词逻辑的构成了.

和普通公式一样, 谓词公式也是由一项一项构成的.

我们来举一些例子:

有了坐标系, 辩证法进入了数学. 有了坐标系, 运动进入了数学. –Engels

这里的“运动”, “坐标系”只是变量引入数学的结果. 自然, 这让我们探索的内容更加的丰富, 同时也更加容易犯错了. 比如, 我们很多时候喜欢对变量做替换. 但是, 下面的代换显然是错的:

因为“中国最大的城市”这个字符串有7个汉字构成. 这就警告我们要在变量代换的时候要格外小心. 那么, 变量有哪些类型呢?

在公式∀x.P(x,y) ∨∃y.R(x,y)中, 根据量词作用域的定义, ∀x的作用域是P(x,y), 因此x受到了∀x的约束, 从而把这个变元称作约束变元. 然而这个的y没有受到∀x的约束, 所以称为自由变元.

可能由于重名的原因, 我们发现同样一个字母既可以表示自由变元, 又可以表示约束变元, 这样就很不利于我们问题的分析. 为此, 我们给出变元的代换规则, 可以让每一个符号各司其职.

上面的两条关系在带入之前和带入之后都没有改变原有命题之间的约束关系. 但是使用(2)之后, 公式的含义就发生了变化, 但是推理是成立的–比如选择常量带入进去, 那么命题就退化成了一个特化的情况了.

没有自由变量的公式有着很好的性质–他的真值表就可以确定了. 我们把这样的内容叫做闭式.

在命题逻辑中, 我们运用了真值指派的方式来了解了这个命题的真值情况, 那么这里, 我们能不能也用类似的方法“解释”一个命题逻辑的含义呢?

2.6 尝试解释谓词公式

2.6.1 谓词公式, 解释, 等价表示

谓词公式的解释远远没有我们想象的那么简单! 在不同的数学结构中, 同一个谓词公式很可能有不同的结果!

𝔼xample:

考虑

α 在数学结构𝒰= ℚ中是真的, 但是在数学结构𝒰= ℝ中是假的.

从上面的例子, 我们可以看出来, 要想解释清楚一个谓词逻辑的公式, 我们需要考虑对象所处的数学空间来下结论. 也就是一个表达式的语义大致取决于:

• 对量词论域(universe)的解释, 限定个体范围;
• 对常数符号、函数符号、谓词符号的解释;
• 对自由变元的解释 (赋值函数 s).

也就是这种“解释”将公式映射到一个数学结构 𝒰上, 这决定了该公式的语义.

什么是解释呢? 更正式一点, 我们认为一个公式的解释由下列四部分组成:

因此, 我们给出在一个特定的数学结构上“满足”的定义.

2.6.2 ((𝒰,s)α). 𝒰 与 s 满足公式 α:

• 将α中的常数符号、函数符号、谓词符号按照结构 𝒰 进行解释,
• 将量词的论域限制在集合 |𝒰|上,
• 将自由变元 x 解释为 s(x),
• 这样就将公式 α 翻译成了某个数学领域中的命题,
• 然后, 使用数学领域知识我们知道该命题成立

同样的, 我们也可以说明语义蕴含在谓词逻辑中的定义:

2.6.3 (语义蕴含 (Logically Imply)). 令 Σ 为一个公式集, α 为一个公式.
Σ 语义蕴含 α, 记为 Σα, 如果每个满足Σ中所有公式的结构𝒰与赋值s都满足α. 记作

当然, 我们当然希望为公式能够在等价的意义下能够完成推理. 所以我们需要首先研究什么样的公式在怎样的情形下是等价的.

注意到全称量词对于合取式子是可以分配的, 存在量词对于析取式子是可以分配的. 我们有时候是可以通过这个来简化计算.

2.7 谓词公式的标准形

仿照命题公式, 我们也想看一看, 谓词公式最后有没有一个统一的形式, 使得我们的表达和交流更加的方便.

当然, 命题逻辑公式有与之等值的范式. 谓词逻辑公式也有范式, 但不是所有范式都与原公式等值, 有一些可能条件会相对弱化一些, 下面介绍两个形式.

我们想, 任何的内容是不是都可以把所有的量词提到前面, 后面的内容就没有量词记号了. 这就会给我们的证明和讨论带来很好的方法.

前束范式

2.7.1 (前束范式). 具有形式

的谓词公式称为前束范式(prenex normal form), 其中Q_i为量词, M为不含量词的公式.

那么这个内容是不是存在的呢? 是不是唯一的呢? 实际上, 这是存在的, 但是不是唯一的.

我们发现, 前束范式虽然能够把两次放在最前端, 但是不唯一.

Skolem范式

要想唯一, 就要牺牲一点“等价性”. 这个意思就是说得到一个比原来命题结果要弱一些的结果. 这样, 我们就可以得到Skolem范式.

2.7.2. 设公式

是一个前束合取范式, 按照从左往右的顺序去掉G中存在的量词, 若Q_i是存在量词, 且i = 1, 则直接用个体常量代替M中的所有的x₁, 并且在G中删除Q₁x₁. 若i > 1,Q₁,Q₂,,Q_i−1都是全称量词, 则在G中使用一个未使用过的函数符号, 如f, 并且用f(x₁,x₂,,x_i−1)替换G中的所有的x_i, 然后删去Q_ix_i. 重复这个过程, 直到G中没有量词为止.

𝔼xample:

求

的Skolem范式.

:

现在消去存在y, 有

然后消去存在z, 有

#

2.8 谓词逻辑的推理要求

相比于命题逻辑, 谓词逻辑要求的内容就多了不少了. 具体的, 我们可以把全称量词, 特称量词替换掉. 或者把它们替换掉为一个特殊的命题. 这样我们就可以把谓词逻辑转化为谓词逻辑了. 因此, 我们有如下的简化的一节逻辑的推理原则.

2.8.1 (“任意”符号消去). ∀-eliminating.

where α is free for x in α.

The symbol α[t∕x] means substituting all the occurrences t in α to x.

2.8.2 (“任意”符号的引入). ∀-introducing.

	[t]	引入变量t
		经过一系列推理
	α[t∕x]	得到的表达式所有的x都是t
	⊢∀x.α	就可以推出任意了

where α is free for x in α.

The symbol α[t∕x] means substituting all the occurrences t in α to x.

下面我们来举一个例子来看看:

:

#

我们再来看一个例子:

解答如下:

:

	∀x.(P(x) →Q(x))	(P)
	∀x.P(x)	(P)
		(引人变量 )
	P →Q	(∀-elim ,(1),(3))
	P	(∀-elim, ,(2),(3))
	Q	(→ -elim ,(4),(5))
	∀x.Q(x)	(∀-intro ,(3) −(6))

#

上面我们介绍了如何把含有任意的内容干掉或者引入. 下面我们来看一下关于存在的一些例子:

2.8.3 (存在符号的引入). ∃-intro:

where t is free for α.

这个定理的意思是: 如果α对于某个项成立, 那么∃x.α 成立.

这里的没有被约束, 我们来举一个例子: P(c) ⊢ ∃x.P(x),c是任意的常元符号: 这样是可以的, 但是注意下面的例子: ∀y.(y = y)⊬∃x.∀y.(x = y)(y is not free for x in α)

存在符号也可以消去. 第一种方式就是上面的反方向的形式. 就是

2.8.4 (存在符号消去). ∃-elim:

where t is free for x in α.

还有一种我们以前经常用到的方法. 我们在这里来看一下, 这也是存在量词消去的一种方法.

2.8.5 (存在量词的消去(2)). ∃-elim:

这个内容说的是什么呢? 考虑我们在高中做题的时候, 对于存在性问题, 我们一般是假设这个存在, 经过一系列推导之后发现确实存在, 于是就说明了这个东西确实是存在的. 更加形式化的就是: 假设x₀使得α成立, 如果从α[x₀∕x]可以推导出β, 那么α从可以推导出β.

我们来看个简单的例子:

:

	∀x.(P(x) →Q(x))	( 前提 )
	∃x.P(x)	(前提 )
		( 引入变量与假设 )
	P →Q	(∀-elim, (1),(3))
	Q	(→ -elim, (3),(4))
	∃x.Q(x)	(∃-intro ,(5))
	∃x.Q(x)	(∃-elim, (2),(3) −(6))

#

:

	∃x.P(x)	( 前提 )
	∀x.∀y.(P(x) →Q(y))	( 前提 )
		( 引入变量与假设 )
	∀y.	(∀-elim, (2),(3))
		( 引入变量 )
	P →Q	(∀-elim, (4), (5))
	Q	(→ -elim, (3),(6))
	Q	(∃-elim, (1), (3) −(7))
	∀y.Q(y)	(∀-intro, (5) −(8))

#

2.9 常见的证明方法

著名的推理规则: 三段论

上一次我们说到了因为(p ∧(p →q)) →q是永真式, 因此我们有了(p ∧(p →q)) ⇒q. 三段论的内容被叫做Modus Ponens.

Modus Ponens来源于古拉丁文, 翻译成英语就是 method of putting by placing. 也就是说, 在推理的过程中, 如果p是真的, p →q, 那么q是可以被接受的.

为什么呢? 因为如果有含蕴含词的永真式(A₁ ∧A₂ ∧∧A_n) →B, 利用推理规则, 我们就能从前提条件A₁ ∧A₂ ∧∧A_n推出B, 以及A₁ →(A₂ →... →(A_k →B)

当且仅当的证明

在中学, 我们学习了充分条件, 必要条件, 以及四种命题.

先对充要条件做描述: 充要条件是(P →Q) ∧(Q →P) →(P ↔Q)

比如来看下面的问题:

充分条件很容易说明. 但是必要条件如何说明呢? 我们高中知道命题和逆否命题真假一致, 能从命题逻辑的角度说明吗?

其实很容易. (P →Q) ↔(¬Q →¬P)是永真式就行了. 我们就有更加公理化的方法完成了证明.

我们发现结论是析取式子(或), 那么我们应该如何证明? 我们考察永真式(P ∧Q) ↔(¬P ∧Q);(P ∧Q),¬P ⇒Q. 为之构造一个合理的语言描述, 然后翻译成符号语言看上去是很好的一个方法.

反证法

Hardy说证明是无理数是最漂亮的证明之一. 其中用了反证法. 不妨自己写出一个证明.

反证法之所以能成立, 是因为¬A ⇒C, ¬A ⇒¬C, 必然有C ∧C ⇒False. 根据上述的内容, (p →q) ∧(¬q)) →¬p, 所以化简得到¬¬A = A.

基于数学对象结构的证明方法: 数学归纳法

在分牌的时候, 我们可以使用这个小魔术:

(1) 将一副纸牌按照红黑相间的模式排好;

(2) 按照传统方式洗一次牌, 分牌时两叠牌显出的两张颜色互异;

(3) 你能做到将牌放在背后(自己看不见), 却能保证每次抽出两张牌, 始终是一红一黑吗?

这个过程的证明可以使用数学归纳法描述. 回忆一下数学归纳法的常见过程. (1) 归纳奠基; (2) 归纳假设; (3)结论.

我们现在进行一个灵魂拷问:

事实上, 其合理性来自证明对象结构的定义.

对于自然数的归纳正确性, 我们还需要良序原理(well-ordering principle). 可能需要很多的背景知识, 在这里仅仅给出基本的定义.