Finding a logically equivalent conjunctive normal form.

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

Here is the definition of a conjunctive normal form:

A conjunctive normal form is a conjunction of one or more conjuncts that are disjunctions of one or more literals (letters). For example, $A land (B lor A) land (lnot B lor A)$ is a conjunctive normal form.

I need to find a logically equivalent conjunctive normal form of the expression $lnot (A to B) lor (lnot A land C)$. The answer in the textbook is $(A lor C) land (lnot B lor lnot A) land (lnot B lor C)$. I don't understand how they got this answer.

Can another answer be $Aland (lnot Blor lnot A)land C$?

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Aug 3 at 6:18

Taroccoesbrocco

3,31941330

asked Aug 3 at 5:29

numericalorange

1,147110

add a comment | 

up vote
2
down vote

favorite

Here is the definition of a conjunctive normal form:

A conjunctive normal form is a conjunction of one or more conjuncts that are disjunctions of one or more literals (letters). For example, $A land (B lor A) land (lnot B lor A)$ is a conjunctive normal form.

I need to find a logically equivalent conjunctive normal form of the expression $lnot (A to B) lor (lnot A land C)$. The answer in the textbook is $(A lor C) land (lnot B lor lnot A) land (lnot B lor C)$. I don't understand how they got this answer.

Can another answer be $Aland (lnot Blor lnot A)land C$?

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Aug 3 at 6:18

Taroccoesbrocco

3,31941330

asked Aug 3 at 5:29

numericalorange

1,147110

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

Here is the definition of a conjunctive normal form:

A conjunctive normal form is a conjunction of one or more conjuncts that are disjunctions of one or more literals (letters). For example, $A land (B lor A) land (lnot B lor A)$ is a conjunctive normal form.

I need to find a logically equivalent conjunctive normal form of the expression $lnot (A to B) lor (lnot A land C)$. The answer in the textbook is $(A lor C) land (lnot B lor lnot A) land (lnot B lor C)$. I don't understand how they got this answer.

Can another answer be $Aland (lnot Blor lnot A)land C$?

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Aug 3 at 6:18

Taroccoesbrocco

3,31941330

asked Aug 3 at 5:29

numericalorange

1,147110

Here is the definition of a conjunctive normal form:

A conjunctive normal form is a conjunction of one or more conjuncts that are disjunctions of one or more literals (letters). For example, $A land (B lor A) land (lnot B lor A)$ is a conjunctive normal form.

I need to find a logically equivalent conjunctive normal form of the expression $lnot (A to B) lor (lnot A land C)$. The answer in the textbook is $(A lor C) land (lnot B lor lnot A) land (lnot B lor C)$. I don't understand how they got this answer.

Can another answer be $Aland (lnot Blor lnot A)land C$?

logic propositional-calculus conjunctive-normal-form

share|cite|improve this question

edited Aug 3 at 6:18

Taroccoesbrocco

3,31941330

asked Aug 3 at 5:29

numericalorange

1,147110

share|cite|improve this question

share|cite|improve this question

edited Aug 3 at 6:18

Taroccoesbrocco

3,31941330

edited Aug 3 at 6:18

Taroccoesbrocco

3,31941330

edited Aug 3 at 6:18

Taroccoesbrocco

3,31941330

3,31941330

asked Aug 3 at 5:29

numericalorange

1,147110

asked Aug 3 at 5:29

numericalorange

1,147110

asked Aug 3 at 5:29

numericalorange

1,147110

1,147110

add a comment | 

add a comment | 

3 Answers
3

active

oldest

votes

up vote
1
down vote



accepted

Conditional Negation, Distribution, Complementation, and Identity.

$beginalign &neg (Ato B)vee(neg Awedge C)\equiv ~& (Awedgeneg B)vee(neg Awedge C)\equiv~& (Aveeneg A)wedge(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)\equiv~& qquadqquadquad(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)endalign$

I am not sure how you figured this would be equivalent to $Awedge(neg Bveeneg A)wedge C$, because it is not.

