Sets, Logic, Computation - People.ucalgary.ca

1y ago
15 Views
2 Downloads
2.83 MB
326 Pages
Last View : 5d ago
Last Download : 2m ago
Upload by : Melina Bettis
Transcription

Sets, Logic, ComputationAn Open Logic TextFall 2017

Sets, Logic, Computation

The Open Logic ProjectInstigatorRichard Zach, University of CalgaryEditorial BoardAldo Antonelli,† University of California, DavisAndrew Arana, Université Paris I Panthénon–SorbonneJeremy Avigad, Carnegie Mellon UniversityWalter Dean, University of WarwickGillian Russell, University of North CarolinaNicole Wyatt, University of CalgaryAudrey Yap, University of VictoriaContributorsSamara Burns, University of CalgaryDana Hägg, University of Calgary

Sets, Logic, ComputationAn Open Logic TextRemixed by Richard ZachWinter 2017

The Open Logic Project would like to acknowledge the generoussupport of the Faculty of Arts and the Taylor Institute of Teachingand Learning of the University of Calgary.This resource was funded by the Alberta Open Educational Resources (ABOER) Initiative, which is made possible through aninvestment from the Alberta government.Illustrations by Matthew Leadbeater, used under a Creative Commons Attribution-NonCommercial 4.0 International License.Typeset in Baskervald X and Universalis ADF Standard by LATEX.This version of phil379 is revision f7344c9 (2017-07-18), withcontent generated from OpenLogicProject revision 977ec76 (201707-18).Sets, Logic, Computation by RichardZach is licensed under a CreativeCommons Attribution 4.0 International License. It is based on The OpenLogic Text by the Open Logic Project,used under a Creative Commons Attribution 4.0 International License.

ContentsPrefaceI12xiiiSets, Relations, Functions1Sets1.1 Basics . . . . . . . . . . . . . . . .1.2 Some Important Sets . . . . . . .1.3 Subsets . . . . . . . . . . . . . . .1.4 Unions and Intersections . . . . .1.5 Pairs, Tuples, Cartesian Products1.6 Russell’s Paradox . . . . . . . . .Summary . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . .224569111213Relations2.1 Relations as Sets . . . . . . . .2.2 Special Properties of Relations2.3 Orders . . . . . . . . . . . . .2.4 Graphs . . . . . . . . . . . . .2.5 Operations on Relations . . .Summary . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . .1414161821222324v.

viCONTENTS34Functions3.1 Basics . . . . . . . . . . . .3.2 Kinds of Functions . . . .3.3 Inverses of Functions . . .3.4 Composition of Functions3.5 Isomorphism . . . . . . . .3.6 Partial Functions . . . . . .3.7 Functions and Relations .Summary . . . . . . . . . . . . .Problems . . . . . . . . . . . . .The Size of Sets4.1 Introduction . . . . . . .4.2 Countable Sets . . . . . .4.3 Uncountable Sets . . . .4.4 Reduction . . . . . . . .4.5 Equinumerous Sets . . .4.6 Comparing Sizes of SetsSummary . . . . . . . . . . . .Problems . . . . . . . . . . . .26262830313233343435.373737434748505253II First-order Logic5Syntax and Semantics5.1 Introduction . . . . . . . . . . . . . . . . . . .5.2 First-Order Languages . . . . . . . . . . . . .5.3 Terms and Formulas . . . . . . . . . . . . . .5.4 Unique Readability . . . . . . . . . . . . . . .5.5 Main operator of a Formula . . . . . . . . . .5.6 Subformulas . . . . . . . . . . . . . . . . . . .5.7 Free Variables and Sentences . . . . . . . . . .5.8 Substitution . . . . . . . . . . . . . . . . . . .5.9 Structures for First-order Languages . . . . . .5.10 Covered Structures for First-order Languages5.11 Satisfaction of a Formula in a Structure . . . .57.585860626569707273757779

