Classical logic
Classical logic is the intensively studied and most used class of logics. Classical logic has had much influence on analytic philosophy, the type of philosophy most found in the English-speaking world; each logical system in this class shares characteristic properties: Law of excluded middle and double negation elimination Law of noncontradiction, the principle of explosion Monotonicity of entailment and idempotency of entailment Commutativity of conjunction De Morgan duality: every logical operator is dual to anotherWhile not entailed by the preceding conditions, contemporary discussions of classical logic only include propositional and first-order logics. In other words, the overwhelming majority of time spent studying classical logic has been spent studying propositional and first-order logic, as opposed to the other forms of classical logic. Most semantics of classical logic are bivalent, meaning all of the possible denotations of propositions can be categorised as either true or false.
Classical logic is a 20th century innovation. The name does not refer to classical antiquity. In fact, classical logic was the reconciliation of Aristotle's logic, which dominated most of the last 2000 years, with the propositional Stoic logic; the two were sometimes seen as irreconcilable. Leibniz's calculus ratiocinator can be seen as foreshadowing classical logic. Bernard Bolzano has the understanding of existential import found in classical logic and not in Aristotle. Though he never questioned Aristotle, George Boole's algebraic reformulation of logic, so called Boolean logic, was a predecessor of modern mathematical logic and classical logic. William Stanley Jevons and John Venn, who had the modern understanding of existential import, expanded Boole's system; the original first-order, classical logic is found in Gottlob Frege's Begriffsschrift. It has a wider application than Aristotle's logic, is capable of expressing Aristotle's logic as a special case, it explains the quantifiers in terms of mathematical functions.
It was the first logic capable of dealing with the problem of multiple generality, for which Aristotle's system was impotent. Frege, considered the founder of analytic philosophy, invented it so as to show all of mathematics was derivable from logic, make arithmetic rigorous as David Hilbert had done for geometry, the doctrine known as logicism in the foundations of mathematics; the notation Frege used never much caught on. Hugh MacColl published a variant of propositional logic two years prior; the writings of Augustus De Morgan and Charles Sanders Peirce pioneered classical logic with the logic of relations. Peirce influenced Ernst Schröder. Classical logic reached fruition in Bertrand Russell and A. N. Whitehead's Principia Mathematica, Ludwig Wittgenstein's Tractatus Logico Philosophicus. Russell and Whitehead were influenced by Peano and Frege, sought to show mathematics was derived from logic. Wittgenstein was influenced by Frege and Russell, considered the Tractatus to have solved all problems of philosophy.
Willard Van Orman Quine insisted on classical, first-order logic as the true logic, saying higher-order logic was "set theory in disguise". Jan Łukasiewicz pioneered non-classical logic; the results of Kurt Goedel and Alfred Tarski undermined the logicist project. With the advent of algebraic logic it became apparent that classical propositional calculus admits other semantics. In Boolean-valued semantics, the truth values are the elements of an arbitrary Boolean algebra. Intermediate elements of the algebra correspond to truth values other than "true" and "false"; the principle of bivalence holds only when the Boolean algebra is taken to be the two-element algebra, which has no intermediate elements. Warren Goldfard, "Deductive Logic", 1st edition, 2003, ISBN 0-87220-660-2
Set theory
Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects. Although any type of object can be collected into a set, set theory is applied most to objects that are relevant to mathematics; the language of set theory can be used to define nearly all mathematical objects. The modern study of set theory was initiated by Richard Dedekind in the 1870s. After the discovery of paradoxes in naive set theory, such as Russell's paradox, numerous axiom systems were proposed in the early twentieth century, of which the Zermelo–Fraenkel axioms, with or without the axiom of choice, are the best-known. Set theory is employed as a foundational system for mathematics in the form of Zermelo–Fraenkel set theory with the axiom of choice. Beyond its foundational role, set theory is a branch of mathematics in its own right, with an active research community. Contemporary research into set theory includes a diverse collection of topics, ranging from the structure of the real number line to the study of the consistency of large cardinals.
Mathematical topics emerge and evolve through interactions among many researchers. Set theory, was founded by a single paper in 1874 by Georg Cantor: "On a Property of the Collection of All Real Algebraic Numbers". Since the 5th century BC, beginning with Greek mathematician Zeno of Elea in the West and early Indian mathematicians in the East, mathematicians had struggled with the concept of infinity. Notable is the work of Bernard Bolzano in the first half of the 19th century. Modern understanding of infinity began in 1870–1874 and was motivated by Cantor's work in real analysis. An 1872 meeting between Cantor and Richard Dedekind influenced Cantor's thinking and culminated in Cantor's 1874 paper. Cantor's work polarized the mathematicians of his day. While Karl Weierstrass and Dedekind supported Cantor, Leopold Kronecker, now seen as a founder of mathematical constructivism, did not. Cantorian set theory became widespread, due to the utility of Cantorian concepts, such as one-to-one correspondence among sets, his proof that there are more real numbers than integers, the "infinity of infinities" resulting from the power set operation.
This utility of set theory led to the article "Mengenlehre" contributed in 1898 by Arthur Schoenflies to Klein's encyclopedia. The next wave of excitement in set theory came around 1900, when it was discovered that some interpretations of Cantorian set theory gave rise to several contradictions, called antinomies or paradoxes. Bertrand Russell and Ernst Zermelo independently found the simplest and best known paradox, now called Russell's paradox: consider "the set of all sets that are not members of themselves", which leads to a contradiction since it must be a member of itself and not a member of itself. In 1899 Cantor had himself posed the question "What is the cardinal number of the set of all sets?", obtained a related paradox. Russell used his paradox as a theme in his 1903 review of continental mathematics in his The Principles of Mathematics. In 1906 English readers gained the book Theory of Sets of Points by husband and wife William Henry Young and Grace Chisholm Young, published by Cambridge University Press.
The momentum of set theory was such. The work of Zermelo in 1908 and the work of Abraham Fraenkel and Thoralf Skolem in 1922 resulted in the set of axioms ZFC, which became the most used set of axioms for set theory; the work of analysts such as Henri Lebesgue demonstrated the great mathematical utility of set theory, which has since become woven into the fabric of modern mathematics. Set theory is used as a foundational system, although in some areas—such as algebraic geometry and algebraic topology—category theory is thought to be a preferred foundation. Set theory begins with a fundamental binary relation between an object o and a set A. If o is a member of A, the notation o. Since sets are objects, the membership relation can relate sets as well. A derived binary relation between two sets is the subset relation called set inclusion. If all the members of set A are members of set B A is a subset of B, denoted A ⊆ B. For example, is a subset of, so is but is not; as insinuated from this definition, a set is a subset of itself.
For cases where this possibility is unsuitable or would make sense to be rejected, the term proper subset is defined. A is called a proper subset of B if and only if A is a subset of B, but A is not equal to B. Note that 1, 2, 3 are members of the set but are not subsets of it. Just as arithmetic features binary operations on numbers, set theory features binary operations on sets. The: Union of the sets A and B, denoted A ∪ B, is the set of all objects that are a member of A, or B, or both; the union of and is the set. Intersection of the sets A and B, denoted A ∩ B, is the set of all objects that are members of both A and B; the intersection of and is the set. Set difference of U and A, denoted U \ A, is the set of all members of U that are not members of A; the set difference \ is, conversely, the set difference \ is. When A is a subset of U, the set difference U \ A is called the complement of A in U. In this case, if the choice of U is clear from the context, the notation Ac is sometimes used instead of U \ A if U is a universal set as in the study of Venn diagrams.
Symmetric difference of sets A and B, denoted A △ B or A ⊖ B, is
Natural deduction
In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules related to the "natural" way of reasoning. This contrasts with Hilbert-style systems, which instead use axioms as much as possible to express the logical laws of deductive reasoning. Natural deduction grew out of a context of dissatisfaction with the axiomatizations of deductive reasoning common to the systems of Hilbert and Russell; such axiomatizations were most famously used by Russell and Whitehead in their mathematical treatise Principia Mathematica. Spurred on by a series of seminars in Poland in 1926 by Łukasiewicz that advocated a more natural treatment of logic, Jaśkowski made the earliest attempts at defining a more natural deduction, first in 1929 using a diagrammatic notation, updating his proposal in a sequence of papers in 1934 and 1935, his proposals led to different notations such as Fitch-style calculus or Suppes' method of which e.g. Lemmon gave a variant called system L.
Natural deduction in its modern form was independently proposed by the German mathematician Gerhard Gentzen in 1934, in a dissertation delivered to the faculty of mathematical sciences of the University of Göttingen. The term natural deduction was coined in that paper: Ich wollte nun zunächst einmal einen Formalismus aufstellen, der dem wirklichen Schließen möglichst nahe kommt. So ergab sich ein "Kalkül des natürlichen Schließens". Gentzen was motivated by a desire to establish the consistency of number theory, he was unable to prove the main result required for the consistency result, the cut elimination theorem—the Hauptsatz—directly for natural deduction. For this reason he introduced his alternative system, the sequent calculus, for which he proved the Hauptsatz both for classical and intuitionistic logic. In a series of seminars in 1961 and 1962 Prawitz gave a comprehensive summary of natural deduction calculi, transported much of Gentzen's work with sequent calculi into the natural deduction framework.
His 1965 monograph Natural deduction: a proof-theoretical study was to become a reference work on natural deduction, included applications for modal and second-order logic. In natural deduction, a proposition is deduced from a collection of premises by applying inference rules repeatedly; the system presented in this article is a minor variation of Gentzen's or Prawitz's formulation, but with a closer adherence to Martin-Löf's description of logical judgments and connectives. A judgment is something, knowable, that is, an object of knowledge, it is evident. Thus "it is raining" is a judgment, evident for the one who knows that it is raining. In mathematical logic however, evidence is not as directly observable, but rather deduced from more basic evident judgments; the process of deduction is. The most important judgments in logic are of the form "A is true"; the letter A stands for any expression representing a proposition. Many other judgments have been studied. To start with, we shall concern ourselves with the simplest two judgments "A is a proposition" and "A is true", abbreviated as "A prop" and "A true" respectively.
The judgment "A prop" defines the structure of valid proofs of A, which in turn defines the structure of propositions. For this reason, the inference rules for this judgment are sometimes known as formation rules. To illustrate, if we have two propositions A and B we form the compound proposition A and B, written symbolically as " A ∧ B ". We can write this in the form of an inference rule: A prop B prop prop ∧ F where the parentheses are omitted to make the inference rule more succinct: A prop B prop A ∧ B prop ∧ F This inference rule is schematic: A and B can be instantiated with any expression; the general form of an inference rule is: J 1 J 2 ⋯ J n J name where each J i is a judgment and the inference rule is named "name". The judgments above the line are known as premises, those below the line are conclusions. Other common logical propositions are disjunction ( A
Computer science
Computer science is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems, its fields can be divided into practical disciplines. Computational complexity theory is abstract, while computer graphics emphasizes real-world applications. Programming language theory considers approaches to the description of computational processes, while computer programming itself involves the use of programming languages and complex systems. Human–computer interaction considers the challenges in making computers useful and accessible; the earliest foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks such as the abacus have existed since antiquity, aiding in computations such as multiplication and division.
Algorithms for performing computations have existed since antiquity before the development of sophisticated computing equipment. Wilhelm Schickard designed and constructed the first working mechanical calculator in 1623. In 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner, he may be considered the first computer scientist and information theorist, among other reasons, documenting the binary number system. In 1820, Thomas de Colmar launched the mechanical calculator industry when he released his simplified arithmometer, the first calculating machine strong enough and reliable enough to be used daily in an office environment. Charles Babbage started the design of the first automatic mechanical calculator, his Difference Engine, in 1822, which gave him the idea of the first programmable mechanical calculator, his Analytical Engine, he started developing this machine in 1834, "in less than two years, he had sketched out many of the salient features of the modern computer".
"A crucial step was the adoption of a punched card system derived from the Jacquard loom" making it infinitely programmable. In 1843, during the translation of a French article on the Analytical Engine, Ada Lovelace wrote, in one of the many notes she included, an algorithm to compute the Bernoulli numbers, considered to be the first computer program. Around 1885, Herman Hollerith invented the tabulator, which used punched cards to process statistical information. In 1937, one hundred years after Babbage's impossible dream, Howard Aiken convinced IBM, making all kinds of punched card equipment and was in the calculator business to develop his giant programmable calculator, the ASCC/Harvard Mark I, based on Babbage's Analytical Engine, which itself used cards and a central computing unit; when the machine was finished, some hailed it as "Babbage's dream come true". During the 1940s, as new and more powerful computing machines were developed, the term computer came to refer to the machines rather than their human predecessors.
As it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. In 1945, IBM founded the Watson Scientific Computing Laboratory at Columbia University in New York City; the renovated fraternity house on Manhattan's West Side was IBM's first laboratory devoted to pure science. The lab is the forerunner of IBM's Research Division, which today operates research facilities around the world; the close relationship between IBM and the university was instrumental in the emergence of a new scientific discipline, with Columbia offering one of the first academic-credit courses in computer science in 1946. Computer science began to be established as a distinct academic discipline in the 1950s and early 1960s; the world's first computer science degree program, the Cambridge Diploma in Computer Science, began at the University of Cambridge Computer Laboratory in 1953. The first computer science degree program in the United States was formed at Purdue University in 1962.
Since practical computers became available, many applications of computing have become distinct areas of study in their own rights. Although many believed it was impossible that computers themselves could be a scientific field of study, in the late fifties it became accepted among the greater academic population, it is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM released the IBM 704 and the IBM 709 computers, which were used during the exploration period of such devices. "Still, working with the IBM was frustrating if you had misplaced as much as one letter in one instruction, the program would crash, you would have to start the whole process over again". During the late 1950s, the computer science discipline was much in its developmental stages, such issues were commonplace. Time has seen significant improvements in the effectiveness of computing technology. Modern society has seen a significant shift in the users of computer technology, from usage only by experts and professionals, to a near-ubiquitous user base.
Computers were quite costly, some degree of humanitarian aid was needed for efficient use—in part from professional computer operators. As computer adoption became more widespread and affordable, less human assistance was needed for common usage. Despite its short history as a formal academic discipline, computer science has made a number of fundamental contributions to science and society—in fact, along with electronics, it is
C++
C++ is a general-purpose programming language, developed by Bjarne Stroustrup as an extension of the C language, or "C with Classes". It has imperative, object-oriented and generic programming features, while providing facilities for low-level memory manipulation, it is always implemented as a compiled language, many vendors provide C++ compilers, including the Free Software Foundation, Intel, IBM, so it is available on many platforms. C++ was designed with a bias toward system programming and embedded, resource-constrained software and large systems, with performance and flexibility of use as its design highlights. C++ has been found useful in many other contexts, with key strengths being software infrastructure and resource-constrained applications, including desktop applications and performance-critical applications. C++ is standardized by the International Organization for Standardization, with the latest standard version ratified and published by ISO in December 2017 as ISO/IEC 14882:2017.
The C++ programming language was standardized in 1998 as ISO/IEC 14882:1998, amended by the C++03, C++11 and C++14 standards. The current C++ 17 standard supersedes these with an enlarged standard library. Before the initial standardization in 1998, C++ was developed by Danish computer scientist Bjarne Stroustrup at Bell Labs since 1979 as an extension of the C language. C++20 is the next planned standard, keeping with the current trend of a new version every three years. In 1979, Bjarne Stroustrup, a Danish computer scientist, began work on "C with Classes", the predecessor to C++; the motivation for creating a new language originated from Stroustrup's experience in programming for his Ph. D. thesis. Stroustrup found that Simula had features that were helpful for large software development, but the language was too slow for practical use, while BCPL was fast but too low-level to be suitable for large software development; when Stroustrup started working in AT&T Bell Labs, he had the problem of analyzing the UNIX kernel with respect to distributed computing.
Remembering his Ph. D. experience, Stroustrup set out to enhance the C language with Simula-like features. C was chosen because it was general-purpose, fast and used; as well as C and Simula's influences, other languages influenced C++, including ALGOL 68, Ada, CLU and ML. Stroustrup's "C with Classes" added features to the C compiler, including classes, derived classes, strong typing and default arguments. In 1983, "C with Classes" was renamed to "C++", adding new features that included virtual functions, function name and operator overloading, constants, type-safe free-store memory allocation, improved type checking, BCPL style single-line comments with two forward slashes. Furthermore, it included the development of a standalone compiler for Cfront. In 1985, the first edition of The C++ Programming Language was released, which became the definitive reference for the language, as there was not yet an official standard; the first commercial implementation of C++ was released in October of the same year.
In 1989, C++ 2.0 was released, followed by the updated second edition of The C++ Programming Language in 1991. New features in 2.0 included multiple inheritance, abstract classes, static member functions, const member functions, protected members. In 1990, The Annotated C++ Reference Manual was published; this work became the basis for the future standard. Feature additions included templates, namespaces, new casts, a boolean type. After the 2.0 update, C++ evolved slowly until, in 2011, the C++11 standard was released, adding numerous new features, enlarging the standard library further, providing more facilities to C++ programmers. After a minor C++14 update released in December 2014, various new additions were introduced in C++17, further changes planned for 2020; as of 2017, C++ remains the third most popular programming language, behind Java and C. On January 3, 2018, Stroustrup was announced as the 2018 winner of the Charles Stark Draper Prize for Engineering, "for conceptualizing and developing the C++ programming language".
According to Stroustrup: "the name signifies the evolutionary nature of the changes from C". This name is credited to Rick Mascitti and was first used in December 1983; when Mascitti was questioned informally in 1992 about the naming, he indicated that it was given in a tongue-in-cheek spirit. The name comes from C's ++ operator and a common naming convention of using "+" to indicate an enhanced computer program. During C++'s development period, the language had been referred to as "new C" and "C with Classes" before acquiring its final name. Throughout C++'s life, its development and evolution has been guided by a set of principles: It must be driven by actual problems and its features should be useful in real world programs; every feature should be implementable. Programmers should be free to pick their own programming style, that style should be supported by C++. Allowing a useful feature is more important than preventing every possible misuse of C++, it should provide facilities for organising programs into separate, well-defined parts, provide facilities for combining separately developed parts.
No implicit violations of the type system (but allow explicit violations.