# COT 3100 - Homework 1
*Michael Akinyemi*
*Tue/Thu 9:00 AM*
### Problem 1: Truth Tables (15 pts)
1. $(p \land q) \lor \neg r$
| $p$ | $q$ | $r$ | $p \land q$ | $\neg r$ | $(p \land q) \lor \neg r$ |
| --- | --- | --- | :---: | :---: | :---: |
| T | T | T | T | F | T |
| T | T | F | T | T | T |
| T | F | T | F | F | F |
| T | F | F | F | T | T |
| F | T | T | F | F | F |
| F | T | F | F | T | T |
| F | F | T | F | F | F |
| F | F | F | F | T | T |
2. $\neg(p \lor q) \land (r \oplus s)$
| $p$ | $q$ | $r$ | $s$ | $p \land q$ | $\neg (p \land q)$ | $r \oplus s$ | $\neg (p \land q) \lor (r \oplus s)$ |
| --- | --- | --- | --- | :---: | :---: | :---: | :---: |
| T | T | T | T | T | F | F | F |
| T | T | T | F | T | F | T | T |
| T | T | F | T | T | F | T | T |
| T | T | F | F | T | F | F | F |
| T | F | T | T | F | T | F | T |
| T | F | T | F | F | T | T | T |
| T | F | F | T | F | T | T | T |
| T | F | F | F | F | T | F | T |
| F | T | T | T | F | T | F | T |
| F | T | T | F | F | T | T | T |
| F | T | F | T | F | T | T | T |
| F | T | F | F | F | T | F | T |
| F | F | T | T | F | T | F | T |
| F | F | T | F | F | T | T | T |
| F | F | F | T | F | T | T | T |
| F | F | F | F | F | T | F | T |
3. $[(q \oplus r) \land s] \implies p$
| $p$ | $q$ | $r$ | $s$ | $q \oplus r$ | $(q \oplus r) \land s$ | $[(q \oplus r) \land s] \implies p$ |
| --- | --- | --- | :---: | :---: | :---: | :---: |
| T | T | T | T | F | F | T |
| T | T | T | F | F | F | T |
| T | T | F | T | T | T | T |
| T | T | F | F | T | T | T |
| T | F | T | T | T | T | T |
| T | F | T | F | T | T | T |
| T | F | F | T | F | T | T |
| T | F | F | F | F | F | T |
| F | T | T | T | F | T | F |
| F | T | T | F | F | F | F |
| F | T | F | T | T | T | F |
| F | T | F | F | T | T | F |
| F | F | T | T | T | T | F |
| F | F | T | F | T | T | F |
| F | F | F | T | F | T | F |
| F | F | F | F | F | F | T |
### Problem 2: Boolean Algebraic Laws (40 pts)
> 1. Use Boolean algebraic laws to prove:
> $[(p \implies q) \lor (p \implies r)] \iff [p \implies (q \lor r)]$
$ \begin{aligned}
\\ \text{1. } & (p \implies q) \lor (p \implies r) && \text{Given}
\\ \text{2. } & (\neg p \lor q) \lor (\neg p \lor r) && \text{2x Implication}
\\ \text{3. } & \neg p \lor (q \lor r) && \text{Distributivity}
\\ \text{4. } & p \implies (q \lor r) && \text{Implication}
\end{aligned}$
> Use Boolean algebraic laws to prove:
> $\neg[\neg(p \land q) \land (p \lor q)] \iff [(p \implies q) \land (q \implies p)]$
$ \begin{aligned}
\\ \text{1. } & \neg[\neg(p \land q) \land (p \lor q)] && \text{Given}
\\ \text{2. } & \neg[(\neg p \lor \neg q) \land (p \lor q)] && \text{De Morgan's}
\\ \text{3. } & \neg(\neg p \lor \neg q) \lor \neg(p \lor q) && \text{De Morgan's}
\\ \text{4. } & (\neg\neg p \land \neg\neg q) \lor (\neg p \land \neg q) && \text{2x De Morgan's}
\\ \text{5. } & (p \land q) \lor (\neg p \land \neg q) && \text{Double Negation}
\\ \text{6. } & [(p \land q) \lor \neg p] \land [(p \land q) \lor \neg q] && \text{Distributivity}
\\ \text{7. } & [(p \lor \neg p) \land (q \lor \neg p)] \land [(p \lor \neg q) \land (q \lor \neg q)] && \text{2x Distributivity}
\\ \text{8. } & [(T) \land (q \lor \neg p)] \land [(p \lor \neg q) \land (T)] && \text{2x Negation}
\\ \text{9. } & (q \lor \neg p) \land (p \lor \neg q) && \text{2x Identity}
\\ \text{10. } & (p \implies q) \land (q \implies p) && \text{2x Implication}
\end{aligned}$
### Problem 3: Disproof (10 pts)
> To _disprove_ a conjecture you need only find one case - or _counter-example_ - where it is not true. **Disprove** that $[(p \land q) \implies r] \iff [(p \implies r) \land (q \implies r)]$.
| $p$ | $q$ | $r$ | $p \land q$ | $(p \land q) \implies r$ |
| --- | --- | --- | :---: | :---: |
| T | T | T | T | T |
| T | T | F | T | F |
| T | F | T | F | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | T | F | F | T |
| F | F | T | F | T |
| F | F | F | F | T |
| $p$ | $q$ | $r$ | $p \implies r$ | $q \implies r$ | $(p \implies r) \land (p \implies r)$ |
| --- | --- | --- | :---: | :---: | :---: |
| T | T | T | T | T | T |
| T | T | F | F | F | F |
| T | F | T | T | T | T |
| **T** | **F** | **F** | F | T | **F** |
| F | T | T | T | T | T |
| **F** | **T** | **F** | T | F | **F** |
| F | F | T | T | T | T |
| F | F | F | T | T | T |
One case where this conjecture is false is *when p is true while q and r are false*.
### Problem 4: Inference - Verbal (15 pts)
r = it was raining
f = it was foggy
s = the sailing race was held
l = the livesaving demonstration was held
t = the trophy was awarded
> **Accepting the following premises:**
>
> 1. $(\neg r \lor \neg f) \implies (s \land l)$
> - “If it does not rain, or it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on.”
> 2. $s \implies t$
> - “If the sailing race is held, then the trophy will be awarded.”
> 3. $\neg t$
> - “The trophy was not awarded.”
>
> **Conclude that it rained.**
$ \begin{aligned}
\\ \text{4. } & \neg s && \text{Modus Tollens (2, 3)}
\\ \text{5. } & \neg s \lor \neg l && \text{Disjunctive Amplification (4)}
\\ \text{6. } & \neg (s \land l) && \text{De Morgan's (5)}
\\ \text{7. } & \neg (\neg r \lor \neg f) && \text{Modus Tollens (1, 6)}
\\ \text{8. } & \neg\neg r \land \neg\neg f && \text{De Morgan's (7)}
\\ \text{9. } & r \land f && \text{2x Double Negation (8)}
\\ \text{10. } & r && \text{Conjunctive Simplification (9)}
\end{aligned}$
### Problem 5: Inference - Symbolic (20 pts)
> **Accepting the following premises:**
>
> 1. $(p \land t) \implies (r \lor s)$
> 2. $q \implies (u \land t)$
> 3. $u \implies p$
> 4. $\neg s$
>
> **Conclude that $q \implies r$.**
$ \begin{aligned}
\\ \text{5. } & \neg q \lor (u \land t) && \text{Implication (2)}
\\ \text{6. } & (\neg q \lor u) \land (\neg q \lor t) && \text{Distributive (5)}
\\ \text{7. } & (q \implies u) \land (q \implies t) && \text{2x Implication (6)}
\\ \text{8. } & q \implies u && \text{Conjunctive Simplification (7)}
\\ \text{9. } & q \implies t && \text{Conjunctive Simplification (7)}
\\ \text{10. } & q \implies p && \text{Syllogism (3, 8)}
\\ \text{11. } & (q \implies p) \land (q \implies t) && \text{Conjunction (9, 10)}
\\ \text{12. } & (\neg q \lor p) \land (\neg q \lor t) && \text{2x Implication (11)}
\\ \text{13. } & \neg q \lor (p \land t) && \text{Distributivity (12)}
\\ \text{14. } & q \implies (p \land t) && \text{Implication (13)}
\\ \text{15. } & q \implies (r \lor s) && \text{Syllogism (1, 14)}
\\ \text{16. } & \neg q \lor (r \lor s) && \text{Implication (15)}
\\ \text{17. } & s \lor (\neg q \lor r) && \text{Associativity/Commutativity (16)}
\\ \text{18. } & \neg s \implies (q \implies r) && \text{2x Implication (17)}
\\ \text{19. } & q \implies r && \text{Modus Ponens (4, 18)}
\end{aligned}$
attempt 1 notes:
- if u is true then p must be true, this makes the conclusion of line 2 similar to the premise of line 1
- we know that s is false, so the conclusion of 1 is essentially just r (absorption?)
- disjunctive syllogism with 1 and 4?
attempt 2 notes:
- implication law is useful for splitting up the conclusions of an implication like line 2 (*zipping/unzipping*), the opposite is also true to link together multiple implications which share a premise
- lines 1-3 can be connected through by modifying connectives that have q (q → u → p)
- unlike the steps with q → (p & t), the q → (r or s) doesn’t need to use distributivity (*aim to keep making lines shorter unless absolutely necessary*)