viiCONTENTS5.12 Variable Assignments5.13 Extensionality . . . .5.14 Semantic Notions . .Summary . . . . . . . . . .Problems . . . . . . . . . .678.8488909394Theories and Their Models6.1 Introduction . . . . . . . . . . . . .6.2 Expressing Properties of Structures6.3 Examples of First-Order Theories .6.4 Expressing Relations in a Structure6.5 The Theory of Sets . . . . . . . . .6.6 Expressing the Size of Structures .Summary . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . .9797100101104106109111111Natural Deduction7.1 Introduction . . . . . . . . . . . . .7.2 Rules and Derivations . . . . . . . .7.3 Examples of Derivations . . . . . .7.4 Proof-Theoretic Notions . . . . . . .7.5 Properties of Derivability . . . . . .7.6 Soundness . . . . . . . . . . . . . .7.7 Derivations with Identity predicate7.8 Soundness with Identity predicate .Summary . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . .113113115118127130135140142143143The Completeness Theorem8.1 Introduction . . . . . . . . . . . . . . .8.2 Outline of the Proof . . . . . . . . . . .8.3 Complete Consistent Sets of Sentences8.4 Henkin Expansion . . . . . . . . . . . .8.5 Lindenbaum’s Lemma . . . . . . . . .8.6 Construction of a Model . . . . . . . .8.7 Identity . . . . . . . . . . . . . . . . . .145145146149151153154157

viiiCONTENTS98.8 The Completeness Theorem . . . . . . . . .8.9 The Compactness Theorem . . . . . . . . .8.10 A Direct Proof of the Compactness Theorem8.11 The Löwenheim-Skolem Theorem . . . . . .Summary . . . . . . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . . . . .160161164166167168Beyond First-order Logic9.1 Overview . . . . . . . .9.2 Many-Sorted Logic . .9.3 Second-Order logic . .9.4 Higher-Order logic . .9.5 Intuitionistic Logic . .9.6 Modal Logics . . . . .9.7 Other Logics . . . . . .170170171173178181187189.III Turing Machines19310 Turing Machine Computations10.1 Introduction . . . . . . . . . . . .10.2 Representing Turing Machines . .10.3 Turing Machines . . . . . . . . . .10.4 Configurations and Computations10.5 Unary Representation of Numbers10.6 Halting States . . . . . . . . . . .10.7 Combining Turing Machines . . .10.8 Variants of Turing Machines . . .10.9 The Church-Turing Thesis . . . .Summary . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . .194194197202203205206207209211212213.11 Undecidability21511.1 Introduction . . . . . . . . . . . . . . . . . . . . . 21511.2 Enumerating Turing Machines . . . . . . . . . . . 21711.3 The Halting Problem . . . . . . . . . . . . . . . . 219

ixCONTENTSABC11.4 The Decision Problem . . . . . . . .11.5 Representing Turing Machines . . . .11.6 Verifying the Representation . . . . .11.7 The Decision Problem is Unsolvable .Summary . . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . .221222226233233234ProofsA.1 Introduction . . .A.2 Starting a Proof .A.3 Using DefinitionsA.4 Inference PatternsA.5 An Example . . .A.6 Another ExampleA.7 Indirect Proof . .A.8 Reading Proofs .A.9 I can’t do it! . . .A.10 Other Resources .Problems . . . . . . . .237237239239241248253255259261263263InductionB.1 Introduction . . . . .B.2 Induction on N . . .B.3 Strong Induction . .B.4 Inductive DefinitionsB.5 Structural Induction graphiesC.1 Georg Cantor . .C.2 Alonzo Church .C.3 Gerhard GentzenC.4 Kurt Gödel . . . .C.5 Emmy Noether .C.6 Bertrand Russell .C.7 Alfred Tarski . . .C.8 Alan Turing . . .

xCONTENTSC.9Ernst Zermelo . . . . . . . . . . . . . . . . . . . . 287Glossary291Photo Credits297Bibliography299About the Open Logic Project304

