### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete Mathematics I MATH 125

Mason

GPA 3.85

### View Full Document

## 8

## 0

## Popular in Course

## Popular in Mathematics (M)

This 4 page Class Notes was uploaded by Michale Kuhlman on Monday September 28, 2015. The Class Notes belongs to MATH 125 at George Mason University taught by Imed Ben Chouikha in Fall. Since its upload, it has received 8 views. For similar materials see /class/215005/math-125-george-mason-university in Mathematics (M) at George Mason University.

## Reviews for Discrete Mathematics I

### 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: 09/28/15

Lecture Notes Discrete Mathematics GMU Math 125001 Spring 2007 Alexei VSamsonovich Any theoretical consideration no matter how fundamental it is inevitably relies on key primary notions that are accepted without de nition In our case examples of notions that we shall accept without de nitions are an object a value a concept a symbol to name just a few In fact most English words used here are not de ned yet expected to be understood Given this agreement our rst step is to give useful de nitions of the key terms notations and concepts wisely selected among others Below in this text whenever a key term is introduced it is typed in bold italic Synonyms are listed in parentheses An example follows immediately Discrete mathematics sometimes understood as nite mathematics is the study of mathematical structures that do not support or require the notion of continuity In particular all computer implementations of continuous mathematical structures involve their nite discretization in a certain sense Topics of discrete mathematics include logic sets number theory combinatorics graphs algorithms probability information complexity computability and more Lecture notes included here should be considered complementary rather than alternative to the textbook The intent is to help with understanding of dif cult concepts sometimes by taking the reader to a higher level of abstraction that opens a better view of the main subject and sometimes by squeezing the essence from long pages into just a few lines Lecture 1 Logic It is generally understood that mathematics plays the role of a theoretical fundament for all modern natural sciences In the same sense logic can be viewed as a theoretical fundament for mathematics in general and for discrete mathematics in particular It is not surprising therefore that we start our consideration with logic In order to introduce concepts of logic from rst principles we need to introduce some other general notions rst By introduce I do not mean rigorously de ne Many of these notions will be addressed in more detail and used extensively in subsequent lectures so in a sense the following three paragraphs are just an outline A set is a collection of distinct objects called elements or members of the set In particular the notion of a set does not allow for multiple instances repetitions of the same element in the set In contrast a sequence is an ordered collection that allows for repetition of its elements An ordered ntnple is a sequence of n elements If X is a set thenXquot the nth power of X is the set of all ordered ntuples overX over X here means composed from elements of X An nplace relation onX is a subset of Xquot Supplementary Lecture Notes forMath 1251 Alexei V Samsonovich 1272007 An expression is a finite sequence of elementssymbols the entire set of symbols of a given language is called alphabet or vocabulary A wellformed expression satisfies certain grammar rules that need to be speci ed separately in each particular case of a formal theory Below the term expression will refer to wellformed expressions only A language is a set of expressions over an alphabet A formal axiomatic theory is a language in which a subset of expressions are called axioms and the rest are connected to the axioms via relations called inference rules A sequence of these connections that starts from axioms is called a proof and the expression at the end of this sequence is a theorem A theory is decidable if there is an algorithm to determine for any given expression whether it has a proof Here we compare two theories propositional calculus and predicate calculus both are addressed in more detail below Elements of propositional calculus are truthvalued Boolean variables constants and expressions constructed from them using connectives AND OR etc Elements of predicate calculus are variables that may take values of any nature e g numbers people plus arbitrary truthvalued functions of those variables called predicates plus connectives and quantifiers used to construct expressions A variable is a symbol that can be associated with bound to a value an object a set or an expression A variable can be free or bound Variables may have types restrictions on the nature of objects to which they can bind On the other hand a quanti er specifies a set of objects to which a variable is to be bound While it is possible to design an unlimited number of quantifiers two of them are commonly used in most cases the universal quanti er V specifying that something applies the variable can be bound to any element of a certain category and the existential quanti er El specifying that something applies to at least one element Given the above outline we can define propositional calculus propositional logic as a formal axiomatic theory L with the alphabet syntax set of axioms and inference rules that follow below The alphabet includes connectives A v gt H parentheses and variables denoted here by lowercase English letters that may appear with or without subscripts Each variable in L is bound to a proposition a statement which is an expression that is either true or false ie has a definite truth value The set of expressions in L can be formally given as follows 1 All letters that denote statements with definite truth values are expressions of L 2 If B and G are expressions of L then so are B and B gtG 3 If B G and D are placeholders for expressions of L then the following axiom schemas define axioms of L a B gtG gtB b B gtG gtD gt B gtG gt B gtD c G gt B gt H gt B gt G 4 It suffices for L to have the only inference rule modus ponens a gtb a 3 b Again in summary propositional calculus propositional logic can be defined as a formal axiomatic theory in which the alphabet includes variables denoted by letters e g Supplementary Lecture Notes for Math 125 Alexei V Samsonovich 1272007 p ql symbols 1 and 0 used for tautology and contradiction connectives u A v a H and parentheses the set of axioms includes those given by the above schemas a b and c and the only inference rule is modus ponens We can avoid using unnecessary parentheses if we agree on a particular order of precedence for connectives eg A v a H and then ltgt and other symbols of metalanguage We can reason about variables in L without knowing their values yet we assume that they have de nite values within the set T F This feature separates propositional calculus from predicate calculus in which predicates may have free variables In L all expressions are propositions A direct analogy with regular numerical expressions can be seen Indeed propositional logic is isomorphic to binary arithmetic calculus of Boolean numbers zeros and ones as the following translation table shows This translation provides an intuition into L and can be taken as a part of its de nition Table l L is isomorphic to Boolean arithmetic Propositional Boolean logic arithmetic T 1 F 0 WI m M pqpq p 1 He 1Ppq p961 1pq2pq I9ch XOR Wei21961 pAp ltgtp 92 Ep EPA IPltgt0 p1pEO Given this table you can con dently solve your HWl problems or you can use the truth tables yet there is a more convenient way of doing this by using equivalence relations listed on page 24 in the textbook At least with this table you should have no problem understanding what L is about it is a calculus in which all variables and expressions take only two values In this sense it is much simpler than predicate calculus Therefore for example it is not surprising that paq and qap cannot be simultaneously false in propositional logic It is also clear that there may be cases when PHQ holds and PltgtQ does not generally whenever PltgtQ holds PHQ is a tautology and vice versa The analogy between A and multiplication v and addition with regard to commutativity associativitv and distributivity is straightforward In particular it implies that equivalence relations allow us to reduce any logical expression to its disjunctive normal form dns ie a logical sum disjunction of disjuncts each of which is either a logical product conjunction of literals ie variable letters or their negations or a single literal The counterpart of dns is a conjunctive normal form cns de ned similarly with swapping A 3 Supplementary Lecture Notes forMath 1251 Alexei V Samsonovich 1272007 and v These forms can be useful when you want to compare two expressions A dns cns is called full if each of its disjuncts conjuncts is a minterm contains each variable used in the form exactly once Every noncontradiction nontautology can be reduced to a full dns cns An expression is satis able if it is true for some values of its variables A logical argument is a nite set of propositions called premises or hypotheses followed by a proposition called conclusion In a valid argument the conclusion is true whenever premises are true A sound argument is a valid argument in which premises are true An arguments can be written in a column form below or as a compound statement with an implication connecting premises to the conclusion As a compound statement a valid argument is a tautology Moreover its variables can be treated as placeholders for expressions substitution theorem All this is useful for problem solving A table of useful arguments 7 some inference rules derived from modus ponens 7 is given below Table 2 Inference rules Modus ponens p gtq Modus tollens p gtq P quotl q Ip H introduction p gtq Contrapositive pgtq H Iq gt Ip PHq Case analysis pvq Vacuous proof p p gtr pgtq q gtr r A introduction p A elimination pAq 1 p PM v introduction p v elimination pvq PVq 39P 1 Disjunctive pvq Resolution pvr syllogism p qv r 1 PW Chain rule p gtq Contradiction p q gtr 39P p gtr F

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

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

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