Here, we introduce the field of Mathematical Logic.
This is by far my favourite topic ^_^, the heart of TCS:
TCS was born out of the endeavours of metamathematicians during the Grundlagenkrise at the beginning of the 20th century, some good reads on the topic are:
Contributions of the Logicians by Burris (https://www.math.uwaterloo.ca/~snburris/htdocs/history.html) and Logicomix by Doxiadis and Papadimitriou (warning: you might get frustrated by Papa constantly barging in, the lack of math and/or the "cliffhanger"!)
From the metaprocesses of Life (evolutionary processes), the human brain has been structured with the capacity for rationality/reason (stemming from fitedness with the seemingly inherent order of the Universe). Logic is the study of using this capacity (notice that it is itself required to study itself!); while Mathematics is using this capacity to study the abstract notions of quantity (arithmetic), structure (algebra), form (topology) and change (analysis).
Without going into the philosophical underpinnings of reasoning (Hume's problem of induction, Grue and Bleen, Occam's razor, etc.), what is important to know about the range of Logic is the following:
Logic has 2 definitions:
(functional) the use of reasoning
(structural) the field of study
The field of study is commonly divided in 3 parts:
However, it is also possible to partition it according to the framework in which it is studied:
Formal Logic (also called Mathematical Logic or Symbolic Logic) is thus the approach to Logic using the setting of formal systems, which are "broadly defined as any well-defined system[s] of abstract thought based on the model of mathematics" -- Wikipedia.
But Mathematical Logic also has another definition, that is, as a branch of Mathematics born out of the field of study denoted as "foundations of mathematics" as mentioned in the introduction. Thus wedged between Logic and Mathematics, Mathematical Logic is a cornerstone of Metamathematics (which will definitely be the topic of a future post ^_*).
Mathematical Logic has 2 definitions:
(logic) formal logic as defined previously
(mathematics) the subfield of Mathematics encompassing the "four pillars of the foundations of mathematics": set theory (sets)[~quantity], proof theory (syntax)[~structure], model theory (semantics)[~form], recursion theory (computation)[~change].
Under the latter definition, notice that Computability Theory (recursion theory) is as much a (seminal) subfield of TCS as it is a subfield of Math Logic.
Under the former definition, Formal Logic is commonly partitioned into:
Just as the interconnectivity of Mathematics doesn't allow all its subfields to be represented in a planar graph, there is no clean scheme for classifying formal logics, and the one above is division is a mesh of generalising or relaxing some properties, such as properties common to the class of classical logics:
The first two laws come from Aristotle's laws of thought:
"The law of noncontradiction, along with its complement, the law of excluded middle (the third of the three classic laws of thought), are correlates of the law of identity (the first of the three laws). Because the law of identity partitions its logical Universe into exactly two parts, it creates a dichotomy wherein the two parts are "mutually exclusive" and "jointly exhaustive". The law of noncontradiction is merely an expression of the mutually exclusive aspect of that dichotomy, and the law of excluded middle, an expression of its jointly exhaustive aspect." --Wikipedia
Notice that this dichotomy of truth core to classical logics is reflected in (equivalent) laws:
Finally, let us briefly touch upon another dichotomy inherent to the structure of formal logic, syntax vs semantics, by properly distinguishing material from logical consequence in the context of classical logic:
http://www.iep.utm.edu/logcon/
http://plato.stanford.edu/entries/logic-classical/
http://en.wikipedia.org/wiki/Logic_in_computer_science
http://en.wikipedia.org/wiki/List_of_logic_symbols
This is by far my favourite topic ^_^, the heart of TCS:
TCS was born out of the endeavours of metamathematicians during the Grundlagenkrise at the beginning of the 20th century, some good reads on the topic are:
Contributions of the Logicians by Burris (https://www.math.uwaterloo.ca/~snburris/htdocs/history.html) and Logicomix by Doxiadis and Papadimitriou (warning: you might get frustrated by Papa constantly barging in, the lack of math and/or the "cliffhanger"!)
From the metaprocesses of Life (evolutionary processes), the human brain has been structured with the capacity for rationality/reason (stemming from fitedness with the seemingly inherent order of the Universe). Logic is the study of using this capacity (notice that it is itself required to study itself!); while Mathematics is using this capacity to study the abstract notions of quantity (arithmetic), structure (algebra), form (topology) and change (analysis).
Without going into the philosophical underpinnings of reasoning (Hume's problem of induction, Grue and Bleen, Occam's razor, etc.), what is important to know about the range of Logic is the following:
Logic has 2 definitions:
(functional) the use of reasoning
(structural) the field of study
The field of study is commonly divided in 3 parts:
- deductive reasoning - drawing conclusions from premises (cf. entailment, modus ponens, syllogisms, material conditional)
- inductive reasoning - given complete (unbiased sample), draw conclusions on the entire population
- abductive reasoning - given incomplete observations, infer to the best explanation
However, it is also possible to partition it according to the framework in which it is studied:
- informal logic - no definite setting
- formal logic - formal setting
But Mathematical Logic also has another definition, that is, as a branch of Mathematics born out of the field of study denoted as "foundations of mathematics" as mentioned in the introduction. Thus wedged between Logic and Mathematics, Mathematical Logic is a cornerstone of Metamathematics (which will definitely be the topic of a future post ^_*).
Mathematical Logic has 2 definitions:
(logic) formal logic as defined previously
(mathematics) the subfield of Mathematics encompassing the "four pillars of the foundations of mathematics": set theory (sets)[~quantity], proof theory (syntax)[~structure], model theory (semantics)[~form], recursion theory (computation)[~change].
Under the latter definition, notice that Computability Theory (recursion theory) is as much a (seminal) subfield of TCS as it is a subfield of Math Logic.
Under the former definition, Formal Logic is commonly partitioned into:
- Classical Logics
- boolean logic - algebra of truth (BL)
- propositional (sentential) logic - 0th order logic, a.k.a. propositional calculus (PL)
- predicate logic - higher-order logics, e.g. first order logic (FOL), second order logic (SOL), infinitary logic, many-sorted logics
- Non-Classical Logics
- modal logic - extends classical logic with non-truth-functional ("modal") operators
- provability logic - changes necessity operator to provability operator
- interpretability logic - extend provability logic to describe interpretability
- many-valued logics - a propositional calculus in which there are more than two truth values
- fuzzy logic - allows as a truth value any real number between 0 and 1
- intuitionistic (constructive) logic - replaces truth by "constructive provability"; rejects the law of the excluded middle and double negative elimination
- paraconsistent logic - rejects the law of noncontradiction
- relevance logic - replaces material conditional (implication) by requiring that antecedent and consequent be related by some "relevance"
- non-monotonic logic - rejects monotonicity of entailment
- default logic - formalizing reasoning with default assumptions
- autoepistemic logic - formalizing reasoning of knowledge about knowledge
Just as the interconnectivity of Mathematics doesn't allow all its subfields to be represented in a planar graph, there is no clean scheme for classifying formal logics, and the one above is division is a mesh of generalising or relaxing some properties, such as properties common to the class of classical logics:
- law of noncontradiction - two contradictory statements cannot both be true at the same time
- law of the excluded middle - statements are either true or false
- monotonicity of entailment - statements derived from a premise can be derived from that premise and any other premise (if they are contradictory, then we get vacuous truth)
- idempotency of entailment - statements that can be derived from a single instance of a premise, can also be derived from multiple instances of the same premise and vice-versa
- commutativity of conjunction - conjuncts can be switched without affecting truth value
- DeMorgan duality - dichotomies of unary and binary logical operators
The first two laws come from Aristotle's laws of thought:
"The law of noncontradiction, along with its complement, the law of excluded middle (the third of the three classic laws of thought), are correlates of the law of identity (the first of the three laws). Because the law of identity partitions its logical Universe into exactly two parts, it creates a dichotomy wherein the two parts are "mutually exclusive" and "jointly exhaustive". The law of noncontradiction is merely an expression of the mutually exclusive aspect of that dichotomy, and the law of excluded middle, an expression of its jointly exhaustive aspect." --Wikipedia
Notice that this dichotomy of truth core to classical logics is reflected in (equivalent) laws:
- the principle of explosion (ex falso quod libet) - anything can be proven from a contradiction
- e.g. A is true and ~A is true, thus A or B is true (or intro), thus A or B and ~A is true (and intro), thus B is true (skipped steps but using principle of noncontradiction)
- the principle of vacuous truth - if the antecedent is false in a conditional statement, the statement is true
Finally, let us briefly touch upon another dichotomy inherent to the structure of formal logic, syntax vs semantics, by properly distinguishing material from logical consequence in the context of classical logic:
logical implication (semantic) as defined in classical logic:
\Phi \models (double turnstile in latex) A iff any truth assignment satisfying \Phi also satisfies A
note: the definition happens in the metalanguage that is used to define the object language, thus symbols like "iff" and notions of truth assignments and satisfiability are about the language that is being defined. We will see later that when logics can express statements about their own statements, interesting issues arise.
material conditional (syntactic) as defined in classical logic:
A \supset B iff ~A \vee B (A implies B iff notA or B)
note: to quickly remember this result think about sets: A implies B means that the elements in set A (i.e. that have property A) are also elements of B (i.e. have property B), thus B contains A. That only means that there can be no elements in A that are not in B (not(A and notB)). Using DeMorgan this is equivalent to the statement above. In this sense B is a broader (also termed stronger, see below) property.
note about the note: there is a confusion I want to resolve here: stronger vs weaker statements. Generally, if assumptions are stronger than others it means that they imply the weaker ones; however the confusion arises when talking about properties: a property that holds on weaker assumptions is stronger (more general) than one that holds on stronger assumptions.
Thus, we conclude our preliminary overview of Math Logic by pointing out that such interconnected notions are best approached from multiple directions, a fact that is true for any concept the brain can handle (cf distributed representations), but that gets amplified as the concepts become more abstract. What does this fact say about the human capacity for abstraction? What does it say about the frame problem?
Further reading:
http://www.iep.utm.edu/logcon/
http://plato.stanford.edu/entries/logic-classical/
http://en.wikipedia.org/wiki/Logic_in_computer_science
http://en.wikipedia.org/wiki/List_of_logic_symbols
