What is the fewest number of edges

Assignment Help Engineering Mathematics

Reference no: EM132363834

SGTA Exercises - Propositional Logic, Graph Theory

Q1. True or false? If monkeys can fly, then 1 + 1 = 3.

Q2. Write the following sentences in symbolic form. Define appropriate terms.

(a) This peach is ripe, but I will not eat it now.

(b) If it is not raining and I wake up early, I will go cycling.

Q3. If p is a proposition, what is the truth value of p ⊕ p? Why?

Q4. Is (¬p ∧ (p ∨ q)) → q always true?

Q5. Construct the truth tables for ¬(p ∨ q) and ¬p ∧ ¬q. Are they the same, or different?

Q6. Determine whether a (simple or non-simple) graph having five vertices can exist, such that the degrees of the vertices are given as follows. If so, draw such a graph. If not, explain why it cannot exist.

(a) {1,1,1,1,1}

(b) {1,3,4,4,32}

(d) {3,3,3,4,4}

(e) {0,1,2,2,3}

Q7. State the converse, contrapositive, and inverse of the following implications:

(a) If it rains tonight, then I will stay home.

(b) If the computer program is given valid input, the output will be sensible.

Q8. Explain the 'Handshake Theorem'; that is, why the total of the degrees of all of the vertices in a (finite) graph must equal twice the number of edges in the graph.

Q9. What is the fewest number of edges a connected graph with n vertices can have? Explain your answer.

10. Consider the graph with adjacency matrix below. Determine the degree of each vertex.

Q11. Write each of these propositions in the form 'if p then q'.

(a) I will remember to send you the address only if you send me an email.

(b) To receive a research award, it is sufficient to prove the Goldbach conjecture.

(d) Jan will go swimming unless the water is too cold.

(e) Carol gets seasick whenever she is on a boat.

Q12. Construct the truth table for [(p →q)→(¬p ∨q)] ∧ [(¬p ∨q)→(p →q)].

(Remark: this can be written more compactly as (p →q)↔(¬p ∨q) .)

Q13. Consider the proposition:

'You can't ride the roller coaster if you are under 110cmtall unless you are over 16 years old'.

Define propositions p, q and r as follows:

p : You can ride the roller coaster.

q : You are under 110cm tall.

r : You are over 16 years old.

If I am a 17 year-old dwarf, can I ride the roller coaster? What if I am a 200cm tall 5 year old? What if I am a 7 year old, who is 87cm tall?

If the proposition is rephrased: 'if I can ride the roller coaster then I am over 110cm, or I am over 16', then we can write the proposition as p →(¬q ∨r ) . Check this answer in the cases above.

14. There are many exercises at the end of §10.1 and §10.2 of the Rosen textbook (any edition). Do as many of these as you have time for. Discuss with other students or your instructor any that you encounter but do not understand.

Reference no: EM132363834

Questions Cloud

What is an appropriate measure of central location : What is an appropriate measure of central location for data that are really skewed?

What is the probability that the tpms will trigger a warning : What is the probability that the TPMS will trigger a warning? (Round your answer to 4 decimal places.)

Identify a company that had accountability issues : Conduct research and identify a company that had accountability issues. Elaborate on the accounting issues, its effects, and how to mitigate it?

How do investors measure the risk of individual common stock : How do investors measure the risk of individual common stocks? Please describe one of these methods in detail. 300 Words: Use at least three sources.

What is the fewest number of edges : SGTA Exercises - Propositional Logic, Graph Theory. What is the fewest number of edges a connected graph with n vertices can have? Explain your answer

What action would you take to increase retention of employee : If you became the new manager at a restaurant with high employee turnover, what actions would you take to increase retention of employees?

What is one key takeaway on what to do : What is one key takeaway on what to do and what not to do when it comes to technological innovation for each case of Google and Lego (four points in all: one).

How knowledge and skills obtained through course objectives : The assignment asks that you reflect how the knowledge and skills obtained through meeting course objectives were applied or could be applied in the workplace.

What is the probability that 2 out of the 5 daughters : What is the probability that 2 out of the 5 daughters are carriers for hemophilia A?

User Account

All Pages