LMD Async Tutoring

[LMD]

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

Okay, the 3 input XOR infix expression I did here is:

(x^y^z)v(x^~y^~z)v(~x^y^~z)v(~x^~y^z)

this in prefix:

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

the tree of this:

5 + 3 * 2:

(add 1 (multiply 8 4)):

7 * 4 - 1:

(multiply 6 (minus 5 3))

Yes I can really see how much easier it is translating a prefix expression to a tree. With infix you have to read through the whole expression, consider the order of operations, and consider how to diagram it. With prefix you can just go left to right and you start with the highest level. Then you can drop down and back up as you go.

[LMD]

@Elliot

There’s a way to use {and, or, not} to construct any logic function with any number of inputs and any truth table. Being able to do this shows that {and, or, not} is universal. There’s one general-purpose method that always works.

Try to figure out what it is, but maybe give up after 10 minutes and I’ll give you a hint.

Is this the method I’ve already used, that I gleaned from Eternity’s approach to a previous problem, namely, or’ing together all of the true input scenarios and representing the input scenarios as the respective combination of true and false inputs anded together? I’ve found this has so far worked with everything I’ve tried.

[Elliot]

yes

[LMD]

@Elliot

ok can you figure out an expression which gives all the correct outputs for this table?

x	y	goal(x, y)
1	1	0
1	0	1
0	1	0
0	0	0

(These tables are just stock Obsidian tables copied and pasted from my note and they render perfectly. cool!)

3 false and 1 true input scenario. The true input scenario is:

(x ^ ~y)

Correct

@Elliot

yes. ok now try to make an expression for this table. 10min max.

x	y	goal-2(x, y)
1	1	1
1	0	1
0	1	0
0	0	0

two true input scenarios:

1. (x^y)
2. (x^~y)

so (x^y)v(x^~y) is an equivalent expression for goal-2(x, y)

goal-2(x, y) = (x^y)v(x^~y)

also

goal-2(x, y) = (x)

i.e just (x) is equivalent to goal-2(x, y)

---

@Elliot

ok what about an expression for:

x	y	goal-3(x, y)
1	1	1
1	0	0
0	1	1
0	0	1

So there are 3 true input cases. To make it simple, if I negate the false input case, it’ll imply the three true input cases. So:

goal-3(x, y) = ~(x^~y)

I know I’m mixing up prefix and infix notation and that’s not ideal.

---

False input scenarios:

so we know that:

goal-3(x, y) = ~(x^~y)

What this means is: goal-3 is true when it’s not the case that x is true and y is false. So what is goal-3 when it is the case that x is true and y is false? In that case, goal-3 is false:

~goal-3(x, y) = (x^~y)

This means what we just said which is that goal-3 is false when x is true and y is false. So the negation of the case equivalent to goal-3 being true, is the equivalent to the case of goal-3 being false.

---

@Elliot

What if every output needs to be false?

okay so i.e what is the expression for:

x	y	goal-false(x, y)
1	1	0
1	0	0
0	1	0
0	0	0

you could specify and then negate all the false input scenarios:

goal-false(x, y) = ~((x^y)v(x^~y)v(~x^y)v(~x^~y))

This means: goal-false(x, y) is true when there is an input scenario other than the four possible input scenarios, which since impossible is never, so it’s always false.

You could do simpler though:

goal-false(x, y) = ~(xv~x)

Which means: goal-false is true when it’s not the case that x is true or not x is true. That’ll mean that goal-false is never true because in all input scenarios x is either true or false. So ~(xv~x) always outputs false like goal-false(x, y). ~(yv~y) also works for the same reason.

---

I feel like I’ve made some good progress on my problem with understanding the concepts and I notice it feels great. Like I’ve really enjoyed studying and practising today more than other days and I’ve spent more time doing it over what I scheduled/expected.

[Elliot]

@LMD

I feel like I’ve made some good progress on my problem with understanding the concepts and I notice it feels great. Like I’ve really enjoyed studying and practising today more than other days and I’ve spent more time doing it over what I scheduled/expected.

great

[LMD]

@Elliot

Construct some logic trees (arithmetic is fine too). Just make them up arbitrarily, not based on an expression. Then convert some from tree form to prefix expressions and some to infix expressions.

Okay I’ll start with three logic trees. Small, medium, big.

Actually, I’ll make three more so I can convert some to infix and some to prefix.

---

first three prefix:

(left to right):

