CS代考 MATH1005/MATH6005 Discrete Mathematical Models

MATH1005/MATH6005 Discrete Mathematical Models
Adam 1, 2022

Preface to the course

An acknowledgment of
We acknowledge and celebrate the First Australians on whose traditional lands we live, work and study. We pay our respects to the elders past and present. In particular, we acknowledge the Ngunnawal and Ngambri people, the Traditional Owners of the land upon which the University’s Acton campus is located.

This course has been developed by a number of mathematicians over more than a decade. Contributing authors include:
■ Judy-anne Osborne
The mathematics in this course has been developed over millennia. Credit for discovery will be given only occasionally.

Learning Outcomes
Upon successful completion of MATH1005, students will have the knowledge and skills to:
1. Recall, invent, interpret examples of motivation for mathematical constructs used in discrete mathematics as models of processes in the world.
2. Recognise, define, explain and use terminology and notation from discrete mathematics.
3. Identify the logical structure of a statement, and then identify the logical structure of an argument that may be used to prove or disprove the statement.
4. Perform mathematical calculations in discrete mathematics using methods presented in the course.
5. Write simple proofs/construct explicit counterexamples for statements relating to discrete mathematics topics covered in the course.

Learning Outcomes
Upon successful completion of MATH6005, in addition to the knowledge and skills attained by students completing MATH1005, students will have the knowledge and skills to:
6. Use their deep knowledge and understanding of the material presented in the course to formulate responses to complex concrete and abstract problems.
7. Communicate their understanding and skills in discrete mathematics with colleagues and non-experts and apply their knowledge in an occupational situation.

Reference materials
The lecture notes for the course are intended to be self-contained. Notes will be available through the course Wattle page immediately after the lecture, if not before. For most students, these notes, the workshop materials and the web will be sufficient.
If you would like an alternative presentation of the material, our optional text is Susanna S. Epp. Discrete Mathematics with Applications: Metric Version. Cengage Learning, 5th edition, 2019. ISBN: 9780357114087.
■ Copies of the text are available in the library.
■ From the publisher: “Students who wish to purchase
their own eBook copies they can do so through https://au.cengage.com/ Use the coupon code GRAD10 to receive a discount at checkout.”

Other notes
■ You must check the Wattle page, particularly the announcements, often.
■ MATH1005 Assessment: workshop quizzes, workshop participation and weekly assignments starting in week 2, a mid-semester exam in week 7, a final exam.
■ MATH6005 Assessment: four graduate assignments, a mid-semester exam in week 7, a final exam.
■ All students should sign up for a workshop through the course Wattle page.
■ No class activities (lectures, workshops, etc) will take place on the following days, as they are public holidays in the ACT: Monday Week 4, Monday Week 7, Monday Week 8.

MATH1005/MATH6005 Discrete Mathematical Models
Adam 1, 2022

Why study discrete mathematical models?

What are discrete mathematical models?
Discrete mathematical models are abstract representations of processes and objects, the steps or units of which can be indexed by the non-negative integers. In particular, we avoid continua (like the open interval (0, 1)).
Discrete mathematics is the study of discrete mathematical models.

Q: Is completing a Sudoku puzzle an exercise in discrete mathematics?

Example: Which
webpages are the most
interesting?
Problem: A search on the internet can produce an overwhelming number of “hits.” We need an effective and efficient method to order the hits from a web search so that the most interesting pages appear first.
Google’s PageRank algorithm is an excellent solution to this problem that has made its inventors very wealthy. The algorithm combines a simple discrete mathematical model of the internet with some linear algebra discovered circa 1910. We will learn this algorithm in our course.

Computing and discrete mathematical models
Discrete mathematics and computer science go hand-in-hand because …
Q: Describe an abstract model of the memory of a computer. That is, how do you think about memory?
Q: Do you think about computers working in continuous time or discrete time (“clock cycles”)?
Q: Can the interval (0, 1) be modeled inside a computer?

Discrete mathematics and computer science In 1974, Knuth wrote:
“Discrete mathematics, especially combinatorial theory, has been given an added boost by the rise of computer science, in addition to all the other fields in which discrete mathematics is currently being extensively applied.”
. Knuth. Computer science and its relation to mathematics. Amer. Math. Monthly, 81:323-343, 1974.

Discrete mathematics
and computer scientists
Let’s consider the educational background of some A. M. Turing Award laureates.
■ (1974)
■ – (2000)
■ (2008)
■ (2017)

Section A1: Logic

Statements: The basic
unit of logic
A statement is a sentence that is true or false but not both.

