Looking at the Venn diagram with sets A, B, and C:
i. Find M the subclass for class of subsets of Y, which contain exactly three elements of Y. M = {{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}}
ii. Find J, the subclass of Y, which contains the number 2 and two other elements of Y. J = {{1,2,3}, {1,2,4}, {2,3,4}}
i. A × B = {(1,a), (1,b), (2,a), (2,b)} ii. A × C = {(1,a), (2,a)} iii. B × D = {(a,1), (b,1)}
i. Using truth table, show if the following statement is true ii. Is it a tautology, contingency or absurdity?
To determine this, we need to construct a truth table for (A ∩ ¬B) ⇒ P. This is a contingency (neither always true nor always false).
i. Write its contrapositive statement: ¬Q ⇒ ¬P ii. Write its converse: Q ⇒ P
In any poset P, if the meets and joins exist, then they must satisfy four lemmas (laws). One of these is already mentioned below so list the remaining three lemmas:
Given: x ∧ (x ∨ y) = x (Absorption law)
The remaining three lemmas are: i. x ∨ (x ∧ y) = x (Absorption law - dual) ii. x ∧ x = x and x ∨ x = x (Idempotent laws) iii. x ∧ y = y ∧ x and x ∨ y = y ∨ x (Commutative laws)
For the Hasse diagram {a,b}: Find the complements of: i. O ii. {a}
In a Boolean lattice, the complement of an element x is the unique element x' such that x ∧ x' = 0 and x ∨ x' = 1. i. Complement of O (bottom element) = {a,b} (top element) ii. Complement of {a} = {b}
Given list A contains 40 students in English class, list B contains 45 students in Mathematics class, and 30 names on both lists. Find number of students: i. only on list A: 40 - 30 = 10 students ii. only on list B: 45 - 30 = 15 students iii. on list A or B (or both): 40 + 45 - 30 = 55 students iv. on exactly one list: 10 + 15 = 25 students
Proof: To show that a complement is unique, you have to prove in both directions.
Suppose B = A' and A ∪ A' = U, A ∩ A' = Ø
Therefore: A ∪ B = U and A ∩ B = Ø
To prove that if A ∪ B = U and A ∩ B = Ø are true then B = A':
Therefore, the complement of a set is unique. QED
Let A = {x ∈ ℕ | 3 ≤ x ≤ 9} and B = {x ∈ ℕ | x is even} i. Find A ∩ B: A = {3,4,5,6,7,8,9}, B = {2,4,6,8,10,...} A ∩ B = {4,6,8} ii. Find A \ B: A \ B = {3,5,7,9}
Check using De Morgan's law and relevant logical identities if the following propositions are equivalent or NOT: ¬(P ⇒ Q) ⇔ P ∧ ¬Q
First, rewrite P ⇒ Q as ¬P ∨ Q So ¬(P ⇒ Q) = ¬(¬P ∨ Q) Using De Morgan's law: ¬(¬P ∨ Q) = ¬(¬P) ∧ ¬Q = P ∧ ¬Q
Therefore, the propositions are equivalent.
Given: P: You can test, Q: You have completed your assignment, R: You are tired
Translate the following logical expressions into sentences: i. ¬Q ⇒ ¬P: "If you have not completed your assignment, then you cannot test" ii. Q ∧ R: "You have completed your assignment and you are tired"
Using truth table, prove that the deduction below is valid: ¬(P ∨ Q) R ⇒ P ∴ ¬R
This is a valid deduction by modus tollens.
State the truth values for each proposition below: i. ∃x∃y[x² = y, x = 0]: TRUE (when x = 0, y = 0) ii. ∀x∃y[x - y = 0]: TRUE (for any x, let y = x) iii. ∀x∀y[x² ≠ y²]: FALSE (counterexample: x = 1, y = 1)
Draw the digraph of less-than ≤ binary relation on a cartesian product A = {1, 2, 3, 4, 5}.
The digraph would show directed edges from each number to all numbers greater than or equal to it.
i. R = {(1,2), (1,3), (2,4)} on the set A = {1, 2, 3, 4}
ii. R = {(x,y) | x ≤ y, x,y ∈ ℤ} on the set A = {0, 1, 2, 3, 4} - Vertices: 5, Edges: 15 - Reflexive, antisymmetric, transitive - State if it is a connected or disconnected graph: Connected
The relation R is defined as R = {(a,b) | a ≥ b²}
Base: (0,0,0) ∈ R Induction: If (x,y,z) ∈ R then (x+1,y,z+1) ∈ R
Fill in the gap to show how the triple X = (1,1,2) is derived from the basis and induction clause: (0,0,0) ∈ R → (1,0,1) ∈ R → (1,1,2) ∈ R
Represent the digraph (Figure 5) above as an adjacency matrix.
Based on the graph shown, the adjacency matrix would be a 4×4 matrix representing connections between vertices.
From the digraph (Figure 5) above, answer the following: i. Is acbacd an undirected path or directed path? Directed path ii. Is acbac a cycle or simple path? Cycle iii. Is acba a directed path and a simple cycle. True or false? False iv. Is acba an undirected path or a simple cycle? Simple cycle
Consider the digraph G below and determine if G', G'' and G''' are subgraphs or partial subgraphs of G.
Based on the definitions:
Write and evaluate the arithmetic expression which the tree below represents.
The tree represents: (4 + 5) × (6 + 2) = 9 × 8 = 72
Consider the three diagrams (fig a to c) below: a. Identify the diagram(s) that is/are NOT a tree/trees b. Identify which is/are a tree(s) and mention the height(s)
Check if the Hasse diagram below is a distributive lattice considering: i. the triple n, b, m ii. the w, f, o
For a lattice to be distributive, it must satisfy: x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) for all x, y, z
Draw the Poset diagram for a partially ordered set A = {2, 3, 4, 5, 7, 8, 9} with a relation R, such that aRb if a divides b.
The diagram would show divisibility relationships with 2→4→8, 3→9, etc.
c. Find the minimum
d. Find the maximum
e. Find the maximal
f. Find the minimal
g. List one antichain
h. What is the longest chain?
i. What is the length of the longest chain?
These would be determined based on the specific Hasse diagram structure shown in the exam.