Project 6: Logic & Reasoning

Due: 12.31 .

Part 1: 符号推理: 好人还是坏人?

在符号推理中, 前人已经开发出多种自动化的符号推理工具, 可以说, 在某些受限的符号逻辑系统(如命题逻辑)中, 从一个形式化的逻辑表达式中自动推理出结论, 已有成熟的自动化工具和方法, 可以视为在实践中"已解决"的问题. 然而, 如何从复杂的系统中提取出符号化的表达式依然是一个难以解决的问题. 在本次实验中, 同学们需要尝试将以下逻辑问题转化为命题逻辑, 并交由一个model checker进行自动化求解.

背景知识

在1978年, 逻辑学家Raymond Sumullyan出版了"What is the name of this book?", 其中有许多有趣的逻辑问题(真的十分值得在闲暇时间读一读, 可能对下学期的数理逻辑有所帮助). 其中有一类问题叫"Knights or Knaves"(好人或坏人). 在一个"好人或坏人"谜题中, 每个人要么是好人要么是坏人, 且好人总是说真话, 坏人总是说假话. 玩家需要做的就是从几个人说的话中推断出他们各自的身份.

举个例子

若A说: "我既是好人也是坏人". 然而已知一个人要么是好人要么是坏人. 因此A说的话一定是假话, 故A是坏人.

当然, 上面这个问题比较简单, 且我也并不认为更复杂的问题会难到聪明的同学们. 因此, 我们这次作业的任务并不是简单的推出答案, 而是将以上问题形式化为一个命题逻辑表达式, 并交由一个自动化的model checker来推算答案. 若是推出的答案和同学们推出的答案一致, 就可以认为同学们把这道题做对啦!

实验环境

本次实验仅包含两个文件: knights

knights/
├── logic.py  # 实现了model checker, 以及命题逻辑的各类运算
└── puzzle.py # 同学们需要完成的内容

logic.py 中实现了本次实验所有需要用到的功能函数, 包括自动推算答案的model checker(强烈建议同学们去查看一下实现, 可能对你们有帮助), 以及命题逻辑相关的类型声明. 在本次实验中, 你不应该修改这个文件中的内容.

你需要在 puzzle.py 中完成对每道题的形式化. 注意, 你的命题逻辑表达式中只应该包含文件中所定义的六个原子命题:

AKnight = Symbol("A is a Knight")
AKnave = Symbol("A is a Knave")
BKnight = Symbol("B is a Knight")
BKnave = Symbol("B is a Knave")
CKnight = Symbol("C is a Knight")
CKnave = Symbol("C is a Knave")

且你不应该修改main函数中的代码.

同时, 本次实验不需要用到任何外部库.

题目描述

Puzzle 0

A说: "我既是好人也是坏人"

请问A是什么?

Puzzle 1

A说: "我是坏人, 但是B是好人"

请问A和B分别是什么?

Puzzle 2

A说: "我和B都是坏人"

请问A和B分别是什么?

Puzzle 3

A说: "我们是同样的人"

B说: "我们才不是同样的人呢"

请问A和B分别是什么?

Puzzle 4

A说了什么你没有听见

B说: "A说: '我是坏人'"

B说: "C是坏人"

C说: "A是好人"

请问A, B和C分别是什么?

Puzzle 5

我问A: "你们之中有多少个好人呀?"

A说了啥我没听见

B说: "A说: '只有一个'"

C说: "B瞎说"

请问B和C分别是什么?

实验提示

我知道最好的实验提示是给同学们提供一道题的例子, 但是我有些担心会将同学们的思路限制住. 毕竟形式化的有趣之处就在于不同的人会将同一个问题形式化成不同的样子.

这个实验中, 你本质上在做的事情是将问题中的信息(包括游戏规则中隐含的信息和角色说的信息)形式化为命题逻辑表达式. 你应该尝试最直白的翻译, 而不进行任何的逻辑推理.

如果运行程序没有输出, 你应该考虑你的形式化中是否遗漏了一些信息.

在Puzzle 0中, 若是填入

knowledge0 = AKnave

即可得到正确结果, 但是这并不是这道题的意图, 因此请不要这样做.

P.S. 搞清楚Puzzle 4中B说的两句话的区别也许会对你们有帮助.

Part 2: 符号推理: Wumpus World

Wumpus World是人工智能Agent的典型例子, 涉及推理, 知识表示和规划. 在这个问题中, 智能体需要根据已有的推理规则, 不断探索世界, 学习新的知识, 以求能够安全地找到宝藏. 在本次实验中, 同学们需要使用Prolog编写一个智能体, 来进行Wumpus World的游戏.

Prolog 教程

在进行本次实验前, 需要配置Prolog环境. 本次实验是使用SWI-Prolog设计的.

Prolog不是一个软件设计语言, 而是专门用来解决逻辑问题的.