Statements: The basic unit of logic
A statement is a sentence that is true or false but not both. Some sentences that are statements:
■ Australia is in the Southern Hemisphere.
■ Tropical storms spin clockwise in the Southern Hemisphere.
■ Canberra is in .
Some sentences that are not statements:
■ How are you going? (question)
■ Canberra is a better city than Sydney. (ambiguous)
■ Wake up! (instruction/advice)
■ This statement is false. (neither true nor false; self-referencing)

Compound statements
Logical connectives such as ‘and’, ‘or’, ‘not’, ‘if-then’,‘if and only if’ may be used to glue the statements together to make new statements.
Compound statements are statements built from other statements using logical connectives.
Example: Australia is in the Southern Hemisphere and tropical storms spin clockwise in the Southern Hemisphere.

Compound statements
Sometimes the way a compound statement is built from other statements is less clear, because our everyday use of language does not make the logical structure obvious. For example, the word ‘not’ sometimes causes confusion because of its placement.

Examples of compound statements
Q: In each of the following examples, identify clearly the way the statement is built from other statements using logical connectives:
■ Australia is in the Southern hemisphere and tropical storms spin clockwise in the Southern Hemisphere.
■ Australia is in the Southern Hemisphere and Canberra is not in .
■ I don’t like either the one or the other.

Compound statements
Takeway: What makes for nice spoken or written language, may not necessary make the logical structure of a compound statement most clear. Worse, the everyday use of language can be ambiguous.
Mathematicians and computer scientists must agree upon the meaning of logical connectives, and must be proficient at recognising the way that compound statements are built from simpler statements, so that we can communicate effectively (human-to-human, and human-to-machine).

How to introduce a
symbol for a statement
When you first learned algebra, you learned that it was useful to use variables to make abstract statements about relationships between numbers. In logic, we sometime save time and space, and clarify the logical structure of a compound statement, by introducing symbols as names for statements.
For example, we write
p : Australia is in the Southern Hemisphere
to mean that the symbol p now represents the statement “Australia is in the Southern Hemisphere.”

Statement variables and statement forms
We can also use variables to represent arbitrary statements. When a variable represents an arbitrary statement, it is called a statement variable.
We have symbols for various logical connectives (such as ¬ for ‘not’, ∧ for ‘and’, ∨ for ‘or’). We will define these properly in a moment.
An expression built using statement variables, parentheses and logical connectives is called a statement form if the expression becomes a statement when actual statements are substituted for the component statement variables.

Examples of statement forms
Example: Let p and q be statement variables. The expression q ∨ ¬(p ∧ q) is a statement form.
The expression p¬ ∧ q is not a statement form (just like x +× y is not an algebraic expression).

About statement forms
The value of the algebraic expression x × y + y depends on the values taken by x and y. You need to understand the multiplication and addition operations, and the order of precedence among operations, to figure out the value of the expression.
Analogously, the truth value of the statement form
q ∨ ¬(p ∧ q) depends on the truth values taken by p and q. You need to understand the logical connectives ¬, ∧, ∨ and the order of precedence among them to figure out the truth value of the statement form.

Truth tables
We are now ready to define logical connectives. We shall do so using truth tables. A truth table records the truth value taken by a statement form for each possible combination of truth values taken by the statement variables appearing in the statement form.

A logical connective: NOT
If p is a statement variable, the negation of p is read “not p”, denoted ¬p, and defined by the following truth table:
p ¬p TF FT

A logical connective: AND
If p and q are statement variables, the conjunction of p and q is read “p and q”, denoted p ∧ q, and defined by the following truth table:
pqp∧q TTT TFF FTF FFF

A logical connective: OR
If p and q are statement variables, the disjunction of p and q is read “p or q”, denoted p ∨ q, and defined by the following truth table:
pqp∨q TTT TFT FTT FFF

A logical connective: XOR
If p and q are statement variables, the exclusive disjunction of p and q is read “p or q but not both”, denoted p ⊕ q, and defined by the following truth table:
pqp⊕q TTF TFT FTT FFF
Note: Grammatically, the words ‘and’ & ‘but’ are both conjunctions, so are both interpreted as AND in logic. You could read p⊕q as “p or q and not both.”

A logical connective: IMPLIES
If p and q are statement variables, the conditional of q by p is read “if p then q” or “p implies q”, denoted p → q, and defined by the following truth table:
pqp→q TTT TFF FTT FFT
There is extra vocabulary associated with conditional. In the statement form p → q, we call p the hypothesis (or antecedent) and q the conclusion (or consequent).

Understanding IMPLIES
Pay careful attention to the truth table for a conditional. On first sight, some find the last two lines surprising. Spend some time making sure you know the details of the definition.
pqp→q TTT TFF FTT FFT
It sometimes helps to use language to emphasize why a conditional is true. When the hypothesis in a conditional is false, we say that the conditional is vacuously true.

A logical connective: IFF
If p and q are statement variables, the biconditional of p and q is read “p if and only if q”, denoted p ↔ q, and defined by the following truth table:
pqp↔q TTT TFF FTF FFT

