Mixing
What is the “official” name for these boolean algebra rules?
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.
logic propositional-calculus boolean-algebra
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
add a comment |
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.
logic propositional-calculus boolean-algebra
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
It is not true for arbitrary expressions, e.g. $P+(Pcdot Q) ne P+(0cdot Q) $.
– Berci
Nov 16 '18 at 0:24
@Berci If $+$ is disjunction and $cdot$ is conjunction, both sides simplify to $P$.
– Fabio Somenzi
Nov 16 '18 at 0:46
1
I've never seen a name given to this pair of identities, but "generalized absorption" seems fitting. As for an elementary proof, observe that for a valuation of the variables that makes $P$ true, both sides evaluate to 1, while for a valuation that makes $P$ false, both sides evaluate to $(...0...)$.
– Fabio Somenzi
Nov 16 '18 at 4:35
add a comment |
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.
logic propositional-calculus boolean-algebra
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
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.
logic propositional-calculus boolean-algebra
logic propositional-calculus boolean-algebra
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
edited Nov 15 '18 at 23:44
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
asked Nov 15 '18 at 23:36
Marnix Klooster
4,20322146
4,20322146
It is not true for arbitrary expressions, e.g. $P+(Pcdot Q) ne P+(0cdot Q) $.
– Berci
Nov 16 '18 at 0:24
@Berci If $+$ is disjunction and $cdot$ is conjunction, both sides simplify to $P$.
– Fabio Somenzi
Nov 16 '18 at 0:46
1
I've never seen a name given to this pair of identities, but "generalized absorption" seems fitting. As for an elementary proof, observe that for a valuation of the variables that makes $P$ true, both sides evaluate to 1, while for a valuation that makes $P$ false, both sides evaluate to $(...0...)$.
– Fabio Somenzi
Nov 16 '18 at 4:35
add a comment |
It is not true for arbitrary expressions, e.g. $P+(Pcdot Q) ne P+(0cdot Q) $.
– Berci
Nov 16 '18 at 0:24
@Berci If $+$ is disjunction and $cdot$ is conjunction, both sides simplify to $P$.
– Fabio Somenzi
Nov 16 '18 at 0:46
1
I've never seen a name given to this pair of identities, but "generalized absorption" seems fitting. As for an elementary proof, observe that for a valuation of the variables that makes $P$ true, both sides evaluate to 1, while for a valuation that makes $P$ false, both sides evaluate to $(...0...)$.
– Fabio Somenzi
Nov 16 '18 at 4:35
It is not true for arbitrary expressions, e.g. $P+(Pcdot Q) ne P+(0cdot Q) $.
– Berci
Nov 16 '18 at 0:24
It is not true for arbitrary expressions, e.g. $P+(Pcdot Q) ne P+(0cdot Q) $.
– Berci
Nov 16 '18 at 0:24
@Berci If $+$ is disjunction and $cdot$ is conjunction, both sides simplify to $P$.
– Fabio Somenzi
Nov 16 '18 at 0:46
@Berci If $+$ is disjunction and $cdot$ is conjunction, both sides simplify to $P$.
– Fabio Somenzi
Nov 16 '18 at 0:46
1
1
I've never seen a name given to this pair of identities, but "generalized absorption" seems fitting. As for an elementary proof, observe that for a valuation of the variables that makes $P$ true, both sides evaluate to 1, while for a valuation that makes $P$ false, both sides evaluate to $(...0...)$.
– Fabio Somenzi
Nov 16 '18 at 4:35
I've never seen a name given to this pair of identities, but "generalized absorption" seems fitting. As for an elementary proof, observe that for a valuation of the variables that makes $P$ true, both sides evaluate to 1, while for a valuation that makes $P$ false, both sides evaluate to $(...0...)$.
– Fabio Somenzi
Nov 16 '18 at 4:35
add a comment |
1 Answer
1
active
oldest
votes
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:
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:
The enclosed figure is called a 'cut'. Putting a cut around some expression negates that expression. So, for example:
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$:
And here is an implication $P rightarrow Q$:
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:
is the $0$ (or $bot$). This is called the 'empty cut'.
OK, now it gets interesting. Existential Graphs has 4 inference rules defined:
- 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:
and:
- 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:
to:
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'.
- 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:
- 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$:
Now, the $P$ inside the cut is at a 'nested' level with regard to the outside $P$ , so we can 'deiterate' it:
Now we can use Double Cut:
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):
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:
(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:
(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:
So, if we now do a Double Cut on the inside $P$:
Then we can Deiterate:
.. 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!
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000498%2fwhat-is-the-official-name-for-these-boolean-algebra-rules%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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:
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:
The enclosed figure is called a 'cut'. Putting a cut around some expression negates that expression. So, for example:
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$:
And here is an implication $P rightarrow Q$:
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:
is the $0$ (or $bot$). This is called the 'empty cut'.
OK, now it gets interesting. Existential Graphs has 4 inference rules defined:
- 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:
and:
- 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:
to:
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'.
- 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:
- 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$:
Now, the $P$ inside the cut is at a 'nested' level with regard to the outside $P$ , so we can 'deiterate' it:
Now we can use Double Cut:
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):
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:
(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:
(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:
So, if we now do a Double Cut on the inside $P$:
Then we can Deiterate:
.. 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!
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
add a comment |
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:
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:
The enclosed figure is called a 'cut'. Putting a cut around some expression negates that expression. So, for example:
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$:
And here is an implication $P rightarrow Q$:
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:
is the $0$ (or $bot$). This is called the 'empty cut'.
OK, now it gets interesting. Existential Graphs has 4 inference rules defined:
- 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:
and:
- 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:
to:
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'.
- 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:
- 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$:
Now, the $P$ inside the cut is at a 'nested' level with regard to the outside $P$ , so we can 'deiterate' it:
Now we can use Double Cut:
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):
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:
(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:
(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:
So, if we now do a Double Cut on the inside $P$:
Then we can Deiterate:
.. 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!
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
add a comment |
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:
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:
The enclosed figure is called a 'cut'. Putting a cut around some expression negates that expression. So, for example:
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$:
And here is an implication $P rightarrow Q$:
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:
is the $0$ (or $bot$). This is called the 'empty cut'.
OK, now it gets interesting. Existential Graphs has 4 inference rules defined:
- 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:
and:
- 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:
to:
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'.
- 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:
- 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$:
Now, the $P$ inside the cut is at a 'nested' level with regard to the outside $P$ , so we can 'deiterate' it:
Now we can use Double Cut:
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):
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:
(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:
(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:
So, if we now do a Double Cut on the inside $P$:
Then we can Deiterate:
.. 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!
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
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:
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:
The enclosed figure is called a 'cut'. Putting a cut around some expression negates that expression. So, for example:
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$:
And here is an implication $P rightarrow Q$:
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:
is the $0$ (or $bot$). This is called the 'empty cut'.
OK, now it gets interesting. Existential Graphs has 4 inference rules defined:
- 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:
and:
- 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:
to:
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'.
- 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:
- 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$:
Now, the $P$ inside the cut is at a 'nested' level with regard to the outside $P$ , so we can 'deiterate' it:
Now we can use Double Cut:
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):
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:
(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:
(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:
So, if we now do a Double Cut on the inside $P$:
Then we can Deiterate:
.. 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!
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
edited Nov 20 '18 at 19:14
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
answered Nov 20 '18 at 19:05
Bram28
60.3k44590
60.3k44590
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000498%2fwhat-is-the-official-name-for-these-boolean-algebra-rules%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
It is not true for arbitrary expressions, e.g. $P+(Pcdot Q) ne P+(0cdot Q) $.
– Berci
Nov 16 '18 at 0:24
@Berci If $+$ is disjunction and $cdot$ is conjunction, both sides simplify to $P$.
– Fabio Somenzi
Nov 16 '18 at 0:46
1
I've never seen a name given to this pair of identities, but "generalized absorption" seems fitting. As for an elementary proof, observe that for a valuation of the variables that makes $P$ true, both sides evaluate to 1, while for a valuation that makes $P$ false, both sides evaluate to $(...0...)$.
– Fabio Somenzi
Nov 16 '18 at 4:35