not(and (x, not(y))

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

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

---

second three infix:

(left to right):

~x^y

(x^y)v~(x^y)

((x v y)^x)^((x^~y)v(x v y))

Ill try those infix ones with the different symbols:

!x & y

(x & y) | !(x & y)

((x | y) & x) & ((x & !y) | (x | y))

[LMD]

@Elliot

OK find a few things online with a bunch of parentheses and draw arrows from open each paren to the matching close paren.

I used stuff just from this tutoring thread. I found an error in this one above by doing this. All other ones were correct.

@LMD

not(and (x, not(y))

It was missing one end bracket.

---

[LMD]

@Elliot

And here’s some lisp code with parentheses you can match. The operator (or sometimes something else) goes immediately after (instead of before) its open parenthesis.

I used pairs of numbers for pairs of brackets. The numbers also indicate the order in which I paired the brackets so you can see my method.

[LMD]

Oops sorry. That was meant to be posted in my tutoring thread. @Elliot That will need to be moved thank you.

[Elliot]

That is not the standard order I would do parentheses in. Try another one but numbering the open parentheses in order from start to end.

[LMD]

Sure. From that same source. Numbers are directly after open brackets and directly before closed brackets:

(1defmacro define-class (2class inst-vars class-vars &body methods2)
  "Define a class for object-oriented programming."
  ;; Define constructor and generic functions for methods
  `(3let ,class-vars
     (4mapcar #'ensure-generic-fn ',(5mapcar #'first methods5)4)
     (6defun ,class ,inst-vars
       #'(7lambda (8message8)
           (9case message
             ,@(10mapcar #'make-clause methods10)9)7)6)3)1)

[LMD]

And another larger one. I’m surprised that I was able to get to the last bracket and not find something wrong.

(1defun interp (2x &optional env2)
  "Interpret (3evaluate3) the expression x in the environment env."
  (4cond
    (5(6symbolp x6) (7get-var x env7)5)
    (8(9atom x9) x8)
    (10(11case (12first x12)
       (13QUOTE  (14second x14)13)
       (15BEGIN  (16last1 (17mapcar #'(18lambda (19y19) (20interp y env20)18)
                              (21rest x21)17)16)15)
       (22SET!   (23set-var! (24second x24) (25interp (26third x26) env25) env23)22)
       (27IF     (28if (29interp (30second x30) env29)
                   (31interp (32third x32) env31)
                   (33interp (34fourth x34) env33)28)27)
       (35LAMBDA (36let (37(38parms (39second x39)38)
                     (40code (41maybe-add 'begin (42rest2 x42)41)40)37)
                 #'(43lambda (44&rest args44)
                     (45interp code (46extend-env parms args env46)45)43)36)35)
       (47t      ;; a procedure application
               (48apply (49interp (50first x50) env49)
                      (51mapcar #'(52lambda (53v53) (54interp v env54)52)
                              (55rest x55)51)49)47)10)8)4)1)

[Elliot]

@LMD

I’m surprised that I was able to get to the last bracket and not find something wrong.

It’s a mechanical procedure. Text editors can match brackets. It shouldn’t be very hard or scary

[LMD]

@LMD

I’m surprised that I was able to get to the last bracket and not find something wrong.

After saying that, I noticed two error in the last run of closed brackets.

51)49)47)10)8)4)1)

should be

51)49)47)11)10)4)1)

Open bracket 8 was closed on the 5th line, and open bracket 11 had no close bracket

Here it is updated:

(1defun interp (2x &optional env2)
  "Interpret (3evaluate3) the expression x in the environment env."
  (4cond
    (5(6symbolp x6) (7get-var x env7)5)
    (8(9atom x9) x8)
    (10(11case (12first x12)
       (13QUOTE  (14second x14)13)
       (15BEGIN  (16last1 (17mapcar #'(18lambda (19y19) (20interp y env20)18)
                              (21rest x21)17)16)15)
       (22SET!   (23set-var! (24second x24) (25interp (26third x26) env25) env23)22)
       (27IF     (28if (29interp (30second x30) env29)
                   (31interp (32third x32) env31)
                   (33interp (34fourth x34) env33)28)27)
       (35LAMBDA (36let (37(38parms (39second x39)38)
                     (40code (41maybe-add 'begin (42rest2 x42)41)40)37)
                 #'(43lambda (44&rest args44)
                     (45interp code (46extend-env parms args env46)45)43)36)35)
       (47t      ;; a procedure application
               (48apply (49interp (50first x50) env49)
                      (51mapcar #'(52lambda (53v53) (54interp v env54)52)
                              (55rest x55)51)49)47)11)10)4)1)

[LMD]

@Elliot

try doing a logical expression using whitespace (multiple lines and indentation) to make it easier to see what is grouped with what

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

not(
	and(
		x
		not(y)))

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

or(
	and(
		not(x)
		not(y))
	or(
		x
		y))

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

not(
	and(
		or(
			not(x)
			and(
				x
				y))
		not(
			and(
				x
				or(
					x
					y)))))

Maybe it’d look better like (parent child child) with this whitespace format instead of parent(child child)? Then you can have the closing brackets under their open brackets. I think I’ve seen this or something like this somewhere.

(not (and x (not y)))

(not
	(and
		x
		(not
			y
		)
	)
)

(or(and(not x)(not y))(or x y)))

(or
	(and
		(not
			x
		)
		(not
			y
		)
	)
	(or
		x
		y
	)
)

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

(not(and(or(not x)(and x y))(not(and x (or x y)))))

(not
	(and
		(or
			(not
				x
			)
			(and
				x
				y
			)
		)
		(not
			(and
				x
				(or
					x
					y
				)
			)
		)
	)
)

Hmm that’s a little bit hard to read. Everything is more spread out. I suppose there are a number of ways to use indenting and whitespace.

[LMD]

@Elliot

Look over some mathematical logic educational materials. See if you have questions or confusions. See if there are some topics you want to learn about more now. Or consider if you’d like to move on to another topic for now.

Do you consider me to be at this point where I should consider what more I want to learn about Math Logic or if I’d like to move on to another topic?

[Elliot]

Yes. Seems like you’re understanding stuff. Or you can keep reading the Eternity topic further.

[LMD]

Okay cool. I feel like I am too. I’ll have a think.

[LMD]

Okay. I am happy to continue with mathematics and logic related topics. I think I am getting somewhere with them and that it would be good to do some more for now. As for which sub-topic, I have no strong preference and would be happy for you to judge what might be good to go to next.

[Elliot]

keep going through the Eternity topic