The “official” name for these boolean algebra rules

boolean-algebralogicpropositional-calculus

In boolean algebra, we have the following simplification rules: $$P + (\ldots P \ldots) = P + (\ldots 0 \ldots)$$ and $$P \cdot (\ldots P \ldots) = P \cdot (\ldots 1 \ldots)$$ (Here $\;\ldots P \ldots\;$ stands for an arbitrary expression containing $\;P\;$. See my answer to 'Where does this rule for Boolean simplification come from?' for the intuition behind an inductive proof.)

What are the "official" names for these rules?

I would expect them to be called something like 'generalized absorption rules', but I couldn't find anything related.

Best Answer

First, I don't know of any name given to this principle in the context of boolean algebra, though if I had to give it a name, it would probably be 'Generalized Reduction' rather than 'Generalized Absorption'

Here are the normal Absorption and Reduction Principles:

Absorption

$P \land (P \lor Q) \Leftrightarrow P$

$P \lor (P \land Q) \Leftrightarrow P$

Reduction

$P \land (\neg P \lor Q) \Leftrightarrow P \land Q$

$P \lor (\neg P \land Q) \Leftrightarrow P \lor Q$

So what you do is more like Reduction than Absorption: rather than that the whole second term is being 'absorbed' (and thus completely eliminated) by the single $P$, the second term is being 'reduced' (and thus simplified) in the context of the single term $P$

Second, and I think a little more interestingly, there is a visual logic system, called Existential Graphs, whose Iteration/Deiteration rule(s) very closely relate to your principles.

Quick explanation of Existential Graphs:

Statements in this system are put onto a Sheet of Assertion. It does not matter where you put the statements ... anything put on the Sheet of Assertion is being asserted as true. Thus, for example:

enter image description here

asserts $P$ as well as $Q$.

There is no explicit conjunction symbol in EG, but you can treat the fact that two statements are being juxtaposed in the same area as a conjunction. Thus, the above graph can be interpreted as having asserted two separate statements $P$ and $Q$, but also as having asserted a single statement $P \land Q$, or (since location does not matter) as the single statement $Q \land P$. This means that there is no one-to-one mapping between graphs in EG and algebraic expressions in normal logic systems, but it is actually quite a powerful cognitive feature: no conjunction symbol is needed, no order is imposed on the statements, and the Commutation and Association principles come for free.

Now, to negate a statement, we do this:

enter image description here

The enclosed figure is called a 'cut'. Putting a cut around some expression negates that expression. So, for example:

enter image description here

means the negation of the juxtaposition (conjunctin) of $P$ and $Q$, i.e. in normal notation this would be either $\neg (P \land Q)$ or $\neg (Q \land P)$

Now, since $\{ \land, \neg \}$ is an expressively complete set, this is actually all we need: the letters and cuts are all we need to express any logic statement. In fact, the cut can be seen as a generalized NAND: it negates everything that is conjuncted inside of it. But in practice, it typically works better to interpret the cut as a negation.

Here is a disjunction $P \lor Q$:

enter image description here

And here is an implication $P \rightarrow Q$:

enter image description here

This is a very common structure: when you have one cut inside another, then the stuff that is between the cuts (i.e. inside the outside cut, but outside the inside cut) is the antecedent, and the stuff that is inside the inside cut is the consequent. Thus, for example, the graph for the disjunction above can also be read as $\neg P \rightarrow Q$ or as $\neg Q \rightarrow P$ ... showing once again the power of these graphs: many equivalence principles become immediately obvious, and many principles intuitively generalize.

... which brings us to your rules:

$$P + (\ldots P \ldots) = P + (\ldots 0 \ldots)$$

and

$$P \cdot (\ldots P \ldots) = P \cdot (\ldots 1 \ldots)$$

Now, first it should be pointed out the in Existential Graphs you do not have an explicit $0$ or $1$ (or $\bot$ and $\top$). However, you can treat any empty bit of space as a $1$ (or $\top$): since all the bits on a graph are implicitly being conjuncted, then the any graph can be seen as that same graph 'conjuncted' with any empty bit of space next to it. But what logic statement has the feature that, when conjuncted with any other statements, results in that other statement? The $1$ and $\top$ of course!

Note this this also immediately means that:

enter image description here

is the $0$ (or $\bot$). This is called the 'empty cut'.

OK, now it gets interesting. Existential Graphs has 4 inference rules defined:

  1. Double Cut: You can add or remove any 'double cut'. This rule of course corresponds to the Double Negation principle in normal algebra. For example, using this principle we can go back and forth between:

enter image description here

and:

enter image description here

  1. Erasure: any graphs can be removed from an 'even level' .... meaning that any graph with an even number of cuts around it can be removed.

Thus, for example, we can go from:

enter image description here

to:

enter image description here

Now, remembering that we can read the original graph as the implication $P \rightarrow (Q \land R)$, and the resulting graph as $P \rightarrow Q$, we recognize this particular inference as the valid 'Weakening the Consequent' inference principle ... but again, the compact nature of Existential Graphs, which allows for many alternative readings, means that the Erasure rule is really much more general than that; it is a kind of 'Generalized Weakening the Consequent'.

  1. Insertion: Any graph can be added to an 'odd level'. I'll give no example, but we can understand this rule as a kind of 'Generalized Strengthening the Antecedent'

OK, and now we come to the interesting rule that I think bears a lot of resemblance to your rules:

  1. Iteration/Deiteration: you can add or remove a copy of any graph on a 'nested' or 'deeper' level. If you think of the cuts as creating a kind of hierarchy (or tree structure), then a 'nested' level would be one that is 'deeper' in this hierarchy or tree.

Let's do Modus Ponens as an example. Start with $P$ and $P \rightarrow Q$:

enter image description here

Now, the $P$ inside the cut is at a 'nested' level with regard to the outside $P$ , so we can 'deiterate' it:

enter image description here

Now we can use Double Cut:

enter image description here

And, if you don't like the fact that the $P$ is still there, we can simply remove it by Erasure (level $0$ is even):

enter image description here

OK, so now let's finally make the connection to your rules. First, consider:

$$P \cdot (\ldots P \ldots) = P \cdot (\ldots 1 \ldots)$$

Well, the graph for the left side would be:

enter image description here

(the dots indicate that the right $P$ can occur at any nested level, even if it is many levels deeper than the outside $P$)

while the right hand side would be:

enter image description here

(remember that a $1$ corresponds to a bit of empty space in Existential Graphs)

OK ... so that is exactly the Iteration/Deiteration rule which, since it goes both ways, is an equivalence principle (just like Double Cut, but unlike Erasure and Insertion, which are one-way inference rules)

OK, now for the other one:

$$P + (\ldots P \ldots) = P + (\ldots 0 \ldots)$$

This one is a little more tricky, but notice that the left hand side is the following graph:

enter image description here

So, if we now do a Double Cut on the inside $P$:

enter image description here

Then we can Deiterate:

enter image description here

.. and remembering that the $0$ corresponds to the Empty Cut, we're there. And, of course, using Double Cut and Iteration we can go back, demonstrating the equivalence.

... So .... I would say that there is a definite connection between your principles and EG's Iteration/Deiteration (equivalence) rule!