Applicability Rules and Installed Rules are evaluated independently. The individual boolean result of those two rulesets are then evaluated.
Simply stated, if Applicability Rules is TRUE =AND= Installed Rules is FALSE, then the package will be detected as applicable for installation.
If Applicability Rules is FALSE =OR= Installed Rules is TRUE, then the package will not be detected as applicable for installation.
I'm not quite sure what you mean by "When the difference between the two is a NOT..", but the above two rules are the only rules that need be considered to determine the expected result.
You may also find some benefit from reviewing the Third Party Package Creation Video #2 which discusses in extensive detail the individual rules, their uses and quirks, and the interaction of the Applicability Rules with the Installed Rules.
It may also be possible toassist you further by looking at the specific example and values involved. Please send the details of your specific scenario to customersupport for further assistance.