Following Along Async Tutoring [Dface]

[Eternity]

naet. how’d you go about finding them? i remember when I did this I kinda just kept brute forcing random truth tables not really understanding what i was doing.

[Dface]

@Eternity

naet. how’d you go about finding them?

if they’re right, what i did is work backwards. Like for or(x,y), the outputs of the truthtable are gonna be 1, 1, 1, 0. I used mindnode and it looked like this:

I just kept inserting ands and nots til the tree made sense

[Elliot]

you got it

[Dface]

Yeah? That sounds good. Sorry i didnt give a good explanation to @Eternity for how i did it. I was trying to explain how i tried to find it n i thought i could also provide pics for how to do that.

[Dface]

@Elliot

Oh and if you understand then label which are which. For {or, and, xor, implies} label each one with one of {one, zero, not, identity} for how it behaves when given 2 of the same input.

• or is identity cuz if you put a 1 u get a 1. If u put a 0 you get a zero
• and is identity cuz if u input 1 u get 1 n if you input a 0 u get a zero
• xor is zero cuz whichever input you insert (1 or 0), ure gonna get an output of 0
• implies is one cuz even if you input 1 or 0 you still get a 1 for an output

[Dface]

@Elliot

you got it. i didn’t say you’d use one of each. try it with nand and nor too.

• nand: is not. Steps for nand are identity → not. Whatever input u put in, you get the opposite for the output.

• nor is not. Same with nand. Whatever input you put in you get opposite for the output

[Dface]

@Elliot

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

Max 60min.

1.Xor: or(and(not(x),y),and(x, not(y)))=xor(x,y)

Truth table:

2.nor: took a while cuz I didn’t think first that nor is just not(or(x,y)). I didn’t connect that to the operators i could use(and, or, not). I think I could do better next time.

3.implies:implies(x,y)=and(or(not(0),0), or(not(0), 0))

truth table:

x	y	and(or(not(x),y), or(not(x), y))
1	1	1
0	1	1
1	0	0
0	0	1

I used a website that makes truth tables and this is what I got:

4.equality is and(or(not(x),y), or(x, not(y)))
I just tried the opposite of the expression I made for xor “or(and(not(x),y),and(x, not(y)))”

I generated the expression and this is what I got:

[Dface]

@Elliot

Can you come up with a universal set of logic operators that is smaller than {and, or, not}? How can you determine if a set of logic operators is universal (both in general or the easier version: using as a premise that {and, or, not} is universal)?

Idk what universal means but i think i know what a

@Elliot

set of logic operators that is smaller than {and, or, not}

could be. A set I think could be {and, or}, {or, not}, or even {and}.

I think universal means that the smaller set takes on the job of the bigger set. Since u can make “or” with “not” and “and” then I think a smaller set could be {not, and}. That set can do the same job as {and, or, not}. Theres just gonna be extra operators to work with.

@Elliot

How can you determine if a set of logic operators is universal (both in general or the easier version: using as a premise that {and, or, not} is universal)?

For the easier version: If you use operators from the smaller set to make expressions that work the same as all the operators of the bigger set, then you got a universal set of logic operators. We already did that with xor, nor, implies, n equality.

I’ll come back to this question later

[Dface]

@Elliot

and(x,y) = ?
not(x) = ?

using only nand on the right?

Truth table for: and(x,y) = ?

and(x,y) = nand(nand(x,y),nand(x,y))

Truth table for not(x) = ?

not(x) = nand(x,x)

[Dface]

@Elliot

@Eternity

@Elliot

Yes. So what small set of operators have you discovered is universal?

Also what universal sets can you make from: {and, or, not}?

I’m kind of confused what you’re asking here. The confusion is about “what universal sets can you make” and “what small set of set of operators have you discovered is universal”. Aren’t those the same thing?

The first one asks for any set. The second one asks for a subset of {and, or, not}.

I think you can make and, or, not with nand. Here are my truth tables:
Truth table for and(x,y) = nand(nand(x,y),nand(x,y)):

Truth table for not(x) = nand(x,x):

Truth table for or(x,y) = nand(nand(x,x), nand(y,y))

