Last night, I came across a simple propositional logic problem concerned with the validity of the statement:

\[ \bigl((A \implies B) \land (B \implies C)\bigr) \iff (A \implies C). \]

At first, I thought it is valid. But on drawing the truth table, I was surprised to see that it isn't valid.

\(A\)\(B\)\(C\) \(A \implies B\)\(B \implies C\)\(A \implies C\) \((A \implies B) \land (B \implies C)\) \(\bigl((A \implies B) \land (B \implies C)\bigr)\) \(\iff\) \((A \implies C)\)
TTT TTT T T
TTF TFF F T
TFT FTT F F
TFF FTF F T
FTT TTT T T
FTF TFT F F
FFT TTT T T
FFF TTT T T

My intuition had failed. The truth table shows that there are two cases in which the statement is false.

Case 1: \((A \implies C) \land (B \implies C) \land \lnot(A \implies B)\)

In this case, \(A\) implies \(C\) and \(B\) implies \(C\), but \(A\) does not imply \(B\). This corresponds to the third row in the truth table. It makes sense. Two things can imply a third thing but they need not imply each other. For example, rain may imply wet soil and snow may imply wet soil as well, but rain need not imply snow. Here is another example that demonstrates this.

The following two statements are true for any integer \(x\).

\[ 4 \mid x \implies 2 \mid x. \\ 6 \mid x \implies 2 \mid x. \]

But the following statement is false when \(x \equiv 4 \pmod{12}\) or \(x \equiv 8 \pmod{12}\).

\[ 4 \mid x \implies 6 \mid x. \]

In other words, if an integer is a multiple of \(4\) as well as a multiple of \(6\), then it is also a multiple of \(2\). But this is not equivalent to claiming that if an integer is a multiple of \(4\), then it is also a multiple of \(6\). Such a claim is not correct as we can confirm for \(x \in \{4, 8, 16, 20, 28, 32, \dots\}\).

Case 2: \((A \implies B) \land (A \implies C) \land \lnot(B \implies C)\)

In this case, \(A\) implies \(B\) as well as \(C\) but \(B\) does not imply \(C\). This corresponds to the sixth row in the truth table. It makes sense as well. One thing can imply two other things but those two things need not imply each other. For example, rain may imply wet soil and flooded rivers but wet soil need not imply flooded rivers. The soil could be wet due to irrigation sprinklers. Once again, here is a mathematical example to demonstrate this.

The following two statements are true for any integer x.

\[ 6 \mid x \implies 2 \mid x. \\ 6 \mid x \implies 3 \mid x. \]

But the following statement is false when \(x\) is an odd multiple of \(3\).

\[ 2 \mid x \implies 3 \mid x. \]

In other words, if an integer is a multiple of 6, then it is a multiple of 2 as well as 3. But this is not equivalent to claiming that if an integer is a multiple of 2, then it is also a multiple of 3. Such a claim is clearly false as we can confirm for \(x \in \{3, 9, 15, 21, \dots\}\).

Encoding intuition correctly

My intuition incorrectly concluded that the \(\bigl((A \implies B) \land (B \implies C)\bigr) \iff (A \implies C)\) is valid because I was not translating the given statement correctly in my mind. I was thinking that if \(A\) implies \(B\) and \(B\) implies \(C\), of course \(A\) must also imply \(C\). This is true but this is not what the given statement represents. The given statement means something more than this. In addition to what I thought, it also means that if \(A\) does not imply \(B\) or \(B\) does not imply \(C\), then \(A\) does not imply \(C\) as well. This however doesn't happen. The truth table shows that even though \(A\) does not imply \(B\) or \(B\) does not imply \(C\), it is possible that \(A\) implies \(C\).

As far as my intuition is concerned, the following would be the right way to represent what I was thinking.

\[ \bigl((A \implies B) \land (B \implies C)\bigr) \implies (A \implies C). \]

Indeed, this statement is valid as can be seen from the truth table below.

\(A\)\(B\)\(C\) \(A \implies B\)\(B \implies C\)\(A \implies C\) \((A \implies B) \land (B \implies C)\) \(\bigl((A \implies B) \land (B \implies C)\bigr)\) \(\implies\) \((A \implies C)\)
TTT TTT T T
TTF TFF F T
TFT FTT F T
TFF FTF F T
FTT TTT T T
FTF TFT F T
FFT TTT T T
FFF TTT T T

