# DeMorgan's Rule

Just out of idle curiosity more than anything else, I was wondering, for anyone with a bit of understanding of basic symbolic logic, if DeMorgan's Rule works with NCBs. Does Nova read, for example, "(!b1 & !b2)" and "!(b1 | b2)" as the same expression?

Extra credit for anyone who can give me the Latin name for this Fallacy:
Pretend > is the symbol for "then"

(p • q)
:
(p > q) v (q > p)

Yes, the two expressions are logically identical. We don't need DeMorgan to tell us that (if Nova didn't interpret them the same there would be something seriously wrong with its logic)

As for the fallacy... sorry, don't think I ever got taught latin names of fallacies.

This post has been edited by Guy : 06 January 2009 - 10:18 PM

As Guy said, Nova's logic interpreter isn't that flawed. If it had problems with those statements, we'd have caught on by now.

For the second one I'm not sure which operator '•' is supposed to represent (Looking at Wikipedia, I might guess Exclusive Disjunction, but I'm not sure), and am guessing that ':' is 'Therefore' in this context.

@archon, on Jan 6 2009, 06:09 PM, said in DeMorgan's Rule:

if DeMorgan's Rule works with NCBs. Does Nova read, for example, "(!b1 & !b2)" and "!(b1 | b2)" as the same expression?

It's a law. It applies to any system with grouping, negation, and, and inclusive-or. (Actually, it doesn't matter what two operators there are, since the others can be constructed, even from a single operator)
However, an aware coder may select one over the other to improve the speed of the processing.
First: 3 operations
Second: 2 operations

@archon, on Jan 6 2009, 06:09 PM, said in DeMorgan's Rule:

Extra credit for anyone who can give me the Latin name for this Fallacy:
⇒ and → are variations on the symbol for "implies."
(p ∙ q)

(p → q) ∨ (q → p)

(corrected symbols: most are in the u22xx range)
For people not familiar with logic, this says:

Spoiler

P and Q,
therefore
P implies Q or Q implies P.

In English, the fallacy is:

Spoiler

they may be unrelated

In Latin,

Spoiler

It's almost Post hoc ergo propter hoc.
but I'd say cum hoc ergo propter hoc.

Not off the top of my head did I know that. But Wikipedia is useful when you know for what you're looking.

@nonconventionally-creative, on Jan 6 2009, 10:39 PM, said in DeMorgan's Rule:

For people not familiar with logic, this says:
P and Q,
therefore
P implies Q or Q implies P.

He used 'v' to represent 'or'.
Wouldn't the notation for 'and' have been '^' or '∧' instead of '•' in that case?

This post has been edited by Eugene Chin : 06 January 2009 - 11:04 PM

@eugene-chin, on Jan 6 2009, 08:02 PM, said in DeMorgan's Rule:

He used 'v' to represent 'or'.
Wouldn't the notation for 'and' have been '^' or '∧' instead of '•' in that case?

I thought about that, but just corrected the symbols he used from ASCII (and that bullet) lookalikes to Unicode.
Interestingly, in my font, the bullet used in the original post is a large circle, but the bullet operator is a small dot like the "middle dot" or interpunct, which is small. In other fonts, they are notably different.
Original bullet: • 2022
Bullet operator (AND): ∙ 2219
Interpunct: · 00B7

Psychologically, we might think of this use of "AND" as different because it is the premise of the statement rather than a variable in a test, but it's really the same thing.

I had an interesting search to determine which characters really were correct. Hopefully I'll remember that they're in the 2200 range (that is in the official definition) and open my character map to that page. Interestingly, the bullet operator is in that section, but that refers to something else, I think.

Nonconventionally Creative wins I know that the notations aren't exact, just approximations of longhand symbolic logic. But thanks to you all, next time I need to type up some logic, I'll know exactly how to do it.

Funny, never thought this thread would have gotten this many replies.

P.S. NC, thanks for pointing out my semantic slip. :laugh:

@archon, on Jan 6 2009, 09:09 PM, said in DeMorgan's Rule:

(p • q)
:
(p > q) v (q > p)

Let p(x) and q(x) be logical statements about x.

The argument,

There exists an x such that p(x) ^ q(x)
Therefore:
For all x, (p(x) -> q(x)) v (q(x) -> p(x))

can be analyzed with a truth table, or symbolically. The statement p(x) -> q(x) is only false when p is true and q is false, so it's equivalent to !(!p ^ q) = p v !q. Similarly, q(x) -> p(x) = q v !p.