nand(nand(x,y),nand(x,y))

I remember before that ET said {and, or, not} are a universal set of logic operators:

@Elliot

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.

If nand can make not, and, or and not, and, or can make all other logic operators, that means nand can also make all other operators. I bet nor can make all other operators too.

To answer the first question I think a small set of universal logic operators is {nand}. Idk if “operators” in the first question means that I have to include two operators.

For the second question, I had to look up what a subset is. I think you can make the universal sets {and, not} or {or, not} from {and, not, or}.

I read ahead and found this question:

@Elliot

@Eternity

@Elliot

Yes. So what small set of operators have you discovered is universal?

{nand, nor}

If you use only one of those, what can and can’t you make from the set {and, or, not}? Or put another way, what is each adding that the other is missing?

nand isn’t missing anything as a universal set cuz it can make nor too.

I read ahead and ET asked @Eternity a question:

@Elliot

So what’s a smaller universal set than {nand, nor}?

@Eternity’s answer:

@Eternity

{nand} or {nor}

ET’s response:

@Elliot

Yeah. Lots of small sets are universal.

Ok cooll you can make a universal set with just nand or just nor

[Elliot]

@Dface

Truth table for or(x,y) = nand(nand(x,x), nand(y,y))

yeah you’re getting stuff. nand(x,x) means not x, so this one means: not both not x and not y. hopefully if you think that over you can see how that means or. or means they can’t both be false. trying to understand logical stuff in words or concepts can help too.

[Dface]

@Elliot

hopefully if you think that over you can see how that means or.

I did see that after u said it. Phrasing logic in english looks useful

[Dface]

@Elliot

One of the advantages of prefix and postfix notations is you can have any number of inputs, e.g.: and(1, 1, 1, 1, 0, 1). Can you evaluate that expression?

for “and” all inputs have to be true or else it’s false. There’s one false in the example so answer is false.

@Elliot

Can you write in English how to evaluate whether and, or and xor are true or false for input lists that could be any length? The answers should be one sentence each.

I think I did “and” already

or: at least one input has to be true or else the statement is false

xor: only one input can be true or else the statement is false

@Eternity’s response to the second question:

@Eternity

and = For “and” to be true all inputs have to be true, otherwise its false.
or = For “or” to be true just one input has to be true, otherwise its false.
xor = For “xor” to be true only one input can be true, otherwise its false.

I like how the words “to be true” are used and “otherwise its false”. I used “otherwise” before in a draft but it got deleted.

[Dface]

@Elliot

That is a good guess and a useful concept. However, FYI, xor often means “an odd number of inputs are true”.

I actually don’t get “an odd number of inputs are true”.

@Elliot

Define or(x,y,z) using only operators that take 2 or fewer inputs.

I found or(x,y,z) = or(or(x,y),or(z,z)). Truth table:

I read ahead found this related to the assignment:

@Elliot

@Eternity

or(x,y,z) = or(or(x,y),or(y,z))

That’s correct but can you find a simpler or shorter answer?

I read ahead on accident and see that maybe or(or(x,y),z) is shorter? Since or(z,z) is identity then why not just use z by itself?

This is what i read accidentally ahead:

@Eternity

or(or(x,y),or(y,z)) = or(or(x,y), z)

ET said it was correct

[Dface]

@Elliot

ok do and(x,y,z) using operators with 2 or fewer inputs

and(x,y,z) = and(and(x,y),z). The answer is just like for or(x,y,z)
Truth table:

@Elliot

and explain nand and nor, in English, for many inputs.

nand: for nand to be true at least one input has to be false, otherwise it’s false

nor: for nor to be true all inputs have to be false, otherwise it’s false.

[Dface]

@Elliot

try making 3 input nand, nor and xor using operators that take 2 or fewer inputs. for each one, you can stop and give up after 15-30min if it’s hard.

nand(x,y,z) = nand(and(x,y),z):

nor(x,y,z) = nor(or(x,y),z):

Couldn’t figure out xor(x,y,z) so I read ahead. I didn’t know actually that an odd number of inputs are true. So three true inputs means the output is true for xor.