share|cite|improve this answer

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there good reason to use $equiv$ and not $=$? I am the only answerer who elected to use $=$...
  – Mason
  Aug 3 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It indicates that the expressions are equivalent rather than identical. They have the same truth evaluation, but are not quite saying the same thing. A subtle distinction to be sure.
  – Graham Kemp
  Aug 3 at 6:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Not sure Its a distinction I am comprehending. But maybe this will help: math.stackexchange.com/questions/1058596/…
  – Mason
  Aug 3 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $3+4=7$ is equivalent to $e^pi i =-1$ in that both statements evaluate to true but we wouldn't say that the statements are identical because it would have Euler turning in his grave.
  – Mason
  Aug 3 at 7:05
  

  
  
  
  

add a comment | 

up vote
1
down vote

$$
beginalign
&neg (Ato B)vee (neg Awedge C)\
&= neg(B vee neg A )vee (neg Awedge C)\
&=(neg B vee A )vee (neg Awedge C)\
&=((neg B wedge A) vee neg A)wedge ((neg B wedge A) vee C)\
&=(neg B vee neg A) wedge (A vee neg A)wedge (neg B vee C) wedge (A vee C)\
&=(neg B vee neg A) wedge (T)wedge (neg B vee C) wedge (A vee C)\
endalign $$

How can we justify these equalities:

1) Definition of $rightarrow$. $xrightarrow y = (yvee neg x)$

2) Distribute $neg$. We can find that $neg(x vee y)=neg x wedge neg y$

3) Demorgan's law. $x wedge (yvee z)=(xvee y) wedge (xvee z) $

4) More application of Demorgan's law.

5) Tautology $x vee neg x =T$

Then you arrive at your conclusion after we remove this Tautology and rearrange.

You can verify that $(A,B,C)= (T,T,F)$ satisfies the expression above.
but it doesn't satisfy $Awedge (neg B veeneg A) wedge C$. This would be one way to assure yourself that these expressions aren't equal.

share|cite|improve this answer

edited Aug 3 at 6:03

answered Aug 3 at 5:44

Mason

1,1271223

add a comment | 

up vote
1
down vote

The formula $A land (lnot B lor lnot A)land C$ is not logically equivalent to the formula $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$: take for instance the truth assignment $v$ such that $v(A) = top$ and $v(B) = v(C) = bot$, then $A land (lnot B lor lnot A)land C$ is false for $v$ but $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is true for $v$. Therefore, it is impossible that both formulas are simultaneously conjunctive normal forms (CNF) of $lnot (Ato B)lor (lnot Aland C)$.

Which one is a CNF of $lnot (Ato B)lor (lnot Aland C)$? To discover it, I use the logical equivalences listed here as rewriting rules for forumlas.

1. First step: eliminate implication.
   beginalign
   lnot (Ato B)lor (lnot Aland C) &equiv lnot (lnot A lor B)lor (lnot Aland C)
   endalign




2. Second step: move NOTs inwards by applying De Morgan's law and double negation law.
   beginalign
   lnot (lnot A lor B)lor (lnot Aland C) &equiv (lnotlnot A land lnot B)lor (lnot Aland C) \
   &equiv (A land lnot B)lor (lnot Aland C)
   endalign




3. Third step: apply the distribution law, identity law and commutativity.
   beginalign
   (A land lnot B)lor (lnot Aland C) &equiv ((A land lnot B) lor lnot A) land ((A land lnot B) lor C) &textdistr. \
   &equiv (A lor lnot A) land (lnot B lor lnot A ) land ((A land lnot B) lor C) &textdistr. \
   &equiv (lnot B lor lnot A ) land ((A land lnot B) lor C) &textident. \
   &equiv (lnot B lor lnot A ) land (A lor C) land (lnot B lor C ) &textdistr. \
   &equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C) &textcomm.
   endalign
   where the identity law can be applied because $A lor lnot A$ is a tautology.

Therefore, $lnot (Ato B)lor (lnot Aland C) equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ and we can conclude that $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is a CNF of $lnot (Ato B)lor (lnot Aland C)$ because $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is in CNF.

share|cite|improve this answer

edited Aug 3 at 6:21

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you for making a very clear answer and taking the time to help me understand. :)
  – numericalorange
  Aug 4 at 1:00
  

  
  
  
  

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870773%2ffinding-a-logically-equivalent-conjunctive-normal-form%23new-answer', 'question_page');

);

Post as a guest

Name Email

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote



accepted

Conditional Negation, Distribution, Complementation, and Identity.

