Only our own ruts

'Build your own beautiful world.'
 'Build your own beautiful world.'

Proof by contradiction

These proofs get me confused because they circle back and shoot down your assumption – which was the point, but it feels like a mental “frame shift” to return to it. One example from Rosen:

Show that at least four days of 22 days fall on the same day.

With proof by contradiction, you assume the opposite and follow that line of reasoning to a true implication. If you can show the conclusion is a contradiction, then it is false. For the implication to be true, !p must also be false. If !p is false, then p must be true.

Rosen uses the term “at most three” to express the negation of “at least four,” but I like “less than four.” (At least being greater than or equal to, and the negation being less than.)

After negating the premise, you show that it could be true for both the given condition and its opposite: so you can fit three of the same day within twenty-two days, but you can also fit them in twenty-one (three weeks’ worth) days. The not-p is true with both circumstances, even though !(twenty-two days) could be twenty-one days.

Then you have

~p -> F

For this implication to be true, !p must also be false. If !p is false, then p must be true.

I can parrot the explanation, but whether I will be able to apply it is another matter.

Solving your own problems

It’s not enough to just solve problems. Each problem is a litmus test of your personal framework, your process. Each successful answer validates the invention; each wrong answer is opportunity for feedback. It’s not explicit, anywhere, that the student’s thinking paradigm is the innovation produced out of procedure; it is simply accepted. If you do not have a framework, there is no sink to which labor strengthens; it is futile.

I almost want to say that moving forward is a failing if a framework hasn’t been forged through the crucible of getting things wrong: you’ll forget how to solve those problems, because your context will have staled. Then it’s a trip back to reference it, a dozen Google searches, and even then you’re not certain. I would think, “Man, I wish I had started a program back then.”

Honestly, who has time for that? Only priests focus on one book. (Well, maybe I am a priest.) The other alternative is to apply what I’ve learned, and that leads directly into waterfall design – imagine writing predicates and quantifiers for each part of a requirements spec!

I do have all the problems worked on looseleaf. That becomes my reference.

Semantic pedantics

No one is perfect.
\forall x \neg P(x)
\equiv \neg P(x_1) \wedge \neg P(x_2) \wedge \dots \wedge \neg P(x_n)
\equiv \neg \exists x P(x)

Not everyone is perfect.
\neg \forall x P(x)
\equiv \neg (P(x_1) \wedge P(x_2) \wedge \dots \wedge P(x_n))

After DeMorgan’s Law
\neg P(x_1) \vee \neg P(x_2) \vee \dots \vee \neg P(x_n) \equiv \exists x \neg P(x)

And the answer key also has this:

Not everybody is your friend or someone is not perfect.
(\forall x \neg F(x)) \vee (\exists x \neg P(x))

So, “everybody” refers to “one” and “someone” is the same as “everyone.”

The fear of insufficiency

I began the next section of discrete math. It covers predicates and quantifiers. These are the loops of the logic world, stretched blankets over exact universes. One quantification, the universal, implies a long conjunction: for every  x1-x2-dot-dot-dot-xn, apply AND to each of them. It takes one counterexample to show a universal quantification false.

I met the propositional function P(x), which encapsulates the subject and predicate of a statement. Specifying the domain lets us assign values to the variable. Since we’re in logic land, each such assignment evaluates to a truth value, True or False.

Multiple variables create instances of tuples. Databases also use the term tuple. Could the row of a database be an instance of a long function P(a, b, c, …, z)? The binding of one or more of those variables specifying uniqueness, and each row mapped to an array with one less dimension: tables as 2D, mappings as collapse to 1-dimensional, linear collections.

But I speak of fear. One example had math: x2-ge-x. Rosen broke it down to x-times-x-minus-1-ge-0. Then he goes to say it’s true if and only if x-le-0 or x-ge-1. How did he get there? I became worried that my math journey would abruptly cease at section three, chapter one.

Wolfram Alpha gave hints, but ultimately I made a table:

Universe: real numbers
x    x*(x-1)  x*(x-1)>=0
-2.0 6        T
-1.5 3.75     T
-1.0 2        T
-0.5 2.25     T
0    0        T
0.5  -0.25    F
1.0  0        T
1.5  0.25     T
2.0  2        T

