### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# FOUNDATNS OF COMPUTATION CSCE 355

GPA 3.61

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 8 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 355 at University of South Carolina - Columbia taught by S. Fenner in Fall. Since its upload, it has received 21 views. For similar materials see /class/229569/csce-355-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for FOUNDATNS OF COMPUTATION

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

CSCE 355 7 Foundations of Computation Stephen A Fenner September 8 2009 1 August 20 2009 This lecture will outline the topics and requirements of the course We will also jump into some review of discrete math Example of a two state automaton modeling a light switch Some basic de nitions so that we re all on the same page De nition 11 A natural number is any whole number that is at least zero We can list the natural numbers as O 1 2 3 Some mathematicians especially those working in algebra or number theory de ne the natural numbers to start at 1 and exclude 0 Logicians and computer scientists usually de ne them as we did above and we ll stick to that A more formal way of de ning the natural numbers is as the least collection of numbers satisfying 0 0 is a natural number and o if z is any natural number then x 1 is a natural number This de nition is the basis of a method of proof called mathematical induction which we ll describe later De nition 12 A number n is an integer if either z or 7m is a natural number The integers form a doubly in nite list 72 71 O 1 2 So the integers are all the whole numbersipositive negative or zero Speaking of which De nition 13 Let x be any real number We say that z is positiue just in the case that z gt 0 We say that z is negatiue just in the case that z lt 0 equivalently 7m is positive So that means that for any real number x exactly one of the following three statements is true 0 z is positive 0 m 0 o z is negative De nition 14 A real number x is rational just in case that z ab for some integers a and b with b 7 0 By negating both the numerator and denominator if necessary we can always assume that b gt 0 If x is not rational then we say that z is irrational Many theorems are of the form If H then C where H and C are statements This is a conditional statement H is the hypothesis and C is the conclusion This statement can be written symbolically as H a C H and C may have variables in which case the statement must be proven true for all appropriate values of the variables If there is any doubt we may quantify exactly what values those are Other ways of saying if H then C are c H implies C C follows from H C if H77 H only if C o H is a sufficient condition for C C is a necessary condition for H it cannot be the case that H is true and C is false Example For all integers x if 2 is even then x is even Here the hypothesis is 2 is even and the conclusion is m is even We quanti ed z over the integers that is we said that the statement holds for all integers z So the statement says nothing about x if z is not an integer 7139 say By the way this statement is true and we ll prove it later The hypothesis or the conclusion may be more complicated Here is a statement where the hypothesis is two simple statements joined by and For all integers x if z gt 2 and z is prime then x is odd This statement is also true 101 Biconditionals A statement of the form H if and only if C is called a biconditional lt asserts that both H implies C and that C implies H ie C and H both follow from each other In other words C and H are equivalent have the same truth value The phrase if and only if is often abbreviated by iff A proof of a biconditional usually requires two subproofs one that H implies C the forward direction or only if part and one that C implies H the reverse direction or if part The converse of a conditional statement if H then C is the conditional statement if C then H Thus a biconditional asserts both the conditional forward direction and its converse reverse direction Here are some other ways of saying H if and only if C o H iff C o C iff H o H implies C and conversely o H and C are equivalent 0 if H then C and if C then H77 H is a necessary and sufficient condition for C77 o C is a necessary and sufficient condition for H77 o H and C are either both true or both false77 Symbolically7 we write H lt gt C77 and this asserts that H a C and C a H 11 Methods of proof We look at several techniques to prove statements 0 direct proof 0 proof by cases 0 proof by contradiction o proof by induction and variants Many complex proofs combine some or all of these ingredients together 111 Direct proofs Theorem 15 For any integer m ifm Z 4 then 2m 2 m2 Proof Notice that 24 16 42 so the statement is true for z 41 Now consider the sequence 4 5 2 7 of values on the left hand side and the sequence 42 527 627 of values on the right hand side Taking the ratio of adjacent terms in each sequence7 we see that 2m1 21 2w 2T 27 and x 12 i m 1 2 2 7 z 39 lfz 2 4 then m 1z 54 1257 and so 35 1 2 5 2 25 7 lt 7 i lt x gt i lt4 16 lt2 So the left hand sequence values increase by a factor of 2 each time7 but the right hand values increase by a factor of less than 2 each time This will make all the left hand values at least as big as the corresponding right hand values This is a direct proof We start by assuming the hypothesis7 infer some new statements based on the hypothesis and using easy and familiar facts about numbers what I ll call high school math 7 and eventually reach the conclusion 1We could check that the statement is for x 57 67 77 but this is not suf cient to prove the statement7 because we are only proving it true for some nite sample of values whereas the theorem asserts the result for all values at least 4 It still may be useful to check a few cases7 however7 to give a hint about the general argument 2 August 25 2009 Continuing with examples of proofs 202 Proof by cases Theorem 21 There exist irrational numbers ab gt 0 such that al7 is rational Proof Consider x2 which is known to be irrational we ll actually prove this later Case 1 is rational Then we set a b x2 and we are done Case 2 is irrational Set a and b Then ab WW WW5 2 which is rational So we are done In either case we have found irrational numbers a7 1 such that al7 is rational Since one of the two cases must hold7 the Theorem must be true Notice that the proof does not depend on which case holds7 because we can prove the theorem in either case It is actually known that Case 2 holds This is how proof by cases works You can split the hypothesis into two or more cases and prove the conclusion in each case In any proof by cases7 the cases must be eraustive7 that is7 it must always be that at least one of the cases holds 203 Proof by induction This method of proof is extremely useful and has many variants It is used to prove statements about the natural numbers In its basic form7 induction is used to prove that some statement 5a is true for every natural number n The argument is in two stages Base case Prove that 50 is true This is often trivial to do Inductive step Prove that for any natural number n 2 07 if 5a is true then 5n 1 is true The base case provides the starting point for the induction7 and the inductive step provides a template for getting 5 to hold for the next natural number given that you ve established it for the current one So if we unwind the argument7 we establish that 50 is true this is the base case 51 is true this applies the inductive step with n 0 and the fact that we ve already established 50 52 is true by the inductive step again7 this time with n 17 as well as the previous proof of 51 0 53 0 etc The point is that once we ve established Sn for some value of n then we can conclude Sn 1 by the inductive step So if we prove both the base case and the inductive step for general n we must conclude that Sn holds for all natural numbers n A common variant is to start the induction with some natural number other than 0 for the base case for example 1 So here the base case is to prove 51 and the induction step is to prove Sn 7 Sn 1 for any n 2 1 From this we conclude that S holds for all positive integers not necessarily for 0 Similarly you can use any other integer as the base case7for an arbitary example you can prove 517 as the base case then prove Sk 7 Sk 1 for all integers k 2 17 Conclude that Sn holds for all integers n 2 17 You could also start the induction with a negative integer if you want Here is a useful example First a familiar de nition De nition 22 Let x be any integer We say that z is even iff z 2k for some integer k We say that z is odd to mean that z is not even ls 0 even Yes because 0 2 0 and 0 is an integer ls 18 even Yes because 18 2 9 and 9 is an integer ls 74 even Yes because 74 272 and 72 is an integer ls 3 even No 3 is odd Now for the theorem we prove by induction The proof will also use cases Theorem 23 For every integer n 2 1 either it is even or n 7 1 is even Proof Let Sn be the statemen either n is even or n 7 1 is even We prove by induction that Sn holds for all integers n 2 1 so we ll start the induction at 1 instead of 0 Base case To see that 51 holds we just note that 0 1 7 1 and 0 is even Inductive step Fix any integer n 2 1 We prove directly that if Sn holds then Sn 1 holds Assume that Sn holds this is called the inductive hypothesis and consider the statement Sn 1 either n 1 is even or n 1 7 1 is even Case 1 n is even Then since n 1 7 1 n we have that n 1 7 1 is even in this case which implies that Sn 1 holds and so we are done Case 2 n is odd ie n is not even Since the inductive hypothesis Sn which we assume is true says that either n is even or n 7 1 is even we must have then that n 7 1 is even By the de nition of evenness this means that n 7 1 2k for some integer k But then by high school math n1n7122k22k1 Since k 1 is an integer this shows that n 1 is even Thus Sn 1 holds in this case as well We ve established Sn 1 assuming Sn in either case Since the cases are exhaustive we have Sn 7 Sn 1 for all n 1 We can now conclude by induction that Sn holds for all integers n 2 1 D A corollary of a theorem is a new theorem that follows easily from the old one The theorem we just proved has a corollary that strengthens it Corollary 24 Ifn is any integer then either n is even or n 7 1 is even Note that in the corollary we ve dropped the restriction that n 2 1 Proof Let n be any integer We know that either n is positive n 0 or 7n is positive so this will be a mini proof by cases If n is positive then n 2 1 because n is an integer so Theorem applies directly to this case If n 0 then n is even If 7n is positive then 7n 2 1 and so applying Theorem to 7n we get that either 7n is even or 7n 7 1 is even If 7n is even then 7n 2k for some integer k Then negating both sides n 72k 27k and so n is even because 7k is an integer If 7n 7 1 is even then we can write 7n 7 1 26 for some integer t Negating both sides gives n 1 726 Then n71n1727267227 71 and so n 7 1 is even 76 7 1 is an integer So in all cases either n is even or n 7 1 is even D 204 Proof by contradiction The next theorem s proof uses a new proof techique proof by contradiction To prove a statement S by contradiction you start out assuming the negation of S ie that S is false then from that assumption you prove a known falsehood a contradiction such as 0 1 or some such You can then conclude that S must be true because its being false implies something absurd and impossible To prove a condition statement if H then C77 by contradiction you start by assuming that the conditional is not true ie that H is true but C is false then from that you prove a contradiction perhaps that H is false and so H is both true and false which is a contradiction Proof by contradiction is useful if you don t see any direct way of proving the statement Theorem 25 An integer n is odd i n 2k 1 1 for some integer k Proof The statement is a biconditional and we prove each direction separately Forward direction For this direction we assume that n is odd and prove that n 2k 1 1 for some integer Assume n is odd Then n is not even and so by Corollary 24 we must have that n 7 1 is even So n 7 1 2k for some integer k de nition of being even So we have nn7112k1 Reverse direction For this direction we assume that n 2k 1 1 for some integer k and prove that n is odd Assume that n 2k 1 1 for some integer k Here s where we use proof by contradiction We want to show that n is odd but we have no direct way of proving this So we will assume for the sake of contradiction that n is not odd ie that n is even From this we will derive something that is obviously not true Assuming n is even we must have n 26 for some integer 6 de nition of evenness Then we have 2k1 n 2t Subtracting 2k from both sides we get 1 2t 7 2k 26 7 Dividing by 2 then gives 1 Z 7 k 7 2 But 6 and k are both integers and so 6 7 k is an integer but 12 is not an integer and so they cannot be equal This is a contradiction2 which means that our assumption that n is even must be wrong Thus n is odd 2A contradiction is often indicated symbolically by The next corollary says that odds times odds is odd Corollary 26 Leta and b be integers fa and b are both odd then ab is odd Proof Assuming a and b are both odd by Theorem 25 forward direction we can write a 2k 1 1 and b 26 1 for some integers k and 6 Then ab2k12 14k 2k2 122k k 12m1 where m 2M k 6 Since m is clearly an integer we use Theorem 25 again reverse direction this time to conclude that ab is odd 3 August 27 2009 305 Strong induction and the wellordering principle x2 is irrational Use the well ordering principlestrong induction 4 September 1 2009 Sets A set is a collection of things its members For any object z and set S we write x E S to mean that z is a member of set S A set is completely determined by its members No other information is carried by the set That is if A and B are sets then A B iff all members of A are also members of B and vice versa ie they have the same members Describing sets If the members of a set are easily listable then we can denote the set by listing its members separated by commas and enclosed in braces curly brackets Examples Set formers for not so easily listable sets Subsets Proving two sets are equal The empty set denoted by or 0 Sets are objects themselves so we can form sets of sets Example Don t confuse a set with its members The objects 2 and 2 are not equal The rst is a natural number the second is a set whose sole element is 2 the set is not itself a natural number the empty set is an actual object despite having no elements And so 0 7 0 because the second set is not empty it has one member namely 0 Set operations union intersection relative complement ordered pairs and Cartesian product Proving some basic identitites commutative associative and distributive laws Alphabets strings and languages The empty string concatenation string length basic iden tities 5 September 3 2009 Several examples of automata today 0 checking that the last symbol of a binary string is 1 o checking for an even number of Us in a binary string 0 product construction for even 0s and odd 1s 0 complementary automata Transition diagrams for automata 6 September 8 2009 2 denotes the set of all strings over alphabet E Automata more formally as mathematical objects De nition of a Deterministic Finite Au tomaton DFA Expanding the transition function to all strings in 2 De ning computation7 acceptance7 language recognition More examples Transition tables to describe DFAs Example nding a search string in text Proofs that certain automata recognize certain languages

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.