PrefaceThis book is an introduction to meta-logic, aimed especially atstudents of computer science and philosophy. “Meta-logic” is socalled because it is the discipline that studies logic itself. Logicproper is concerned with canons of valid inference, and its symbolic or formal version presents these canons using formal languages, such as those of propositional and predicate, a.k.a., firstorder logic. Meta-logic investigates the properties of these language, and of the canons of correct inference that use them. Itstudies topics such as how to give precise meaning to the expressions of these formal languages, how to justify the canonsof valid inference, what the properties of various proof systemsare, including their computational properties. These questionsare important and interesting in their own right, because the languages and proof systems investigated are applied in many different areas—in mathematics, philosophy, computer science, andlinguistics, especially—but they also serve as examples of howto study formal systems in general. The logical languages westudy here are not the only ones people are interested in. Forinstance, linguists and philosophers are interested in languagesthat are much more complicated than those of propositional andfirst-order logic, and computer scientists are interested in otherkinds of languages altogether, such as programming languages.And the methods we discuss here—how to give semantics for formal languages, how to prove results about formal languages, howxiii

PREFACExivto investigate the properties of formal languages—are applicablein those cases as well.Like any discipline, meta-logic both has a set of results orfacts, and a store of methods and techniques, and this text covers both. Some students won’t need to know some of the resultswe discuss outside of this course, but they will need and use themethods we use to establish them. The Löwenheim-Skolem theorem, say, does not often make an appearance in computer science, but the methods we use to prove it do. On the other hand,many of the results we discuss do have relevance for certain debates, say, in the philosophy of science and in metaphysics. Philosophy students may not need to be able to prove these resultsoutside this course, but they do need to understand what theresults are—and you really only understand these results if youhave thought through the definitions and proofs needed to establish them. These are, in part, the reasons for why the resultsand the methods covered in this text are recommended study—insome cases even required—for students of computer science andphilosophy.The material is divided into three parts. Part 1 concerns itself with the theory of sets. Logic and meta-logic is historicallyconnected very closely to what’s called the “foundations of mathematics.” Mathematical foundations deal with how ultimatelymathematical objects such as integers, rational, and real numbers, functions, spaces, etc., should be understood. Set theoryprovides one answer (there are others), and so set theory andlogic have long been studied side-by-side. Sets, relations, andfunctions are also ubiquitous in any sort of formal investigation,not just in mathematics but also in computer science and in someof the more technical corners of philosophy. Certainly for thepurposes of formulating and proving results about the semanticsand proof theory of logic and the foundation of computability itis essential to have a language in which to do this. For instance,we will talk about sets of expressions, relations of consequenceand provability, interpretations of predicate symbols (which turnout to be relations), computable functions, and various relations

xvbetween and constructions using these. It will be good to haveshorthand symbols for these, and think through the general properties of sets, relations, and functions in order to do that. If youare not used to thinking mathematically and to formulating mathematical proofs, then think of the first part on set theory as atraining ground: all the basic definitions will be given, and we’llgive increasingly complicated proofs using them. Note that understanding these proofs—and being able to find and formulatethem yourself—is perhaps more important than understandingthe results, and especially in the first part, and especially if youare new to mathematical thinking, it is important that you thinkthrough the examples and problems.In the first part we will establish one important result, however. This result—Cantor’s theorem—relies on one of the moststriking examples of conceptual analysis to be found anywherein the sciences, namely, Cantor’s analysis of infinity. Infinity haspuzzled mathematicians and philosophers alike for centuries. Noone knew how to properly think about it. Many people eventhought it was a mistake to think about it at all, that the notionof an infinite object or infinite collection itself was incoherent.Cantor made infinity into a subject we can coherently work with,and developed an entire theory of infinite collections—and infinite numbers with which we can measure the sizes of infinitecollections—and showed that there are different levels of infinity.This theory of “transfinite” numbers is beautiful and intricate,and we won’t get very far into it; but we will be able to showthat there are different levels of infinity, specifically, that thereare “countable” and “uncountable” levels of infinity. This resulthas important applications, but it is also really the kind of result that any self-respecting mathematician, computer scientist,or philosopher should know.In the second part we turn to first-order logic. We will definethe language of first-order logic and its semantics, i.e., what firstorder structures are and when a sentence of first-order logic istrue in a structure. This will enable us to do two important things:(1) We can define, with mathematical precision, when a sentence