``````|  p  |  q  | p^q | p->q| q->p| (p->q)v(q->p)
|  T  |  T  |  T  |  T  |  T  |  T
|  T  |  F  |  F  |  F  |  T  |  T
|  F  |  T  |  F  |  T  |  F  |  T
|  F  |  F  |  F  |  T  |  T  |  T
``````

Since we are given the premise that there is at least one x such that p^q is true, we know the first line is definitely a possibility. We are given no information about the other lines, so we must suppose there could be an x such that for any of the other lines, that combination of p(x) and q(x) would happen. So we look at every line. Note that replacing the premise with "For all x, p(x) ^ q(x)" actually makes it so we only have to look at the first line. It's a subset of the argument I'm dealing with.

An argument of the form,

<premises>
Therefore:
<conclusion>

is valid if, whenever the premises are true, the conclusion is true. Here we have as the premise,

There exists an x such that p(x) ^ q(x)

which could be true regardless of the x we pick, or it could be false. If it is false the argument form is automatically valid, so we only need look at the case where it is true. The conclusion is,

For all x, (p(x) -> q(x)) v (q(x) -> p(x))

which according to the truth table, is always true. Thus, for any premise, this conclusion is true. As a result, there is no premise which would make the argument invalid. Ergo, for the specific premise given, the argument is valid.

There exists an x such that p(x) ^ q(x)
Therefore:
For all x, (p(x) -> q(x)) v (q(x) -> p(x))

is a valid argument.

Please do not confuse the logical "then" with the concept of "causes". The fallacy described amounts to "Correlation implies causation." But the logical argument presented amounts to "Correlation implies tautology." Since tautology is always true, the argument is valid.

This post has been edited by Qaanol : 07 January 2009 - 02:32 PM

The argument is logically valid, yes, but it is a fallacy when used in the real world, eg. a court of law.

@qaanol, on Jan 7 2009, 11:30 AM, said in DeMorgan's Rule:

Please do not confuse the logical "then" with the concept of "causes". The fallacy described amounts to "Correlation implies causation." But the logical argument presented amounts to "Correlation implies tautology." Since tautology is always true, the argument is valid.

I acknowledge that there may be confusion about the term "causation." The statement:
A implies B
only means that
It does not imply that in natural terms, A is the cause per se of B, according to the natural concept.

The fallacy of your argument lies in the order in which you evaluated your truth table.
Note: None of my following argument would be true if p is always true or if q is always true, because if p is always true, then q -> p. However, neither of those statements can be derived from the original premise, which is: for some x, p(x) and q(x)

``````|  p  |  q  | p^q | p->q| q->p| (p->q)v(q->p)
|  T  |  T  |  T  |  T  |  T  |  T
|  T  |  F  |  F  |  F  |  T  |  T
|  F  |  T  |  F  |  T  |  F  |  T
|  F  |  F  |  F  |  T  |  T  |  T
``````

The last column is not valid.

The conclusion of the statement requires that
p -> q for all x.
or
q -> p for all x.
because the domains of p and q , as you defined them, are all x.

Some definitions:
X: the domain of all possible values of x.
X1: values of x such that p and q
X2: values of x such that p and not q
X3: values of x such that (not p) and q
X4: values of x such that (not p) and (not q)

X1..4 are mutually exclusive, and X is the union of them.

Now, a final row showing the logical AND of each individual possibility, which is: is this statement always true?

``````x in|  p  |  q  | p^q | p->q| q->p| (p->q)v(q->p)
X1 |  T  |  T  |  T  |  T  |  T  |  T
X2 |  T  |  F  |  F  |  F  |  T  |  T
X3 |  F  |  T  |  F  |  T  |  F  |  T
X4 |  F  |  F  |  F  |  T  |  T  |  T
====+=====+=====+=====+=====+=====+=====
X |  F  |  F  |  F  |  F  |  F  |  F
``````

p is not true for all x in X, because it is not true in X3 and X4.
true likewise.
p ^ q is not true for all x in X, because it is only true in X1.
p->q is not true for all x in X, because it is not true for x in X2.
q->p likewise.

@guy, on Jan 7 2009, 12:08 PM, said in DeMorgan's Rule:

The argument is logically valid, yes, but it is a fallacy when used in the real world, eg. a court of law.

It is invalid in court because it is invalid in logic, Q.E.D.

