The negation of "A and B" does not include "not A and not B"

[docnet]

Homework Statement

What is the negation of "A and B"?

Relevant Equations

There are no equations.

This website says that the negation of "A and B" is "not A or not B"

It seems there are four possible combinations:

$1.$ A and B

$2.$ A and not B

$3.$ B and not A

$4.$ not A and not B

The correct negation is "not A or not B", which only includes $2$ and $3$. It seems like the negation should also include $4$, since $4$ is not $1.$. What gives?

 

[FactChecker]

The condition "not A or not B" includes all elements in the set of "not A and not B", and possibly more.

 

[PeroK]

The correct negation is "not A or not B", which only includes $2$ and $3$. It seems like the negation should also include $4$, since $4$ is not $1.$.

It does. In general, "P or Q" means P or Q or both. There is a logical operation called exclusive or, XOR, which excludes the case of both.

 

[PeroK]

PS in terms of sets: "Not A or Not B" means $A^c \cup B^c$, which is everything not in $A \cap B$. I.e.$$(A \cap B)^c = A^c \cup B^c$$Which is another way to say that the negation of "A and B" is "not A or not B".

 

[valenumr]

Hopefully your question has been answered by now, but this is a very basic principal in boolean algebra (De Morgan's law), which extends into deeper branches of math, as has been mentioned. It might be helpful to write out simple truth tables for each expression to see that they are equivalent, but more understanding can be gained by studying the proof of the theorem.

 

[docnet]

PS in terms of sets: "Not A or Not B" means $A^c \cup B^c$, which is everything not in $A \cap B$. I.e.$$(A \cap B)^c = A^c \cup B^c$$Which is another way to say that the negation of "A and B" is "not A or not B".

For $A^c \cup B^c$, which is everything not in $A \cap B$, it seems more appropriate to say "Not A and/or Not B" instead of "Not A or Not B"
..?

 

[PeroK]

For $A^c \cup B^c$, which is everything not in $A \cap B$, it seems more appropriate to say "Not A and/or Not B" instead of "Not A or Not B"
..?

In everyday English that is common usage to avoid ambiguity. But not in mathematics, logic or computer programming, where ambiguity is avoided by definition of "or". And, as I said, logic and programming have an XOR (exclusive OR).

Another example is "there exists $x$ such that ...". In common English you might say "there exists one or more ...". But, not in mathematics, where the convention is that "there exists" is any number and "there exists a unique $x$" is used when you need to limit it to only one possible element.

There's no right and wrong, but these are the conventions of mathematical language.

 

[FactChecker]

This is just a matter of understanding what the union, $\cup$, means.

 

[sysprog]

In everyday English that is common usage to avoid ambiguity. But not in mathematics, logic or computer programming, where ambiguity is avoided by definition of "or". And, as I said, logic and programming have an XOR (exclusive OR).

And, to be clear, the negation of AND is NAND $-$ XOR means 'either A is true or B is true, but not both', while NAND means 'it is not the case that both A and B are true', and allows, but does not require, that one or the other of them is true.

 

[docnet]

Question: Does that definition of OR change when you have, for example, three items A, B and C?

So, does 'A or B or C' make possible these seven choices?

1. 'A'
2. 'B'
3. 'C'
4. 'A and B'
5. 'B and C'
6. 'A and C'
7. 'not A, not B, not C'

 

[sysprog]

Question: Does that definition of OR change when you have, for example, three items A, B and C?

So, does 'A or B or C' make possible these seven choices?

1. 'A'
2. 'B'
3. 'C'
4. 'A and B'
5. 'B and C'
6. 'A and C'
7. 'not A, not B, not C'

7. should be 'A and B and C'.

The definition of 'or' (conjunction) does not change; however, it's a binary relation, and adding a 3rd term means there are 2 binary relations, which can risk ambiguity when the 2 binary relations are not the same, as in e.g. 'A or B and C' $-$ we could distinguish the 2 meanings with a comma, as in 'A, or B and C' or 'A or B, and C'; however, it's generally more clear to use parentheses, as in 'A or (B and C)' or '(A or B) and C'.

 

[PeroK]

Question: Does that definition of OR change when you have, for example, three items A, B and C?

So, does 'A or B or C' make possible these seven choices?

1. 'A'
2. 'B'
3. 'C'
4. 'A and B'
5. 'B and C'
6. 'A and C'
7. 'not A, not B, not C'

Yes, except 7 should be 'A and B and C'. Mathematically "or" works like a union of sets and is not exclusive.

 

[valenumr]

7. should be 'A and B and C'.

The definition of 'or' (conjunction) does not change; however, it's a binary relation, and adding a 3rd term means there are 2 binary relations, which can risk ambiguity when the 2 binary relations are not the same, as in e.g. 'A or B and C' $-$ we could distinguish the 2 meanings with a comma, as in 'A, or B and C' or 'A or B, and C'; however, it's generally more clear to use parentheses, as in 'A or (B and C)' or '(A or B) and C'.

If we're talking boolean algebra, I would recommend learning about disjunctive / conjunctive normal form. Either would be a minimal representation of a boolean expression of multiple variables.

Edit: should have been in reply to docnet

 

[sysprog]

If we're talking boolean algebra, I would recommend learning about disjunctive / conjunctive normal form.

I think that learning fundamentals of binary logic does not require, and should precede, learning about canonical normal forms $-$ this might be a useful reference: https://en.wikipedia.org/wiki/Truth_table

 

[valenumr]

El

I think that learning fundamentals of binary logic does not require, and should precede, learning about canonical normal forms $-$ this might be a useful reference: https://en.wikipedia.org/wiki/Truth_table

I guess my meaning was that one can distill a logical equation (via truth tables) in a fairly straightforward way, and going through that process is a pretty useful way to better understand the math.

 

[sysprog]

I guess my meaning was that one can distill a logical equation (via truth tables) in a fairly straightforward way, and going through that process is a pretty useful way to better understand the math.

The original question can be rephrased as, why is 'not A or not B' the negation of 'A and B', and in particular, why is 'neither A nor B' allowed by that negation.

A quick answer to that is that the negation of 'both' is simply 'not both', which doesn't prohibit 'neither'.

 

[valenumr]

The original question can be rephrased as, why is 'not A or not B' the negation of 'A and B', and in particular, why is 'neither A nor B' allowed by that negation.

A quick answer to that is that the negation of 'both' is simply 'not both', which doesn't prohibit 'neither'.

I was just trying to point out, in light of the three variable example, one could drive a disjunctive normal form simply by looking at the fact that (typically) first row of the truth table has the only false value, for the specific case. One could also derive a conjunctive normal form the hard way, using the seven "truths" in the other rows of the truth table and reducing, which ultimately is just (a or b or c), so... But one can see that both forms are ultimately the De Morgan's equivalent of each other.

 

[sysprog]

I was just trying to point out, in light of the three variable example, one could drive a disjunctive normal form simply by looking at the fact that (typically) first row of the truth table has the only false value, for the specific case. One could also derive a conjunctive normal form the hard way, using the seven "truths" in the other rows of the truth table and reducing, which ultimately is just (a or b or c), so... But one can see that both forms are ultimately the De Morgan's equivalent of each other.

The question was what is the negation of 'A and B'. The given answer was 'not A or not B'. That answer is correct.

We can observe that both 'not (A and B)' and 'not A or not B' are negations of 'A and B' $-$ the negation of a conjunction is equivalent to the disjunction of negations of the constituents of the conjunction (DeMorgan's) $-$ and that the second of the two expressions has the negation distributed over the constituents, while the first does not (the second is in DNF and the first isn't).

The construction of a truth table methodically distributes the negation over the constituents.

 

[Mark44]

So, does 'A or B or C' make possible these seven choices?

1. 'A'
2. 'B'
3. 'C'
4. 'A and B'
5. 'B and C'
6. 'A and C'
7. 'not A, not B, not C'

A truth table for a Boolean expression A will contain two rows, one for each possible value of A. A truth table for two Boolean expressions A and B will contain four ($2^2$) rows. With three Boolean expressions A, B, and C, there will be eight ($2^3$) rows.

As already noted, what you have in #7 is incorrect for A or B or C. Here is an expanded version of your list, together with the value of A or B or C.

1. 'A' true, B false, C false
2. 'B' true, A false, C false
3. 'C' true, A false, B false
4. 'A and B' both true, C false
5. 'B and C' both true, A false
6. 'A and C' both true, B false
7. A, B, C all true
8. A, B, C all false -- This is the only combination for which A or B or C is false.

If we're talking boolean algebra, I would recommend learning about disjunctive / conjunctive normal form.

Normal form seems like a topic that would be presented in a course on database design, which is not usually part of a precalculus course.

I was just trying to point out, in light of the three variable example, one could drive a disjunctive normal form

Same comment as above.

 

[sysprog]

Normal form seems like a topic that would be presented in a course on database design, which is not usually part of a precalculus course.

I think that @valenumr was making reference not to database design normalization, but to the logic concepts of canonical forms, e.g. disjunctive normal form.

 

[WWGD]

Maybe this way of looking at things is helpful: A&B is only true when A, B are both simultaneously true. Its negation is then true when it is not the case that both are true. This includes the situation/case where neither is true.

 

[sysprog]

Here is an expanded version of your list, together with the value of A or B or C.

1. 'A' true, B false, C false
2. 'B' true, A false, C false
3. 'C' true, A false, B false
4. 'A and B' both true, C false
5. 'B and C' both true, A false
6. 'A and C' both true, B false
7. A, B, C all true
8. A, B, C all false -- This is the only combination for which A or B or C is false.

@docnet, I think that this part of @Mark44's answer to your follow-up question is worth another look, in that it completes the truth table.