Homework 16: SAT_逻辑学满足性问题_美国留学生作业答案_assignment answer

Python海龟宝典含200多个原创的用turtle模块制作的创意程序,原名《Python趣味编程200例》。准备参加全国创意编程与智能设计大赛的同学们可以用来做参考。

本人已完成此作业,需要请联系本人微信pythonxia,以下是问题描述。

Let 𝑝1,𝑝2,p1,p2,… be propositional variables. A SAT problem, represented in conjunctive normal form, consists in a conjunction of disjunctions of propositional variables and their complements, such as

(𝑝1𝑝¯2𝑝3)(𝑝2𝑝5).(p1∨p¯2∨p3)∧(p2∨p5).

We call each conjuct a clause; in the above example, we have two clauses, 𝑐1=𝑝1𝑝¯2𝑝3c1=p1∨p¯2∨p3 and 𝑐2=𝑝2𝑝5c2=p2∨p5. The disjuncts in a clause are called literals: for example, the first clause 𝑐1=𝑝1𝑝¯2𝑝3c1=p1∨p¯2∨p3 contains the literals 𝑝1p1𝑝¯2p¯2, and 𝑝3p3.

The satisfiability question is: can we find a truth assignment to the variables that makes the expression true? In the above case, the answer is yes: we can take:

𝑝1=𝑇𝑟𝑢𝑒,𝑝5=𝑇𝑟𝑢𝑒p1=True,p5=True

and any value for 𝑝2,𝑝3p2,p3.

SAT representation

To represent an instance of SAT, we represent literals, clauses, and the overall expression, as follows.

Literals. We represent the literal 𝑝𝑘pk via the positive integer 𝑘k, and the literal 𝑝¯𝑘p¯k via the negative integer 𝑘−k.

Clauses. We represent a clause via the set of integers representing the clause literals.
For instance, we represent the clause 𝑝1𝑝¯3𝑝4p1∨p¯3∨p4 via the set {1,3,4}{1,−3,4}.

SAT problem. We represent a SAT problem (again, in conjunctive normal form) via the set consisting in the representation of its clauses. For instance, the problem

(𝑝1𝑝¯2𝑝3)(𝑝2𝑝5)(p1∨p¯2∨p3)∧(p2∨p5)

is represented by the set of sets:

{{1,2,3},{2,5}}.{{1,−2,3},{2,5}}.

There are various operations that we need to do on clauses, and on the overall SAT problem, to solve it. Thus, we encapsulate both clauses, and the SAT problem, in python classes, so we can associate the operations along with the representations.

Clauses

We first define an auxiliary function, which tells us whether a set contains both an integer and its negative. This will be used, for instance, to detect whether a clause contains both a literal and its complement.

Truth assignments

We are seeking a truth assignment for the propositional variables that makes the expression true, and so, that makes each clause true.

We represent the truth assignment that assigns True to 𝑝𝑘pk via the integer 𝑘k, and the truth assignment that assigns False to 𝑝𝑘pk via 𝑘−k. Thus, if you have a (positive or negative) literal 𝑖i, the truth assignment 𝑖i will make it true.

We represent truth assignments to multiple variables simply as the set of assignments to individual variables. For example, the truth assignment that assigns True to 𝑝1p1 and False to 𝑝2p2 will be represented via the set {1,2}{1,−2}.

Question 1: Define Clause simplification

To solve a SAT instance, we need to search for a truth assignment to its propositional variables that will make all the clauses true. We will search for such a truth assignment by trying to build it one variable at a time. So a basic operation on a clause will be:

Given a clause, and a truth assignment for one variable, compute the result on the clause.

What is the result on the clause? Consider a clause with representation 𝑐c (thus, 𝑐c is a set of integers) and a truth assignment 𝑖i (recall that 𝑖i can be positive or negative, depending on whether it assigns True or False to 𝑝𝑖pi). There are three cases:

  • If 𝑖𝑐i∈c, then the 𝑖i literal of 𝑐c is true, and so is the whole clause. We return True to signify it.
  • If 𝑖𝑐−i∈c, then the 𝑖−i literal of 𝑐c is false, and it cannot help make the clause true. We return the clause 𝑐{𝑖}c∖{−i}, which corresponds to the remaining ways of making the clause true under assignment 𝑖i.
  • If neither 𝑖i nor 𝑖−i is in 𝑐c, then we return 𝑐c itself, as 𝑐c is not affected by the truth assignment 𝑖i.

Based on the above discussion, implement a simplify method for a Clause that, given a truth assignment, returns either a simplified clause, if some literals

本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » Homework 16: SAT_逻辑学满足性问题_美国留学生作业答案_assignment answer

李兴球Python微信公众号文章列表

Python编程家长会花絮_萍乡中小学Python家长会现场

火星路上等着你_少儿从小学什么最好呢?

国家大力整顿教育培训机构,Scratch或Python少儿编程还有得教吗?

鸿蒙系统支持Python开发_可视化编程特别兴趣小组

Scratch作品转Python作品_小猴接桃

python海龟数据可视化。第七次全国人口普查历年数据图表

你的孩子Python编程学到哪个阶段了?给孩子报编程的家长,务必仔细一读。

五一神女来对话,看看她们聊什么?赠Python教案等。

五一快乐有大礼,告诉大家我是如何上Python课的。

Python名堂多,趣味到处有,劈开机械手,帧帧是图片。速算达人之猫狮大战正在进行。 逐字动画不独享,自动生成皆有它。2行代码自动生成字幕gif动画。 Python之潮来临,我在安源区教师科技创新能力的Python讲座

小心你的Python程序,它会是你的一面镜子。小方块闯迷宫.py源代码简析。送Scratch算法集。?

铃儿响钉铛_音效怎能忘_Python配音之Pygame混音器

人面桃花相映红_winsound模块简介

《Python昨晚我想你了》_开源的游戏海龟模块实例案例浅析

《八猫联动初体验》_来自游戏海龟模块的问候

喜爱春天的人儿啊 心地纯洁的人_Python逐行像素显示

旋转之三叶炫彩扇_蟒蛇与海龟的表演

彩虹欢迎字幕_三模合体滚图形

《Python海龟宝典》简介

100%错误的算法还在用,明明没有错别字,说我有11个错别字

奇怪的Python代码,谁能帮我解释一下??

人造地球系统让人类文明充满整个宇宙之Python32768版

深夜,是什么把你的大脑搞成一团浆糊!再谈少儿编程!

5线城市萍乡的少儿Python寒假班学的是什么内容?

关于纯少儿编程课程进化的自然选择

Python海龟画图经典作品_国庆中秋双重喜庆源代码免费下载

海龟为什么要自杀!turtle制作游戏秘籍之一

朋友,你是否知道我在仰望着你_Python神笔马良案例集

酷酷的爆炸效果_Python海龟画图不仅仅是画图

虫子满屏爬_三bug多线程示例程序浅析 少儿Python视频课程A级简介

给的gif图片加文字水印_拆帧与合帧(免费下载180个Python创意源码

用Python制作酷炫图形之如意金箍棒_颜色增加模块应用

简单的用Python做酷炫图形与动画

sb3转exe,sb3素材提取器,编程小子apk, 未公开的pygame游戏集/scratch/python少儿编程免费下载集合

夜幕下的霓虹

学本领,探索更大的世界!

李兴球博客 风火轮编程主页