I read ahead for more clues and saw this question:

@Elliot

Can you think of a way to check if exactly two inputs are true?

yeah with and(x,y)

I read ahead further and found this:

@Elliot

The context is there are 3 inputs.

You can go through each number (0, 1, 2, 3) and try to think of a way to figure out if exactly that many inputs, out of 3, are true. Give up if you’re stuck too long for each number though.

I was thinking phrasing xor(x,y,z) in english: At least one or three inputs are true.

checking if 0 inputs are true: using only two inputs per operator, it’s nor(or(x,y),z). expression returns true if 0 inputs are true.

checking if 3 inputs are true: and(and(x,y),z). Returns true if 3 of the inputs are true.

I see @Eternity got something similar:

@Eternity

0 and 3 were easy.
For 0 you can use an “or” or “nor” gate. If OR outputs false, all the inputs are false. If NOR outputs true all inputs are false. Regardless you can judge that all three inputs were false.
For 3 you can use an “and” or “nand” gate. If and outputs true, that means all the inputs were true. If nand outputs false that means no input was false, they were all true. Regardless you can judge that all three inputs were true.

I like how nand and or are used to say the same thing. It’s like a way to check the answer twice.

checking if 1 input is true: or(and(x,not(y), not(z)), and(not(x), not(y), z), and(not(x), y, not(z)).
Truth table:

checking if 2 inputs are true: or(and(x, y, not(z), and(not(x), y, z), and(x, not(y, z))
xor(x,y,z)

I think I see what we’re trying to do. If we break down how we find if 1 input is true and 3 inputs are true, then maybe we can find an odd number of inputs being true for xor(x,y,z).

[Dface]

Assignment to explain in english how 1 or 2 inputs are true:

@Elliot

@Eternity

For 1 and 2 I came up with these expressions:

Can you explain them in English?

For 1 input: At least x has to be true and y and z are false, or z has to be true and x and y are false, or y has to be true and x and z are false. Otherwise the statement is false

For 2 input: At least x and y are true and z is false, y and z are true and x is false, or x and z are true and y is false.

@Elliot

Can you define xor(x,y,z) now (for odd number of true inputs meaning of xor, not exactly one true input meaning)?

or(and(x, not(y), not(z)), and(not(x), y, not(z)), and(not(x), not(y), z), and(x,y,z))
Truth table:

@Elliot

try making 3 input nand, nor and xor using operators that take 2 or fewer inputs. for each one, you can stop and give up after 15-30min if it’s hard.

I think for this question the answer is or(or(or(or(and(and(x, not(y), not(z))), and(and(not(x), y), not(z))), and(and(not(x), not(y)),z)),and(x,y,z)))

Truth table:

I counted the open and closed parentheses to see if the number matched

[Dface]

@Elliot

Make trees for these expressions then evaluate them using the trees.

1&0

or(1, not(0))

(not (and (or 1 0) 0))

1&0:

And of 1 and 0 is 0

or(1, not(0)):

Start with not 0. Thats 1 so “or” of 1 and 1 is 1

(not (and (or 1 0) 0)):

lets start with “or” of 1,0. Thats 1. Then and of 1,0. Thats 0. Then not if that which is 1

Answer is 1

[Dface]

@Elliot

Try making trees from the expressions you were just talking about and see if this makes sense. Also try making trees for:

5+3*2

(add 1 (multiply 8 4))

7*4-1

(multiply 6 (minus 5 3))

5+3*2:

(add 1 (multiply 8 4)):

7*4-1:

(multiply 6 (minus 5 3)):

Tree of: (x^~y^~z)v(~x^y^~z)v(~x^~y^z) & or(or((and(x,y,~z), and(~x,y,z), and(x,~y,z))), or((and(x,~y,~z), and(~x,y,~z), and (~x,~y,z))):

I’ll do more trees later

[Dface]

@Elliot

There’s one general-purpose method that always works.

Im thinking use english and {and, or, not} to say out loud what a logic operator is doing. You can say it in terms of “and”, “or”, or “not” to make any operator.