尽管Prolog曾被视为未来主流编程语言的有力候选, 但随着技术演进, 其应用范围逐渐缩小, 如今已较少被使用. 与此同时, 现代语言如Lean 4在设计上也融入了对逻辑推理的支持, 为逻辑编程提供了新的替代路径.

本次实验中的重点并非掌握一门新的编程语言, 而是体会这种编程范式. 因此大家不必(但是推荐)纠结于语言的实现方式及语法细节.

Prolog就是"PROgramming in LOGic"的意思, 只要给出事实和规则, 它会自动分析其中的逻辑关系, 进行逻辑运算, 并允许用户查询.

SWI-Prolog安装

在官网下载二进制安装程序进行安装, 注意安装过程中勾选添加至Path中. 没有勾选也没关系, 只需要将 \path\to\swipl\bin 自行添加到环境变量中即可.

线上环境

同时, Prolog(以及其他许多函数式编程语言)有现成的线上环境. 虽然Prolog环境配置也并不复杂, 但是同学们也可以在线上环境完成实验.

Prolog教程

常量与变量

在Prolog中, 小写字母开头的符号就是常量(我认为理解为符号更好), 大写字母开头的符号就是变量

?- write(abc).
abc
true.

?- write(Abc).
_3386 % 这里实质上就是任意一个值
true.
关系和属性

这两者本质都是谓词, 描述一个对象的属性或多个对象之间的关系. 两个对象之间的关系, 使用括号表示.

friend(jack, peter). % 声明jack和peter是朋友
friend(peter, jack). % 声明peter和jack是朋友, 注意, 这两者不天然等价

male(peter). % 声明peter是男的
规则

规则是推理的方法, 从一些谓词中推出另一个谓词.

friend(X, Y) :- friend(Y, X). % 朋友交换律
friend(x, y) :- friend(y, x). % 思考: 这两者有什么区别?

mother(X, Y) :- % 复杂一些的规则定义
    child(Y, X),
    female(X).
查询

已有以下条件:

friend(john, julia).
friend(john, jack).
friend(julia, sam).
friend(julia, molly).

friend(X, Y) :- friend(Y, X).

可以查询以下信息:

?- friend(john, jack).
?- friend(john, sam).

?- friend(julia, X).

在你配置好的环境中跑一下这些查询, 并理解为什么会有这些输出吧.

分支(模式匹配)

Prolog中的分支更加类似函数式编程语言中的模式匹配.

(
    cond1 ->
        suite1
    ;cond 2 ->
        suite2
    ;suite3
).

在Prolog中, 递归函数可以这么写:

fact(N, A) :-
    (
        N =:= 0 -> A = 1
    ;
        M is N - 1,
        fact(M, NewA),
        A is N * NewA
    ).

% --------- 也可以这么写 ---------

fact(0, 1).
fact(N, A) :- 
    M is N - 1,
    fact(M, NewA),
    A is N * NewA.

以上两者的区别大家可以自行搜索或询问AI工具, 在实现中, 更推荐大家按照第二种写法.

Wumpus World

Wumpus World由$4\times 4$的网格组成, 共有16个房间, Agent从房间$(1, 1)$开始, 目标是找到宝藏, 并且避开陷坑和Wumpus这样的危险.

Wumpus World

环境(Environment):

  • 世界由$4\times 4$的网格组成, 共有16个房间
  • 与Wumpus相邻(非对角线相邻)的房间会有臭味(Stench)
  • 与陷坑相邻(非对角线相邻)的房间会有微风(Breeze)
  • 有宝藏的房间会闪闪发光(Glitter)
  • Agent的初始位置在$(1, 1)$
  • Wumpus, 陷坑, 宝藏会出现在$(1, 1)$之外的任何地方

Agent能进行的动作(Action):

  • 移动: Agent每次只能移动到相邻的房间

Agent能够感受到以下信息(Perception)::

  • 微风(Breeze): 在陷坑相邻的格子中会有微风
  • 臭味(Stench): 在Wumpus相邻的格子中会有臭味
  • 闪光(Glitter): 在宝藏的格子中会有闪光

实现提示

本次实验框架中, 你需要完成基于客观环境对于Agent的感官反馈(Environment -> Perception)逻辑, 还需要根据感官完成对知识库的丰富(Perception -> Knowledge Base), 以及根据知识库进行对下一步的推理(`askKB`). 值得注意的是, 目前的框架代码中, 只定义了环境相关的谓词, 并没有定义知识库相关的谓词, 这是同学们需要自行设计补充的. 同时, 在对下一步的推理(`askKB`)过程中, 不应该用到任何环境相关的谓词.

新添加的谓词不要忘了初始化哦~

实验代码可见：wumpus.pl.

这次实验中大部分代码都可以修改, 除了 step_pre 和 take_steps , 但是最后一定至少要实现我们所提供的默认世界.

提交要求

请将wumpus.pl和puzzle.py合并为一个压缩包, 并命名为 学号.zip 提交.