Yes I was going to play around with those but didn't do it in this post. I just used AND/OR/NOT. NAND is interesting because it is also functionally complete.
Yep, I love how strings of nands or nors by themselves can be strung together to produce all Sixteen logic states. So the logic alphabet would be just a shorthand version of parts of the above strings?
For example (AND 0 1) can be thought of as a tree with AND as the parent node and 0 and 1 as the two leaves. The operators are just AND, OR, and NOT. The operands are 0, 1, 2 referencing the 3 bits of a 3-bit string.
Result looks very weird. For example 00000001 is much more frequent than 01000000, what's up with that?
Instead of sampling you could have just counted occurences of each set in these 5000 expressions. Also why 5000? Why not every expression of depth at most k?
Most emphasis should have been put to specify the distribution used, since that is what you're visualizing.
Could someone explain "predicate logic expression (AND 0 1)" more fully? I don't see the correlation between that statement and the strings 110 and 111?
Does it mean if I were to say (AND 0 1 2) the only string matching would be 111? If I were to say (AND 1 2) would that be the strings 011 and 111? If that is correct they why the logic AND? Why not TRUE or 1? (TRUE 0 1) or (1 0 1) instead of AND. AND is a binary logic operator, what are the two objects that it acts on?
"so 0 1 and 2 represent the 0th 1st and 2nd bit in the three bit string?"
This is correct. But (OR (AND 0 1) 2) would represent {001 011 101 111}. I.e., every string where the last bit (the 2-indexed) is true OR the first two bits are both true.
Thanks :) A three circle Venn diagram has eight separate areas because of how the circles overlap, This means by darkening or not darkening each section gives you 2^8 (256) possibilities. I am just trying relate your set of strings to something familiar to me :)
In a like manner a two circle Venn diagram has 2^4 (16) different possibilities which is the logic alphabet list which includes nand, nor, and, or and the like.
Oh! I think I see what I have done. I took the 8 blocks and mashed them together into one three circle Venn diagram. It is still the same information just represented differently.
Cool :) In my mind they are just different ways to represent and work on data.
I was wondering, do the more complex trees only use 0 1 and 2 in their statements? Or do they go on to 3 4 5 and so on? My guess is only 0 1 and 2 are used since the result has to be a three bit string.
Could this also be expressed using the sixteen value logic alphabet? Wikipedia has a good article on it under "Logic Alphabet"
ReplyDeleteHaven't heard of that but yes you could use different operators than AND/OR.
DeleteThanks for the reply :) I could use XOR, XNOR, NAND, NOR and the like?
DeleteYes I was going to play around with those but didn't do it in this post. I just used AND/OR/NOT. NAND is interesting because it is also functionally complete.
DeleteYep, I love how strings of nands or nors by themselves can be strung together to produce all Sixteen logic states. So the logic alphabet would be just a shorthand version of parts of the above strings?
DeleteLooks like it
DeleteWhat you mean by the complexity of a logic expression?
ReplyDeleteJust the depth of the expression if represented as a tree.
DeleteThis is very interesting, thanks for writing it up! By tree do you mean boolean tree? If so can you list the operators and operands?
DeleteFor example (AND 0 1) can be thought of as a tree with AND as the parent node and 0 and 1 as the two leaves. The operators are just AND, OR, and NOT. The operands are 0, 1, 2 referencing the 3 bits of a 3-bit string.
DeleteThanks for going into detail on that. I'l need to think some more on this :-D
DeleteInteresting idea!
ReplyDeleteResult looks very weird. For example 00000001 is much more frequent than 01000000, what's up with that?
Instead of sampling you could have just counted occurences of each set in these 5000 expressions. Also why 5000? Why not every expression of depth at most k?
Most emphasis should have been put to specify the distribution used, since that is what you're visualizing.
"Instead of sampling you could have just counted occurences of each set in these 5000 expressions"
DeleteThat is what I did :)
As for 5000, mostly just memory issues. There are a lot of boolean expressions.
Could someone explain "predicate logic expression (AND 0 1)" more fully? I don't see the correlation between that statement and the strings 110 and 111?
ReplyDeleteDoes it mean if I were to say (AND 0 1 2) the only string matching would be 111? If I were to say (AND 1 2) would that be the strings 011 and 111? If that is correct they why the logic AND? Why not TRUE or 1? (TRUE 0 1) or (1 0 1) instead of AND. AND is a binary logic operator, what are the two objects that it acts on?
I think I get it now, (OR (AND 0 1) 2) would be 111 and 110 yes? so 0 1 and 2 represent the 0th 1st and 2nd bit in the three bit string?
ReplyDelete"so 0 1 and 2 represent the 0th 1st and 2nd bit in the three bit string?"
DeleteThis is correct. But (OR (AND 0 1) 2) would represent {001 011 101 111}. I.e., every string where the last bit (the 2-indexed) is true OR the first two bits are both true.
Oops, 110 also included :)
DeleteThanks! I was wondering about that one :-) And NOT is used to say that that particular nth bit must be 0?
DeleteYep
DeleteI think I have it: {001 011 101 110 111} might be represented by
ReplyDelete000 001 010 011 100 101 110 111
0 1 0 1 0 1 1 1
The eight bit string:
01010111
Would you say the lists of three bit strings can be represented by a three circle Venn diagram, which would have 256 possibilities?
Yeah that's how that set would be represented. Not sure about the venn diagram.
DeleteThanks :) A three circle Venn diagram has eight separate areas because of how the circles overlap, This means by darkening or not darkening each section gives you 2^8 (256) possibilities. I am just trying relate your set of strings to something familiar to me :)
ReplyDeleteIn a like manner a two circle Venn diagram has 2^4 (16) different possibilities which is the logic alphabet list which includes nand, nor, and, or and the like.
Oh! I think I see what I have done. I took the 8 blocks and mashed them together into one three circle Venn diagram. It is still the same information just represented differently.
ReplyDeleteHaha ok. I have seen Venn diagrams used here but I don't remember exactly how they work :)
DeleteCool :) In my mind they are just different ways to represent and work on data.
ReplyDeleteI was wondering, do the more complex trees only use 0 1 and 2 in their statements? Or do they go on to 3 4 5 and so on? My guess is only 0 1 and 2 are used since the result has to be a three bit string.