PREFACExviis a logical consequence of another. (2) We can also consider howthe relations that make up a first-order structure are described—characterized—by the sentences that are true in them. This inparticular leads us to a discussion of the axiomatic method, inwhich sentences of first-order languages are used to characterizecertain kinds of structures. Proof theory will occupy us next,and we will consider the original version of natural deduction asdefined in the 1930s by Gerhard Gentzen. The semantic notion ofconsequence and the syntactic notion of provability give us twocompletely different ways to make precise the idea that a sentencemay follow from some others. The soundness and completenesstheorems link these two characterization. In particular, we willprove Gödel’s completeness theorem, which states that whenevera sentence is a semantic consequence of some others, there is alsoa deduction of said sentence from these others. An equivalentformulation is: if a collection of sentences is consistent—in thesense that nothing contradictory can be proved from them—thenthere is a structure that makes all of them true.The second formulation of the completeness theorem is perhaps the more surprising. Around the time Gödel proved thisresult (in 1929), the German mathematician David Hilbert famously held the view that consistency (i.e., freedom from contradiction) is all that mathematical existence requires. In otherwords, whenever a mathematician can coherently describe a structure or class of structures, then they should be be entitled to believe in the existence of such structures. At the time, many foundthis idea preposterous: just because you can describe a structure without contradicting yourself, it surely does not follow thatsuch a structure actually exists. But that is exactly what Gödel’scompleteness theorem says. In addition to this paradoxical—and certainly philosophically intriguing—aspect, the completeness theorem also has two important applications which allow usto prove further results about the existence of structures whichmake given sentences true. These are the compactness and theLöwenheim-Skolem theorems.In the third part, we connect logic with computability. Again,

xviithere is a historical connection: David Hilbert had posed as afundamental problem of logic to find a mechanical method whichwould decide, of a given sentence of logic, whether it has a proof.Such a method exists, of course, for propositional logic: one justhas to check all truth tables, and since there are only finitely manyof them, the method eventually yields a correct answer. Such astraightforward method is not possible for first-order logic, sincethe number of possible structures is infinite (and structures themselves may be infinite). Logicians were working to find a moreingenious methods for years. Alonzo Church and Alan Turingeventually established that there is no such method. In order todo this, it was necessary to first provide a precise definition ofwhat a mechanical method is in general. If a decision procedurehad been proposed, presumably it would have been recognizedas an effective method. To prove that no effective method exists,you have to define “effective method” first and give an impossibility proof on the basis of that definition. This is what Turingdid: he proposed the idea of a Turing machine1 as a mathematical model of what a mechanical procedure can, in principle, do.This is another example of a conceptual analysis of an informalconcept using mathematical machinery; and it is perhaps of thesame order of importance for computer science as Cantor’s analysis of infinity is for mathematics. Our last major undertakingwill be the proof of two impossibility theorems: we will show thatthe so-called “halting problem” cannot be solved by Turing machines, and finally that Hilbert’s “decision problem” (for logic)also cannot.This text is mathematical, in the sense that we discuss mathematical definitions and prove our results mathematically. But itis not mathematical in the sense that you need extensive mathematical background knowledge. Nothing in this text requiresknowledge of algebra, trigonometry, or calculus. We have madea special effort to also not require any familiarity with the waymathematics works: in fact, part of the point is to develop the kinds1 Turingof course did not call it that himself.

PREFACExviiiof reasoning and proof skills required to understand and proveour results. The organization of the text follows mathematicalconvention, for one reason: these conventions have been developed because clarity and precision are especially important, andso, e.g., it is critical to know when something is asserted as theconclusion of an argument, is offered as a reason for somethingelse, or is intended to introduce new vocabulary. So we followmathematical convention and label passages as “definitions” ifthey are used to introduce new terminology or symbols; and as“theorems,” “propositions,” “lemmas,” or “corollaries” when werecord a result or finding.2 Other than these conventions, we willonly use the methods of logical proof as they should be familiarfrom a first logic course, with one exception: we will make extensive use of the method of induction to prove results. A chapter ofthe appendix is devoted to this principle.2 Thedifference between the latter four is not terribly important, butroughly: A theorem is an important result. A proposition is a result worthrecording, but perhaps not as important as a theorem. A lemma is a result wemainly record only because we want to break up a proof into smaller, easier tomanage chunks. A corollary is a result that follows easily from a theorem orproposition, such as an interesting special case.

