643 lines
15 KiB
Plaintext
643 lines
15 KiB
Plaintext
#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%),
|
||
)[If you are interested in viewing the source code of this document, you can do so
|
||
by clicking
|
||
#text(
|
||
blue,
|
||
link(
|
||
"https://gitlab.orion-technologies.io/philler/college/-/blob/Development/Spring-2023/CS-2233/Assignment-1/Solution.typ?ref_type=heads",
|
||
"here",
|
||
),
|
||
). 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.],
|
||
)
|
||
= 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:
|
||
#m[s → p]
|
||
|
||
Now slightly rewriting the statement with our logic embedded, "If you can
|
||
register for CS 3343, then you have passed CS 2233 and $(s → p)$".
|
||
|
||
Then further refining the statement: "If you can register for CS 3343 then $p ∧ (s → p)$.
|
||
|
||
And with a final refinement: $r → p ∧ (s → p)$
|
||
|
||
Thus the final expression logically would be:
|
||
][$r → (p ∧ (s → p))$]
|
||
]
|
||
#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[
|
||
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_.
|
||
][
|
||
#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.][
|
||
#table(columns: 2, align: left, [
|
||
#align(center)[*$¬q → (p ∧ r)$*]
|
||
#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]
|
||
], [#align(center)[*$(¬q → r) ∧ (q ∨ p)$*]
|
||
#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$],
|
||
)])]
|
||
]
|