$beginalign &neg (Ato B)vee(neg Awedge C)\equiv ~& (Awedgeneg B)vee(neg Awedge C)\equiv~& (Aveeneg A)wedge(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)\equiv~& qquadqquadquad(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)endalign$

I am not sure how you figured this would be equivalent to $Awedge(neg Bveeneg A)wedge C$, because it is not.

share|cite|improve this answer

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there good reason to use $equiv$ and not $=$? I am the only answerer who elected to use $=$...
  – Mason
  Aug 3 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It indicates that the expressions are equivalent rather than identical. They have the same truth evaluation, but are not quite saying the same thing. A subtle distinction to be sure.
  – Graham Kemp
  Aug 3 at 6:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Not sure Its a distinction I am comprehending. But maybe this will help: math.stackexchange.com/questions/1058596/…
  – Mason
  Aug 3 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $3+4=7$ is equivalent to $e^pi i =-1$ in that both statements evaluate to true but we wouldn't say that the statements are identical because it would have Euler turning in his grave.
  – Mason
  Aug 3 at 7:05
  

  
  
  
  

add a comment | 

up vote
1
down vote



accepted

Conditional Negation, Distribution, Complementation, and Identity.

$beginalign &neg (Ato B)vee(neg Awedge C)\equiv ~& (Awedgeneg B)vee(neg Awedge C)\equiv~& (Aveeneg A)wedge(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)\equiv~& qquadqquadquad(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)endalign$

I am not sure how you figured this would be equivalent to $Awedge(neg Bveeneg A)wedge C$, because it is not.

share|cite|improve this answer

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there good reason to use $equiv$ and not $=$? I am the only answerer who elected to use $=$...
  – Mason
  Aug 3 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It indicates that the expressions are equivalent rather than identical. They have the same truth evaluation, but are not quite saying the same thing. A subtle distinction to be sure.
  – Graham Kemp
  Aug 3 at 6:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Not sure Its a distinction I am comprehending. But maybe this will help: math.stackexchange.com/questions/1058596/…
  – Mason
  Aug 3 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $3+4=7$ is equivalent to $e^pi i =-1$ in that both statements evaluate to true but we wouldn't say that the statements are identical because it would have Euler turning in his grave.
  – Mason
  Aug 3 at 7:05
  

  
  
  
  

add a comment | 

up vote
1
down vote



accepted

up vote
1
down vote



accepted

Conditional Negation, Distribution, Complementation, and Identity.

$beginalign &neg (Ato B)vee(neg Awedge C)\equiv ~& (Awedgeneg B)vee(neg Awedge C)\equiv~& (Aveeneg A)wedge(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)\equiv~& qquadqquadquad(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)endalign$

I am not sure how you figured this would be equivalent to $Awedge(neg Bveeneg A)wedge C$, because it is not.

share|cite|improve this answer

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

Conditional Negation, Distribution, Complementation, and Identity.

$beginalign &neg (Ato B)vee(neg Awedge C)\equiv ~& (Awedgeneg B)vee(neg Awedge C)\equiv~& (Aveeneg A)wedge(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)\equiv~& qquadqquadquad(Avee C)wedge(neg Bvee neg A)wedge(neg Bvee C)endalign$

I am not sure how you figured this would be equivalent to $Awedge(neg Bveeneg A)wedge C$, because it is not.

share|cite|improve this answer

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

share|cite|improve this answer

share|cite|improve this answer

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

answered Aug 3 at 5:48

Graham Kemp

79.9k43275

79.9k43275

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there good reason to use $equiv$ and not $=$? I am the only answerer who elected to use $=$...
  – Mason
  Aug 3 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It indicates that the expressions are equivalent rather than identical. They have the same truth evaluation, but are not quite saying the same thing. A subtle distinction to be sure.
  – Graham Kemp
  Aug 3 at 6:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Not sure Its a distinction I am comprehending. But maybe this will help: math.stackexchange.com/questions/1058596/…
  – Mason
  Aug 3 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $3+4=7$ is equivalent to $e^pi i =-1$ in that both statements evaluate to true but we wouldn't say that the statements are identical because it would have Euler turning in his grave.
  – Mason
  Aug 3 at 7:05
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is there good reason to use $equiv$ and not $=$? I am the only answerer who elected to use $=$...
  – Mason
  Aug 3 at 6:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It indicates that the expressions are equivalent rather than identical. They have the same truth evaluation, but are not quite saying the same thing. A subtle distinction to be sure.
  – Graham Kemp
  Aug 3 at 6:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Not sure Its a distinction I am comprehending. But maybe this will help: math.stackexchange.com/questions/1058596/…
  – Mason
  Aug 3 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $3+4=7$ is equivalent to $e^pi i =-1$ in that both statements evaluate to true but we wouldn't say that the statements are identical because it would have Euler turning in his grave.
  – Mason
  Aug 3 at 7:05
  

  
  
  
  