PART ISets,Relations,Functions1

CHAPTER 1Sets1.1BasicsSets are the most fundamental building blocks of mathematicalobjects. In fact, almost every mathematical object can be seen asa set of some kind. In logic, as in other parts of mathematics,sets and set-theoretical talk is ubiquitous. So it will be importantto discuss what sets are, and introduce the notations necessaryto talk about sets and operations on sets in a standard way.Definition 1.1 (Set). A set is a collection of objects, consideredindependently of the way it is specified, of the order of the objectsin the set, or of their multiplicity. The objects making up the setare called elements or members of the set. If a is an element of aset X , we write a X (otherwise, a X ). The set which has noelements is called the empty set and denoted by the symbol .Example 1.2. Whenever you have a bunch of objects, you cancollect them together in a set. The set of Richard’s siblings, forinstance, is a set that contains one person, and we could writeit as S {Ruth}. In general, when we have some objects a1 ,. . . , an , then the set consisting of exactly those objects is written{a1, . . . , an }. Frequently we’ll specify a set by some property thatits elements share—as we just did, for instance, by specifying Sas the set of Richard’s siblings. We’ll use the following shorthand2

31.1. BASICSnotation for that: {x : . . . x . . .}, where the . . . x . . . stands for theproperty that x has to have in order to be counted among theelements of the set. In our example, we could have specified Salso asS {x : x is a sibling of Richard}.When we say that sets are independent of the way they arespecified, we mean that the elements of a set are all that matters.For instance, it so happens that{Nicole, Jacob},{x : is a niece or nephew of Richard}, and{x : is a child of Ruth}are three ways of specifying one and the same set.Saying that sets are considered independently of the order oftheir elements and their multiplicity is a fancy way of saying that{Nicole, Jacob} and{Jacob, Nicole}are two ways of specifying the same set; and that{Nicole, Jacob} and{Jacob, Nicole, Nicole}are also two ways of specifying the same set. In other words, allthat matters is which elements a set has. The elements of a setare not ordered and each element occurs only once. When wespecify or describe a set, elements may occur multiple times and indifferent orders, but any descriptions that only differ in the orderof elements or in how many times elements are listed describesthe same set.Definition 1.3 (Extensionality). If X and Y are sets, then X andY are identical, X Y , iff every element of X is also an element

4CHAPTER 1. SETSof Y , and vice versa.Extensionality gives us a way for showing that sets are identical: to show that X Y , show that whenever x X then alsox Y , and whenever y Y then also y X .1.2Some Important SetsExample 1.4. Mostly we’ll be dealing with sets that have mathematical objects as members. You will remember the various setsof numbers: N is the set of natural numbers {0, 1, 2, 3, . . . }; Z theset of integers,{. . . , 3, 2, 1, 0, 1, 2, 3, . . . };Q the set of rational numbers (Q {z /n : z Z, n N, n , 0});and R the set of real numbers. These are all infinite sets, thatis, they each have infinitely many elements. As it turns out, N,Z, Q have the same number of elements, while R has a wholebunch more—N, Z, Q are “countable and infinite” whereas R is“uncountable”.We’ll sometimes also use the set of positive integers Z {1, 2, 3, . . . } and the set containing just the first two natural numbers B {0, 1}.Example 1.5 (Strings). Another interesting example is the setA of finite strings over an alphabet A: any finite sequence ofelements of A is a string over A. We include the empty string Λamong the strings over A, for every alphabet A. For instance,B {Λ, 0, 1, 00, 01, 10, 11,000, 001, 010, 011, 100, 101, 110, 111, 0000, . . .}.If x x 1 . . . x n A is a string consisting of n “letters” from A,then we say length of the string is n and write len(x) n.

