Absorption (logic)

The law of absorption in propositional logic says that a proposition is absorbed; This means that its assignment is irrelevant for the evaluation of the overall formula if it is linked conjunctively and disjunctively with another statement, the order of the links being irrelevant.

The truth value development of proposition forms, which directly connect the statements a and b consecutively conjunctive and disjunctive or disjunctive and conjunctive, corresponds to the truth value of a.

${\displaystyle a\lor (a\land b)=a}$ and ${\displaystyle a\land (a\lor b)=a}$

In words: The conjunction can only be true if a is true. But then every disjunction with a is also true, independent of b. Conversely, the disjunction can only be false if a is false. Thus the conjunction is also wrong and thus the entire expression is independent of b. Analogous with swapped junctions. The proof takes place via truth tables: ${\displaystyle (a\land b)}$ ${\displaystyle (a\land b)}$

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle (a\land b)}$	${\displaystyle (a\lor b)}$	${\displaystyle a\lor (a\land b)=a}$	${\displaystyle a\land (a\lor b)=a}$
0	0	0	0	0	0
0	1	0	1	0	0
1	0	0	1	1	1
1	1	1	1	1	1

The set- theoretical formulation is also clear :

${\displaystyle A\cup \left(A\cap B\right)=A}$ and ${\displaystyle A\cap \left(A\cup B\right)=A}$

The set A combined with its intersection with B is the set A. Similarly, the intersection of the set A with its union with B is again the set A.

Predicate logic

Since the law of absorption does not contain any quantifiers , the propositional and predicate logic formulations correspond . Russell and Whitehead put it in their Principia mathematica as follows:

${\displaystyle (P\to Q)\leftrightarrow (P\to (P\land Q))}$,

where and are predicates of a formal system . The absorption law can be deemed sequence (that evidence) of the sequent calculus be formulated: ${\displaystyle P}$ ${\displaystyle Q}$

${\displaystyle P\to Q\vdash P\to (P\land Q)}$   or in alternative notation: ${\displaystyle {\frac {\Gamma \,\varphi \to \psi }{\varphi \to (\varphi \land \psi )}}}$

${\displaystyle {\begin{alignedat}{3}1.&\quad &\Gamma \,\varphi \rightarrow \psi &\quad &({\text{Prämisse}})\\2.&\quad &\Gamma \,\neg \varphi \lor \psi &\quad &({\text{Umformung}})\\3.&\quad &\Gamma \,\neg \varphi \lor \varphi &\quad &({\text{Satz vom ausgeschlossenen Dritten}})\\4.&\quad &\Gamma \,(\neg \varphi \lor \varphi )\land (\neg \varphi \lor \psi )&\quad &({\text{Konjunktion 2. und 3.}})\\5.&\quad &\Gamma \,\neg \varphi \lor (\varphi \land \psi )&\quad &({\text{Distributivgesetz}})\\6.&\quad &\Gamma \,\varphi \rightarrow (\varphi \land \psi )&\quad &({\text{Umformung}})\\\end{alignedat}}}$

Web links

• s. T5.3 Gate implementation of the law of absorption
• Propositional Logic Exercise Sheet

Individual evidence

1. ↑ Important equivalences (Theorem 4.7)
2. ↑ Overview at formel-sammlung.de