Is there good reason to use $equiv$ and not $=$? I am the only answerer who elected to use $=$...
– Mason
Aug 3 at 6:24

Is there good reason to use $equiv$ and not $=$? I am the only answerer who elected to use $=$...
– Mason
Aug 3 at 6:24

It indicates that the expressions are equivalent rather than identical. They have the same truth evaluation, but are not quite saying the same thing. A subtle distinction to be sure.
– Graham Kemp
Aug 3 at 6:57

It indicates that the expressions are equivalent rather than identical. They have the same truth evaluation, but are not quite saying the same thing. A subtle distinction to be sure.
– Graham Kemp
Aug 3 at 6:57

Not sure Its a distinction I am comprehending. But maybe this will help: math.stackexchange.com/questions/1058596/…
– Mason
Aug 3 at 7:00

Not sure Its a distinction I am comprehending. But maybe this will help: math.stackexchange.com/questions/1058596/…
– Mason
Aug 3 at 7:00

$3+4=7$ is equivalent to $e^pi i =-1$ in that both statements evaluate to true but we wouldn't say that the statements are identical because it would have Euler turning in his grave.
– Mason
Aug 3 at 7:05

$3+4=7$ is equivalent to $e^pi i =-1$ in that both statements evaluate to true but we wouldn't say that the statements are identical because it would have Euler turning in his grave.
– Mason
Aug 3 at 7:05

add a comment | 

up vote
1
down vote

$$
beginalign
&neg (Ato B)vee (neg Awedge C)\
&= neg(B vee neg A )vee (neg Awedge C)\
&=(neg B vee A )vee (neg Awedge C)\
&=((neg B wedge A) vee neg A)wedge ((neg B wedge A) vee C)\
&=(neg B vee neg A) wedge (A vee neg A)wedge (neg B vee C) wedge (A vee C)\
&=(neg B vee neg A) wedge (T)wedge (neg B vee C) wedge (A vee C)\
endalign $$

How can we justify these equalities:

1) Definition of $rightarrow$. $xrightarrow y = (yvee neg x)$

2) Distribute $neg$. We can find that $neg(x vee y)=neg x wedge neg y$

3) Demorgan's law. $x wedge (yvee z)=(xvee y) wedge (xvee z) $

4) More application of Demorgan's law.

5) Tautology $x vee neg x =T$

Then you arrive at your conclusion after we remove this Tautology and rearrange.

You can verify that $(A,B,C)= (T,T,F)$ satisfies the expression above.
but it doesn't satisfy $Awedge (neg B veeneg A) wedge C$. This would be one way to assure yourself that these expressions aren't equal.

share|cite|improve this answer

edited Aug 3 at 6:03

answered Aug 3 at 5:44

Mason

1,1271223

add a comment | 

up vote
1
down vote

$$
beginalign
&neg (Ato B)vee (neg Awedge C)\
&= neg(B vee neg A )vee (neg Awedge C)\
&=(neg B vee A )vee (neg Awedge C)\
&=((neg B wedge A) vee neg A)wedge ((neg B wedge A) vee C)\
&=(neg B vee neg A) wedge (A vee neg A)wedge (neg B vee C) wedge (A vee C)\
&=(neg B vee neg A) wedge (T)wedge (neg B vee C) wedge (A vee C)\
endalign $$

How can we justify these equalities:

1) Definition of $rightarrow$. $xrightarrow y = (yvee neg x)$

2) Distribute $neg$. We can find that $neg(x vee y)=neg x wedge neg y$

3) Demorgan's law. $x wedge (yvee z)=(xvee y) wedge (xvee z) $

4) More application of Demorgan's law.

5) Tautology $x vee neg x =T$

Then you arrive at your conclusion after we remove this Tautology and rearrange.

