LMD Async Tutoring

[LMD]

@Elliot

Check this expression directly with all 4 input cases (11 10 01 00).

or(x, y):
11: 1
10: 1
01: 1
00: 0

not(and(not(and(x, not(y))), not(y))):

• input: 11
  • and(1, not(1)) = 0
  • not(0) = 1
  • and(1, not(1)) = 0
  • not(0) = 1
• input: 10
  • and(1, not(0)) = 1
  • not(1) = 0
  • and(0, not(0)) = 0
  • not(0) = 1
• input: 01
  • and(0, not(1)) = 0
  • not(0) = 1
  • and(1, not(1)) = 0
  • not(0) = 1
• input: 00
  • and(0, not(0)) = 0
  • not(0) = 1
  • and(1, not(0)) = 1
  • not(1) = 0

not(and(not(and(x, not(y))), not(y))):

11: 1
10: 1
01: 1
00: 0

[Elliot]

Cool. FYI there is a simpler way to do it

[LMD]

@Elliot

@LMD

If OR can be expressed in terms of just {and, not} then {and, or, not} isn’t as fundamental a set as {and, not}.

I wouldn’t necessarily equate a smaller set with being more fundamental.

Ok. I feel like I should have a further question about that but don’t. I’ll think about it as just equivalent and simpler but not more fundamental.

@Elliot

Cool. FYI there is a simpler way to do it

Interesting. I think I won’t try again. But are there like, rules or methods of simplifying logic expressions like this? I’m guessing some of the algebra knowledge I’ve got will come in handy with that somehow. I’m wondering if someone like you who understands it better can see how my expression could be translated into the simpler way. Maybe I’ll find out as we go.

I’m going to continue though Eternity’s thread.

[LMD]

I’ve skipped some questions you asked Eternity because they seemed more specifically targeted at them.

@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?

and(1, 1, 1, 1, 0, 1) = 0

@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.

and:
False unless all inputs are true.

or:
True unless all inputs are false

xor:
True unless all inputs are identical.

Actually xor I am unsure on for multiple inputs. Is xor only true if one input is true, or is it only true if the inputs aren’t identical?

Xor or either-or means ‘either input but not both’. ‘Either’ seems to imply binary inputs to me. So I’m not sure how this extends to multiple inputs. It could mean ‘some inputs but not all’, or it could mean ‘any one input but not more’.

I know that a negated xor gate is an equality(xnor) gate. If this is still true with multiple inputs then my one sentence description of xor is right.

[Elliot]

@LMD

@Elliot

I wouldn’t necessarily equate a smaller set with being more fundamental.

Ok. I feel like I should have a further question about that but don’t. I’ll think about it as just equivalent and simpler but not more fundamental.

I don’t think trying to find out what “fundamental” means in this context is needed, nor determining which things are more fundamental.

@LMD

Interesting. I think I won’t try again. But are there like, rules or methods of simplifying logic expressions like this?

There are some rules related to the not operator. But I don’t know many rules like that.

@LMD

I’ve skipped some questions you asked Eternity because they seemed more specifically targeted at them.

ok

@LMD

xor:
True unless all inputs are identical.

In English, xor means only (exactly) one but English is often ambiguous between (inclusive) or and xor so you have to use context to figure it out since they share one word (“or”). The term “and/or” is an unambiguous way to say inclusive or. In logic, xor can mean an odd number of true inputs.

[LMD]

@Elliot

In English, xor means only (exactly) one but English is often ambiguous between (inclusive) or and xor so you have to use context to figure it out since they share one word (“or”). The term “and/or” is an unambiguous way to say inclusive or. In logic, xor can mean an odd number of true inputs.

Okay gotcha. So:

xor:
True if only one input is true.

Interesting. I intuitively used another logic operator (bi conditional) in the description of xor.

Is an equality gate still equivalent to an xnor gate in the context of multiple inputs?

edit: fixed misquote. (was missing first letter of first word)

[LMD]

@Elliot

@Eternity

xor = For “xor” to be true only one input can be true, otherwise its false.

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

Okay wait. If thats what xor or means (or ‘often’ means?) with multiple inputs I made a mistake. I see that when you this:

@Elliot

In English, xor means only (exactly) one but English is often ambiguous between (inclusive) or and xor so you have to use context to figure it out since they share one word (“or”). The term “and/or” is an unambiguous way to say inclusive or. In logic, xor can mean an odd number of true inputs.

You were just talking about xor’s use in English.

What do you mean that it ‘often’ means an odd number of inputs are true?

[LMD]

From Eternity’s thread:

@Elliot

Assignment:

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

Maybe, or(or(x, y), z)?

Okay yes that works. As does or(x, or(y, z)):

Highlighted green columns are equivalent.

[Elliot]

@LMD

or(x, or(y, z))

Yes.

So about xor, make a truth table for

xor(x, xor(y, z))

Note this can be extended to more inputs, e.g.:

(xor a (xor b (xor c (xor d e))))

