Discrete Mathematics Assignment: Logic, Proofs, and Graphs

This document presents a solved assignment in discrete mathematics, covering key concepts such as logical equivalence, contrapositive statements, and truth tables. The solution includes detailed explanations and proofs for conditional statements, demonstrating the application of logical principles. The assignment further explores graph theory, analyzing vertex degrees and graph properties to determine graph equivalence. The solutions provided offer a comprehensive understanding of discrete mathematical concepts and problem-solving techniques. The document provides a complete solution to the assignment, making it an excellent resource for students seeking to understand discrete mathematics.

1
a) If you have the latest operating system then the app will install.
b) Obtaining a pass in discreet maths is necessary to enrol in the Algorithm unit.
c) Satisfying the Turing test is necessary for a computer to have artificial intelligence
Converse
If the app installs then you have the latest operating system.
If you enrol in the algorithm unit then you have a pass in discreet maths.
If the computer has an intelligence system then it satisfies the Turing test.
Contrapositive
If you do not have the latest operating system then the app will not install.
If you do not obtain a pass in discreet maths then you will not enrol in the Algorithm unit.
If the computer does not satisfy the Turing test then it does not have an artificial
intelligence.
2
a) Truth table for q ↔ (¬p ∨ ¬q)
p q ¬p ¬q ¬p ∨ ¬q q ↔ (¬p ∨
¬q)
T T F F F F
T F F T T F
F T T F T T
F F T T T F
b) By examining the truth table (¬p ∨ ¬q) ∧q is logically equivalent to q ↔ (¬p ∨ ¬q)
c) This equivalence is because the two share a similar truth table hence (¬p ∨ ¬q) ∧q is
the contrapositive of q ↔ (¬p ∨ ¬q)
d) q ↔ ( ¬ p ∨¬ q ) =q →(¬ p ∨¬ q) ∧ (¬ p ∨¬ q)→ q
¿(¬p ∨ ¬q) ∧ q
3
a) F
b) F

c) T
d) T
4
a) Truth table of p → q and that of ¬q → ¬p
p q ¬p ¬q p → q ¬q → ¬p
T T F F T T
T F F T F F
F T T F T T
f F T T F F
The truth table of p → q is like that of ¬q → ¬p hence the two propositions are
logically equivalent
b) Truth table of [¬p ∧ (p ∨ q)] → q
p q ¬p (p ∨ q) ¬p ∧ (p ∨
q)
[¬p ∧ (p ∨ q)]
→ q
T T F T F T
T F F T F T
F T T T T T
F F T F F T
From the truth table of [¬p ∧ (p ∨ q)] → q all the possibilities are true hence it is a
TRUE
5
a) If n2 is a multiple of 4, then n is a multiple of 4
Take n as 2 the 2^2= 4 by observation 2 is a multiple of 4 so is four itself hence the
proof hold.
b) For a number to be a multiple of 6 then it must be a multiple of both 2 and 3.
Therefore if it is not a multiple of 2 it cannot be a multiple of 6. The proof holds.

c) Let n3 be 33 which is 9 which is not a multiple of 2 the same case 3 is not a multiple of
2. Taking the contrapositive of the same the proof holds.
6
a) 2,2,2,3 the list doesn’t not represent the degrees of all the vertices of the graph.
b) 1,2,2,3,5 the list doesn’t not represent the degrees of all the vertices of the graph.
c) 1,2,3,4 the list doesn’t not represent the degrees of all the vertices of the graph.
7 it cannot be completed is detectable by observing the trend values of the components of
the graph
1 2 3 4 5 6 7 8 9
5 4 5 2 1 3 2 2 1
9 7 6 7 3 5 4 4 3
9 8 9 8 6 9 6 7 6
8
0 1 1
1 0 1
1 1 0
9 the two graphs are not equivalent this because the elements of the graphs are different