You can verify that $(A,B,C)= (T,T,F)$ satisfies the expression above.
but it doesn't satisfy $Awedge (neg B veeneg A) wedge C$. This would be one way to assure yourself that these expressions aren't equal.

share|cite|improve this answer

edited Aug 3 at 6:03

answered Aug 3 at 5:44

Mason

1,1271223

add a comment | 

up vote
1
down vote

up vote
1
down vote

$$
beginalign
&neg (Ato B)vee (neg Awedge C)\
&= neg(B vee neg A )vee (neg Awedge C)\
&=(neg B vee A )vee (neg Awedge C)\
&=((neg B wedge A) vee neg A)wedge ((neg B wedge A) vee C)\
&=(neg B vee neg A) wedge (A vee neg A)wedge (neg B vee C) wedge (A vee C)\
&=(neg B vee neg A) wedge (T)wedge (neg B vee C) wedge (A vee C)\
endalign $$

How can we justify these equalities:

1) Definition of $rightarrow$. $xrightarrow y = (yvee neg x)$

2) Distribute $neg$. We can find that $neg(x vee y)=neg x wedge neg y$

3) Demorgan's law. $x wedge (yvee z)=(xvee y) wedge (xvee z) $

4) More application of Demorgan's law.

5) Tautology $x vee neg x =T$

Then you arrive at your conclusion after we remove this Tautology and rearrange.

You can verify that $(A,B,C)= (T,T,F)$ satisfies the expression above.
but it doesn't satisfy $Awedge (neg B veeneg A) wedge C$. This would be one way to assure yourself that these expressions aren't equal.

share|cite|improve this answer

edited Aug 3 at 6:03

answered Aug 3 at 5:44

Mason

1,1271223

$$
beginalign
&neg (Ato B)vee (neg Awedge C)\
&= neg(B vee neg A )vee (neg Awedge C)\
&=(neg B vee A )vee (neg Awedge C)\
&=((neg B wedge A) vee neg A)wedge ((neg B wedge A) vee C)\
&=(neg B vee neg A) wedge (A vee neg A)wedge (neg B vee C) wedge (A vee C)\
&=(neg B vee neg A) wedge (T)wedge (neg B vee C) wedge (A vee C)\
endalign $$

How can we justify these equalities:

1) Definition of $rightarrow$. $xrightarrow y = (yvee neg x)$

2) Distribute $neg$. We can find that $neg(x vee y)=neg x wedge neg y$

3) Demorgan's law. $x wedge (yvee z)=(xvee y) wedge (xvee z) $

4) More application of Demorgan's law.

5) Tautology $x vee neg x =T$

Then you arrive at your conclusion after we remove this Tautology and rearrange.

You can verify that $(A,B,C)= (T,T,F)$ satisfies the expression above.
but it doesn't satisfy $Awedge (neg B veeneg A) wedge C$. This would be one way to assure yourself that these expressions aren't equal.

share|cite|improve this answer

edited Aug 3 at 6:03

answered Aug 3 at 5:44

Mason

1,1271223

share|cite|improve this answer

share|cite|improve this answer

edited Aug 3 at 6:03

edited Aug 3 at 6:03

edited Aug 3 at 6:03

answered Aug 3 at 5:44

Mason

1,1271223

answered Aug 3 at 5:44

Mason

1,1271223

answered Aug 3 at 5:44

Mason

1,1271223

1,1271223

add a comment | 

add a comment | 

up vote
1
down vote

The formula $A land (lnot B lor lnot A)land C$ is not logically equivalent to the formula $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$: take for instance the truth assignment $v$ such that $v(A) = top$ and $v(B) = v(C) = bot$, then $A land (lnot B lor lnot A)land C$ is false for $v$ but $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is true for $v$. Therefore, it is impossible that both formulas are simultaneously conjunctive normal forms (CNF) of $lnot (Ato B)lor (lnot Aland C)$.

Which one is a CNF of $lnot (Ato B)lor (lnot Aland C)$? To discover it, I use the logical equivalences listed here as rewriting rules for forumlas.

1. First step: eliminate implication.
   beginalign
   lnot (Ato B)lor (lnot Aland C) &equiv lnot (lnot A lor B)lor (lnot Aland C)
   endalign




