I'm a newbie to probability theory and am currently working through Chapter 1 of Jaynes' "Probability Theory, The Logic of Science". In it, he introduces the Boolean algebra and a number of identities associated with it, specifically idempotence, commutativity, associativity, distributivity, and duality. However, in this list there seems to be no mention of the following

$$\overline{\overline{X}} = X$$

i.e. the negation of the negation of the proposition has the same truth value as the proposition and

$$X + XY = X$$

My question is: why are the two propositional statements above not considered to be "identities" of Boolean algebra? And more generally, what then is the requirement for a propositional statement to be an identity in Boolean algebra?

  • $\begingroup$ Without seeing the book, my guess would be that the list is of a few identities which suffice to generate all valid identities. e.g. using other identities, $X+XY = X\cdot 1 + XY = X(1+Y) = X\cdot 1 = X$. $\endgroup$ Jan 10 '19 at 22:28

It's not that those equations you posted aren't identities. Rather, it's that they aren't taken to be axiomatic (assumed), because they can be proven from the given (axiomatic) identities. In fact, we can take even fewer of the identities for granted, and still prove the others. We need only include:

  1. both associativity identities,
  2. both commutativity identities,
  3. both absorbtion identities (that is, $X(X+Y)=X$ and $X+XY=X$ for all $X$),
  4. one of the distributivity laws, and
  5. both complementation laws ($X+\overline X=1$ and $X\overline X=0$).

This comprises one such list of axioms. There are others that are even shorter. The upshot is that the "identities" presented are simply the axioms which the text uses to prove everything else.

  • $\begingroup$ Isn't it even simpler to state the truth tables of $\overline{X} , +, \cdot$ as axioms ? $\endgroup$
    – user65203
    Jan 10 '19 at 22:50
  • $\begingroup$ @Yves: I suppose it might be, though I've never been partial to proof by truth table. $\endgroup$ Jan 11 '19 at 12:10

The author writes on page 10: https://books.google.com/books?id=tTN4HuUNXjgC&pg=PA10

$\overline A\equiv A$ is false (1.8)
$A=\overline A$ is false (1.9)

Equation 1.9 is the axiom you're looking for. It allows us to compute $\overline{\overline X}=\overline X$ is false${}=X$. The first equality is given by substituting $A=\overline X$ in (1.8), and the second equality is just (1.9) backwards.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.