19th Ave New York, NY 95822, USA

# 数学代考| Early Automation of Proof 离散数学代写

## 数学代写| Early Automation of Proof 离散代考

my-assignmentexpert愿做同学们坚强的后盾，助同学们顺利完成学业，同学们如果在学业上遇到任何问题，请联系my-assignmentexpert™，我们随时为您服务！

## 离散数学代写

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$ Intelligence in 1956 .
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. . 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-

## 图论代考

3.这个立场与其他人争论如果正确性是用数学定义的这个立场是有争议的，其他人认为如果正确性是用数学定义的，那么数学定义（即形式规范）是一个定理，任务是证明并且这种证明的例子不多的原因是缺乏数学规范。
290
17 定理证明的本质
Logic Theorist (LT)，在 1956 年的达特茅斯人工智能会议上提出，1956 年的智能 。

$\overline{{ }^{4} \text { 据说罗素说过他很高兴看到数学原理 }$ 可以由机器完成，如果他和怀特黑德事先知道这一点，他们不会由机器来完成，如果他和怀特黑德事先知道这一点，那么 ${ }^{5}$ 另一种可能性（尽管是对人类智能的低效和糟糕的模拟）将从五个公理开始原理，并应用三个推理规则从逻辑上推导出所有可能的有效演绎序列。这被称为大英博物馆算法（就像将猴子放在打字机前以复制大英博物馆的所有书籍一样明智）。
17.2 美元的早期自动化证明
291

Alan Robinson 在 1960 年代初期对定理证明器的工作导致了一种称为“解析”的证明程序，这似乎为谓词微积分定理证明器的自动化提供了突破。解决定理证明者是对寻求证明的猜想的否定。然后它继续进行，直到达到一个矛盾，在这个矛盾中，公理不可能为真，而猜想不可能为假。

## 密码学代考

• 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

## 编码理论代写

1. 数据压缩（或信源编码
2. 前向错误更正（或信道编码
3. 加密编码
4. 线路码