1.3. SUBSETS5Example 1.6 (Infinite sequences). For any set A we may alsoconsider the set Aω of infinite sequences of elements of A. Aninfinite sequence a 1 a2 a3 a4 . . . consists of a one-way infinite list ofobjects, each one of which is an element of A.1.3SubsetsSets are made up of their elements, and every element of a set is apart of that set. But there is also a sense that some of the elementsof a set taken together are a “part of” that set. For instance, thenumber 2 is part of the set of integers, but the set of even numbersis also a part of the set of integers. It’s important to keep thosetwo senses of being part of a set separate.Definition 1.7 (Subset). If every element of a set X is also anelement of Y , then we say that X is a subset of Y , and writeX Y.Example 1.8. First of all, every set is a subset of itself, and isa subset of every set. The set of even numbers is a subset of theset of natural numbers. Also, {a, b } {a, b, c }.But {a, b, e } is not a subset of {a, b, c }.Note that a set may contain other sets, not just as subsets butas elements! In particular, a set may happen to both be an element and a subset of another, e.g., {0} {0, {0}} and also{0} {0, {0}}.Extensionality gives a criterion of identity for sets: X Y iffevery element of X is also an element of Y and vice versa. Thedefinition of “subset” defines X Y precisely as the first half ofthis criterion: every element of X is also an element of Y . Ofcourse the definition also applies if we switch X and Y : Y Xiff every element of Y is also an element of X . And that, in turn,is exactly the “vice versa” part of extensionality. In other words,extensionality amounts to: X Y iff X Y and Y X .

6CHAPTER 1. SETSDefinition 1.9 (Power Set). The set consisting of all subsets ofa set X is called the power set of X , written (X ). (X ) {Y : Y X }Example 1.10. What are all the possible subsets of {a, b, c }?They are: , {a}, {b }, {c }, {a, b }, {a, c }, {b, c }, {a, b, c }. Theset of all these subsets is ({a, b, c }): ({a, b, c }) { , {a}, {b }, {c }, {a, b }, {b, c }, {a, c }, {a, b, c }}1.4Unions and IntersectionsWe can define new sets by abstraction, and the property used todefine the new set can mention sets we’ve already defined. So forinstance, if X and Y are sets, the set {x : x X x Y } definesa set which consists of all those objects which are elements ofeither X or Y , i.e., it’s the set that combines the elements of Xand Y . This operation on sets—combining them—is very usefuland common, and so we give it a name and a define a symbol.Definition 1.11 (Union). The union of two sets X and Y , writtenX Y , is the set of all things which are elements of X , Y , or both.X Y {x : x X x Y }Example 1.12. Since the multiplicity of elements doesn’t matter,the union of two sets which have an element in common containsthat element only once, e.g., {a, b, c } {a, 0, 1} {a, b, c, 0, 1}.The union of a set and one of its subsets is just the bigger set:{a, b, c } {a} {a, b, c }.The union of a set with the empty set is identical to the set:{a, b, c } {a, b, c }.The operation that forms the set of all elements that X andY have in common is called their intersection.

1.4. UNIONS AND INTERSECTIONS7Figure 1.1: The union X Y of two sets is set of elements of X together withthose of Y .Figure 1.2: The intersection X Y of two sets is the set of elements they havein common.Definition 1.13 (Intersection). The intersection of two sets X andY , written X Y , is the set of all things which are elements ofboth X and Y .X Y {x : x X x Y }Two sets are called disjoint if their intersection is empty. Thismeans they have no elements in common.

8CHAPTER 1. SETSExample 1.14. If two sets have no elements in common, theirintersection is empty: {a, b, c } {0, 1} .If two sets do have elements in common, their intersection isthe set of all those: {a, b, c } {a, b, d } {a, b }.The intersection of a set with one of its subsets is just thesmaller set: {a, b, c } {a, b } {a, b }.The intersection of any set with the empty set is empty: {a, b, c } .We can also form the union or intersection of more than twosets. An elegant way of dealing with this in general is the following: suppose you collect all the sets you want to form the union(or intersection) of into a single set. Then we can define the unionof all our original sets as the set of all objects which belong to atleast one element of the set, and the intersection as the set of allobjects which belong to every element of the set.ÐDefinition 1.15. If Z is a set of sets, then Z is the set ofelements of elements of Z :ØZ {x : x belongs to an element of Z }, i.e.,ØZ {x : there is a Y Z so that x Y }ÑDefinition 1.16. If Z is a set of sets, then Z is the set of objectswhich all elements of Z have in common:ÙZ {x : x belongs to every element of Z }, i.e.,ÙZ {x : for all Y Z, x Y }Example 1.17. Suppose Z {{a, b }, {a, d, e }, {a, d }}. ThenÑ{a, b, d, e } and Z {a}.ÐZ

