{"id":23748,"date":"2023-05-10T01:29:31","date_gmt":"2023-05-10T01:29:31","guid":{"rendered":"https:\/\/www.booksofall.com\/in\/?post_type=product&p=23748"},"modified":"2023-05-10T01:29:31","modified_gmt":"2023-05-10T01:29:31","slug":"delftse-foundations-of-computation-2","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/in\/delftse-foundations-of-computation-2\/","title":{"rendered":"Delftse Foundations of Computation"},"content":{"rendered":"

Chapter 2 – <\/span>Logic<\/span><\/h2>\n

In a scene, we know a lot more than we realise, because everything that <\/span>we know has consequences\u2014<\/span>logical<\/span> consequences\u2014that follow automat<\/span>ically. If you know that all humans are mortal, and you know that Socrates is <\/span>human, then in a sense you know that Socrates<\/a> is mortal, whether or not you <\/span>have ever considered or wanted to consider that fact. This is an example of <\/span>logical deduction<\/span>: from the<\/span> premises<\/span> that \u201cAll humans are mortal\u201d and \u201cSo<\/span>crates is human\u201d, the<\/span> conclusion<\/span> that \u201cSocrates is mortal\u201d can be deduced <\/span>by logic.<\/span><\/p>\n

Logical deduction is a kind of computation. By applying rules of logic <\/span>to a given set of premises, conclusions that follow from those premises can <\/span>be generated automatically. This computational process could for instance <\/span>be carried out by a computer.<\/span> Once you know the premises, or are will<\/span>ing to accept them for the sake of argument, you are forced<\/span> by logic<\/span> to ac<\/span>cept the conclusions. Still, to say that you \u2018know\u2019 those conclusions would <\/span>be misleading. The problem is that there are too many of them (infinitely <\/span>many), and, in general, most of them are not particularly interesting. Until <\/span>you have actually made the deduction, you don\u2019t<\/span> really<\/span> know the conclusion, <\/span>and knowing which of the possible chains of deduction to follow is not easy. <\/span>The<\/span> art<\/span> of logic is to find an interesting conclusion and a chain of logical de<\/span>ductions that leads from the premises to that conclusion. Checking that the <\/span>deductions are valid is the mechanical, computational side of logic.<\/span><\/p>\n

This chapter is mostly about the mechanics of logic. We will investig<\/span>ate logic as a branch of mathematics, with its own symbols, formulas and <\/span>rules of computation. Your objective is to learn the rules of logic, to under<\/span>stand why they are valid, and to develop skill in applying them. As with <\/span>any branch of mathematics, there is a certain beauty to the symbols and for<\/span>mulas themselves. But it is the applications that bring the subject to life for <\/span>most people. We will, of course, cover some applications as we go along. <\/span>In a sense, though, the real applications of logic include much of computer <\/span>science and of mathematics itself.<\/span><\/p>\n

Among the fundamental elements of thought, and therefore of logic, are <\/span>propositions. A<\/span> proposition<\/span> is a statement that has a truth value: it is either <\/span>true or false. \u201cDelft is a city\u201d and \u201c<\/span>2<\/span> +<\/span> 2<\/span> =<\/span> 42<\/span>\u201d are propositions. In the <\/span>first part of this chapter, we will study<\/span> propositional logic<\/span>, which takes pro<\/span>positions and considers how they can be combined and manipulated. This <\/span>branch of logic has surprising application to the design of the electronic cir<\/span>cuits that make up computers. This ties closely to the digital and boolean <\/span>logic you will study in your course<\/span> Computer Organisation<\/span>. <\/span>Logic gets more interesting when we consider the internal structure of <\/span>propositions. In English, a proposition<\/a> is expressed as a sentence, and, as<\/span>
you know from studying grammar, sentences have parts. A simple sentence <\/span>like \u201cDelft<\/a> is a city\u201d has a<\/span> subject<\/span> and a<\/span> predicate<\/span>. The sentence says something about its subject. The subject of \u201cDelft is a city\u201d is Delft. The sentence says something about Delft. The something that the sentence says about its subject is the predicate. In the example, the predicate is the phrase \u2018is a city\u2019. Once we start working with predicates, we can create propositions using quantifiers like \u2018all\u2019, \u2018some\u2019 and \u2018no\u2019. For example, working with the predicate \u2018has a university\u2019 we can move from simple propositions like \u201cDelft has a university\u201d to \u201cAll cities have a university\u201d or to \u201cNo city has a university\u201d or to the rather more realistic \u201cSome cities have a university\u201d.<\/span><\/p>\n

Logical deduction usually deals with quantified statements, as shown by the basic example of human mortality<\/a> with which we began this chapter. Logical deduction will be a major topic of this chapter; and under the name of proof , it will be the topic of the next chapter and a major tool for the rest of this book and indeed your computer science degree programme.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"