Is the minimal conjunctive normal form for positive formula unique? If so, how do you calculate it?
$begingroup$
I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms.
$$A$$
$$A land (A lor B)$$
The minimal example is $A$.
Does every positive boolean formula have a unique minimal conjunctive normal form? If so, how does one calculate it?
(I conjecture that you can do so by finding a positive conjuctive normal form, and then pruning any terms that are implied by other terms (for example, $A lor B$ is implied by the previous term $A$, so it gives no additional information in a conjuction). I don't know how to prove that this is correct, if it is so. (It is also not very efficient.))
logic boolean-algebra conjunctive-normal-form
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
$endgroup$
add a comment |
$begingroup$
I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms.
$$A$$
$$A land (A lor B)$$
The minimal example is $A$.
Does every positive boolean formula have a unique minimal conjunctive normal form? If so, how does one calculate it?
(I conjecture that you can do so by finding a positive conjuctive normal form, and then pruning any terms that are implied by other terms (for example, $A lor B$ is implied by the previous term $A$, so it gives no additional information in a conjuction). I don't know how to prove that this is correct, if it is so. (It is also not very efficient.))
logic boolean-algebra conjunctive-normal-form
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
$endgroup$
$begingroup$
Did I answer your question?
$endgroup$
– Bram28
Oct 25 '16 at 16:55
add a comment |
$begingroup$
I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms.
$$A$$
$$A land (A lor B)$$
The minimal example is $A$.
Does every positive boolean formula have a unique minimal conjunctive normal form? If so, how does one calculate it?
(I conjecture that you can do so by finding a positive conjuctive normal form, and then pruning any terms that are implied by other terms (for example, $A lor B$ is implied by the previous term $A$, so it gives no additional information in a conjuction). I don't know how to prove that this is correct, if it is so. (It is also not very efficient.))
logic boolean-algebra conjunctive-normal-form
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
$endgroup$
I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms.
$$A$$
$$A land (A lor B)$$
The minimal example is $A$.
Does every positive boolean formula have a unique minimal conjunctive normal form? If so, how does one calculate it?
(I conjecture that you can do so by finding a positive conjuctive normal form, and then pruning any terms that are implied by other terms (for example, $A lor B$ is implied by the previous term $A$, so it gives no additional information in a conjuction). I don't know how to prove that this is correct, if it is so. (It is also not very efficient.))
logic boolean-algebra conjunctive-normal-form
logic boolean-algebra conjunctive-normal-form
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
asked Oct 10 '16 at 19:14
PyRulezPyRulez
5,00722471
5,00722471
$begingroup$
Did I answer your question?
$endgroup$
– Bram28
Oct 25 '16 at 16:55
add a comment |
$begingroup$
Did I answer your question?
$endgroup$
– Bram28
Oct 25 '16 at 16:55
$begingroup$
Did I answer your question?
$endgroup$
– Bram28
Oct 25 '16 at 16:55
$begingroup$
Did I answer your question?
$endgroup$
– Bram28
Oct 25 '16 at 16:55
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This showed up on the Wikipedia Math Help Desk, see 1. It looks like the minimal expression is unique for positive expressions.
Proof: Let S and T be two equivalent positive expressions in CNF which are both minimal. Let {Si} be the set of clauses in S and {Tj} be the set of clauses in T. Each Si and Tj, in turn, corresponds to a subset of a set of Boolean variables {xk}. Since S is minimal, no Si is contained in Sj for j≠i, and similarly for T. For each assignment a:xk → {T, F}, define Z(a) to be the set of variables for which a is F, i.e. Z(a) is the compliment of the support of a. A clause Si evaluates to F iff Si⊆Z(a) and the expression S evaluates to F iff Si⊆Z(a) for some i. A similar statements holds for T. Fix i and define the truth assignment ai(xk) to be T when xk is not in Si, in other words ai is the truth assignment so that Z(ai) = Si. The clause Si evaluates to F under this assignment, so S evaluates to F. But S and T are equivalent so T evaluates to F. Therefore Tj⊆Z(ai)= Si for some j. Similarly, for each j there is k so that Sk ⊆ Tj. (I think another way of saying this is that S and T are refinements of each other.) If Si is an element of S, then there is Tj in T so that Tj ⊆ Si, and there is an Sk so that Sk ⊆ Tj. Then Sk ⊆ Si and so, since ''S'' is minimal, i=k. We then have Si ⊆ Tj ⊆ Si, Si = Tj ∈ T. So S ⊆ T and similarly T ⊆ S, therefore S = T.
Another (probably better) approach is to characterize the clauses that appear.
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
$endgroup$
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%2f1962707%2fis-the-minimal-conjunctive-normal-form-for-positive-formula-unique-if-so-how-d%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
$begingroup$
This showed up on the Wikipedia Math Help Desk, see 1. It looks like the minimal expression is unique for positive expressions.
Proof: Let S and T be two equivalent positive expressions in CNF which are both minimal. Let {Si} be the set of clauses in S and {Tj} be the set of clauses in T. Each Si and Tj, in turn, corresponds to a subset of a set of Boolean variables {xk}. Since S is minimal, no Si is contained in Sj for j≠i, and similarly for T. For each assignment a:xk → {T, F}, define Z(a) to be the set of variables for which a is F, i.e. Z(a) is the compliment of the support of a. A clause Si evaluates to F iff Si⊆Z(a) and the expression S evaluates to F iff Si⊆Z(a) for some i. A similar statements holds for T. Fix i and define the truth assignment ai(xk) to be T when xk is not in Si, in other words ai is the truth assignment so that Z(ai) = Si. The clause Si evaluates to F under this assignment, so S evaluates to F. But S and T are equivalent so T evaluates to F. Therefore Tj⊆Z(ai)= Si for some j. Similarly, for each j there is k so that Sk ⊆ Tj. (I think another way of saying this is that S and T are refinements of each other.) If Si is an element of S, then there is Tj in T so that Tj ⊆ Si, and there is an Sk so that Sk ⊆ Tj. Then Sk ⊆ Si and so, since ''S'' is minimal, i=k. We then have Si ⊆ Tj ⊆ Si, Si = Tj ∈ T. So S ⊆ T and similarly T ⊆ S, therefore S = T.
Another (probably better) approach is to characterize the clauses that appear.
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
$endgroup$
add a comment |
$begingroup$
This showed up on the Wikipedia Math Help Desk, see 1. It looks like the minimal expression is unique for positive expressions.
Proof: Let S and T be two equivalent positive expressions in CNF which are both minimal. Let {Si} be the set of clauses in S and {Tj} be the set of clauses in T. Each Si and Tj, in turn, corresponds to a subset of a set of Boolean variables {xk}. Since S is minimal, no Si is contained in Sj for j≠i, and similarly for T. For each assignment a:xk → {T, F}, define Z(a) to be the set of variables for which a is F, i.e. Z(a) is the compliment of the support of a. A clause Si evaluates to F iff Si⊆Z(a) and the expression S evaluates to F iff Si⊆Z(a) for some i. A similar statements holds for T. Fix i and define the truth assignment ai(xk) to be T when xk is not in Si, in other words ai is the truth assignment so that Z(ai) = Si. The clause Si evaluates to F under this assignment, so S evaluates to F. But S and T are equivalent so T evaluates to F. Therefore Tj⊆Z(ai)= Si for some j. Similarly, for each j there is k so that Sk ⊆ Tj. (I think another way of saying this is that S and T are refinements of each other.) If Si is an element of S, then there is Tj in T so that Tj ⊆ Si, and there is an Sk so that Sk ⊆ Tj. Then Sk ⊆ Si and so, since ''S'' is minimal, i=k. We then have Si ⊆ Tj ⊆ Si, Si = Tj ∈ T. So S ⊆ T and similarly T ⊆ S, therefore S = T.
Another (probably better) approach is to characterize the clauses that appear.
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
$endgroup$
add a comment |
$begingroup$
This showed up on the Wikipedia Math Help Desk, see 1. It looks like the minimal expression is unique for positive expressions.
Proof: Let S and T be two equivalent positive expressions in CNF which are both minimal. Let {Si} be the set of clauses in S and {Tj} be the set of clauses in T. Each Si and Tj, in turn, corresponds to a subset of a set of Boolean variables {xk}. Since S is minimal, no Si is contained in Sj for j≠i, and similarly for T. For each assignment a:xk → {T, F}, define Z(a) to be the set of variables for which a is F, i.e. Z(a) is the compliment of the support of a. A clause Si evaluates to F iff Si⊆Z(a) and the expression S evaluates to F iff Si⊆Z(a) for some i. A similar statements holds for T. Fix i and define the truth assignment ai(xk) to be T when xk is not in Si, in other words ai is the truth assignment so that Z(ai) = Si. The clause Si evaluates to F under this assignment, so S evaluates to F. But S and T are equivalent so T evaluates to F. Therefore Tj⊆Z(ai)= Si for some j. Similarly, for each j there is k so that Sk ⊆ Tj. (I think another way of saying this is that S and T are refinements of each other.) If Si is an element of S, then there is Tj in T so that Tj ⊆ Si, and there is an Sk so that Sk ⊆ Tj. Then Sk ⊆ Si and so, since ''S'' is minimal, i=k. We then have Si ⊆ Tj ⊆ Si, Si = Tj ∈ T. So S ⊆ T and similarly T ⊆ S, therefore S = T.
Another (probably better) approach is to characterize the clauses that appear.
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
$endgroup$
This showed up on the Wikipedia Math Help Desk, see 1. It looks like the minimal expression is unique for positive expressions.
Proof: Let S and T be two equivalent positive expressions in CNF which are both minimal. Let {Si} be the set of clauses in S and {Tj} be the set of clauses in T. Each Si and Tj, in turn, corresponds to a subset of a set of Boolean variables {xk}. Since S is minimal, no Si is contained in Sj for j≠i, and similarly for T. For each assignment a:xk → {T, F}, define Z(a) to be the set of variables for which a is F, i.e. Z(a) is the compliment of the support of a. A clause Si evaluates to F iff Si⊆Z(a) and the expression S evaluates to F iff Si⊆Z(a) for some i. A similar statements holds for T. Fix i and define the truth assignment ai(xk) to be T when xk is not in Si, in other words ai is the truth assignment so that Z(ai) = Si. The clause Si evaluates to F under this assignment, so S evaluates to F. But S and T are equivalent so T evaluates to F. Therefore Tj⊆Z(ai)= Si for some j. Similarly, for each j there is k so that Sk ⊆ Tj. (I think another way of saying this is that S and T are refinements of each other.) If Si is an element of S, then there is Tj in T so that Tj ⊆ Si, and there is an Sk so that Sk ⊆ Tj. Then Sk ⊆ Si and so, since ''S'' is minimal, i=k. We then have Si ⊆ Tj ⊆ Si, Si = Tj ∈ T. So S ⊆ T and similarly T ⊆ S, therefore S = T.
Another (probably better) approach is to characterize the clauses that appear.
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
answered Dec 14 '18 at 19:43
RDBuryRDBury
711
711
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.
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%2f1962707%2fis-the-minimal-conjunctive-normal-form-for-positive-formula-unique-if-so-how-d%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
$begingroup$
Did I answer your question?
$endgroup$
– Bram28
Oct 25 '16 at 16:55