> See also: > - Reference # COT 3100 - Final Exam ## Unit 1: Logic and Sets ### Problem 1 (10) Draw a truth table for the compound statement: $q\lor r\rightarrow[(p\land q)\lor(q\land r)]$ | $q$ | $r$ | $p$ | $(p\land q)$ | $(q\land r)$ | $(p\land q)\lor(q\land r)$ | $q\lor r$ | $q\lor r\rightarrow[(p\land q)\lor(q\land r)]$ | | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | ### Problem 2 (15) Use the laws of logic to show that: $((s\lor \neg r \lor \neg q ) \land (\neg s \lor r \lor s )\land(\neg r \lor \neg s \lor \neg q))=\neg (q \land r)$ $\begin{aligned} \\ \text{1. } & (s\lor \neg r \lor \neg q ) \land (\neg s \lor r \lor s )\land(\neg r \lor \neg s \lor \neg q) && \text{Given LHS} \\ \text{2. } & (s\lor \neg r \lor \neg q ) \land (r \lor \neg s \lor s )\land(\neg r \lor \neg s \lor \neg q) && \text{Associativity} \\ \text{3. } & (s\lor \neg r \lor \neg q ) \land (r \lor T)\land(\neg r \lor \neg s \lor \neg q) && \text{Negatoion} \\ \text{4. } & (s\lor \neg r \lor \neg q ) \land (T)\land(\neg r \lor \neg s \lor \neg q) && \text{Domination} \\ \text{5. } & (s\lor \neg r \lor \neg q )\land(\neg r \lor \neg s \lor \neg q) && \text{Identity} \\ \text{6. } & (s\lor (\neg r \lor \neg q))\land(\neg s \lor (\neg r \lor \neg q)) && \text{Associativity} \\ \text{7. } & (s\lor \neg(r \land q))\land(\neg s \lor \neg(r \land q)) && \text{2x De Morgan's} \\ \text{8. } & \neg(r \land q) \lor (s \land \neg s) && \text{Distributivity} \\ \text{9. } & \neg(r \land q) \lor F && \text{Negation} \\ \text{10. } & \neg(r \land q) && \text{Identity} \\ \text{11. } & \neg(q \land r) && \text{Associativity} \end{aligned}$ ### Problem 3 (20) Show by any valid method except Venn diagram that $((A\cup D) \cap B) \cap ((C\cup B) \cap A)=A\cap B$ By “verbal proof” (I’m getting tired of typing LaTeX, please spare me oh mighty and powerful graders 😥): The union that preceeds both $\cap$‘s ensure that all elements from the “opposite” set (A vs B) are being considered. Therefore, regardless of the elements within sets $C$ or $D$, after the following $\cap$’s are performed, by the definition of $\cap$, the resulting sets are guaranteed to have all elements of $A \cap B$ and doesn’t risk being a subset ### Problem 4 (25) Prove by universal generalization: $(((A\cap D) \cup B) \cap C)\subseteq ((A \cap D)\cup (B\cap C))$ For some arbitrary $x \in ((A\cap D)\cup D)\cap C))$. Aim to prove that if $x$, then by universal generalization and definition of $\subseteq$, it follows that the premise is true: > todo: > handle every case ($x\in A, x\in B$…) to ensure all possibilities align with goal For all cases of $x$, $x\in ((A\cap D)\cup (B\cap C))$. By generalization and definition of $\subseteq$: $\therefore(((A\cap D) \cup B) \cap C)\subseteq ((A \cap D)\cup (B\cap C))$ ### Problem 5 (10) Disprove by counterexample: $((A\cap D) \cup (B \cap C))\subseteq ((A \cap D)\cup B)\cap C)$ $A=\{2\}$ $B=\{4\}$ $C=\{1\}$ $D=\{2,3\}$ $A\cap D=\{2\}$ $B\cap C=\{\}$ $\{2\} \cup \{\} = \{2\}$ $\{2\}\cup B=\{2,4\}$ $\{2,4\}\cap C=\{\}$ $\{2\} \not \subseteq \{\}$ ### Problem 6 (25) Accepting the following premises: 1. $r\rightarrow (q\land s)$ 2. $p \lor r$ 3. $\neg q \lor \neg t$ 4. $t\land s$ Conclude $p$. $ \begin{aligned} \\ \text{5. } & \neg r \lor (q\land s) && \text{Implication (1)} \\ \text{6. } & t && \text{Conjunctive Syllogism (4)} \\ \text{7. } & s && \text{Conjunctive Syllogism (4)} \\ \text{8. } & \neg q && \text{Absorption (3, 6)} \\ \text{9. } & (\neg r \lor q) \land (\neg r \lor s) && \text{Distribution (5)} \\ \text{10. } & \neg r \lor q && \text{Conjunctive Simplification (9)} \\ \text{11. } & r \rightarrow q && \text{Implication (10)} \\ \text{12. } & \neg r && \text{Modus Tollens (8, 11)} \\ \text{13. } & p && \text{Disjunctive Syllogism (2, 12)} \end{aligned}$ ## Unit 2: Numbers ### Problem 7 (25) Prove by induction that for positive integers $n$, that: $\sum^{n}_{i=1}(3i^2+2i+5)=\frac{1}{2}(2n^3+5n^2+13n)$ **Base Case:** Let $n=1$, then $3(1)^2+2(1)+5=10$ and $\frac{1}{2}(2(1)^3+5(1)^2+13(1))=10$ Base case holds 👍 **Inductive Hypothesis:** Accept that $\sum^{k}_{i=1}(3i^2+2i+5)=\frac{1}{2}(2k^3+5k^2+13k)$ **Induction:** Show that $\sum^{(k+1)}_{i=1}(3i^2+2i+5)=\frac{1}{2}(2(k+1)^3+5(k+1)^2+13(k+1))$ *Note that:* $\frac{2(k+1)^3+5(k+1)^2+13(k+1)}{2}=\frac{2(k^3+3k^2+3k+1)+5(k^2+2k+1)+13k+13}{2}$ $=\frac{2k^3+6k^2+6k+2+5k^2+10k+5+13k+13}{2}=\frac{2k^3+11k^2+29k+20}{2}$ --- $\sum^{(k+1)}_{i=1}(3i^2+2i+5)=\sum^{k}_{i=1}(3i^2+2i+5) + (3(k+1)^2+2(k+1)+5)$ *Via Inductive Hypothesis:* $\frac{2k^3+5k^2+13k}{2}+3k^2+8k+10=\frac{2k^3+5k^2+13k}{2}+\frac{6k^2+16k+20}{2}$ $=\frac{2k^3+11k^2+29k+20}{2}$ …as desired. By induction, $\sum^{n}_{i=1}(3i^2+2i+5)=\frac{1}{2}(2n^3+5n^2+13n)$ for positive integers $n$. ### Problem 8 (20) Prove that if 7 divides $n$ with remainder 1, 7 divides $n^2+2n+7$ with remainder 3. For some arbitrary $q \in Z$ $n=7q+1$ $n-1=7q$ $7\vert n-1$ $n^2+2n+7=7q+3$ $n^2+2n+4=7q$ $7 \vert n^2+2n+4$ Goal is to create: $n^2+2n+4=7(\text{Some Integer Stuff})$ $2n^2+2n+4=(7q+1)^2+2(7q+1)+4$ $49q^2+14q+1+14q+2+4$ $49q^2+28q+7=7(7q^2+4+1)$ $\therefore 7\vert n^2+2n+4$ ### Problem 9 (20) Taking into account identical letters, how many ways are there to arrange the word PARVAMONSTRA that both begin and end with consonants? P A A A (3) R R (2) V M O N S T Vowels: P R R V M N S T Consonants: A A A O ` C __ __ __ __ __ __ __ __ __ __ C` ` 1 2 3 4 5 6 7 8 9 10 11 12` > todo: > 1. because there is not a uniform amount of repetition throughout the consonants, whichever one is picked could influence > 2. The middle section of letters can use the simple permutations with repetition in regards to the possible vowels (will also need to handle the possible consonants based on whether or not R, the only consonant with repetition, was chosen) $\frac{12!}{3!2!}$ ### Problem 10 (20) How many unique combinations of monsters can a small monster collector capture, if that collector: - Has 22 small monster containment devices - Intends to use all of those devices - Has access to Earth, Fire, Ice, and Steam type small monsters - Intends to capture at least three Ice, at least two Earth and at most two Steam type small monsters ${19+3-1\choose 19}$ > todo: > - use simple choose with replacement function for “at least” conditions and remove catches after each conditions > - use similar conditions for “at most” and subtract out conditions where more than the amount are picked --- **For questions 11 and 12**, a small monster collector has captured thirty-one Anachronism-type small monsters. Each Anachronism-type small monster has a 27% chance of being a Phlogiston-subtype and a 47% chance of being an Aether-subtype; it cannot be both. ### Problem 11 (10) What is the probability that exactly seven of the captured small monsters are Phlogiston-subtypes? ${31\choose 7}\cdot 0.27^7 \cdot (1-0.27)^{31-7}=0.144$ ### Problem 12 (10) What is the probability of all but five of the captured small monsters being either Phlogiston- or Aether-subtypes, with those five being plain Anachronism-type monsters of neither subtype? By addition (OR) rule: $p=0.27+0.47=0.74$ ${31 \choose 26}\cdot 0.74^{26} \cdot (1-0.74)^{31-26}=0.08$ ### Problem 13 (10) What is the probability that all thirty-one captured small monsters are either Phlogiston- or Aether-subtypes, with no plain Anachronism-type monsters captured? By addition (OR) rule: $p=0.27+0.47=0.74$ $(0.27+0.47)^{31}=3.58 \times 10^{-5}$ it’s very low :) ## Unit 3: Relations and Functions ### Problem 14 (10) Let $𝑅 ⊆ ℝ × ℝ$ with $\{(𝑥, 𝑦)\vert x^2 \equiv_5 y^2\}$ Characterize $R$ in terms of whether it is reflexive, irreflexive, symmetric, anti-symmetric, transitive, complete, any sort of ordering relation, and/or an equivalence relation. This is not a formal proof, but briefly explain your reasoning. > Notes: > $\equiv_5$ represents congruence modulo 5 $R$ is: - **Reflextive** - $x^2 \equiv_5 x^2$ - **Symmetric** - $x^2 \equiv_5 y^2 \iff y^2 \equiv_5 x^2$ - **Transitive** - By definition of congruence, if $x^2 \equiv_5 y^2$ and $y^2 \equiv_5 z^2$ then $x^2 \equiv_5 z^2$ - **Equivalence Relation** - Because it is reflexive, symmetric and transitive ### Problem 15 (10) Let $R ⊆ ℝ^+ \times ℝ^+$ with $R= {(x, y)|⌈x⌉ = ⌈y⌉}$, that is, x and y round up to the sane number. Characterize R in terms of whether it is reflexive, irreflexive, symmetric, anti-symmetric, transitive, complete, any sort of ordering relation, and/or an equivalence relation. This is not a formal proof, but briefly explain your reasoning. > Notes: > $\lceil x\rceil$ is a ceiling function that basically rounds up to the nearest integer $R$ is: - **Reflexive** - Rounding up two identical numbers results in the same number - **Symmetric** - If $\lceil x\rceil =\lceil y\rceil$ then $\lceil y\rceil =\lceil x\rceil$ since they will always round up to the same integer - **Transitive** - If $\lceil x\rceil =\lceil y\rceil$ and $\lceil y\rceil =\lceil z\rceil$, then $\lceil x\rceil =\lceil z\rceil$ since they will always round up to the same integer - Equivalence Relation ### Problem 16 (10) Let $𝑓: ℝ^+ → ℕ^+$ with $𝑓(𝑥) = ⌈𝑥^2⌉$; that is, 𝑓(𝑥) returns the square of 𝑥 rounded up. Characterize 𝑓 in terms of whether it is injective, surjective and/or bijective. This is not a formal proof, but briefly explain your reasoning. $f$ is: - **Injective** -