(Now I feel odd, not using the mathematical symbols, after making a deal about that. But there are a lot )
(That could probably be reordered to follow a better pattern, but I'm making it more of a reply, depending on previous material).

As long as we're on the subject, I still can't wrap my head around this one even though I know it's valid:

~p → p

∴ p

@archon, on Jan 7 2009, 09:17 PM, said in DeMorgan's Rule:

~p → p

∴ p

This has to do with the way → is defined to work.

The only time a → statement is false is when the condition is true but the implication is false.
If the condition (here ~p) is not true, then the statement is not false.
In other words, → would be true even for cases where the sub-statements only matched by coincidence.

Here, you are given the statement ~p → p, and told that the statement is true.

The only way this statement is false is if the first part is true (i.e. if ~p = T) and the implication is false (i.e. if p = F).

If p is false, then ~p is true, and the statement ~p → p cannot be true.
If p is true, then the condition isn't an issue, and the statement is true.

The operator is more stringent, as it would require the sides to be either both true or both false for the whole to be true.

@nonconventionally-creative, on Jan 7 2009, 07:33 PM, said in DeMorgan's Rule:

I acknowledge that there may be confusion about the term "causation." The statement:
A implies B
only means that
It does not imply that in natural terms, A is the cause per se of B, according to the natural concept.

The fallacy of your argument lies in the order in which you evaluated your truth table.
Note: None of my following argument would be true if p is always true or if q is always true, because if p is always true, then q -> p. However, neither of those statements can be derived from the original premise, which is: for some x, p(x) and q(x)

``````|  p  |  q  | p^q | p->q| q->p| (p->q)v(q->p)
|  T  |  T  |  T  |  T  |  T  |  T
|  T  |  F  |  F  |  F  |  T  |  T
|  F  |  T  |  F  |  T  |  F  |  T
|  F  |  F  |  F  |  T  |  T  |  T
``````

The last column is not valid.

The conclusion of the statement requires that
p -> q for all x.
or
q -> p for all x.
because the domains of p and q , as you defined them, are all x.

There was no fallacy in my logic. The conclusion of the original statement is,

(p->q)v(q->p)

I interpret that to mean (for all x, (p->q)v(q->p)), which is not the same as (for all x, p->q)v(for all x, q->p). The conclusion above requires that, for any x in X, at least one of (p->q) and (q->p) is true. Your version is the same as requiring that at least one of the following is valid:

There exists an x such that p(x)^q(x)
Therefore:
For all x, p->q

OR

There exists an x such that p(x)^q(x)
Therefore:
For all x, q->p

And that is not the same as the argument as I took it in my previous post. However, that is an argument with the fallacy originally given, so perhaps it is what was intended. More briefly,

There exists an x such that p(x)^q(x)
Therefore:
(For all x, p->q)v(for all x, q->p)

There is ambiguity when "for all" and "there exist" statements are left out. Or, rather, when they are left out, the argument only deals with the first row of my original truth table, and the conclusion is tautology. But with the "for all" statements added this way, you are correct that it has a fallacy.

@qaanol, on Jan 7 2009, 08:00 PM, said in DeMorgan's Rule:

I interpret that to mean (for all x, (p->q)v(q->p)), which is not the same as (for all x, p->q)v(for all x, q->p). The conclusion above requires that, for any x in X, at least one of (p->q) and (q->p) is true.

We understand each other.

However, I don't believe the meaning of that statement is up to interpretation. As before, p and q are defined as functions that take x.

The statement
P → Q
is equivalent to:
{x| P(x) is true} ⊆ {x| Q(x) is true}
which is to say:
(the set of x such that P(x) is true) is a subset of (the set of x such that Q(x) is true).

And from the truth table, neither this nor its converse is true.

Nope. Sorry guys.

You've all neglected to account for the possibility of a universe in which multiple control bit bays launch the same control bit type.

Wait... what?

I apologize, that was an extremely obscure Nova Bible pun. :hector_bird:

No apologies necessary!

@nonconventionally-creative, on Jan 8 2009, 12:06 AM, said in DeMorgan's Rule:

We understand each other.

However, I don't believe the meaning of that statement is up to interpretation. As before, p and q are defined as functions that take x.

The statement
P → Q
is equivalent to:
{x| P(x) is true} ⊆ {x| Q(x) is true}
which is to say:
(the set of x such that P(x) is true) is a subset of (the set of x such that Q(x) is true).

And from the truth table, neither this nor its converse is true.

I see now this is correct.

However, I believe I also took liberties in interpreting "p^q" to mean "there exists an x such that p(x) and q(x) are true". A strict logical reading would give, "for all x, p(x) and q(x) are true". From there, it immediately follows that both p implies q and q implies p, for all x.

Yo, I actually read this thread, and now my brain is melting. wth