数学代考| Early Automation of Proof 离散数学代写代写 - 代考代写：100%准时可靠您的作业代写专家

Early work on the automation of proof began in the 1950 s with the beginning of work in the Artificial Intelligence field, where the early AI practitioners were trying to develop a ‘thinking machine’. One of the earliest programs developed was the
3.This position is controversial with others arguing that if correctmess is defined mathematically This position is controversial with others arguing that if correctiness is defined mathematically then the mathematical definition (i.e., formal specification) is a theorem, and the task is to prove and that the reason why there are not many examples of such proofs is due to a lack of mathematical specifications.
290
17 The Nature of Theorem Proving
Logic Theorist (LT), which was presented at the Dartmouth conference on Artificial Intelligence in $1956[1]$ Intelligence in 1956 [1].
It was developed by Allen Newell and Herbert Simon, and it could prove 38 of the first 52 theorems from Russell and Whitehead’s Principia Mathematica. [2]. the inference rules of logic, and the LT program conducted proof from a small set of propositional axioms and deduction rules. Its approach was to start with the theorem to be proved, and to then search for relevant axioms and operators to prove the theorem. The Logic Theorist proved theorems in the propositional calculus, but it did not support predicate calculus. It used the five basic axioms of propositional logic and three rules of inference from the Principii to prove theorems LT demonstrated that computers had the ability to encode knowledge and information and to perform intelligent operations such as solving theorems in mathematics. The heuristic approach of the LT program tried to emulate human mathematicians, but could not guarantee that proof would be found for every valid theorem.
If no immediate one-step proof could be found, then a set of subgoals was generated (these are formulae from which the theorem may be proved in one step) and proofs of these were then searched for, and so on. The program could use previously proved theorems in the course of developing a proof of a new theorem. Newell and Simon were hoping that the Logic Theorist would do more than just prove theorems in logic, and their goal was that it would attempt to prove theorems in a human-like way, especially with a selective search. in a human-like way, especially with a selective search. However, in practice, the Logic Theorist search was not very selective in its approach, and the subproblems were considered in the order in which they were solving) to guess at which subproblem was most likely to yield an actual proof. This meant that the Logic Theorist could, in practice, find only very short proofs, since as the number of steps in the proof increased, the amount of search required to find the proof exploded.
The Geometry Machine was developed by Herbert Gelemter at the IBM Research Center in New York, in the late $1950 \mathrm{~s}$, with the goal of developing intelligent behaviour in machines. It differed from the Logic Theorist in that it selected only the valid subgoals (i.e. it ignored the invalid ones), and attempted to find proof of these. The Geometry Machine was successful in finding the solution to geometry.
$\overline{{ }^{4} \text { Russell is said to have remarked that he was delighted to see that the Principia Mathematica could }$ be done by machine, and that if he and Whitehead had known this in advance that they would not be done by machine, and that if he and Whitehead had known this in advance that ${ }^{5}$ Another possibility (though an inefficient and poor simulation of human intelligence) would be to start with the five axioms of the Principia, and to apply the three rules of inference to logically derive all possible sequences of valid deductions. This is known as the British Museum algorithm (as sensible as putting monkeys in front of typewriters to reproduce all of the books of the British Museum).
$17.2$ Early Automation of Proof
291
The logicians Hao Wang and Evert Beth (the inventor of semantic tableaux which was discussed in Chap. 15) were critical of the approaches of the AI pioneers and believed that mathematical logic could do a lot more. Wang and others developed a theorem prover for first-order predicate calculus in 1960 , but it had serious limitations due to the combinatorial explosion.
Alan Robinson’s work on theorem provers in the early 1960 s led to a proof procedure termed ‘resolution’, which appeared to provide a breakthrough in the automation of predicate calculus theorem provers. A resolution theorem prover is negation of the conjecture whose proof is sought. It then proceeds until a contradiction is reached, where there is no possible way for the axioms to be true and for the conjecture to be false.

The initial success of resolution led to excitement in the AI field where pioneers such as John McCarthy (see Chap. 16) believed that human knowledge could be expressed in predicate calculus, ${ }^{6}$ and therefore, if the resolution was indeed successful for efficient automated theorem provers, then the general problem of Arti-

图论代考

证明自动化的早期工作始于 1950 年代，当时人工智能领域的工作开始，早期的人工智能从业者试图开发一种“思考机器”。最早开发的程序之一是
3.这个立场与其他人争论如果正确性是用数学定义的这个立场是有争议的，其他人认为如果正确性是用数学定义的，那么数学定义（即形式规范）是一个定理，任务是证明并且这种证明的例子不多的原因是缺乏数学规范。
290
17 定理证明的本质
Logic Theorist (LT)，在 1956 年的达特茅斯人工智能会议上提出[1]，1956 年的智能 [1]。
它是由 Allen Newell 和 Herbert Simon 开发的，它可以证明 Russell 和 Whitehead 的数学原理中的前 52 个定理中的 38 个。 [2]。逻辑的推理规则，LT 程序从一小组命题公理和演绎规则进行证明。它的方法是从要证明的定理开始，然后寻找相关的公理和算子来证明定理。逻辑理论家在命题演算中证明了定理，但它不支持谓词演算。它使用命题逻辑的五个基本公理和原理的三个推理规则来证明定理 LT 证明了计算机具有编码知识和信息以及执行智能运算的能力，例如解决数学中的定理。 LT 程序的启发式方法试图模仿人类数学家，但不能保证可以为每个有效定理找到证明。
如果无法立即找到一步证明，则生成一组子目标（这些是可以一步证明定理的公式），然后搜索这些子目标的证明，依此类推。该程序可以在开发新定理证明的过程中使用先前证明的定理。纽厄尔和西蒙希望逻辑理论家能做的不仅仅是证明逻辑中的定理，他们的目标是尝试以类似人类的方式证明定理，特别是通过选择性搜索。以类似人类的方式，尤其是通过选择性搜索。然而，在实践中，Logic Theorist 搜索在其方法中并不是很有选择性，并且子问题是按照它们解决的顺序来考虑的）来猜测哪个子问题最有可能产生一个实际的证明。这意味着逻辑理论家在实践中只能找到非常短的证明，因为随着证明中步骤数的增加，找到证明所需的搜索量激增。
几何机器是由纽约 IBM 研究中心的 Herbert Gelemter 在 1950 年后期开发的，目标是在机器中开发智能行为。它与逻辑理论家的不同之处在于它只选择了有效的子目标（即它忽略了无效的子目标），并试图找到这些的证据。几何机器成功地找到了几何的解决方案。
$\overline{{ }^{4} \text { 据说罗素说过他很高兴看到数学原理 }$ 可以由机器完成，如果他和怀特黑德事先知道这一点，他们不会由机器来完成，如果他和怀特黑德事先知道这一点，那么 ${ }^{5}$ 另一种可能性（尽管是对人类智能的低效和糟糕的模拟）将从五个公理开始原理，并应用三个推理规则从逻辑上推导出所有可能的有效演绎序列。这被称为大英博物馆算法（就像将猴子放在打字机前以复制大英博物馆的所有书籍一样明智）。
17.2 美元的早期自动化证明
291
逻辑学家 Hao Wang 和 Evert Beth（第 15 章讨论的语义画面的发明者）对 AI 先驱者的方法持批评态度，并认为数理逻辑可以做得更多。 Wang等人在1960年开发了一个一阶谓词演算的定理证明器，但由于组合爆炸，它有严重的局限性。
Alan Robinson 在 1960 年代初期对定理证明器的工作导致了一种称为“解析”的证明程序，这似乎为谓词微积分定理证明器的自动化提供了突破。解决定理证明者是对寻求证明的猜想的否定。然后它继续进行，直到达到一个矛盾，在这个矛盾中，公理不可能为真，而猜想不可能为假。

解决方案的初步成功引起了人工智能领域的兴奋，约翰麦卡锡等先驱（见第 16 章）认为人类知识可以用谓词演算 ${ }^{6}$ 来表达，因此

数学代写| DISCRETE MATHEMATICS代考请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

Cryptosystem
A system that describes how to encrypt or decrypt messages
Plaintext
Message in its original form
Ciphertext
Message in its encrypted form
Cryptographer
Invents encryption algorithms
Cryptanalyst
Breaks encryption algorithms or implementations

编码理论代写

编码理论（英语：Coding theory）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、纠错，最近也用于网络编码中。不同学科（如信息论、电机工程学、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。

编码共分四类：^[1]