CS157: Logic in Real Life: From Engineering to Computer Science

Optional Logic is an ancient discipline that has been studied by many great thinkers, from Aristotle to Kurt Godel. Logic dates back at least to the ancient Greeks, and was part of the trivium, which was this set of three subjects that were taught in Greek education, along with grammar and rhetoric. This subject continues to be a subject of study today, with contributions from a wide variety of big minds and great minds; Leibnitz, Russell and Whitehead in the middle there, JR and Robinson on the right and George Boole over here. These people have all made contributions to logic enhancing its expressiveness, ability to derive 2D reasoning etc. Today it is a very active area for research particularly in relation to computers. If you are interested in the history of logic, we recommend a book called Logicomix. If you prefer a more accessible account, consider a graphic novel like Logicomix, which was written by an eminent logician and illustrated by some really talented artists who paint a compelling picture of logic in the 20th century. From there, let's turn to the subject matter itself: we use logic every day — not just in mathematics but also in many other areas. Logic is used to prove theorems in mathematics, for engineering design, and for figuring out which configurations of logic gates will accomplish the functionality you want. The process of identifying faulty gates in a circuit is based on logical reasoning. One must determine which gate is faulty by observing inputs and outputs in order to troubleshoot the circuit. This can be done through logical reasoning and pervades engineering, including mechanical engineering and software engineering. Logical reasoning is also applied elsewhere: for instance, when writing programs to perform some task or verify that programs do what they're supposed to do, or when debugging programs that give results we didn't expect from them. Logic is used in the creation of laws, rules and regulations, policies for organizations and establishments, and academic requirements at educational institutions. It can also be found in games by determining what steps need to be taken to win the game based on an opponent's moves; this process is called problem-solving. Logic is used in public debates to create or argue policy changes or other forms of legislation; this process is called debating. It can be employed in personal interactions between individuals of the same or different professions, whether it is in a professional setting or not; this process is called reasoning. Computer science relies on logic to prove the validity of its theories. Whether you are proving that an algorithm works or that it has certain computational characteristics, or whether you are in machine learning and do not normally think of logic as being a thing that machine learning papers themselves have theorems in them and have proofs of those theorems in them, computer scientists use logic to prove the validity of theories. Computer science is rooted in logic, a branch of mathematics. It has been said that logic is the mathematics of computer science, just as calculus is the mathematics of physics. If you want to become a physicist, you must learn calculus. If you would like to be a computer scientist, you must study logic. It's an indispensable skill for us—more important than calculus. Calculus does play a role in some aspects of computer science, but logic is foundational for all branches of computer science. The topic for today is logic, and some basic principles of logic. Today we'll begin by defining what logic is. Logic is the study of valid inference — reasoning done correctly. Consider the following example. Suppose we have four people: Abby, Bess, Cody and Dana. Some of these people like each other; some dislike each other. We can capture this information using a table such as the one below: Let us suppose that the world is organized into rows and columns. In this case, Abby likes people in Row 1, Bess likes people in Row 2, and so on. In this scenario, Abby likes Cody, Bess likes Cody; Cody likes Abby, and so forth. This scenario is one way the world might be. We could also have a table where there are different people liking different other people. There are many ways that a romantic relationship can progress. For example, it can be complicated and occur in the real world. We want to know, okay, how is the real world? Who likes whom anyway? There are 16 different possibilities in this table. Now, one person might tell us which table it is. They provide us some information and we're done. But normally, what happens is that we're given little tidbits of information over time. We receive information from people who tell us what they have overheard. For example, someone might say that Dana likes Cody and someone else might say that Abby dislikes Dana. By the way, Dana dislikes Abby either. We have to make judgments about these bits of information based on our knowledge of the situation and what we see in other situations. For one situation we know directly that Dana likes Cody, but for another situation we do not know whether it is true or false because we do not have enough information yet to make a judgment about it. Here, we know it is either Cody or Dana liking everyone the Bess likes. Abby likes everyone who is liked by Bess. Cody likes whoever likes her, but she also likes herself. These are the clues that give us an idea of how the world works and who likes whom. Our job is to understand this process. We do so by examining the information at hand and determining what must be true in this world — if that information is true. In this case, these sentences are premises. From those premises, we can conclude some things about our world. For example, we know that some statements are false. We also know there may be statements that we do not yet know but can infer from what we have been told so far. Let's see. It says here that it is false that Bess likes Dana. Why is that? Well, does anybody know why? The statement that Abby likes everyone that Bess likes and Abby doesn’t like Dana can be logically connected to the previous statement that Bess likes Cody, which is known to be true. This allows us to conclude, then, that Bess dislikes Dana. What makes Bess like Cody? Foremost, we know that she doesn’t Dana. We can infer from this that Bess likes Cody. To conclude, we are using some additional tidbits of information and a line of reasoning to derive new information that is not explicitly stated in the sentence. Logical reasoning allows us to deduce the truth or falsity of a statement given certain premises. In the example above, we are given just parts of the information and not all of it; however, using logical reasoning, we can deduce that Dana likes Bess since there is no one world in which Dana likes Bess and one world in which she doesn't. Logic is a field of study concerned with how we draw conclusions from premises. It reminds of looking at a situation where there are certain things that follow from the premises and there are certain things that are definitely not true given the premises as well. Logic is concerned with how we write these sentences? What's the language for encoding such sentences and then how do we derive conclusions like these from those sentences? There are two ways that you can do that: one way of determining whether a logical argument is sound is to determine whether each possible world satisfies the premises. If so, we then ask whether the conclusion is true or false according to that world. If every case in which the premises are true also satisfies the conclusion, then it must be true in all such cases. However, this approach can be time-consuming even for computers; it requires essentially listing all possible worlds and checking them one by one. While model checking works in some cases, it's not always efficient. For example, if we have 65,000 possibilities to check and infinite models, we'll never get done with that approach. Logical reasoning is one approach to reasoning. How do we develop logical reasoning? How did we come to that conclusion so quickly? Well, sometimes model checking doesn't work so well. The approach of symbolic manipulation involves deriving conclusions based on the forms of sentences. For example, if all of Abby's friends are Bess's friends and all Bess's friends are Cody's friends, it wouldn't be hard to figure out that all of Abby's friends are Cody's friends. All of A's are B's and all of B's are C's, therefore all A's are C's. This is straightforward because "all" implies the meaning "each and every one," and this is inherent in the word "all." One way to make such an argument is to show that there is a syntactic structure to the sentences; that is, one can show that the sentences have a particular structure (for example, "All Hondas are Accords, all Accords are Japanese cars"). In this case, you could conclude that all Hondas are Japanese cars. This sort of reasoning has nothing to do with friends. Another way to make such an argument would be to say something like, "All borogoves are slithy toves, all slithy toves are mimsy; therefore, all borogoves are mimsy." Notice that you don't really have to know what a borogove or slithy tove is or know what it means to be mimsy in order to reason like this. Logic has nothing at all to do with meaning or individual real-world references in these sentences. If we believe the following two sentences — for any x and y, all x's are y's, and all y's are z's — we will effectively be forced to believe that the last statement follows logically from the first two. All x's are z's. All z are y All y are z Therefore, all x are z. The word "all" means "every single one of" when it is used in the plural. Bertrand Russell, a famous philosopher and logician, wrote that logic can be defined as that branch of philosophy in which we never know what we're talking about nor whether what we're saying is true. What does he mean? We don't know what I'm talking about because it doesn't really matter what slithy toves are in order to derive a logical conclusion. We don't really know whether that conclusion is true. We can only derive logical conclusions from the things we already understand. If a logical pattern applies to one set of statements, it also applies to another. However, this does not mean that the premises are true—we simply cannot determine that. We were told those premises and believed in them, but we do not know whether they are true; therefore, we can only accept or reject their conclusion based on our own preexisting beliefs. The notion that we can capture all of reasoning as a set of patterns like those shown here is compelling and suggests that maybe we can apply these patterns to all forms of logical reasoning. The question is, which patterns are the most useful? Which ones should we focus on? Here's another pattern to consider. Some x's are y's; all y's are z's. We could infer that some x's are z's. Let's see how it works. All x are y Some y are z Therefore, some x are z. Let's consider an example. All Toyotas are Japanese cars, some Japanese cars are made in America, therefore some Toyotas are made in America. We didn't do so bad with that line of reasoning; the problem is there are other instances where your reasoning will lead you to incorrect conclusions: All Toyotas are cars and some cars are Porsches so some Toyotas are Porsches—that doesn't hold up. What happened there was we used an unsound rule of inference (also known as logical fallacy). When logic is applied to reasoning, a rule is said to be sound if and only if the conclusion is true whenever the premises are true. If this is the case, then the rule of inference is sound. The first rule we looked at was sound; the second one was not sound because it had a false premise. When an argument uses deduction, we refer to this type of reasoning as deduction — the process by which a conclusion is reached from one or more premises. Whenever we form a conclusion using one of these rules of inference, it has to be true; there's no way it can be false provided that all the premises are true. Now, deduction is not the only kind of reasoning. There is incomplete induction: induction that doesn't have all its premises covered, so we can't say that it's complete induction. Incomplete induction is similar to deductive reasoning, except that it goes from specific cases to general laws or hypotheses after observing patterns in those cases — a process known scientifically as forming hypotheses. Induction is not a valid method of reasoning on its own, but it is useful in numerous instances. For example, consider the following argument: "I have seen 1000 black ravens; I have never seen a raven that's not black. Therefore, every raven is black." This argument is not necessarily sound because it might be wrong; however, it can be a useful way to make an educated guess about the situation at hand. Although deduction is a sound form of reasoning, you cannot use it incorrectly because it will never lead to an incorrect conclusion. Induction — a different kind of reasoning that looks at what caused something to happen and makes generalizations based on those causes—can be useful in science and machine learning. These fields use induction because they need to find the causes behind things so they can apply those causes to other instances. Newtonian mechanics works until relativistic mechanics has to take over and then we have to bring in quantum physics and so forth. Sometimes we make generalizations, but they may not be completely accurate in our cases; we must tune and tweak them a little to get them right. Deduction never leads you to that; it's always going to give you correct answers. When you're trying to understand the world around you, science is the way to go. As it says here, it aspires to discover new knowledge so that it can form new generalizations. Whereas logic aspires to use previous generalizations in order to figure out what the conclusions are from those things — not that the premises are right, but it tells you whatever your conclusions are must be right. Deductive reasoning and inductive reasoning are both important aspects of the way we think. But deduction is more fundamental than induction, while induction offers the opportunity to learn new things from the world. In fact, Albert Einstein once complained that physicist Niels Bohr was not thinking but just being logical — an accusation that meant Einstein did not think Bohr was making any new discoveries about how the world works. Given that logic is about defining concepts and deriving conclusions from those definitions, we will be studying formal languages for encoding information like definitions. The triangle example given here in English can be expressed as a formal language. Constraints are statements in formal languages that limit the allowable values of variables. The constraint "Parents must be older than their children" is an example. This type of constraint does not define who a parent is, but it gives you a constraint on the ages of parents and their kids. Or it could be just partial information like, Abby likes one of Cody or Dana. But we don't know which. We'll be looking at three topics: logical reasoning, both model checking techniques and metalevel concepts. We'll prove that all possibilities have been considered, including truth tables and logic breeds; we'll also prove equivalent transformations and find out the two formulas are logically equivalent. In addition to doing that, we will be studying metalevel concepts and metalevel analysis. In other words, as we proceed through this course, we'll give names to logical concepts and prove things about statements like, for example, does this technique equal that technique? This rule sounds like it's complete—is it equivalent to this other one? So we're going to do some proofs about logic itself as opposed to proofs about Abby, Bess, Cody, and Dana. There are many extensions to what we will discuss in this course. We will discuss languages which are capable of expressing more complex forms of things, such as probabilities. We will also discuss languages used to describe knowledge about knowledge; that is, not just knowledge of the world but my knowledge and your knowledge and so forth. We will touch on paradoxes as well. We won't be covering these areas of reasoning: negation as failure, which is the distinction between knowing that something's not true versus not knowing that it is true. Not knowing that it is true is not the same as knowing that it's not true; induction, abduction or analogical reasoning; and other work expressing what we'll be doing here. For example, paraconsistent reasoning. How do you reason when you've got inconsistent facts? What are the problems of reasoning with inconsistent premises, and what are the techniques for dealing with them? Again, logic research has given us answers to these questions in other contexts, but they're all beyond the scope of this course so we'll touch on them but not go deeply into these subjects (using symbolic logic to investigate philosophical problems and arguments). To illustrate the different forms logical arguments can take, we've used sentences in English so far. However, it's not always easy to understand the structure of an English sentence — even native speakers have difficulty sometimes — and furthermore, natural languages are inherently ambiguous. As a result, it's important to eliminate these ambiguities when we're speaking and writing about logic so that our meaning is clear. As an example of the complexity of natural language, consider this sentence: "The cherry blossoms in the spring." Where is the fall now? One might think that since "blossoms" refers to a tree's flowering — a springtime event—the sentence should read "the cherry tree blossoms in the spring." However, if one considers that "blossoms" is plural, while "spring" is singular, then it becomes clear that the sentence should read: "The cherry blossoms in the spring." Here's another example of complex grammar: "The cherry blossoms in the spring; I didn't write the whole sentence. Sometimes it takes people a second to understand what that means. The cherry blossoms fell off the cherry trees and sank into the water, so "sank" is the verb, "cherry blossoms" is a noun phrase and "in the spring" gives us information about location. This can be tricky, and sometimes people can get it wrong. Consider the following sentence in English: There is a girl in the room with a telescope. Without context, there is no way to know what this sentence is referring to. It could be that there is a girl in the room, who has a telescope; or it could be that there is just a girl with a telescope, but no room. The ambiguity of the English language makes it impossible to know for sure. We do not know which is correct. Context may resolve the problem in various circumstances, but then that's a much more complicated thing, and it was not guaranteed to be right. We would like to eliminate such ambiguities. However, these ambiguities are not terrible in real life because they can lead to fun. The walls of the cafeteria are covered with headlines from newspapers around the world. Crowds Rush to See Pope Trample 6 to Death, reads one. Who knew that the pope was so mean as to trample people to death? Another headline asks, Scientists Grow Frog Eyes and Ears. Well, probably doesn't mean they got funny-looking eyes and ears. A third declares: Fried Chicken Cooked in Microwave Wins a Trip. Can chickens take trips? Finally, a headline from England reads British Left Waffles on the Falkland Islands. This one actually got me for a second. Why did the British leave waffles on the Falkland Islands? Did they not like waffles? Were they so bad that they had to leave the damn waffles on the Falkland Islands? Or was it the case that the leftist party in Britain was unclear what to do about the Falklands? Which of course is what it meant. The writers of these headlines used wording that could be interpreted in multiple ways. For example, "Residents report that a hole was cut in the fence surrounding a nudist colony." Although it seems reasonable to report that there is a hole in the fence, this statement could also imply that residents believe someone cut through the fence. Because English is ambiguous innately, native speakers can easily misinterpret statements; however, nonnative speakers are especially vulnerable to such misunderstandings because they may not fully understand English idioms or colloquialisms. Let's examine an example. Champagne is better than beer; beer is better than soda. Therefore, champagne is better than soda. You may disagree about those two things, but somebody likes champagne more than beer and somebody likes beer more than soda. That's reasonable and it's a fairly reasonable deduction to perform. X is better than Y; Y is better than Z; therefore, X is better than Z. Who's going to complain about that? Seems pretty reasonable. X is better than Y. Y is better than Z. Therefore , X is better than Z. Sex that is bad and merely "better than nothing" is still not good. Sex that is good, but not better than nothing, is still not good. The question is "What's wrong here?" The answer is the meaning of the word nothing and how we use the word nothing in English. The answer requires an understanding of how we use words in general. It means one thing in the first sentence. It's used in one syntactic construct in the first sentence and it's a totally different construct in the second sentence. However, because syntactically it looks like the others, if we're implementing this in a computer we might make the mistake of deriving that conclusion and getting it wrong. We want languages that don't have problems like this. For those reasons, we go to formal languages and codify everything in formal languages to manipulate them. This is not new in logic. In algebra, we solve this by multiplying each side of the equation by "3" to make "Xavier's age" and "Yolanda's age" equal to 12. × − 3𝑦 = 0 𝑥 + 𝑦 = 12 − 4𝑦 =− 12 𝑦=3 𝑥=9 When we convert a problem into symbolic form, it becomes easier to manipulate the variables. When we make x equal 3y, we can then cancel the x's and subtract 4y from both sides. After canceling the x's and simplifying, we are left with y equals 3. Therefore x equals 9. We can easily solve problems this way because there are no ambiguities about any mistakes we might make. In logic, we use a similar process. If Mary loves Pat, and it's Monday and raining, then Mary either loves Quincy or she does not. This can be expressed in symbols as follows: p implies q, if Mary loves Pat then Mary loves Quincy; m and r implies p or q. Here are our premises: p implies q, m and r implies p or q. And here is our conclusion: Therefore, it is true that if (p and m) then either q or not-q (that is, not-q). You can cancel the same thing when it occurs on the opposite sides of implications like this. Then you get the line below m and r implies q or q, or q where q is the same as q. If it's Monday and raining, then Mary loves Quincy. The technique is similar, you codify symbols, you do some canceling, and you get your results. When you use logic, you capture information in formulas and rules. These formulas and rules are always right because they are intentionally stated; there is no ambiguity or mistake when you use symbolic logic. Therefore, we will state the principles of logic in symbolic form rather than just in natural language form. That's all I wanted to say about an overview of material. Let's move ahead here and discuss logistical matters concerning the course. First, we have been discussing the subject of logic as if it were a single thing. Although there are various branches of mathematics — group theory, topology, algebra — there are also various different kinds of logic. The difference is how expressive the languages are and then what reasoning rules apply to those sentences. This course introduces a progression of logical systems, beginning with propositional logic. Propositional logic adds only logical operators and atomic propositions to the language of first-order logic. Relational logic adds quantifiers and variables to the propositional system. Functional logic expands the language further by adding functions. Finally, proof theory and model theory comprise the core topics for intermediate logic. Propositional logic is the basis of formal reasoning and will be covered in this course. Propositional logic is a simple form of logical language, and we will limit our discussion to this simple language because it allows us to focus on the essential concepts of logic.