Conversion from PL to CNF

0

$begingroup$

I am trying to convert some formulas into CNF even if I understood both concepts and rules of it I cannot always get a solution. For example I have this statement to convert: $(pLeftrightarrow p)Rightarrow (neg p wedge r)$. Applying the rules I get this formula (that I know it is right since the solution for both formulas is the same according to Wolfram) $(p wedge neg q) vee (q wedge neg p) vee (neg p wedge r)$. From this position I know I should apply some distributive law to "move the OR inside and the AND outside" but I really don't get how. I already know the result that is $(neg p vee neg q) wedge (p vee q vee r)$.

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Feb 1 at 13:50

whiskeyo

1368

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

$endgroup$

add a comment | 

0

$begingroup$

I am trying to convert some formulas into CNF even if I understood both concepts and rules of it I cannot always get a solution. For example I have this statement to convert: $(pLeftrightarrow p)Rightarrow (neg p wedge r)$. Applying the rules I get this formula (that I know it is right since the solution for both formulas is the same according to Wolfram) $(p wedge neg q) vee (q wedge neg p) vee (neg p wedge r)$. From this position I know I should apply some distributive law to "move the OR inside and the AND outside" but I really don't get how. I already know the result that is $(neg p vee neg q) wedge (p vee q vee r)$.

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Feb 1 at 13:50

whiskeyo

1368

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

$endgroup$

add a comment | 

0

0

0

$begingroup$

I am trying to convert some formulas into CNF even if I understood both concepts and rules of it I cannot always get a solution. For example I have this statement to convert: $(pLeftrightarrow p)Rightarrow (neg p wedge r)$. Applying the rules I get this formula (that I know it is right since the solution for both formulas is the same according to Wolfram) $(p wedge neg q) vee (q wedge neg p) vee (neg p wedge r)$. From this position I know I should apply some distributive law to "move the OR inside and the AND outside" but I really don't get how. I already know the result that is $(neg p vee neg q) wedge (p vee q vee r)$.

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Feb 1 at 13:50

whiskeyo

1368

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

$endgroup$

I am trying to convert some formulas into CNF even if I understood both concepts and rules of it I cannot always get a solution. For example I have this statement to convert: $(pLeftrightarrow p)Rightarrow (neg p wedge r)$. Applying the rules I get this formula (that I know it is right since the solution for both formulas is the same according to Wolfram) $(p wedge neg q) vee (q wedge neg p) vee (neg p wedge r)$. From this position I know I should apply some distributive law to "move the OR inside and the AND outside" but I really don't get how. I already know the result that is $(neg p vee neg q) wedge (p vee q vee r)$.

logic propositional-calculus conjunctive-normal-form

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Feb 1 at 13:50

whiskeyo

1368

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

share|cite|improve this question

edited Feb 1 at 13:50

whiskeyo

1368

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

share|cite|improve this question

share|cite|improve this question

edited Feb 1 at 13:50

whiskeyo

1368

edited Feb 1 at 13:50

whiskeyo

1368

edited Feb 1 at 13:50

whiskeyo

1368

1368

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

asked Jan 30 at 15:31

Craig MontevecchiCraig Montevecchi

447

447

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

1

$begingroup$

There are several options how you could apply distributive law. Here's one. The version I'm using says that $(A land B) lor C equiv (A lor C) land (B lor C)$. Let's apply this to your formula $$(p land lnot q) lor (q land lnot p) lor (lnot p land r)$$ Here you can set $A := p$, $B := lnot q$ and $C := (q land lnot p) lor (lnot p land r)$. Then distributivity yields $$(p lor (q land lnot p) lor (lnot p land r)) land (lnot q lor (q land lnot p) lor (lnot p land r))$$

We need to apply distributivity a few times more. Consider the left side first. $$(p lor (q land lnot p) lor (lnot p land r)) equiv [(p lor q) land (p lor lnot p)] lor (lnot p land r) equiv (p lor q) lor (lnot p land r) \ equiv (p lor q lor lnot p) land (p lor q lor r) equiv p vee q vee r$$