2. Second step: move NOTs inwards by applying De Morgan's law and double negation law.
   beginalign
   lnot (lnot A lor B)lor (lnot Aland C) &equiv (lnotlnot A land lnot B)lor (lnot Aland C) \
   &equiv (A land lnot B)lor (lnot Aland C)
   endalign




3. Third step: apply the distribution law, identity law and commutativity.
   beginalign
   (A land lnot B)lor (lnot Aland C) &equiv ((A land lnot B) lor lnot A) land ((A land lnot B) lor C) &textdistr. \
   &equiv (A lor lnot A) land (lnot B lor lnot A ) land ((A land lnot B) lor C) &textdistr. \
   &equiv (lnot B lor lnot A ) land ((A land lnot B) lor C) &textident. \
   &equiv (lnot B lor lnot A ) land (A lor C) land (lnot B lor C ) &textdistr. \
   &equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C) &textcomm.
   endalign
   where the identity law can be applied because $A lor lnot A$ is a tautology.

Therefore, $lnot (Ato B)lor (lnot Aland C) equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ and we can conclude that $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is a CNF of $lnot (Ato B)lor (lnot Aland C)$ because $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is in CNF.

share|cite|improve this answer

edited Aug 3 at 6:21

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you for making a very clear answer and taking the time to help me understand. :)
  – numericalorange
  Aug 4 at 1:00
  

  
  
  
  

add a comment | 

up vote
1
down vote

The formula $A land (lnot B lor lnot A)land C$ is not logically equivalent to the formula $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$: take for instance the truth assignment $v$ such that $v(A) = top$ and $v(B) = v(C) = bot$, then $A land (lnot B lor lnot A)land C$ is false for $v$ but $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is true for $v$. Therefore, it is impossible that both formulas are simultaneously conjunctive normal forms (CNF) of $lnot (Ato B)lor (lnot Aland C)$.

Which one is a CNF of $lnot (Ato B)lor (lnot Aland C)$? To discover it, I use the logical equivalences listed here as rewriting rules for forumlas.

1. First step: eliminate implication.
   beginalign
   lnot (Ato B)lor (lnot Aland C) &equiv lnot (lnot A lor B)lor (lnot Aland C)
   endalign




2. Second step: move NOTs inwards by applying De Morgan's law and double negation law.
   beginalign
   lnot (lnot A lor B)lor (lnot Aland C) &equiv (lnotlnot A land lnot B)lor (lnot Aland C) \
   &equiv (A land lnot B)lor (lnot Aland C)
   endalign




3. Third step: apply the distribution law, identity law and commutativity.
   beginalign
   (A land lnot B)lor (lnot Aland C) &equiv ((A land lnot B) lor lnot A) land ((A land lnot B) lor C) &textdistr. \
   &equiv (A lor lnot A) land (lnot B lor lnot A ) land ((A land lnot B) lor C) &textdistr. \
   &equiv (lnot B lor lnot A ) land ((A land lnot B) lor C) &textident. \
   &equiv (lnot B lor lnot A ) land (A lor C) land (lnot B lor C ) &textdistr. \
   &equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C) &textcomm.
   endalign
   where the identity law can be applied because $A lor lnot A$ is a tautology.

Therefore, $lnot (Ato B)lor (lnot Aland C) equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ and we can conclude that $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is a CNF of $lnot (Ato B)lor (lnot Aland C)$ because $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is in CNF.

share|cite|improve this answer

edited Aug 3 at 6:21

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you for making a very clear answer and taking the time to help me understand. :)
  – numericalorange
  Aug 4 at 1:00
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

The formula $A land (lnot B lor lnot A)land C$ is not logically equivalent to the formula $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$: take for instance the truth assignment $v$ such that $v(A) = top$ and $v(B) = v(C) = bot$, then $A land (lnot B lor lnot A)land C$ is false for $v$ but $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is true for $v$. Therefore, it is impossible that both formulas are simultaneously conjunctive normal forms (CNF) of $lnot (Ato B)lor (lnot Aland C)$.

Which one is a CNF of $lnot (Ato B)lor (lnot Aland C)$? To discover it, I use the logical equivalences listed here as rewriting rules for forumlas.

1. First step: eliminate implication.
   beginalign
   lnot (Ato B)lor (lnot Aland C) &equiv lnot (lnot A lor B)lor (lnot Aland C)
   endalign




