Ready to Start Your Career?Create Free Account
October 13, 2016
A Mathematical Introduction to Logic: How Logic Provides a Foundation for Hacking
October 13, 2016
October 13, 2016
Like any other profession, hacking has both practical and theoretical applications. Most of the Open topics deal with the practical side of hacking, so I thought I could help balance that a little by talking about the theoretical side of hacking.I am going to vastly simplify the material in my third year mathematics course "A mathematical introduction to logic" so that those with little to no mathematical aptitude can follow along. If you wish to read more on the subject, you can always get the book cited in my bibliography.Today I'd like to focus on the topic of deductive proofs. That is, I would like to look at getting from a set of hypothesis (i.e. assumptions), a set of tautologies (i.e. always true statements), and the use of Modus Ponens (If P is true, and P implies Q, then Q), we can reach a conclusion.Here's a practical example of a informal proof:Assume the following two statements which are both a hypothesis:A = "If port 22 is open then the computer is running SSH"B = "The computer is not running SSH"And the following tautology:C="If Y implies Z, then not Z implies not Y" [p.s. this is called the contrapositive, and is provably a tautology]Can we prove the following?D = "Port 22 is closed"The answer is yes. Let me explain the proof informally:If we apply our tautology C to A (through Modus Ponus), we get the statement E = "If the computer is not running SSH, then port 22 is closed." We then use Modus Ponens with B being true and E = B implying D to get that D is true.What we did above is the essence of deductive proofs. The rest of this article will be devoted to recreating the above proof in the context in mathematics.Describing a formal language requires three pieces of of information:
- A set of symbols. For our purposes we will only consider 0-order logic. Don't worry if you do not understand the next sentence as I will cover these in more detail below. These consist of the left parenthesis, the right parenthesis, the negation symbol, the and symbol, the or symbol, the if then symbol, the if and only if symbol, and a countably infinite set of sentence symbols.
- rules for "grammatically correct" finite sequences of symbols (i.e. (((1 + 3) + 1) = 5) is grammatically correct in common mathematics where )+(1(31+)()= is not.)
- Allowable translations between English and Logic
- The left parenthesis ('('), and the right parenthesis (')') are used for the order of operations. We first evaluate expressions inside brackets before we evaluate anything after brackets.
- The 'not' operator has only one parameter, and returns the opposite of the parameter.
- The 'and' operator has two parameters and returns true if both of it's parameters are true.
- The 'or' operator has two parameters and returns true if one of it's parameters are true or both of it's parameters are true
- The 'if then' operator has two parameters and returns true if the first parameter is false or the second parameter is true or both.
- The 'if and only if' operator has two parameters and returns true if both of it's parameters are false or both of it's parameters are true
- The sentence symbols, unlike the rest of the symbols are subject to change from one context to the other. These are true of false statements
- Every sentence symbol is a well formed formula
- If a and b are well formed formula's, so are '(not a)', '(not b)', '(a and b)', '(a or b)', '(if a then b)', '(a if and only if b)'
- No expression is a well formed formula unless it is compelled by 1. or 2.
- Reduction of ambiguity: most modern everyday languages are powerful because there are many ways to express the same statement. In formal logic, we cannot have any two sentence symbols be reducible to a combination of the other sentence symbols
- Justification: While informal proofs can be correct, often steps will be omitted or tautologies assumed without justification. Using a formal system exposes hidden assumptions and allows us to make sure that our conclusion follows from our premises
- Reduction of words: While this article was written in English, the mathematical equivalent takes much less space to express and therefore much more complex proofs can be expressed without losing sight of the bigger picture.