Somewhere between 0 and 1, the values we assign to the x variable do not result in a true inequality. Another way to say “x <= 0 or x >=1” is 0-lt-x-lt-1. Can we believe that, though? What if there’s some number 0.000029482 that satisfies greater than or equal to zero? We can think through some assumptions:

x*(x-1) >= 0
A. if x = 0, x*(x-1) = 0
B. if x < 0,
x * (x - 1) >= 0
(x - 1) <= 0     | divide by x (-), switches sign
x <= 1           | add 1 to both sides
x >= 1           | multiply by -1 on both sides (x is -)

The inequality is true when x <= 0.

x*(x-1) >= 0
A. if x = 1, x*(x-1) = 0
B. if x > 1,
x * (x - 1) >= 0
(+) * (+) >= 0   | positive times positive is >= 0

The inequality is also true when x >= 1.

x*(x-1) >= 0
if 0 < x < 1,
x * (x - 1) >= 0
(+) * (-) >= 0 ? | x (less than 1) minus 1 is negative (so, False)

When x is between 0 and 1, the inequality is false. Going back to the universal quantifier, for every x, P(x), with the domain of all real numbers, is false.

I generalized the process thus:

  • Gather “data”: make a table. play with numbers. fiddle around. You are the compiler.
  • Discover the “rules”: 0 < x < 1
  • Check yourself: if x <= 0, if x >= 1, if 0 < x < 1
  • Conclude: agree with the author or disagree; move on

Short dip into negative space

A compound proposition is made up of multiple propositions. If we can assign a truth value to each proposition that makes the compound proposition true, then the compound proposition is satisfiable. If every assignment leads to the compound proposition being true, then the compound proposition is a tautology. Tautologies are true “no matter what.”

p | p v ~p
T     T
F     T

The compound proposition is always true regardless of the assignment of truth values to p. The compound proposition p OR NOT p is a tautology.

An algorithm can be written that determines if a compound proposition is satisfiable. Such an algorithm could be used in a loop. For each assignment, continue until an assignment of propositions is unsatisfiable. If so, exit: that compound proposition is not a tautology. You would have to test every assignment.

Rosen hints at an alternative: try the negation of the compound proposition. If a compound proposition is a tautology, it will always be True, True, …, True for any assignment of Ts and Fs. Then its negation would always be False, False, …, False. However, with the negated version of the compound proposition, we only need to test one instance of satisfiability: if the NOT version is satisfiable once, the original compound proposition is not a tautology.

You can show a compound proposition is true every time, or that its negation is true once. If the negated version is True with that assignment, then the original version will evaluate to False. One False means the compound proposition is not always true, and you need “always True” to get a tautology.

When you are proving something, you could assume the opposite – then you only need to show one example. That means the original given can’t always be true. Would you prefer to demonstrate one counterexample or an exhaustive* listing?

* “Define exhaustive.”

Speculative generator

A story being an aggregate of chunked words to bond various explanations, then it could show us the progression of a thought process where each compound proposition is satisfied by one combination of truth values.

We plug into this “world engine” certain facts [1], and it creates random compound propositions that are all true for some combination of True and False for each assignment of p, q, r, s, etc.

Our work consists of kicking out each false in some way, changing our preconceptions in each chapter, assuming a different role, until things begin to resolve toward the One Path in which every compound proposition is True.

p q r s C1 C2 C3 C4 C5 ...
T T T F T  F
T T F T T  T  F
T T F F T  T  T  F
T F T T T  T  T  T  F
T F T F T  T  T  T  T

It’s a harebrained idea, attempting to mechanize what intuition and skill melds in a writer to weave magic. Even if the method is systematic, all the reader cares about is the “user experience.” For books, that’s great writing and consistent verisimilitude. People can tell artificiality without training.

But as a check against our gut in the middle of a complex narrative, it may have some use. If I bang one out before NaNoWriMo, that would be a nice laboratory for its efficacy.

Inspired by exercise 53 of Rosen’s 5e “Discrete Mathematics and Its Applications.” In the picture below, we see several ways that every compound proposition is satisfied. Ideally, there would only be one set of assignments to p, q, r, and s that made every compound proposition True.