Here I used the law that $A wedge top equiv A$ twice, removing the tautologous $(p vee lnot p)$ and $(p vee q vee lnot p)$.

Let's turn to the right-hand side. By similar reductions as in the first step, you get $$(lnot q lor (q land lnot p) lor (lnot p land r)) equiv (lnot q lor lnot p lor lnot p) wedge (lnot q lor lnot p lor r)$$

By the law that $(A lor B) wedge (A lor B lor C) equiv A lor B$, this is equivalent to $$lnot q lor lnot p$$

Thus, combining the results we get $(p vee q vee r) wedge (lnot q lor lnot p)$, as desired.

share|cite|improve this answer

edited Feb 1 at 13:05

answered Feb 1 at 10:08

konstkonst

1113

$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
});


}
});

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.

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093676%2fconversion-from-pl-to-cnf%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

1

$begingroup$

There are several options how you could apply distributive law. Here's one. The version I'm using says that $(A land B) lor C equiv (A lor C) land (B lor C)$. Let's apply this to your formula $$(p land lnot q) lor (q land lnot p) lor (lnot p land r)$$ Here you can set $A := p$, $B := lnot q$ and $C := (q land lnot p) lor (lnot p land r)$. Then distributivity yields $$(p lor (q land lnot p) lor (lnot p land r)) land (lnot q lor (q land lnot p) lor (lnot p land r))$$

We need to apply distributivity a few times more. Consider the left side first. $$(p lor (q land lnot p) lor (lnot p land r)) equiv [(p lor q) land (p lor lnot p)] lor (lnot p land r) equiv (p lor q) lor (lnot p land r) \ equiv (p lor q lor lnot p) land (p lor q lor r) equiv p vee q vee r$$

Here I used the law that $A wedge top equiv A$ twice, removing the tautologous $(p vee lnot p)$ and $(p vee q vee lnot p)$.

Let's turn to the right-hand side. By similar reductions as in the first step, you get $$(lnot q lor (q land lnot p) lor (lnot p land r)) equiv (lnot q lor lnot p lor lnot p) wedge (lnot q lor lnot p lor r)$$

By the law that $(A lor B) wedge (A lor B lor C) equiv A lor B$, this is equivalent to $$lnot q lor lnot p$$

Thus, combining the results we get $(p vee q vee r) wedge (lnot q lor lnot p)$, as desired.

share|cite|improve this answer

edited Feb 1 at 13:05

answered Feb 1 at 10:08

konstkonst

1113

$endgroup$

add a comment | 

1

$begingroup$

There are several options how you could apply distributive law. Here's one. The version I'm using says that $(A land B) lor C equiv (A lor C) land (B lor C)$. Let's apply this to your formula $$(p land lnot q) lor (q land lnot p) lor (lnot p land r)$$ Here you can set $A := p$, $B := lnot q$ and $C := (q land lnot p) lor (lnot p land r)$. Then distributivity yields $$(p lor (q land lnot p) lor (lnot p land r)) land (lnot q lor (q land lnot p) lor (lnot p land r))$$

We need to apply distributivity a few times more. Consider the left side first. $$(p lor (q land lnot p) lor (lnot p land r)) equiv [(p lor q) land (p lor lnot p)] lor (lnot p land r) equiv (p lor q) lor (lnot p land r) \ equiv (p lor q lor lnot p) land (p lor q lor r) equiv p vee q vee r$$

Here I used the law that $A wedge top equiv A$ twice, removing the tautologous $(p vee lnot p)$ and $(p vee q vee lnot p)$.

Let's turn to the right-hand side. By similar reductions as in the first step, you get $$(lnot q lor (q land lnot p) lor (lnot p land r)) equiv (lnot q lor lnot p lor lnot p) wedge (lnot q lor lnot p lor r)$$

By the law that $(A lor B) wedge (A lor B lor C) equiv A lor B$, this is equivalent to $$lnot q lor lnot p$$

Thus, combining the results we get $(p vee q vee r) wedge (lnot q lor lnot p)$, as desired.

