数学代考| Logicism and Formalism 离散数学代写代写 - 代考代写：100%准时可靠您的作业代写专家

Gottlob Frege (Fig. 14.8) was a nineteenth-century German mathematician and logician who invented a formal system which is the basis of modern predicate logic. It included axioms, definitions, universal and existential quantification, and formalization of proof. His objective was to show that mathematics was reducible to logic (logicism) but his project failed as one of the axioms used as part of the axiomatisation of set theory led to inconsistentcy.

This inconsistency was pointed out by Bertrand Russell, and it is known as Russell’s paradox. $^{2}$ Russell later introduced the theory of types to deal with the paradox, and he jointly published Principia Mathematica with Whitehead as an attempt to derive the truths of arithmetic from a set of logical axioms and rules of inference.

The sentences of Frege’s logical system denote the truth-values of true or false. The sentences may include expressions such as equality $(x=y)$, and this returns true if $x$ is the same as $y$, and false otherwise. Similarly, a more complex expression such as $f(x, y, z)=w$ is true if $f(x, y, z)$ is identical with $w$, and false otherwise. Frege represented statements such as ‘5 is a prime’ by ‘ $P(5)$ ‘ where $P($ is termed a concept. The statement $P(x)$ returns true if $x$ is prime and false otherwise. His approach was to represent a predicate as a function of one variable which returns a Boolean value of true or false.

Formalism was proposed by Hilbert (Fig. 13.1) as a foundation for mathematics in the early twentiety century. The motivation for the programme was to provide a secure foundations for mathematics, and to resolve the contradictions in the formalization of set theory identified by Russell’s paradox. The presence of a contradiction in a theory means the collapse of the whole theory, and so it was seen as essential that there be a proof of the consistency of the formal system. The formalist approach means that the methods of proof in mathematics are formalized with axioms and rules of inference.
${ }^{2}$ Russell’s paradox (discussed in Chap. 2) considers the question as to whether the set of all sets that contain themselves as members is a set. In either case there is a contradiction.
$13.2$ Logicism and Formalism
215
Fig. $13.1$ David Hilbert
Formalism is a formal system that contains meaningless symbols together with rules for manipulating them. The individual formulas are certain finite sequences of symbols obeying the syntactic rules of the formal language. A formal system consists of:

A formal language;
A set of axioms;
Rules of inference

The expressions in a formal system are terms, and a term may be simple or complex. A simple term may be an object such as a number, and a complex term may be an arithmetic expression such as $4^{3}+1 .$ A complex term is formed via functions, and the expression above uses two functions namely the cube function with argument 4 and the plus function with two arguments.

A formal system is generally intended to represent some aspect of the real world. A rule of inference relates a set of formulas $\left(P_{1}, P_{2}, \ldots P_{k}\right)$ called the premises to the consequence formula $P$ called the conclusion. For each rule of inference there is a finte procedure for determining whether a given formula $Q$ is an immediate consequence of the rule from the given formulas $\left(P_{1}, P_{2}, \ldots P_{k}\right) .$ A proof in a formal system consists of a finite sequence of formulae, where each formula is either an axiom or derived from one or more preceding formulae in the sequence by one of the rules of inference.

Hilbert’s programme was concerened with the formalization of mathematics (i.e. the axiomatization of mathematics) together with a proof that the axiomatization was consistent (i.e. there is no formula $A$ such that both $A$ and $\neg A$ are deducible in the calculus). The specific objectives of Hilbert’s programme were to

Provide a formalism of mathematics.
Show that the formalization of mathematics was complete: i.e. all mathematical truths can be proved in the formal system.
216
13 Computability and Decidability
Provide a proof that the formal system is is consistent (i.e. that no contradictions may be derived).
Show that mathematics is decidable: i.e. there is an algorithm to determine the truth of falsity of any mathematical statement.

The formalist movement in mathematics led to the formalization of large parts of mathematics, where theorems could be proved using just a few mechanical rules. The two most comprehensive formal systems developed were Principia Mathematica by Russell and Whitehead, and the axiomatization of set theory by Zermelo-Fraenkel (subsequently developed further by von Neumann).

Principia Mathematica is a comprehensive three volume work on the logical foundations of mathematics written by Bertrand Russel and Alfred Whitehead between 1910 and 1913 . Its goal was to show that all of the concepts of mathematics can be expressed in logic, and that all of the theorems of mathematics can be proved using only the logical axioms and rules of inference of logic. It covered set theory, ordinal numbers and real numbers, and it showed that in principle that large parts of mathematics could be developed using logicism [1].

It avoided the problems with contradictions that arose with Frege’s system by introducing the theory of types in the system. The theory of types meant that one could no longer speak of the set of all sets, as a set of elements is of a different type from that of each of its elements, and so Russell’s paradox was avoided. It remained an open question at the time as to whether the Principia was consistent and complete. That is, is it possible to derive all the truths of arithmetic in the system and is it possible to derive a contradiction from the Principia’s axioms? However, it was clear from the three volume work that the development of mathematics using the approach of the Principia was extremely lengthy and time consuming.

Chapter 17 discusses early automation of mathematical proof in the $1950 \mathrm{~s}$, including the Logic Theorist (LT) computer program that was demonstrated at the Dartmounth conference on Artificial Intelligence in 1956 , as well as interactive and automated theorem provers. LT was developed by Allen Newell and Herbert Simon, and it could prove 38 of the first 52 theorems from Principia Mathematica.

图论代考

数学中的形式主义运动导致了大部分的形式化

正式系统通常旨在代表现实世界的某些方面。推理规则将一组称为前提的公式 $\left(P_{1}, P_{2}, \ldots P_{k}\right)$ 与称为结论的结果公式 $P$ 联系起来。对于每个推理规则，都有一个有限过程来确定给定公式 $Q$ 是否是给定公式 $\left(P_{1}, P_{2}, \ldots P_{k} 的规则的直接结果\right) .$ 形式系统中的证明由有限的公式序列组成，其中每个公式要么是公理，要么是根据推理规则之一从序列中的一个或多个前面的公式推导出来的。

Hilbert 的程序关注数学的形式化（即数学的公理化）以及公理化是一致的证明（即没有公式 $A$ 使得 $A$ 和 $\neg A$ 都是在微积分中可推导）。希尔伯特计划的具体目标是

形式系统中的表达式是项，项可以是简单的，也可以是复杂的。简单项可以是数字等对象，复杂项可以是 $4^{3}+1 等算术表达式。$ 复杂项是通过函数形成的，上面的表达式使用两个函数，即立方体带有参数 4 的函数和带有两个参数的 plus 函数。

弗雷格逻辑系统的句子表示真或假的真值。句子可能包含诸如等式 $(x=y)$ 之类的表达式，如果 $x$ 与 $y$ 相同，则返回 true，否则返回 false。类似地，如果 $f(x, y, z)$ 与 $w$ 相同，则 $f(x, y, z)=w$ 等更复杂的表达式为真，否则为假。弗雷格用“$P(5)$”表示诸如“5 是素数”的语句，其中 $P($ 被称为概念。如果 $x$ 是素数，则语句 $P(x)$ 返回真，否则返回假。他的方法是将谓词表示为一个变量的函数，该变量返回一个布尔值 true 或 false。

希尔伯特（图 13.1）提出形式主义作为 20 世纪初数学的基础。该计划的动机是为数学提供一个安全的基础，并解决罗素悖论所确定的集合论形式化中的矛盾。理论中矛盾的存在意味着整个理论的崩溃，因此有必要证明形式系统的一致性。形式主义方法意味着数学中的证明方法是用公理和推理规则形式化的。
${ }^{2}$ 罗素悖论（在第 2 章中讨论）考虑的问题是：包含自己作为成员的集合是一个集合。无论哪种情况都存在矛盾。
$13.2$ 逻辑主义和形式主义
215
图。 $13.1$ David Hilbert
形式主义是一个形式系统，它包含无意义的符号以及操作它们的规则。单个公式是遵循正式语言句法规则的特定有限符号序列。一个正式的系统包括：

伯特兰·罗素（Bertrand Russell）指出了这种不一致，被称为罗素悖论。 $^{2}$ Russell 后来引入了类型理论来处理悖论，并与 Whitehead 共同出版了《数学原理》，试图从一组逻辑公理和推理规则中推导出算术的真理。

Gottlob Frege（图 14.8）是 19 世纪的德国数学家和逻辑学家，他发明了一个形式系统，它是现代谓词逻辑的基础。它包括公理、定义、普遍和存在量化以及证明的形式化。他的目标是表明数学可以简化为逻辑（逻辑主义），但他的项目失败了，因为作为集合论公理化一部分的公理之一导致了不一致。

数学代写| 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]