Solution to a problem asked by Rohan at RSA.

Prove that for every positive integer n there exists an n-digit number divisible by 5n all of whose digits are odd.
Before we proceed let us keep a note of a little thing we'll need.

1 ≡ -4 (mod 5) 3 ≡ -2 (mod 5) 5 ≡ 0 (mod 5) 7 ≡ -3 (mod 5) 9 ≡ -1 (mod 5)

So, the set {1, 3, 5, 7, 9} covers all possible values in mod 5 arithmetic. Now, let us begin the proof.

The statement is clearly true for n = 1 as there exists 5 which is a 1-digit number divisibile by 51 and all its digits are odd.

Let us assume that the statement is true for n = N where N is a positive integer. So, there exists an integer m which is N-digit, divisible by 5N and all its digits are odd.

Now, we will show that for n = N + 1, there exists an integer k10N + m divisible by 5N+1 where k ∈ {1, 3, 5, 7, 9};

k10N + m ≡ 0 (mod 5N+1)

⇔ 5N(k2N + m5N) ≡ 0 (mod 5N+1)

⇔ k2N + m5N ≡ 0 (mod 5)

⇔ k6N + m5N ⋅ 3N ≡ 0 (mod 5)

⇔ k ≡ -m5N ⋅ 3N (mod 5)

⇔ k ∈ {1, 3, 5, 7, 9} … (from the note in the beginning)

So, we have shown that for some odd digit k, we have a number k10N + m divisible by 5N+1. Also, note that this number is an N+1 digit number because m was an N digit number.

Hence, from the principle of mathematical induction, the proof is complete for all positive integers n.

We can use this proof to generate the n-digit numbers for all values of n.

1-digit number: 5 2-digit number: 75 since k = -551 ⋅ 31 mod 5 = -3 mod 5 = 7. 3-digit number: 375 since k = -7552 ⋅ 32 mod 5 = -2 mod 5 = 3. 4-digit number: 9375 since k = -37553 ⋅ 33 mod 5 = -1 mod 5 = 9. and so on …

OEIS entry for this sequence: A151752

1 ⋅ 1! + 2 ⋅ 2! + … + n ⋅ n! = (n + 1)! - 1

It is easy to prove this using the principle of mathematical induction. Some ways to interpret this formula.

  1. For values of k from 1 to n - 1, the number of possible permutations of n items where the kth item is the first one to be moved from its original position is equal to the number of possible permutations of the sequence where at least one element has moved from its original position. This gives us the formula: 1 ⋅ 1! + 2 ⋅ 2! + … + (n - 1) ⋅ (n - 1)! = n! - 1. In other words, k ⋅ k! is the number of permutations in which (n - k)th item is the first one to be moved from its original position.
  2. The largest factoradic number that can be represented using n digits is 1 ⋅ 1! + 2 ⋅ 2! + … + n ⋅ n! = (n + 1)! - 1.
Update 1: Realized that interpretation 1 can be made simpler if we consider kth item as the last one to be moved from its original position. The number of permutations in which kth item is the last one to be moved from its original position is: (k - 1)(k - 1)!. In this case, the interpretation becomes: For values of k from 2 to n, the number of possible permutations of n items where the kth item is the last one to be moved from its original position is 1 ⋅ 1! + 2 ⋅ 2! + … + (n - 1) ⋅ (n - 1)!.

Derived these properties while solving a problem posted by Rohan in the math forum at RSA.

Generalized Fermat numbers Fn for a given integer a, Fn = a2n + 1

  1. Fn+1 - 2 = (Fn)(Fn - 2).
  2. Fn+1 = FnFn-1…F0(a - 1) + 2
  3. gcd(Fm, Fn) = 1 if a is even and 2 if a is odd, where m ≠ n.

Derived some identities while thinking on what James Randi said in the following video (James Randi and a Graphologist) after 1 minute 50 seconds.

Let d0 = 1 and dn be the number of derangements of n elements, where n is a positive integer.

nnC0d0 + (n − 1)nC1d1 + … + 0nCndn = n!

nC0d0 + nC1d1 + … + nCndn = n!

Update: A detailed blog here: James Randi and a graphologist

Newer | Older
RSS