Combinatorics is usually one of the first non-introductory topics in discrete mathematics that students encounter in their mathematical studies. This also makes it one of the hardest topics to get to grips with, as it often requires a different way of thinking from other mathematical fields, such as calculus.
Combinatorics encompasses various subfields of study of discrete structures. In general, when given a problem in combinatorics, it will usually belong to one of three categories:
1) The existence problem. Given a problem, with specific characteristics and parametres, does a solution to this problem exist? For example, the dean's office at a college will want to assign time slots and classrooms to the various courses which will be taught in the semester. Such an assignment must not have two courses at the same time if the same professor is teaching them. (It is also usually desired that, if a lot of students are expected to take two courses concurrently, these courses not be assigned at the same time, if possible). Furthermore, if two courses are at the same time, they should not be assigned to the same room. Finally, if certain courses are expected to have large numbers of students, they should be assigned to large classrooms, so that everyone can have a seat. Given a list of courses, time slots and classrooms can such an arrangement be found? This is the existence problem. Sometimes there are no solutions to these problems. If, for example there is only one professor teaching both calculus and algebra, both classes needing the same single amphitheatre, and there is only one available time slot, the problem becomes impossible.
2) The counting problem. As mentioned before, some problems cannot be solved. Sometimes, on the other hand, a problem will have more than one possible solution. In our classroom assignment question, there could be several different assignments, which all work with the given parametres. The counting problem asks us to find how many different ways a problem can be solved. If there are two courses to be assigned to two different classrooms, at the same time, we can do this in two different ways; either have the first course in the first room and the second one in the second room, or vice versa.
3) The optimisation problem. Having figured out the different ways in which we can solve a given problem, we may then be interested in the best (whatever this means) solution out of the possible ones. For example, in the classroom assignment problem, we may want to pick the assignment that uses the fewest time slots, or the one that uses the fewest classrooms, or even the one with the fewest clashes between courses with common students. The optimisation problem is probably the most important one of the three, in the sense of solving applied problems, but it is often impossible to get started on, without a thorough understanding of the other two.
I will close this post by mentioning that the field of combinatorics is probably the largest one in mathematics, as it encompasses theory which is needed for almost all other mathematical fields. It would be impossible for a simple blog to present it properly, but perhaps in future posts, I may be able to present some of the more fundamental ideas.
Saturday, May 26, 2012
Sunday, April 29, 2012
Graph Theory
We come now to my own personal field of interest, the subject of graph theory. This has nothing to do with pie charts or bar graphs; these are a different kind of graph.
Formally, a graph is a special type of mathematical structure, composed of two parts. The first part is a set, a collection of distinct elements called vertices or nodes. The second is a collection of 2-tuples of the vertex set. These 2-tuples are the edges. Visually, we represent a graph as a network. The vertices are points and the edges are lines connecting these points. More specifically, we are usually interested in graphs with a finite vertex set and where the edges are distinct and connect distinct vertices. The networks we draw for these graphs will have at most one edge between two vertices and no loops on any single vertex.
Graph theorists are interested in many different characteristics of graphs. The reason these characteristics are studied is that there are many applications to real world problems which are more easily solved with graphs. For example, computer networks could not run smoothly and successfully without a proper understanding of graph theory, resource allocation problems become much harder to solve and so on and so forth.
The biggest problem for students learning graph theory is its apparent lack of connectivity to other mathematical topics. More often than not, students have a background that is (perhaps detrimentally) over-abundant in calculus (or rather, the techniques of calculus) and therefore lack a proper foundation in more fundamental branches of Mathematics, including set theory. This means that they will be bombarded with several new definitions and almost none of them will be present in their mathematical background; they will have no previous knowledge to draw upon, to help them understand these new topics. In this post (and hopefully future ones), I will attempt to give these definitions in a slower, more relaxed pace, than a graph theory course would require. Perhaps this method would be best suited for a two semester graph theory course, but that is neither here nor there.
We first consider the idea of measuring things about a graph. How large or small a graph is can depend on what we are using it for. The two most generals ways in which we measure graphs are the number of vertices it has (known as the order of the graph) and the number of edges it has (known as the size). For example, if you look at a map of, say, major motorways and represent these motorways as edges in a graph, the size of the graph will be the number of motorways you have. On the other hand, the order will be the number of destinations (cities for example) that are connected by these motorways. The order and size of a graph, give us an idea of how large our graph is. They also tell us other things, like how dense or sparse a graph is. For example, if a graph has 10 vertices, the largest number of edges it can possibly have is 45. If we have a graph with 10 vertices and only 15 edges, this could be considered a very sparse graph. If on the other hand it had 40 edges, this would be a very dense graph. The ideas of density and sparsity become more important when other measurements are made on graphs, but they're interesting enough on their own as well.
The next simplest definition we can give for graphs is that of adjacency. We say that two vertices are adjacent (or neighbouring), if there is an edge between them. That is, if we have an edge connecting the vertices u and v, then u and v are adjacent. We also say that v belongs in the neighbourhood of u (and vice-versa). In computer networking, if we take a graph of connections in a serve-client model, we could say that a server is adjacent to the clients it is connected to.
It is often the case that we want to know how many neighbours a vertex has (usually because we want to minimise them or maximise them). The number of neighbours of a vertex u, or the number of vertices adjacent to u, is denoted as d(u) and is known as the degree of u. Vertices with many neighbours will have a high degree. In the server-client model, the degree of each server is the number of clients it connects to.
Clearly, there are many more questions one can ask about graphs. (Is there a way to get from a certain vertex to another, following the edges between adjacent vertices? Is there a way to start at some vertex in a graph, and go through every edge exactly once, going sequentially through adjacent vertices? How many colours do we need to colour the countries of a map, so that no neighbouring countries share the same colour?) However, this post is a mere introduction to the idea of what a graph is, and will not delve any deeper into the theory. Perhaps in future posts, I will try to answer these and other questions about graphs.
Formally, a graph is a special type of mathematical structure, composed of two parts. The first part is a set, a collection of distinct elements called vertices or nodes. The second is a collection of 2-tuples of the vertex set. These 2-tuples are the edges. Visually, we represent a graph as a network. The vertices are points and the edges are lines connecting these points. More specifically, we are usually interested in graphs with a finite vertex set and where the edges are distinct and connect distinct vertices. The networks we draw for these graphs will have at most one edge between two vertices and no loops on any single vertex.
Graph theorists are interested in many different characteristics of graphs. The reason these characteristics are studied is that there are many applications to real world problems which are more easily solved with graphs. For example, computer networks could not run smoothly and successfully without a proper understanding of graph theory, resource allocation problems become much harder to solve and so on and so forth.
The biggest problem for students learning graph theory is its apparent lack of connectivity to other mathematical topics. More often than not, students have a background that is (perhaps detrimentally) over-abundant in calculus (or rather, the techniques of calculus) and therefore lack a proper foundation in more fundamental branches of Mathematics, including set theory. This means that they will be bombarded with several new definitions and almost none of them will be present in their mathematical background; they will have no previous knowledge to draw upon, to help them understand these new topics. In this post (and hopefully future ones), I will attempt to give these definitions in a slower, more relaxed pace, than a graph theory course would require. Perhaps this method would be best suited for a two semester graph theory course, but that is neither here nor there.
We first consider the idea of measuring things about a graph. How large or small a graph is can depend on what we are using it for. The two most generals ways in which we measure graphs are the number of vertices it has (known as the order of the graph) and the number of edges it has (known as the size). For example, if you look at a map of, say, major motorways and represent these motorways as edges in a graph, the size of the graph will be the number of motorways you have. On the other hand, the order will be the number of destinations (cities for example) that are connected by these motorways. The order and size of a graph, give us an idea of how large our graph is. They also tell us other things, like how dense or sparse a graph is. For example, if a graph has 10 vertices, the largest number of edges it can possibly have is 45. If we have a graph with 10 vertices and only 15 edges, this could be considered a very sparse graph. If on the other hand it had 40 edges, this would be a very dense graph. The ideas of density and sparsity become more important when other measurements are made on graphs, but they're interesting enough on their own as well.
The next simplest definition we can give for graphs is that of adjacency. We say that two vertices are adjacent (or neighbouring), if there is an edge between them. That is, if we have an edge connecting the vertices u and v, then u and v are adjacent. We also say that v belongs in the neighbourhood of u (and vice-versa). In computer networking, if we take a graph of connections in a serve-client model, we could say that a server is adjacent to the clients it is connected to.
It is often the case that we want to know how many neighbours a vertex has (usually because we want to minimise them or maximise them). The number of neighbours of a vertex u, or the number of vertices adjacent to u, is denoted as d(u) and is known as the degree of u. Vertices with many neighbours will have a high degree. In the server-client model, the degree of each server is the number of clients it connects to.
Clearly, there are many more questions one can ask about graphs. (Is there a way to get from a certain vertex to another, following the edges between adjacent vertices? Is there a way to start at some vertex in a graph, and go through every edge exactly once, going sequentially through adjacent vertices? How many colours do we need to colour the countries of a map, so that no neighbouring countries share the same colour?) However, this post is a mere introduction to the idea of what a graph is, and will not delve any deeper into the theory. Perhaps in future posts, I will try to answer these and other questions about graphs.
Sunday, March 25, 2012
Finite State Machines
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.
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.
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.