Logical Equivalence and Graph Theory

This assignment covers various concepts in logic and graph theory. It includes tasks like constructing truth tables for logical expressions, proving equivalence between propositions, analyzing the validity of statements, and identifying properties of graphs based on their vertex degrees. Students are also expected to demonstrate understanding of converse, contrapositive, and implications in logic.

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