2. Second step: move NOTs inwards by applying De Morgan's law and double negation law.
   beginalign
   lnot (lnot A lor B)lor (lnot Aland C) &equiv (lnotlnot A land lnot B)lor (lnot Aland C) \
   &equiv (A land lnot B)lor (lnot Aland C)
   endalign




3. Third step: apply the distribution law, identity law and commutativity.
   beginalign
   (A land lnot B)lor (lnot Aland C) &equiv ((A land lnot B) lor lnot A) land ((A land lnot B) lor C) &textdistr. \
   &equiv (A lor lnot A) land (lnot B lor lnot A ) land ((A land lnot B) lor C) &textdistr. \
   &equiv (lnot B lor lnot A ) land ((A land lnot B) lor C) &textident. \
   &equiv (lnot B lor lnot A ) land (A lor C) land (lnot B lor C ) &textdistr. \
   &equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C) &textcomm.
   endalign
   where the identity law can be applied because $A lor lnot A$ is a tautology.

Therefore, $lnot (Ato B)lor (lnot Aland C) equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ and we can conclude that $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is a CNF of $lnot (Ato B)lor (lnot Aland C)$ because $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is in CNF.

share|cite|improve this answer

edited Aug 3 at 6:21

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

The formula $A land (lnot B lor lnot A)land C$ is not logically equivalent to the formula $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$: take for instance the truth assignment $v$ such that $v(A) = top$ and $v(B) = v(C) = bot$, then $A land (lnot B lor lnot A)land C$ is false for $v$ but $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is true for $v$. Therefore, it is impossible that both formulas are simultaneously conjunctive normal forms (CNF) of $lnot (Ato B)lor (lnot Aland C)$.

Which one is a CNF of $lnot (Ato B)lor (lnot Aland C)$? To discover it, I use the logical equivalences listed here as rewriting rules for forumlas.

1. First step: eliminate implication.
   beginalign
   lnot (Ato B)lor (lnot Aland C) &equiv lnot (lnot A lor B)lor (lnot Aland C)
   endalign




2. Second step: move NOTs inwards by applying De Morgan's law and double negation law.
   beginalign
   lnot (lnot A lor B)lor (lnot Aland C) &equiv (lnotlnot A land lnot B)lor (lnot Aland C) \
   &equiv (A land lnot B)lor (lnot Aland C)
   endalign




3. Third step: apply the distribution law, identity law and commutativity.
   beginalign
   (A land lnot B)lor (lnot Aland C) &equiv ((A land lnot B) lor lnot A) land ((A land lnot B) lor C) &textdistr. \
   &equiv (A lor lnot A) land (lnot B lor lnot A ) land ((A land lnot B) lor C) &textdistr. \
   &equiv (lnot B lor lnot A ) land ((A land lnot B) lor C) &textident. \
   &equiv (lnot B lor lnot A ) land (A lor C) land (lnot B lor C ) &textdistr. \
   &equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C) &textcomm.
   endalign
   where the identity law can be applied because $A lor lnot A$ is a tautology.

Therefore, $lnot (Ato B)lor (lnot Aland C) equiv (Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ and we can conclude that $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is a CNF of $lnot (Ato B)lor (lnot Aland C)$ because $(Alor C) land (lnot B lor lnot A) land (lnot B lor C)$ is in CNF.

share|cite|improve this answer

edited Aug 3 at 6:21

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

share|cite|improve this answer

share|cite|improve this answer

edited Aug 3 at 6:21

edited Aug 3 at 6:21

edited Aug 3 at 6:21

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

answered Aug 3 at 5:45

Taroccoesbrocco

3,31941330

3,31941330

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you for making a very clear answer and taking the time to help me understand. :)
  – numericalorange
  Aug 4 at 1:00
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you for making a very clear answer and taking the time to help me understand. :)
  – numericalorange
  Aug 4 at 1:00
  

  
  
  
  

Thank you for making a very clear answer and taking the time to help me understand. :)
– numericalorange
Aug 4 at 1:00

Thank you for making a very clear answer and taking the time to help me understand. :)
– numericalorange
Aug 4 at 1:00

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870773%2ffinding-a-logically-equivalent-conjunctive-normal-form%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Name Email

Name

Email

Name Email

Name

Email