1.5. PAIRS, TUPLES, CARTESIAN PRODUCTS9Figure 1.3: The difference X \ Y of two sets is the set of those elements of Xwhich are not also elements of Y .We could also do the same for a sequence of sets X 1 , X 2 , . . .ØXi {x : x belongs to one of the Xi }iÙXi {x : x belongs to every Xi }.iDefinition 1.18 (Difference). The difference X \ Y is the set ofall elements of X which are not also elements of Y , i.e.,X \ Y {x : x X and x Y }.1.5Pairs, Tuples, Cartesian ProductsSets have no order to their elements. We just think of them as anunordered collection. So if we want to represent order, we useordered pairs hx, yi. In an unordered pair {x, y

"Meta-logic" is so-called because it is the discipline that studies logic itself. Logic proper is concerned with canons of valid inference, and its sym-bolic or formal version presents these canons using formal lan-guages, such as those of propositional and predicate, a.k.a., first-order logic. Meta-logic investigates the properties of .

Related Documents:

Dynamic Logic Dynamic Circuits will be introduced and their performance in terms of power, area, delay, energy and AT2 will be reviewed. We will review the following logic families: Domino logic P-E logic NORA logic 2-phase logic Multiple O/P domino logic Cascode logic

these works focus on traffic offloading rather than computation offloading, and computation offloading decisions have to con-sider the delay and energy consumption of both computation execution and data transmission. In this paper, we propose a Peer-Assisted Computation Offloading (PACO) framework to enable computation offload-

MOSFET Logic Revised: March 22, 2020 ECE2274 Pre-Lab for MOSFET logic LTspice NAND Logic Gate, NOR Logic Gate, and CMOS Inverter Include CRN # and schematics. 1. NMOS NMOSNAND Logic Gate Use Vdd 10Vdc. For the NMOS NAND LOGIC GATE shown below, use the 2N7000 MOSFET LTspice model that has a gate to source voltage Vgs threshold of 2V (Vto 2.0).File Size: 586KB

Digital Logic Fundamentals Unit 1 – Introduction to the Circuit Board 2 LOGIC STATES The output logic state (level) of a gate depends on the logic state of the input(s). There are two logic states: logic 1, or high, and logic 0, or low. The output of some gates can also be in a high-Z (high impedance) state, which is neither a high

categorical and hypothetical syllogism, and modal and inductive logic. It is also associated with the Stoics and their propositional logic, and their work on implication. Syllogistic logic and propositional logic led later to the development of predicate logic (or first order logic, i.e. the foundational logic for mathematics)

Sets and Logic This chapter introduces sets. In it we study the structure on subsets of a set, operations on subsets, the relations of inclusion and equality on sets, and the close connection with propositional logic. 2.1 Sets A set (or cla

An Introduction to Modal Logic 2009 Formosan Summer School on Logic, Language, and Computation 29 June-10 July, 2009 ; 9 9 B . : The Agenda Introduction Basic Modal Logic Normal Systems of Modal Logic Meta-theorems of Normal Systems Variants of Modal Logic Conclusion ; 9 9 B . ; Introduction Let me tell you the story ; 9 9 B . Introduction Historical overview .

An API (US) nationally adopted standard, either modified from or identical to the ISO standard, may include the API Monogram Program requirements. This shall be noted on the front cover as to be evident to the reader. Both modified and identical adoptions which include the API Monogram should be designated as follows: API Title . ANSI/API XX . Edition, Month/Year . Effective Date: (minimum of .