Note that some operators treat their inputs symmetrically. Each input is treated the same and order doesn’t matter. In other words: (xor x y) = (xor y x) This also works with “and” and “or”. What are some other operators it works and doesn’t work with?

Extending operators to more inputs makes more sense with operators that don’t care about input order. I don’t think we’ll attempt it with operators that give different outputs for different orders of the same inputs.

@LMD

Is an equality gate still equivalent to an xnor gate in the context of multiple inputs?

Make truth tables for these:

eq(x, eq(y, z))

xnor(x, xnor(y, z))

Do not jump to conclusions. There will be a followup.

[LMD]

@Elliot

So about xor, make a truth table for

xor(x, xor(y, z))

Cool. I can see that it’s showing true for even inputs and false for odd (I actually wasn’t aware of zero’s evenness till now. What I read briefly about it made sense.)

And I see with more it works too:

@Elliot

Note that some operators treat their inputs symmetrically. Each input is treated the same and order doesn’t matter. In other words: (xor x y) = (xor y x) This also works with “and” and “or”. What are some other operators it works and doesn’t work with?

Yeah I had noticed this ‘commutativity’ of some operators. Cool. I can see that like multiplication and addition OR can be nested and give the same result.

So with these, the order doesn’t matter for two inputs and above:

• or
• and
• xor
• equality

With these, it works with only two inputs. With more than two inputs it seems to care about the order:

• nor
• nand

e.g nand(x nand(y z)) and nand(z nand(y x)) have different truth tables. But nand(x y) and nand(y x) have the same truth table.

It doesn’t work for:

• implies

i.e the order matters for implies(x y)

[LMD]

@LMD

e.g nand(x nand(y z)) and nand(z nand(y x)) have different truth tables. But nand(x y) and nand(y x) have the same truth table.

Unless, my representation of nand(x y z) as nand(x nand(y z)) is wrong.

Without checking, I think not(and(x and(y z))) has the commutativity that AND and OR does.

[LMD]

@Elliot

@LMD

Is an equality gate still equivalent to an xnor gate in the context of multiple inputs?

Make truth tables for these:

eq(x, eq(y, z))

xnor(x, xnor(y, z))

Sure, here they are:

[Elliot]

OK, also do this truth table and compare:

not(xor(x, xor(y, z)))

[LMD]

Okay:

not(xor(x, xor(y, z))) has the same but negated output of eq(x, eq(y, z)) and xnor(x, xnor(y, z)).

That means xor(x, xor(y, z)) and xnor(x, xnor(y, z)) have the same truth table. Which is surprising. But I guess the implied NOT’s in xnor when nested cancel each other out like a double negative? That makes sense.

[Elliot]

@LMD

Unless, my representation of nand(x y z) as nand(x nand(y z)) is wrong.

Re that, 3-input xnor and more:

Some two-input operators have more than one reasonable way to extend them for more inputs. Strategies for dealing with this include: explicit definitions of what you mean, following conventions, or avoiding ambiguity (e.g. in many contexts you can just not use nand, nor or xnor, at all, or at least avoid using them with 3+ inputs, and just use combinations of unambiguous operators instead).

nand and xnor aren’t English anyway so are less relevant to philosophy. Some common operators for expressing English are {not, and, or, xor, implies, equality, inequality}.

[LMD]

Next in Eternity’s thread:

@Elliot

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

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

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

Okay nand in english would be: not a and b and c. Like “it’s not raining and cold and windy today”. In that case it’d be nand(raining, cold, windy) or not(and(raining and(cold windy))) etc. So it’s saying today the weather is not all of those things but could be any other combination of them (including none of them).

Actually thinking about it I think you mean to do the one sentence explanations like we did before? In that case:

nand:
True unless all inputs are true, then false.

nor:
False unless all inputs are false, then true.

[LMD]

@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.

With these operations as how they are usually used in English:

nand(x y z) = not(and(x and(y z)))
nor(x y z) = not(or(x or(y z)))
xor(x y z) = xor(x xor(y z))

~2mins

[Elliot]

@LMD

With these operations as how they are usually used in English:

nand(x y z) = not(and(x and(y z)))
nor(x y z) = not(or(x or(y z)))
xor(x y z) = xor(x xor(y z))

define standard English xor in English, make a truth table for what you think it should be, and make truth table for xor(x xor(y z))

[LMD]

Oh yeah. I kinda ran into this problem already.

xor in english means: only exactly one. The truth table for that would be:

But in logic with multiple inputs, it is true when the inputs are odd otherwise it’s false:

@LMD

The difference for 3 inputs is that in logic, when all the inputs are true, xor is true. But in english, when all the inputs are true, xor is false. All the other cases with 3 inputs are the same.

[Elliot]

I know you don’t play video games in general but I think you should try Baba Is You unless that sounds bad to you. No experience with other games is needed, and there’s no need to be good with button pressing and controls. Eternity Async Tutoring - #333 by Elliot