A Mathematical Introduction to Logic: How Logic Provides a Foundation for Hacking

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:

1. 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.
2. 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.)
3. Allowable translations between English and Logic

(Enderton, 1972, p. 12-13)Before we look at grammar, let's look at the atoms of our 0-order logic:

1. 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.
2. The 'not' operator has only one parameter, and returns the opposite of the parameter.
3. The 'and' operator has two parameters and returns true if both of it's parameters are true.
4. 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
5. The 'if then' operator has two parameters and returns true if  the first parameter is false or the second parameter is true or both.
6. 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
7. 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

(Enderton, 1972, p. 14)The grammar for our 0-order logic (henceforth known as a well formed formula)  will be built from the following rules:

1. Every sentence symbol is a well formed formula
2. 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)'
3. No expression is a well formed formula unless it is compelled by 1. or 2.

(Enderton, 1972, p. 16)I could go on and create a 10 part series where I explain 0-order logic in depth (let me know if you want that), but this is a hacking forum and not a mathematics forum. Let me just skip to the point and use the extreamly limited tools we have to make a proof:A = "Port 22 is running"B = "SSH is running"Then we can construct a proof. Justification is as follows. H is a hypothesis, T is a Tautology, and (i, j; MP) is Modus Ponus applying to the ith and jth components.<(If A then B), (not B), (If (If Y then Z) then (If (not  Z) then (not Y))), If (not B) then (not A), not(A)>Justifications: <H, H, T, (1, 3; MP), (2, 4; MP)>So, what is the point of the mathematical proofs? After all, we were able to explain the proof in English, do why take the time to translate to logic? Here are three reasons we would want to do that:

1. 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
2. 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
3. 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.

The next time you want to prove a computer is secure, don't just run your suite of tools on it, but try to prove it rigorously.If you have any suggestions on what you would like me to post next, please comment on this article.If you liked my article and would like to read another one posted by me, visit https://www.cybrary.it/0p3n/tailgating-following-someone-into-a-building-101/ . I promise it will be more practical.Bibliography:Enderton, H. B. (1972). A mathematical introduction to logic (2nd ed.). New York: Academic Press.Regards,ProgrammerE