As was foretold, we've added advertisements to the forums! If you have questions, or if you encounter any bugs, please visit this thread: https://forums.penny-arcade.com/discussion/240191/forum-advertisement-faq-and-reports-thread/
Options
Symbolic Logic
Inquisitor77
2 x Penny Arcade Fight Club ChampionA fixed point in space and timeRegistered User regular
2 x Penny Arcade Fight Club ChampionA fixed point in space and timeRegistered User regular
Howdy all. I've run across a set of syntax that has been proposed which bothers the back of my brain, but I can't quite put a finger on why, and I was hoping I could get some input. It basically works as follows:
Valid "Operators"
AND
OR
AND NOT
1) In this world of logic, there is no "OR NOT" because if you attempt to write it, the system will not recognize it as a valid operator. Trying to trick the system and writing "OR AND NOT" is also not valid.
2) The only valid expressions are as follows: P OPERATOR Q. Expressions that include more than two symbols or more than two "operators" are not allowed.
3) Nesting, however, is allowed, using the following syntax: P OPERATOR1 (X OPERATOR2 Y).
What is bothering me is that I feel like the combination of these rules should create some sort of contradiction - in particular, the valid creation of an "OR NOT" using the operators available. But I've played around with this a little bit and refreshed my memory on logic, and so far it seems OK. For the sake of my sanity, does anyone here have anything they can come up with, or am I just worrying unnecessarily?
Valid "Operators"
AND
OR
AND NOT
1) In this world of logic, there is no "OR NOT" because if you attempt to write it, the system will not recognize it as a valid operator. Trying to trick the system and writing "OR AND NOT" is also not valid.
2) The only valid expressions are as follows: P OPERATOR Q. Expressions that include more than two symbols or more than two "operators" are not allowed.
3) Nesting, however, is allowed, using the following syntax: P OPERATOR1 (X OPERATOR2 Y).
What is bothering me is that I feel like the combination of these rules should create some sort of contradiction - in particular, the valid creation of an "OR NOT" using the operators available. But I've played around with this a little bit and refreshed my memory on logic, and so far it seems OK. For the sake of my sanity, does anyone here have anything they can come up with, or am I just worrying unnecessarily?
0
Posts
P NOR Q =
NOT(P AND Q) =
(P AND Q) NAND (P AND Q)
No, I would think it's NOR.
For what it's worth, I tried my hand at this and while I can get to "NOT (P ORNOT Q)" I can't get to just "P ORNOT Q".
If it helps to visualize, this system is being used to define populations, so it isn't a full-fledged "logic" per se. It's just a syntax being used to validate who should and should not be included in the group. As examples:
P = red ants
Q = blue ants
Group A = P AND Q = any ant that is both red and blue (e.g., a red ant with blue spots)
Group B = P AND NOT Q = red ants and not blue ants (i.e., equivalent to all ants that aren't blue)
Group C = P OR Q = red ants or blue ants (i.e., both red ants and blue ants are in this group)
Hopefully this also clarifies the use of OR.
I don't think NAND is equivalent to the "AND NOT" operator in this system, so I'm not sure this works (although my logic is admittedly rusty, so I could be wrong?).
I'll see if I can track this down...
Ok, this is no formal proof at all, but see how the last line is always FALSE for all available operators. Basically there's no way to get a TRUE out of two FALSE statements with the given operators. Nesting also doesn't help, because you can only negate the second half of a statement, so the first half will always stay FALSE (and therefore make the whole thing FALSE). So you can't derive ORNOT.
You can even see it in the shitty table above: Because the last line never happens in your example (no ant is neither red nor blue) and ORNOT is the same as P for all other lines, they are functionally equivalent.
Hmm...I think I'm following, but would you mind helping me play out another example, then? Let's say you have six types of ants: red, orange, yellow, green, blue, and purple. Each of those ants can have spots of those same six colors. In addition, they can have spots of one or more colors (so you can have a red ant with spots of orange, yellow, green, blue, and purple).
I could be wrong, but doesn't this example allow for "OR NOT" to be logically true? I could in plain English want to say that I want "all ants that are red or not blue-spotted", meaning I want all of the ants that are red (regardless of spots) and all of the ants that don't have blue spots (to clarify, this is inclusive, so the population would indeed have red ants with blue spots).
As an aside: This population is not as easy to translate into the system's syntax, because "OR NOT" is not allowed. I would have to figure out a way to positively define it, perhaps by saying: "Red Ants" OR "Red-Spotted Ants" OR "Orange-Spotted Ants" OR "Yellow-Spotted Ants" OR "Green-Spotted Ants" OR "Purple-Spotted Ants".
At first glance I think this should be a decent workaround (as long as your demographics are small and you don't have to write strings of dozens of logical operators).
Out of curiosity, though: in the example you gave above (P = red ants, Q = blue ants), there was no distinction between base color and spot color--is that an actual constraint you need to worry about?
What is bothering me is that I feel like the combination of these rules should create some sort of contradiction - in particular, the valid creation of an "OR NOT" using the operators available. But I've played around with this a little bit and refreshed my memory on logic, and so far it seems OK. For the sake of my sanity, does anyone here have anything they can come up with, or am I just worrying unnecessarily?[/quote]
The only possible issue with these rules is if OR NOT can actually be derived. A contradiction cannot come from the operators because they are just less expressive than normal logic. In fact I can't imagine any operator ever by itself resulting in a contradiction; operators are just functions on boolean values. It's statements about them that can be contradicted about what they actually do.
I can construct OR NOT using only AND NOT... damnit I need to have TRUE as a primitive as well though.
In short A OR NOT B == TRUE AND NOT (B AND NOT A)
1) TRUE AND NOT (B AND NOT A) is the same as
2) TRUE AND (NOT B OR NOT NOT A)
this is cause NOT (x AND y) == NOT y OR NOT y
this is the same as
3) TRUE AND (NOT B OR A)
cause NOT NOT x = x
this is the same as
4) TRUE AND (A OR NOT
cause x AND y == y AND x
5) A OR NOT B
cause the TRUE is redundant.
Can you have a description for just being some type of ant? :P
The definition would be
"red OR (orange ANDNOT blue) OR (yellow ANDNOT blue) OR (green ANDNOT blue) OR (purple ANDNOT blue)" (I left out most of the formally required parentheses for clarity)
I'm pretty sure this also only works because of the specific application. You have additional knowledge about the "universe" that you can use to construct statements that isn't built into the logic system.
So to clarify: The above is equivalent to "red ORNOT blue" in the same way as "P" was equivalent to "P ORNOT Q" in the only red/blue ants example. It uses the same fact (that you know all the possible colors) to construct a statement.
red AND NOT (blue_spots AND NOT red)
The nested part defines a population of non-red ants with blue spots, which is then excluded. You're left with all red ants and all ants without blue spots.
edit: Wait, not sure I understand AND NOT in this syntax after all. Maybe this would leave you with no ants (edit3: no it would leave you with only red ants). I need more coffee.
edit2: Yeah I guess this is why you'd want OR NOT in the first place *headdesk*
I didn't realize how much I took that for granted until reading this thread.
Also, when you are talking about these being used to define populations and the whole ant based explanation, then it doesn't seem like you are directly dealing with formal logic but more likely with sets and set theory. Are you using P and Q propositions of truth and falsehood, or are they sets that are subsets of a greater population?
That's part of what was confusing me about that "AND NOT" rule you listed, because even though it's been a while since I've messed with the formal logic stuff it seemed a bit weird to include that one in a syntax of three operators with only those three operators. But if what you are really dealing with is sets, then the OR is the union of two sets (has the elements of set A or set
If this is the case, is the problem that you can't do everything you would potentially want to with just these operators? Or is there some other problem?
Doing the "OR NOT" seems sort of hard from what you guys have discussed, because the set complement is not one of the included operators (all elements in the universal set not in the set being complemented), but I can understand why putting that in the syntax could be a really bad idea or even impossible depending upon the sizes of the sets involved. I could see "NOT" or the "OR NOT" being excluded for practical rather than strictly logical reasons.
Edit: Thinking about it, if you are just testing on individual elements of sets you might be able to include NOT, but if you are actually constructing the overall sets then a set compliment doesn't seem like it would be necessarily straightforward to have in general.
If he's just dealing with logical propositions like 1s and 0s, then it wouldn't make much sense to exclude the NOT operator unless for some reason they were absolutely insistent on only having binary operators.
But if you are really dealing with constructing sets, the NOT might not be tenable, and requires knowledge or assumptions about the universal set, or the population not included in the sets you are dealing with. Or it could have you end up with rather ridiculously large sets even if you do know.
For example, let's say that P and Q are subsets of the set of integers from 1 to 1 million.
P = {1, 2, 3}, Q = {3, 4, 5}
Then if we take P AND Q to be the intersection of P and Q, that set is {3}. If we use P OR Q to be of the sets, the union is {1, 2, 3, 4, 5}. If P AND NOT Q is the set difference, that set is {1, 2}. None of these required us to know what P and Q were subsets of.
But if NOT P is the complement of set P, then it is {4, 5, 6, ..., 1000000}. And P OR NOT Q would give you {1, 2, 3, 6, 7, 8, ..., 1000000}. If these sets were actually being constructed, this could really easily get out of hand.
That's why I'm suspecting that this syntax is really dealing with sets, because these operators make a whole lot more sense in that context. Also, if you were just testing an individual potential element of the sets, it seems like you could do a NOT operator, if you just did a sequential test on whether or not an element was in each of the starter sets being plugged into the formula then using that to construct a straightforward logical statement and computing that. I'm not sure that would be computationally all that hot if you wanted to do something more than just that though.
Using the previous example, I have a syntax for defining the population of all red ants because I want to be able to tell the system "Tell me the average distance traveled for all red ants", where I have a data set consisting of individual ants, their colors, and their distances traveled.
The logic involved simply evaluates each individual ant to see if it conforms to the definition specified. If so, then great, it's included. If not, then it's excluded. So in some sense it doesn't matter if I can create a "contradictory" definition ("All red ants" AND NOT "All red ants"), because in those cases the system would simply return a population of 0.
In this example we assume the manager of the data set is OK with the ambiguity in things like a red ant with red spots, etc. and has worked that out as part of the design of the experiment in the first place (and hence will take that into consideration in the analysis).
I wish. =P
@Grobian @Bliss 101 @Arbitrary Descriptor - I think all of you are expressing similar issues to the one I am having (from a personal standpoint) with this syntax. I feel it arbitrarily restricts the user from performing what may be much simpler logical definitions for the sake of some limited practical concerns (i.e., our user base may or may not be all that great at logic to begin with, so we want to restrict their functionality to some basic things that can be readily translated to "plain English"). For one, being able to create "AND NOT" but not a plain "NOT" is kind of...weird. I could just trick the system and say "I want everything AND NOT red ants" which would be the equivalent of "NOT red ants". Also, not having a full logic syntax means that users will have to perform the kind of data workarounds that we don't want them doing - if they are users that can't handle logic, they are the same users who can't handle properly adjusting a data set. So for me, the real sticking point seems to the exclusion of "OR NOT".
In this case, I don't see why you would add an "OR NOT" operator if you could just add a "NOT" operator to act as the set compliment.
The reasons why they might not want to have set compliment were along what I was getting into before. The three supplied operators only require that you know the contents of the two sets in the operation, they require no knowledge of the greater population. And if you are dealing with relatively small subsets of a large population, then the set compliments will be large sets that are almost the whole population themselves.
If that sort of thing is actually fine for the particular application you are doing, you may be able to add an "Everything" or universal set (or whatever you want to call it) primitive or some other way to include the whole population set like you mentioned, since that would give you the functionality of NOT (Everything AND NOT P). That way you are explicitly invoking the overall population set, which people might be effectively doing without realizing if they just have a "NOT" operator.
Yeah I suggested a universal or "true." Inquisitor said no to a descriptor just for being an ant
Might be worth noting though that you can get something equivalent by just using all sets / a collection of sets whose union is the universal (unless someone has covered this).
E.G. say that you are given sets A,B,C,D,E,F,G. You also have defined a set X which you want to negate
NOT X == (A AND NOT X) OR (B AND NOT X) OR (C AND NOT X) OR (D AND NOT X) OR (E AND NOT X) OR (F AND NOT X) OR (G AND NOT X)
From a practical point of view, the question becomes how much work a redesign is. The system works as is, but some specific requests are kinda complicated and weird (to someone with no background in logic or set theory). A real NOT operator would be the cleanest option, but it also would require changed parsing (it is a unary operator after all). We don't know how costly (performance-wise) a NOT operator really is (see Savants posts), because we don't know about the magnitude of the population. We also don't know how a typical request looks like, maybe the need for ORNOT doesn't even come up in the real application.
There's arguments for a lot of solutions (including keeping everything as is) and it comes down to a trade-off between development time, user experience and performance. If this was going over my desk, I would present it as such to some stakeholders (developers/ costumers/ users/ bosses/ whatever you have) and try to get everyone on a compromise that can be documented.
Ah, I see what you guys are getting at now. @Chake99 I thought you were just making a joke, not a real question. =P There does exist a way for the system to simply treat the entire data set as a group, in which case you can create the "Everything AND NOT X" rule to replicate "NOT" by itself that I described in my last post. "NOT", as per my OP, is not valid as a unary operator in the system as it is currently designed.
The "Everything" population is, by the way, incredibly easy to call up - it even has its own special code in the system which users input all the time in the current state.
Right, the system is being designed with a particular user base in mind, but I am just concerned that it is being unnecessarily restrictive from a logic perspective (i.e., the underlying syntax) for the sake of the end-user. In this system, the end-user isn't going to be dealing with code or syntax anyway, so it makes no sense to me that they would restrict everything up front rather than just create special "plain-English" buttons that translate basic commands into the underlying logic (e.g. "I want all red ants except those with blue spots" = RedAnts AND NOT BlueSpots).
At any rate, I think this discussion has been very helpful, so thanks for the input, everyone! My takeaways:
1) The "AND NOT" operator can actually behave like "NOT" simply by including an "Everything" group in front of it.
2) "OR NOT" does not seem possible to extrapolate from the set of proposed operators. This is actually a good thing, because that was my primary concern (i.e., "breaking" the logic somehow). "OR NOT" has been treated as some sort of Voldemort operator that can't ever be allowed into the system, for what I assume are performance or developmental reasons.
3) Logic is both fun and annoying.
A OR NOT B == EVERYTHING AND NOT (B AND NOT A)
A OR (Everything ANDNOT
==
A OR ~B
So if 1 is true, then 2 is not. It was unfeasible to construct an OR NOT from the operators alone, but an "EVERYTHING" group changes that.
Edit: (3 holds up in either case)
http://logic.ly/demo/
For my discrete class this summer I built all the other gates out of NOR gates for fun on that website.
Well, guess this means I'll have to be the annoying person that brings up yet more issues...
Thanks everyone! I'll update if anything happens. Chances are they will most likely ignore these concerns and proceed anyway, but hey, they asked for an evaluation and daggum if I'm not gonna give them one.
NAND is
Here Is my shot at getting to a NAND Gate with this. ANDN being your not and so A ANDN B is A and Not B
1 ANDN A (G1) (true for 0X)
1 ANDN B (G2) (true for X0)
G1 AND G2 (G3) (Only true for 00)
A ANDN B (G4) (True for 10)
B ANDN A (G5) (True for 01)
G4 OR G5 (G6) (True for 10 & 01)
G6 OR G3 =FINAL OUT (True for 10 & 01 & 00)
But as Grobian pointed out there is no way to generate a static 1 for the 00 case of AB with the operators you have.
Really having a separate AND NOT operation but no NOT is goofy as shit along with the missing TRUE and FALSE.
Really as long as you can get a NOT and an AND you can make everything else. even without the TRUE and FALSE, because you can make them out of AND and NOT. ~(A AND ~A) and (A AND ~A) respectively.