### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction to Discrete Structures COT 3100

University of Central Florida

GPA 3.74

### View Full Document

## 19

## 0

## Popular in Course

## Popular in Engineering and Tech

This 5 page Class Notes was uploaded by Lamont Block on Thursday October 22, 2015. The Class Notes belongs to COT 3100 at University of Central Florida taught by Arup Guha in Fall. Since its upload, it has received 19 views. For similar materials see /class/227689/cot-3100-university-of-central-florida in Engineering and Tech at University of Central Florida.

## Similar to COT 3100 at University of Central Florida

## Popular in Engineering and Tech

## Reviews for Introduction to Discrete Structures

### 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/22/15

COT 3100 Topics Covered Logic Use of truth tables logical connectives implications logic and implication laws use of quantifiers Sets Definition Union Intersection Minus Some Counting Set Laws Set Table Venn Diagrams InclusionExclusion Principle Relations amp Functions Definition of a relation reflexive irreflexive symmetric antisymmetric transitive injection surjection and bijection Number Theory Induction Definition of divisibility Use of mod and mod rules Euclid s Algorithm Strings and Languages Regular expressions DFAs languages are sets of strings Relevant parts in the book Logic 21 24 Sets 31 33 Number Theory 41 44 Relations amp Functions 515256717374 Strings amp Languages 61 remember 6263 talks about FSMs but I have dealt only With DFA s Since we have not had an exam With induction number theory and strings and languages that Will be the stress of the exam No need to memorize the logic or set laws I Will attach the necessary tables Logic problem Show that the following is a tautology PVFV qAFVPV IPODP pvrv qArvpV uupODpltgt pvrv qArvpv pAqv p lt2 DeMorgans pvrv qArvpvpAqv pltgtDoubleNegation p v p v p v r v q A r v p A q ltgt ComAssoc over or T v p v r v q A r v p A q lt2 Inverse Law T C Domination Law Set Problem Prove or disprove A c C A B c C gt A U B C Q PROVE if A c C A B c C that means we can assume if XEA then XEC and if XEB then XEC Now we need to show that A U B C Q Consider to the contrary that there is an element xeA U B C That would mean by definition of set difference that xe A U B but XE C If XE A U B we must have either xeA or XEB In the first case we nd XE C by the assumption And we find the same thing in the second case But this contradicts that Xe C Thus the set A U B C must be empty Function Problem Let f A B and g B C denote two functions If g f is an injection prove that f must be an injection Also show that it is not necessary for g to be an injection That is show that there is a case where g is not an injection but g f is an injection We must show that f is an injection We are given the fact that g f is an injection We will prove the statement using contradiction Assume that f is not an injection In this situation we can find two distinct elements of the set A a and a such that fa fa Let each of these be inputs to the function g Then we have the following gfa gfa where a a since we assumed the two to be distinct BUT this contradicts the assumption that g f is an injection Thus we can conclude that f must be injective Here is a small example that satisfies the restrictions of the question but where g is not injective A 1 Bab Cz f1 a ga z gb z gf1 2 Here we have that g f is not only injective but also bijective But g is not injective since gagb Induction Problem n1 Show that for all n 2 0 and x gt 2 x lt X Use induction on 11 Base case n0 LHS X0 1 RHS x With given information we find LHS lt RHS as desired Inductive hypothesis Assume for an arbitrary value of nk that x lt xk Inductive Step Under this assumption we must prove our formula for nk1 That is we must show Ex lt X061 10 Ex 3614 Xk1 10 lt Xkl xk by the inductive hypothesis 2Xk1 ltxxk1 using given information about X Xk11 proving the inductive step Thus we can conclude that x lt Xn1 for all n 2 0 and x gt 2 10 Number Theory Problem Given that 5 2X 5y where X and y are integers show that 5 X Using our given information we find that 2X 5y 5c for some integer c 2X 5c 5y X 5c y2 We are given that X is an integer Thus we must have that 2 5c y But if c y is odd this will be false So we must have that 2 c y In this case we can let c y 2d for some integer d Substituting we have X 52d2 X 5d so we can conclude that 5 X StringLanguage problem Let T W and X be languages over the alphabet ab Show that ifT C W then T n X C W m T First we will show that T n X C W n T Let y ET m X We must show that y e W m T If we have that y ET 0 X we can conclude that y ET and y EX But we also know that T C W Thus given that y e T we also know that yeW Since both of these are true we have y e W m T as desired Now that we have established that T n X C W n T we can star both sides to yield T n X C W n T

### 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.