Price/college
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
Development
college/Spring-2024/CS-2233/Assignment-1/Solution.typ

643 lines
15 KiB
Plaintext
Raw Permalink Normal View History

feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
#let m(math) = align(center)[$#math$]
#let pgbreakmsg = align(center, text(blue, weight: "black", size: 1.5em)[See Next Page\ ↓])
#let solve(work, solution) = align(
center,
)[
#let solution = align(center, block(
inset: 5pt,
stroke: blue + .3pt,
fill: rgb(0, 149, 255, 15%),
radius: 4pt,
)[#align(left)[#solution]])
#if work == [] [
#solution
] else [
#block(inset: 6pt, radius: 4pt, stroke: luma(50%) + .5pt, fill: luma(90%))[
#align(left, text(font: "Liberation Sans", size: .85em, work))
#solution
]
]
]
#let problem-header(number, points) = [== Problem #number. #text(weight: "regular")[[#points
points]]]
#let problem(number, points, body) = [
== Problem #number. #text(weight: "regular")[[#points points]]
#body
]
#set page(margin: (x: .4in, y: .4in))
#set table(align: center)
_*Price Hiller*_
#v(-.8em)
_*zfp106*_
#v(-.8em)
Homework Assignment 1
#v(-.8em)
CS 2233
#v(-.8em)
Section 001
#align(
center,
block(
inset: 6pt,
radius: 4pt,
stroke: luma(50%) + .5pt,
fill: luma(90%),
style: format with typstfmt
2024-01-26 23:18:31 -06:00
)[If you are interested in viewing the source code of this document, you can do so
by clicking
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
#text(
blue,
link(
"https://gitlab.orion-technologies.io/philler/college/-/blob/Development/Spring-2023/CS-2233/Assignment-1/Solution.typ?ref_type=heads",
"here",
),
style: format with typstfmt
2024-01-26 23:18:31 -06:00
). This document was written in Typst and a bit of infinite _withering_ pain in
Neovim, a Vim derivative. Here's to hoping everything below is correct.],
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
)
= Problems
#problem(
1,
10,
)[
- Complete all participation activities in zyBook sections: 1.1, 1.2, 1.3, 1.4,
1.5.
#solve[][Done]
]
#problem(
2,
15,
)[
Let $p$ denote "You passed CS 2233".
Let $q$ denote "You passed CS 3333".
Let $r$ denote "You can register for CS 3343".
Let $s$ denote "You understand propsitional logic".
Use $p$, $q$, $r$, and $s$, to create propositions representing the following
statements.
a. [5 points] You did not pass CS 2233, but you understand propositional logic.
#solve[
This can be alternatively expressed as
#align(
center,
)["You did not pass CS 2233 and you understand propositional logic"]
As the "but" in the statement is _not_ an exclusion, it is a conjunction in
typical english language.
][$¬p ∧ s$]
b. [5 points] You cannot register for CS 3343 only if you have not passed both
CS 2233 and CS 3333
#solve[
This can be alternatively expressed as
#align(
center,
)["If you can register for CS 3343 then that implies you have passed CS 2233 and
CS 3333"]
Which can also be rewritten as
#align(
center,
)["If you have passed CS 2233 and CS 3333 then you can register for CS 3343"]
In the original statement, we're negating both sides, thus $¬r$ and $¬p ∧ ¬q$ which
can be written as:
][$¬r → ¬(p ∧ q)$]
#pgbreakmsg
#pagebreak()
c. [5 points] If you can register for CS 3343, then you have passed CS 2233 and
you understand propositional logic if you passed CS 2233\
#solve[
So this can be more easily understood by "solving" the latter half of the
statement first.
Expressing "You understand propositional logic if you passed CS 2233" logically
would be:
style: format with typstfmt
2024-01-26 23:18:31 -06:00
#m[s → p]
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
Now slightly rewriting the statement with our logic embedded, "If you can
style: format with typstfmt
2024-01-26 23:18:31 -06:00
register for CS 3343, then you have passed CS 2233 and $(s → p)$".
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
style: format with typstfmt
2024-01-26 23:18:31 -06:00
Then further refining the statement: "If you can register for CS 3343 then $p ∧ (s → p)$.
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
style: format with typstfmt
2024-01-26 23:18:31 -06:00
And with a final refinement: $r → p ∧ (s → p)$
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
Thus the final expression logically would be:
style: format with typstfmt
2024-01-26 23:18:31 -06:00
][$r → (p ∧ (s → p))$]
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
]
#problem(
3,
40,
)[
Show that $(¬q ∧ (p ∨ p)) → ¬q$ is a tautology, i.e. $(¬q ∧ (p ∨ p)) → ¬q ≡ T$
a. [10 points] By creating a truth table
// | q | p | ¬q | (p ∨ p) | (¬q ∧ (p ∨ p)) | (¬q ∧ (p ∨ p)) → ¬q |
// |---|---|----|---------|----------------|---------------------|
// | T | T | F | T | F | T |
// | T | F | F | F | F | T |
// | F | T | T | T | T | T |
// | F | F | T | F | F | T |
#solve[
Notice that the furthest right column only has true values, thus the above
proposition is a
_tautology_ and is always _True_
][
#table(
columns: 6,
[q],
[p],
[¬q],
[(p ∨ p)],
[(¬q ∧ (p ∨ p))],
[(¬q ∧ (p ∨ p)) → ¬q],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$F$],
[$F$],
[$T$],
)
]
b. [10 points] By creating a sequence of logical equivalences and annotating
each step
#solve[][
#grid(columns: 2, row-gutter: .5em, column-gutter: 6em)[
1. $¬q ∧ (p ∨ p) → ¬q$
][Starting Proposition][
2. $(¬q ∧ p) → ¬q ∵ (z ∨ z) ≡ p$
][Idempotent Law][
3. $¬(¬q ∧ p) ∨ ¬q ∵ y → z ≡ ¬y ∨ q$
][Conditional Identitify][
4. $(¬¬q ∨ ¬p) ∨ q ∵ ¬(z ∧ y) ≡ (¬z ∨ ¬q) $
][De Morgan's laws][
5. $(q ∨ ¬p) ∨ ¬q ∵ ¬¬z ≡ z$
][Double Negation laws][
6. $(q ∨ ¬q) ∨ ¬p ∵ (z ∨ y) ∨ x ≡ z ∨ (y ∨ x)$
][Associative Laws][
7. $T ∨ ¬p ∵ z ∨ ¬z ≡ T ∴ (q ∨ ¬q) ∨ ¬p ≡ T ∨ ¬p$
][Complement Laws][
8. $T ∵ T ∨ z ≡ T$
][Domination Laws]
]
#pgbreakmsg
#pagebreak(weak: true)
Show that $¬q → (p ∧ r) ≡ (¬q → r) ∧ (q ∨ p)$
c. [10 points] By creating a truth table
// * ¬q → (p ∧ r)
//
// | $q$ | $p$ | $r$ | $¬q$ | $(p ∧ r)$ | $¬q → (p ∧ r)$ |
// |-----|-----|-----|------|-----------|----------------|
// | T | T | T | F | T | T |
// | T | T | F | F | F | T |
// | T | F | T | F | F | T |
// | T | F | F | F | F | T |
// | F | T | T | T | T | T |
// | F | T | F | T | F | F |
// | F | F | T | T | F | F |
// | F | F | F | T | F | F |
//
//
// * (¬q → r) ∧ (q ∨ p)
//
// | $q$ | $p$ | $r$ | $¬q$ | $¬q → r$ | $q ∨ p$ | $(¬q → r) ∧ (q ∨ p)$ |
// |-----|-----|-----|------|----------|---------|----------------------|
// | T | T | T | F | T | T | T |
// | T | T | F | F | T | T | T |
// | T | F | T | F | T | T | T |
// | T | F | F | F | T | T | T |
// | F | T | T | T | T | T | T |
// | F | T | F | T | F | T | F |
// | F | F | T | T | T | F | F |
// | F | F | F | T | T | F | F |
#solve[
fix(CS-2233): resolve minor tpo
2024-01-26 23:30:55 -06:00
Notice that both truth tables have equivalent values in their furthest right
columns. As a result of this, the proposition $¬q → (p ∧ r) ≡ (¬q → r) ∧ (q ∨ p)$ must
be _True_.
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
][
#table(columns: 2, stroke: none, [Truth table for *$¬q → (p ∧ r)$*
#table(
columns: 6,
[$q$],
[$p$],
[$r$],
[$¬q$],
[$(p ∧ r)$],
[$¬q → (p ∧ r)$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$F$],
)], [Truth table for *$(¬q → r) ∧ (q ∨ p)$*
#table(
columns: 7,
[$q$],
[$p$],
[$r$],
[$¬q$],
[$¬q → r$],
[$q ∨ p$],
[$(¬q → r) ∧ (q ∨ p)$ ],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
)])
]
d. [10 points] By creating a sequence of logical equivalences and annotating
each step
#solve[Notice by step three, both logical sequences are equivalent.][
style: format with typstfmt
2024-01-26 23:18:31 -06:00
#table(columns: 2, align: left, [
#align(center)[*$¬q → (p ∧ r)$*]
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
#grid(columns: 2, row-gutter: .5em, column-gutter: 1em)[
1. $¬¬q ∨ (p ∧ r)$
][Conditional Identities][
2. $q ∨ (p ∧ r)$
][Double Negation Law][
3. $(q ∨ p) ∧ (q ∨ r)$
][Distributive Laws]
style: format with typstfmt
2024-01-26 23:18:31 -06:00
], [#align(center)[*$(¬q → r) ∧ (q ∨ p)$*]
feat: completed HW-1 for CS 2233 Nothing quite like cutting it this close 🤡
2024-01-26 23:02:48 -06:00
#grid(columns: 2, row-gutter: .5em, column-gutter: 1em)[
1. $(¬¬q ∨ r) ∧ (q ∨ p)$
][Conditional Identities][
2. $(q ∨ r) ∧ (q ∨ p)$
][Double Negation Law][
3. $(q ∨ p) ∧ (q ∨ r)$
][Commutative Laws]
])
Thus $¬q → (p ∧ r) ≡ (¬q → r) ∧ (q ∨ p)$
]
]
#pgbreakmsg
#pagebreak()
#problem(
4,
20,
)[
a. [10 points] Show that the $∨$ operator is associative by creating a truth
table showing that $p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r$
#solve[Notice that the furthest right columns of both tables are equivalent, therefore
the $∨$ operator is associative][
#table(columns: 2, stroke: none, [Truth table for *$p ∨ (q ∨ r)$*
#table(
columns: 5,
[$q$],
[$p$],
[$r$],
[$(q ∨ r)$],
[$p ∨ (q ∨ r)$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$F$],
)], [Truth table for *$(p ∨ q) ∨ r$*
#table(
columns: 5,
[$q$],
[$p$],
[$r$],
[$(p ∨ q)$],
[$(p ∨ q) ∨ r$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$T$],
[$T$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$F$],
)])
]
b. [10 points] The NOR operator $↓$ is the negation of a disjunction: $p ↓ q ≡ ¬(p ∨ q)$.
Its truth table is:
#table(
columns: 3,
[$p$],
[$q$],
[$p ↓ q$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
)
Show that The NOR operator is not associative by creating a truth table showing
that it is not the case that *$p ↓ (q ↓ r) ≡ (p ↓ q) ↓ r$*. In other words,
create a truth table showing that *$(p ↓ (q ↓ r)) ↔ ((p ↓ q) ↓ r)$* is not a
tautology.
#solve[Notice that the two tables' outputs are different in the furthest righthand
column. If the NOR were associative, the furthest right columns of both tables
would be identical. Since this is not the case, the NOR operator isn't
associative.][#table(columns: 2, stroke: none, [Truth table for *$p ↓ (q ↓ r)$*
#table(
columns: 5,
[$q$],
[$p$],
[$r$],
[$(q ↓ r)$],
[$p ↓ (q ↓ r)$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
)], [Truth table for *$(p ↓ q) ↓ r$*
#table(
columns: 5,
[$q$],
[$p$],
[$r$],
[$(p ↓ q)$],
[$(p ↓ q) ↓ r$],
[$T$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$T$],
[$F$],
[$F$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
[$F$],
[$T$],
[$F$],
[$F$],
[$T$],
[$T$],
[$F$],
[$F$],
[$F$],
[$F$],
[$T$],
[$F$],
)])]
]
Reference in New Issue Copy Permalink