share|cite|improve this answer

edited Feb 1 at 13:05

answered Feb 1 at 10:08

konstkonst

1113

$endgroup$

add a comment | 

1

1

1

$begingroup$

There are several options how you could apply distributive law. Here's one. The version I'm using says that $(A land B) lor C equiv (A lor C) land (B lor C)$. Let's apply this to your formula $$(p land lnot q) lor (q land lnot p) lor (lnot p land r)$$ Here you can set $A := p$, $B := lnot q$ and $C := (q land lnot p) lor (lnot p land r)$. Then distributivity yields $$(p lor (q land lnot p) lor (lnot p land r)) land (lnot q lor (q land lnot p) lor (lnot p land r))$$

We need to apply distributivity a few times more. Consider the left side first. $$(p lor (q land lnot p) lor (lnot p land r)) equiv [(p lor q) land (p lor lnot p)] lor (lnot p land r) equiv (p lor q) lor (lnot p land r) \ equiv (p lor q lor lnot p) land (p lor q lor r) equiv p vee q vee r$$

Here I used the law that $A wedge top equiv A$ twice, removing the tautologous $(p vee lnot p)$ and $(p vee q vee lnot p)$.

Let's turn to the right-hand side. By similar reductions as in the first step, you get $$(lnot q lor (q land lnot p) lor (lnot p land r)) equiv (lnot q lor lnot p lor lnot p) wedge (lnot q lor lnot p lor r)$$

By the law that $(A lor B) wedge (A lor B lor C) equiv A lor B$, this is equivalent to $$lnot q lor lnot p$$

Thus, combining the results we get $(p vee q vee r) wedge (lnot q lor lnot p)$, as desired.

share|cite|improve this answer

edited Feb 1 at 13:05

answered Feb 1 at 10:08

konstkonst

1113

$endgroup$

There are several options how you could apply distributive law. Here's one. The version I'm using says that $(A land B) lor C equiv (A lor C) land (B lor C)$. Let's apply this to your formula $$(p land lnot q) lor (q land lnot p) lor (lnot p land r)$$ Here you can set $A := p$, $B := lnot q$ and $C := (q land lnot p) lor (lnot p land r)$. Then distributivity yields $$(p lor (q land lnot p) lor (lnot p land r)) land (lnot q lor (q land lnot p) lor (lnot p land r))$$

We need to apply distributivity a few times more. Consider the left side first. $$(p lor (q land lnot p) lor (lnot p land r)) equiv [(p lor q) land (p lor lnot p)] lor (lnot p land r) equiv (p lor q) lor (lnot p land r) \ equiv (p lor q lor lnot p) land (p lor q lor r) equiv p vee q vee r$$

Here I used the law that $A wedge top equiv A$ twice, removing the tautologous $(p vee lnot p)$ and $(p vee q vee lnot p)$.

Let's turn to the right-hand side. By similar reductions as in the first step, you get $$(lnot q lor (q land lnot p) lor (lnot p land r)) equiv (lnot q lor lnot p lor lnot p) wedge (lnot q lor lnot p lor r)$$

By the law that $(A lor B) wedge (A lor B lor C) equiv A lor B$, this is equivalent to $$lnot q lor lnot p$$

Thus, combining the results we get $(p vee q vee r) wedge (lnot q lor lnot p)$, as desired.

share|cite|improve this answer

edited Feb 1 at 13:05

answered Feb 1 at 10:08

konstkonst

1113

share|cite|improve this answer

share|cite|improve this answer

edited Feb 1 at 13:05

edited Feb 1 at 13:05

edited Feb 1 at 13:05

answered Feb 1 at 10:08

konstkonst

1113

answered Feb 1 at 10:08

konstkonst

1113

answered Feb 1 at 10:08

konstkonst

1113

1113

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.

draft saved

draft discarded

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.

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093676%2fconversion-from-pl-to-cnf%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

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

Name

Email

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

Name

Email

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

Name

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

This page is only for reference, If you need detailed information, please check here