Order of precedence
among connectives
When evaluating a statement form:
■ Obey parentheses over any precedence rule
■ Evaluate ¬ first
■ Evaluate ∧, ∨ and ⊕ second. When two or more are
present, parentheses may be needed
■ Evaluate → and ↔ third. When both are present,
parentheses may be needed.
When writing statement forms, you must use parentheses to avoid ambiguity. For example, you should write p ∧ (q ∨ r) rather than p∧q∨r.

Example: A truth table
for a statement form
Q: Write a truth table for (p∧q)∨(¬p∧¬r). First we note that:
■ Our table needs a row for each combination of truth values among the statement variables. Since there are three statement variables in the statement form, our table will need 23 = 8 rows.
■ We need to obey the order of precedence among logical connectives as we evaluate the truth value of the statement form.
We shall present two ways to lay out our work.

Method 1: Extra columns
p q r p∧q ¬p ¬r ¬p∧¬r (p∧q)∨(¬p∧¬r) TTTTFFF T TTFTFTF T TFTFFFF F TFFFFTF F FTTFTFF F FTFFTTT T FFTFTFF F FFFFTTT T
An advantage of this method is that you leave a record of your working. A disadvantage is that is can take a lot of room on the page.

Method 2: Align T/F under connectives
p q r (p∧q)∨(¬p∧¬r) TTTTTFFF TTFTTFFT TFTFFFFF TFFFFFFT FTTFFTFF FTFFTTTT FFTFFTFF FFFFTTTT
■ Be careful because your work leaves less of a record of how you did it.
■ Bold, circle or highlight the column with the final result.

Statements and statement forms
Each statement is an instance of one or more statement forms.

Statements and statement forms
Each statement is an instance of one or more statement forms.
EXAMPLE: Consider the statement “√2 is negative or non-negative.” The statement is an instance of the statement form p ∨ q with
p :√2 is negative
q :√2 is not negative.
The statement is also an an instance of the statement form p∨¬p.

Tautologies
A statement form that is true regardless of the truth values of its variables is called a tautology. A statement whose form is a tautology is also called a tautology.
We can show that a statement form is a tautology by making a truth table. We can show that a statement is a tautology by making a truth table for a corresponding statement form.
Please note that a statement may be true even though it is not a tautology.

Showing a statement form is a tautology
Example: The statement form p ∨ ¬p is a tautology, as shown by:
p ¬p p∨¬p TFT FTT

Showing a statement form is a tautology
Example: The statement form p ∨ ¬p is a tautology, as shown by:
p ¬p p∨¬p TFT FTT
Example: The statement “√2 is negative or non-negative” is a tautology because it is an instance of the statement form
p ∨ ¬p with
and the statement form p ∨ ¬p is a tautology.
p : √2 is negative,

Contradiction
A statement form that is false regardless of the truth values of its variables is called a contradiction. A statement whose form is a contradiction is also called a contradiction.
We can show that a statement form is a contradiction by making a truth table. We can show that a statement is a contradiction by making a truth table for the corresponding statement form.

Logical equivalence
When two statement forms f, g have identical truth tables we say they are logically equivalent and write f ≡ g.
(ALTERNATIVE DEFINITION: When f, g are statement forms and f ↔ g is a tautology, we say that f and g are logically equivalent and write f ≡ g. )
Knowing some logical equivalences allows us to replace complicated statement forms by simpler, logically equivalent, statement forms.
Some well-known logical equivalences are shown on the next slide.

From page 49 of your optional text
Note: The text uses ∼ for negation instead of ¬.

Example: An equivalent form of XOR
Q: Justify the earlier claim that p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q).

Example: An equivalent
form of XOR
Q: Justify the earlier claim that p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q). We compute a truth table:
p q p⊕q p∨q p∧q ¬(p∧q) (p∨q)∧¬(p∧q) TTFTTFF TFTTFTT FTTTFTT FFFFFTF
Because the entries in column 3 and column 7 agree in every row, the truth table above establishes that
p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q).

Example: Another equivalent form for XOR Q: Show that p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q)

Example: Another equivalent form for XOR Q: Show that p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q)
We compute a truth table:
p q p⊕q ¬p ¬q p∧¬q ¬p∧q (p∧¬q)∨(¬p∧q) TTFFFFFF TFTFTTFT FTTTFFTT FFFTTFFF
Because the entries in column 3 and column 8 agree in every row, the truth table above establishes that
p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q).

Your homework between now and lecture 2
■ Master the vocabulary introduced in this lecture and practice making truth tables for complex statement forms.
■ Read the first 4 sections (pp. 323-329) of Knuth’s paper referenced on slide #9 (the paper is avail

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts