This topic will appear not to be mathematical in nature to many people, but that is a misconception. I suspect that the most common reason for this misconception and other similar ones, is that many people confuse mathematics with arithmetic, statistics, geometry or trigonometry. It is true that these topics are part of mathematics. They are not by any means an exhaustive list of mathematical topics. In fact, most mathematical topics have very little to do with arithmetic, statistics etc. In this case, the field in question is the theory of computation and complexity; a part of mathematics which mostly has applications in computer science.
A finite state machine (FSM) is at the same time a mathematical structure, a simple type of computer and a language checker. Formally, it is composed of five parts. These are:
a) An alphabet. This is the collection of all symbols that can be passed into the machine. It can be the Latin alphabet, the numbers 0 and 1, or any other predetermined set of symbols.
b) A set of states. These are abstract states the machine can be in. Since these machines generally relate to a physical model, the states will have some meaning.
c) An initial state. This is how the machine starts out, before any input is given.
d) A transition function. This tells the machine how to change its state according to each new input.
e) A set of final states. When the input stops, if the machine is in a final state, we say that the input was accepted. If on the other hand, a certain input ends with the machine at a non-final state, we say that the input was rejected.
To illustrate all this, I will give two common examples. The first one is for an automatic door. Let's say you have an automatic door. For simplicity, its states will be "Closed" and "Open". The "alphabet" will be an input of "0" if no one is within a small area around the door and "1" if there is someone in this area. The initial state will be "Closed". The transition function is as follows: If the input is 0 and the door is open, close it. If the input is 1 and the door is closed, open it. Otherwise, make no changes. Finally, we can say that both our states are acceptable final states, again for simplicity. As you see, this FSM models our automatic door fairly well. The question arises, why do we need this model? The answer is: Because this is how the door can be made automatic. By making this model, we can create the appropriate digital control system, which will be used to make the door work in this way. In fact, the actual electronics involved in making the automatic door work, are nothing more than a finite state machine, although it will be a more complex one than our simplistic model here.
The second example deals with numbers. We want to make a machine that will take in strings of zeroes and ones as input (I keep using this as my alphabet, because this is essentially how computers work; with 0s and 1s) and accept those strings that end in 1; this corresponds to accepting odd integers. To do this, we define our start state (0) and our final state (1). These are enough for the purpose of this simple machine. Our transition function will be: Move to the state which is the same as the symbol we entered. That is, if the most recent symbol is a 0, go to state 0. If it is a 1, go to state 1. Here, if a string is given in that ends in a 0, our machine will finish in state 0, which is not a final state. So the string will be rejected. Our machine only accepts the strings that end in a 1.
You may think that the second example has little to do with a physical model, compared to the door example before it. This is only partly true. The second example helps us understand a very important concept in the fields of mathematics, computer science and linguistics; that of language and grammar. Formally, languages and grammars can be separated into groups, according to their machine complexity. The grammar above ("all strings of 0s and 1s that end in 1) belongs to the group of languages, which can be formally defined by a FSM. These are known as "regular" or Type-3 grammars. Other grammars require more complex machines, in order to be defined. For example, we have the Type-2 or "context-free" grammars, which can be defined by a type of machine called a "Push-down automaton" or PDA. This is a more complicated machine than the FSM, as it also involves an additional structure, known as a stack, which helps maintain some history of the input, as opposed to the FSM, which only knows its current state.
I would like to end by pointing something very important out. Everything I said above may sound extremely theoretical, but it is vital for the design of personal computers. As you are probably viewing this blog on some machine that can access the internet and decode hypertext into readable text, it is safe to assume that your machine contains any number of these FSMs, PDAs and other, even more complicated computational structures. Without these, it would be impossible for your computer to do all the amazing things it does.
Sunday, March 25, 2012
Wednesday, March 14, 2012
Logical Fallacies
In my previous post I introduced some valid rules of inference. In this topic I would like to discuss invalid inference and logical fallacies. I will begin by way of an example:
My dog has four legs. Cats have four legs. Therefore, my dog is a cat.
The above syllogism is obviously wrong, since although both the premises are correct, the conclusion is not. This is because the conclusion does not follow from the premises. If one of the premises had been "Everything which has four legs is a cat", the syllogism would be valid. The conclusion would still be false, since this new premise is not actually true, but the inference itself would have been correct. Indeed, if we imagine a world in which all four-legged creatures are cats and my dog was a four-legged creature, in that world he would be a cat. A valid conclusion from the given premises, might instead be "At least one four-legged creature is not a cat". To reiterate, the fallacy in the example above lies in the fact that the conclusion does not follow from the premises. This type of fallacy is known as affirming the consequent and is very common in cases where unidirectional implication is not understood.
A similar fallacy is known as denying the antecedent. An example of that would be as follows:
Cats have four legs. My dog is not a cat. Therefore, my dog does not have four legs.
Once again, this syllogism fails to properly connect the premises to the conclusion logically, so it constitutes a fallacy. And it is also a fallacy created from a lack of understanding of the rules of implication, just like the previous one.
The third most common logical fallacy arises from a misunderstanding of the logical OR relation, also known as "inclusive or" (to distinguish it from XOR, the exclusive or). Although in spoken language we often use the word "or" as an exclusive disjunction, the same is not true in logic. In logic, "p OR q" is a statement which is true when at least one of p and q are true; or even both. A misunderstanding of disjunctions leads to the following fallacy:
My pet is a dog OR it is not a cat. My pet is a dog. Therefore, it is not true that my pet is not a cat, so my pet is a cat.
In fact, my pet can be a dog and not a cat at the same time. This is, in fact, the case. The first premise allows for this situation and does not imply that only one statement is true.
The above are propositional fallacies and, as discussed, they arise from a misunderstanding of logical operators, like implication and disjunction. There are also other types of fallacies, which come about from misunderstanding the rules of inference themselves, the scope of the premises or the conclusion, the words and language used and so on. I will not discuss these more general fallacies for now, as they are abundantly available online and also because they are beyond the scope of what I am discussing in this post.
My dog has four legs. Cats have four legs. Therefore, my dog is a cat.
The above syllogism is obviously wrong, since although both the premises are correct, the conclusion is not. This is because the conclusion does not follow from the premises. If one of the premises had been "Everything which has four legs is a cat", the syllogism would be valid. The conclusion would still be false, since this new premise is not actually true, but the inference itself would have been correct. Indeed, if we imagine a world in which all four-legged creatures are cats and my dog was a four-legged creature, in that world he would be a cat. A valid conclusion from the given premises, might instead be "At least one four-legged creature is not a cat". To reiterate, the fallacy in the example above lies in the fact that the conclusion does not follow from the premises. This type of fallacy is known as affirming the consequent and is very common in cases where unidirectional implication is not understood.
A similar fallacy is known as denying the antecedent. An example of that would be as follows:
Cats have four legs. My dog is not a cat. Therefore, my dog does not have four legs.
Once again, this syllogism fails to properly connect the premises to the conclusion logically, so it constitutes a fallacy. And it is also a fallacy created from a lack of understanding of the rules of implication, just like the previous one.
The third most common logical fallacy arises from a misunderstanding of the logical OR relation, also known as "inclusive or" (to distinguish it from XOR, the exclusive or). Although in spoken language we often use the word "or" as an exclusive disjunction, the same is not true in logic. In logic, "p OR q" is a statement which is true when at least one of p and q are true; or even both. A misunderstanding of disjunctions leads to the following fallacy:
My pet is a dog OR it is not a cat. My pet is a dog. Therefore, it is not true that my pet is not a cat, so my pet is a cat.
In fact, my pet can be a dog and not a cat at the same time. This is, in fact, the case. The first premise allows for this situation and does not imply that only one statement is true.
The above are propositional fallacies and, as discussed, they arise from a misunderstanding of logical operators, like implication and disjunction. There are also other types of fallacies, which come about from misunderstanding the rules of inference themselves, the scope of the premises or the conclusion, the words and language used and so on. I will not discuss these more general fallacies for now, as they are abundantly available online and also because they are beyond the scope of what I am discussing in this post.
Saturday, March 10, 2012
Logic and Inference
This is a rather deep topic, which has been studied since ancient times. In simple terms, if a fact is known, logic and inference tell us what other facts are also known because of it. This is not, of course, a simple process. In my previous post, I discussed theorems, which are essentially statements of these facts. Some theorems are extremely complicated. Logic and inference are what we generally use in proofs to connect known facts with those we want to prove.
As an example, let us take the statement "All my friends are taller than I am". Then, let us take the statement "Ed is my friend". Inference tells us that "Ed is taller than I am". If both the first two statements (premises) are true, then so is the third statement (conclusion). If, however, at least one of the premises is false, then the conclusion need not be true. For example, it might not be the case that all my friends are taller than I am. Then Ed may or may not be taller than I am. The creation of this conclusion from the premises above is a valid rule of inference, known as Universal Instantiation. This rule takes a characteristic of a set and applies it to a specific element in the set.
There are various other rules of inference, most of them dealing with taking two premises that are somehow related and extracting from them a conclusion which is related to each of them. The following is a short list of some common rules, with examples. I will use the letters p, q and r as statements, ~ as the negation symbol "NOT", ^ as the conjunction symbol "AND", * as the disjunction symbol "OR" and => (with other similar arrows) as the implication symbols.
Modus ponens (affirming the antecedent). Premises: p, p => q. Conclusion: q.
Here, one of the statements implies the other. Whenever p is true, it makes q true as well. We also have that p is true. Therefore, q must be true as well.
Example: If there is cake, I will eat it. There is cake. So, I will eat it. Here, p is "there is cake" and q is "I will eat the cake".
Modus tollens (denying the precedent). Premises: p => q, ~q. Conclusion: ~p.
This, in a sense, is the reversal of the previous rule. Again, p implies q. If p were true, q would be true. But q is false. So p cannot be true either.
Example: If there is cake, I will eat it. I will not eat cake. Therefore, there is no cake. (Otherwise, I'd be eating it).
Reductio ad absurdum (reduction to the absurd). Premises: p => q, p => ~q. Conclusion: ~p.
This one is a bit of a tricky one at first. In essence, if some statement being true makes another statement both true and false, then the first statement must be false.
Example: If I have a first-born, it is a boy. If I have a first-born, it is a girl. So, I do not have a first-born. (If I did, it would have to be both a boy and a girl).
Disjunctive syllogism. Premises: p * q, ~p. Conclusion: q.
Here we are given that at least one of our premises must be true. We are also given that one of them is definitely false. Then, we know that the other premise has to be the true one.
Example: My wall is white, or the door is open. The door is closed. So, my wall is white.
Note that here, the word "or" does not mean that only one of the two statements is true. In logic, that would be known as an "exclusive or". What we have instead in this case is an inclusive or, where it is possible for both statements to be true and at least one of them is true.
Hypothetical syllogism. Premises: p => q, q => r. Conclusion: p => r
This can be seen as a sequence of implication. When p is true, it causes q to be true. When q is true, it causes r to be true. So, if p is true, it will also cause r to be true. Also, using the same reversals as before, if r is false, it causes q to be false, which in turn causes p to be false.
Example: If it rains, I will bring my umbrella. If I bring my umbrella, I will lose it. so, if it rains, I will lose my umbrella.
There are many more rules of inference, some of which include more (and sometimes fewer) premises. In all of them, the single characteristic is the following: the conclusion follows directly from the premises. All that is at work are the rules of logic and inference. These rules are important; as I mentioned earlier, they give us guidelines in finding new facts, from previously known ones. This is not limited to Mathematics. Science, Law, Medicine all rely on the application of logic to their specific fields. A good understanding of logic is almost indispensable in most academic pursuits.
Of course, logic is often misused. There are many fallacies and errors which can be inadvertently committed by the misapplication of logical rules. I will be going over some of the more common errors of logic in my next post.
As an example, let us take the statement "All my friends are taller than I am". Then, let us take the statement "Ed is my friend". Inference tells us that "Ed is taller than I am". If both the first two statements (premises) are true, then so is the third statement (conclusion). If, however, at least one of the premises is false, then the conclusion need not be true. For example, it might not be the case that all my friends are taller than I am. Then Ed may or may not be taller than I am. The creation of this conclusion from the premises above is a valid rule of inference, known as Universal Instantiation. This rule takes a characteristic of a set and applies it to a specific element in the set.
There are various other rules of inference, most of them dealing with taking two premises that are somehow related and extracting from them a conclusion which is related to each of them. The following is a short list of some common rules, with examples. I will use the letters p, q and r as statements, ~ as the negation symbol "NOT", ^ as the conjunction symbol "AND", * as the disjunction symbol "OR" and => (with other similar arrows) as the implication symbols.
Modus ponens (affirming the antecedent). Premises: p, p => q. Conclusion: q.
Here, one of the statements implies the other. Whenever p is true, it makes q true as well. We also have that p is true. Therefore, q must be true as well.
Example: If there is cake, I will eat it. There is cake. So, I will eat it. Here, p is "there is cake" and q is "I will eat the cake".
Modus tollens (denying the precedent). Premises: p => q, ~q. Conclusion: ~p.
This, in a sense, is the reversal of the previous rule. Again, p implies q. If p were true, q would be true. But q is false. So p cannot be true either.
Example: If there is cake, I will eat it. I will not eat cake. Therefore, there is no cake. (Otherwise, I'd be eating it).
Reductio ad absurdum (reduction to the absurd). Premises: p => q, p => ~q. Conclusion: ~p.
This one is a bit of a tricky one at first. In essence, if some statement being true makes another statement both true and false, then the first statement must be false.
Example: If I have a first-born, it is a boy. If I have a first-born, it is a girl. So, I do not have a first-born. (If I did, it would have to be both a boy and a girl).
Disjunctive syllogism. Premises: p * q, ~p. Conclusion: q.
Here we are given that at least one of our premises must be true. We are also given that one of them is definitely false. Then, we know that the other premise has to be the true one.
Example: My wall is white, or the door is open. The door is closed. So, my wall is white.
Note that here, the word "or" does not mean that only one of the two statements is true. In logic, that would be known as an "exclusive or". What we have instead in this case is an inclusive or, where it is possible for both statements to be true and at least one of them is true.
Hypothetical syllogism. Premises: p => q, q => r. Conclusion: p => r
This can be seen as a sequence of implication. When p is true, it causes q to be true. When q is true, it causes r to be true. So, if p is true, it will also cause r to be true. Also, using the same reversals as before, if r is false, it causes q to be false, which in turn causes p to be false.
Example: If it rains, I will bring my umbrella. If I bring my umbrella, I will lose it. so, if it rains, I will lose my umbrella.
There are many more rules of inference, some of which include more (and sometimes fewer) premises. In all of them, the single characteristic is the following: the conclusion follows directly from the premises. All that is at work are the rules of logic and inference. These rules are important; as I mentioned earlier, they give us guidelines in finding new facts, from previously known ones. This is not limited to Mathematics. Science, Law, Medicine all rely on the application of logic to their specific fields. A good understanding of logic is almost indispensable in most academic pursuits.
Of course, logic is often misused. There are many fallacies and errors which can be inadvertently committed by the misapplication of logical rules. I will be going over some of the more common errors of logic in my next post.