The direct solution is p AND NOT q AND NOT r AND NOT s, where p is True and q, r, and s are all False. We call that Author’s Intent.

[1] Cultural perspective or a moral, objective one – the viewpoint of the Main Character?

The not-not is

Given an implication, we have its converse, contrapositive and inverse:

p -> q
q -> p
~q -> ~p (contrapositive)
~p -> ~q (inverse)

The original implication is logically equivalent to its contrapositive. The converse and inverse are logically equivalent to each other.

p -> q
~p v q, because p -> q = ~p v q
q v ~p, because p v q = q v p
~(~q) v ~p, because ~(~p) = p
~q -> ~p, because p -> q = ~p v q

So we see that an implication and its contrapositive are logically equivalent.

Given p -> q,
q -> p
~q v p, because p -> q = ~p v q
p v ~q, because p v q = q v p
~(~p) v ~q, because ~(~p) = p
~p -> ~q, because p -> q = ~p v q

And this shows the converse and inverse of an implication are logically equivalent.

I ordered a raft of books, old books, costing about a cent each, whose value outweighs the ship rate of which I paid the majority of the total. Books from shops into the hands of a collector, a private math where communion competes with pragmatics.

Truth table combinatorics

For every n propositions, you have 2-to-the-n possibilities. That adds up: given three characters and two propositions for each, you get six propositions – and 2, 4, 8, 16, 32, 64 combinations. Span your cast to seven or eight simple, archetypal characters as per Dramatica, and it’s 128 combinations!

That’s only theoretic: some combinations are too outlandish to work, and some progressions don’t make sense. At the climax, a character may flip from T to F or from F to T, but flip-flopping would be harder to track. Few readers scribble out a truth table for a one-off, I think.

Using the sequences of a truth table to thread your work can give you a roadmap for developing each character. How does the reader perceive this character to be “True” or “False” in regards to a proposition? For example, “The prince is honorable.” It can appear true in the beginning, but his actions may sway the reader to believe otherwise. Redemption is ripe after a steady string of False, only to turn True at the end.

You’re asking yourself, “How do I show this? How do I show that? How would this show that? Is that good enough? Would I believe it?”

Things can be further complicated by combining logic with constraints: societal constraints, traditions, law and culture. Take your reader on a journey into a rich world – a world that is not only punchy, but internally consistent.

This was also inspired by Bioshock. A friend said Spector’s genius lay in leading the gamer by the nose – getting him to think one thing until the very end, when everything completely shifts. Perception. Prejudice. Preservation.

All the truth in the world

From Discrete Mathematics and Its Applications, 5e, Rosen:

A detective has interviewed four witnesses to a crime. [Propositions follow.]

  • B: The butler is telling the truth.
  • C: The cook is telling the truth.
  • G: The gardener is telling the truth.
  • H: The handyman is telling the truth.

From the problem statement, I get the following compound propositions:

B -> C
C + G
~(~G & ~H)
H -> ~C

Here’s the truth table:

B  C  G  H   B->C  C+G  H->~C  ~(~G&~H)
-  -  -  -    -     -     -        -
T  T  T  T    T     F
T  T  T  F    T     F
T  T  F  T    T     T     F
T  T  F  F    T     T     T        F
T  F  T  T    F
T  F  T  F    F
T  F  F  T    F
T  F  F  F    F
F  T  T  T    T     F
F  T  T  F    T     F
F  T  F  T    T     T     F
F  T  F  F    T     T     T        F
F  F  T  T    T     T     T        T
F  F  T  F    T     T     T        T
F  F  F  T    T     F
F  F  F  F    T     F

There are two cases where all propositions together cause consistency: when G is true or when G and H are true. Assuming there was only one criminal, we could point out the gardener and close the case. But the question asks

For each of the four witnesses, can the detective determine whether that person is telling the truth or lying?

What? I looked in the back for the answer. The answer is that we can determine that the butler and cook are lying, but we cannot determine if the gardener or the handyman are telling the truth.

That makes sense: a criminal wouldn’t implicate himself, and presumably the truth-tellers wouldn’t take the fall. Somewhere in here are the seeds of plot and human nature, and why stories can still be the taut battleground of drama.