LMD Async Tutoring

[LMD]

Okay, moving on to the next assignment:

@Elliot

I don’t think most people ever reinvent the laws. I thought it was worth a try. Let’s try this next (there’s a chance it’s too hard but you did the same thing with nand so worth a try):

It turns out that {and, or, not} is a universal set of logic operators (this is closely related to stuff you may have heard about computational universality). You can construct all the other operators from them.

Assignment: Using {and, or, not}, construct xor, nor, implies and equality.

Max 60min.

PS This is standard logic. There are other types of logic (that you don’t need to know about) including reversible logic, where, given the outputs and the arrangement of operators used, you can figure out what the inputs were. Reversible logic is relevant to quantum computing and to computing with low energy usage.

Assignment: Using {and, or, not}, construct xor, nor, implies and equality.

My working:

nor is just not(or)

xor is true if the inputs are different, and false if they’re the same.

identity is true if the inputs are same, and false if they’re different.

right so not(xor) = identity and not(identity) = xor

So I remembered noticing that bi-conditional (i.e if and only if) had the same outputs as EQUALITY. And I remember that bi-conditional was two conditionals going both ways ‘anded’ together.

so:

and(x⇒y, y⇒x) = x⇔y = equality

I knew from previously that equality was equivalent to xnor so:

not(equality) = xor

so if I can express IMPLIES in AND, NOT, OR, I can express them all. I remembered from my reading trying to understand the conditional operator that the expression P⇒Q was equivalent to ~PvQ so

implies = or(not(x), y)

so all of them expressed in terms of OR, NOT, AND:

nor = not(or)
implies = or(not(x), y)
equality = and(or(not(x), y), or(not(y), x))
xor = not(and(or(not(x), y), or(not(y), x)))

~30mins

Table working:

---

I don’t think I like, figured figured this out. Think the important/hard bits of this were luckily solved by things I happened to encounter already and couldn’t claim to fully understand. I don’t know if I would’ve figure out the fact that ~p v q is equivalent to p ⇒ q on my own.