Mixing
![Casino Profit/Loss (Expected Value) [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Is it possible for the DNF and CNF to be the same
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
For example
can $A land C$ be both the conjunctive normal form and the disjunctive normal form of
$(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$
logic proof-writing propositional-calculus conjunctive-normal-form
edited Aug 2 at 15:44
Taroccoesbrocco
3,31941330
asked Aug 2 at 14:51
user10168997
434
add a comment |Â
up vote
2
down vote
favorite
For example
can $A land C$ be both the conjunctive normal form and the disjunctive normal form of
$(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$
logic proof-writing propositional-calculus conjunctive-normal-form
edited Aug 2 at 15:44
Taroccoesbrocco
3,31941330
asked Aug 2 at 14:51
user10168997
434
2
Can you add your work to show how you simplified the highlighted expression to $Aland C$?
– amWhy
Aug 2 at 14:56
Yes, the formula $A land C$ can both be interpreted as CNF and DNF.
– Sudix
Aug 2 at 16:39
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
For example
can $A land C$ be both the conjunctive normal form and the disjunctive normal form of
$(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$
logic proof-writing propositional-calculus conjunctive-normal-form
edited Aug 2 at 15:44
Taroccoesbrocco
3,31941330
asked Aug 2 at 14:51
user10168997
434
For example
can $A land C$ be both the conjunctive normal form and the disjunctive normal form of
$(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$
logic proof-writing propositional-calculus conjunctive-normal-form
edited Aug 2 at 15:44
Taroccoesbrocco
3,31941330
asked Aug 2 at 14:51
user10168997
434
edited Aug 2 at 15:44
Taroccoesbrocco
3,31941330
edited Aug 2 at 15:44
Taroccoesbrocco
3,31941330
edited Aug 2 at 15:44
Taroccoesbrocco
3,31941330
3,31941330
asked Aug 2 at 14:51
user10168997
434
asked Aug 2 at 14:51
user10168997
434
asked Aug 2 at 14:51
user10168997
434
434
2
Can you add your work to show how you simplified the highlighted expression to $Aland C$?
– amWhy
Aug 2 at 14:56
Yes, the formula $A land C$ can both be interpreted as CNF and DNF.
– Sudix
Aug 2 at 16:39
add a comment |Â
2
Can you add your work to show how you simplified the highlighted expression to $Aland C$?
– amWhy
Aug 2 at 14:56
Yes, the formula $A land C$ can both be interpreted as CNF and DNF.
– Sudix
Aug 2 at 16:39
2
2
Can you add your work to show how you simplified the highlighted expression to $Aland C$?
– amWhy
Aug 2 at 14:56
Can you add your work to show how you simplified the highlighted expression to $Aland C$?
– amWhy
Aug 2 at 14:56
Yes, the formula $A land C$ can both be interpreted as CNF and DNF.
– Sudix
Aug 2 at 16:39
Yes, the formula $A land C$ can both be interpreted as CNF and DNF.
– Sudix
Aug 2 at 16:39
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
The short answer is: yes!
Indeed, $A land C$ is both a CNF (because it is a conjunction of two disjunctive clauses, each one made of just one literal) and a DNF (with just one conjunctive clause).
To prove that $A land C$ is a CNF and a DNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$, it remains to prove that $A land C$ is logically equivalent to $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. To prove it, I use logical equivalences listed here as rewriting rules (the use of the associativity is left implicit):
beginalign
(A lor (A land B) lor (lnot A land lnot B land lnot C)) land C &equiv (A lor (lnot A land lnot B land lnot C)) land C &textabsortion law \
&equiv (A lor lnot A) land (A lor lnot B) land (A lor lnot C) land C &textdistributivity law \
&equiv (A lor lnot B) land (A lor lnot C) land C &textidentity law \
&equiv (A lor (lnot B land lnot C)) land C &textdistributivity law \
&equiv (Aland C) lor (lnot B land lnot C land C) &textdistributivity law \
&equiv Aland C &textidentity law
endalign
where the first identity law can be applied since $A lor lnot A$ is a tautology, and the second identity law can be applied because $lnot B land lnot C land C$ is a contradiction.
Remark. Pay attention that a CNF of a given formula is not unique, and similarly for DNF. For instance, also $A land C land (B lor lnot B)$ is a CNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. So, properly speaking it is not clear what you refer to when you talk of the CNF (or the DNF) of a given formula.
More interesting remarks about the non-uniqueness of CNF (or DNF) of a given formula are in this question.
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
add a comment |Â
up vote
0
down vote
A conjunctive normal form is a conjunction of a sequence of disjunctions of a sequence of literals or their negations. Â Abreviated as: a conjunction of disjunctions of literals or their negations.
A single literal is a conjunction of a sequence of one literal. Â It is also a disjunction of a sequence of one literal.
Thus $Awedge C$ is a conjunction of two disjunctions of one literal; and also a disjunction of two conjunctions of one literal. Â That is it is both a conjunctive normal form and a disjunctive normal form.
Now, is it a CNF/DNF for $(Avee((Awedge B)vee(neg Awedgeneg Bwedgeneg C)))wedge C$?
Well, $C$ must be true for the statement to hold. Â When we substitue $top$ for $C$, that becomes $(Avee((Awedge B)vee(neg Awedgeneg Bwedge bot)))wedge top$ which simpliefies to $A$. Â So $A$ must be true too. Â The value of $B$ is irrelevant.
Therefore $Awedge C$ is indeed a CNF/DNF equivalent to the statement.
answered Aug 2 at 23:39
Graham Kemp
80k43275
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
The short answer is: yes!
Indeed, $A land C$ is both a CNF (because it is a conjunction of two disjunctive clauses, each one made of just one literal) and a DNF (with just one conjunctive clause).
To prove that $A land C$ is a CNF and a DNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$, it remains to prove that $A land C$ is logically equivalent to $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. To prove it, I use logical equivalences listed here as rewriting rules (the use of the associativity is left implicit):
beginalign
(A lor (A land B) lor (lnot A land lnot B land lnot C)) land C &equiv (A lor (lnot A land lnot B land lnot C)) land C &textabsortion law \
&equiv (A lor lnot A) land (A lor lnot B) land (A lor lnot C) land C &textdistributivity law \
&equiv (A lor lnot B) land (A lor lnot C) land C &textidentity law \
&equiv (A lor (lnot B land lnot C)) land C &textdistributivity law \
&equiv (Aland C) lor (lnot B land lnot C land C) &textdistributivity law \
&equiv Aland C &textidentity law
endalign
where the first identity law can be applied since $A lor lnot A$ is a tautology, and the second identity law can be applied because $lnot B land lnot C land C$ is a contradiction.
Remark. Pay attention that a CNF of a given formula is not unique, and similarly for DNF. For instance, also $A land C land (B lor lnot B)$ is a CNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. So, properly speaking it is not clear what you refer to when you talk of the CNF (or the DNF) of a given formula.
More interesting remarks about the non-uniqueness of CNF (or DNF) of a given formula are in this question.
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
add a comment |Â
up vote
1
down vote
The short answer is: yes!
Indeed, $A land C$ is both a CNF (because it is a conjunction of two disjunctive clauses, each one made of just one literal) and a DNF (with just one conjunctive clause).
To prove that $A land C$ is a CNF and a DNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$, it remains to prove that $A land C$ is logically equivalent to $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. To prove it, I use logical equivalences listed here as rewriting rules (the use of the associativity is left implicit):
beginalign
(A lor (A land B) lor (lnot A land lnot B land lnot C)) land C &equiv (A lor (lnot A land lnot B land lnot C)) land C &textabsortion law \
&equiv (A lor lnot A) land (A lor lnot B) land (A lor lnot C) land C &textdistributivity law \
&equiv (A lor lnot B) land (A lor lnot C) land C &textidentity law \
&equiv (A lor (lnot B land lnot C)) land C &textdistributivity law \
&equiv (Aland C) lor (lnot B land lnot C land C) &textdistributivity law \
&equiv Aland C &textidentity law
endalign
where the first identity law can be applied since $A lor lnot A$ is a tautology, and the second identity law can be applied because $lnot B land lnot C land C$ is a contradiction.
Remark. Pay attention that a CNF of a given formula is not unique, and similarly for DNF. For instance, also $A land C land (B lor lnot B)$ is a CNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. So, properly speaking it is not clear what you refer to when you talk of the CNF (or the DNF) of a given formula.
More interesting remarks about the non-uniqueness of CNF (or DNF) of a given formula are in this question.
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The short answer is: yes!
Indeed, $A land C$ is both a CNF (because it is a conjunction of two disjunctive clauses, each one made of just one literal) and a DNF (with just one conjunctive clause).
To prove that $A land C$ is a CNF and a DNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$, it remains to prove that $A land C$ is logically equivalent to $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. To prove it, I use logical equivalences listed here as rewriting rules (the use of the associativity is left implicit):
beginalign
(A lor (A land B) lor (lnot A land lnot B land lnot C)) land C &equiv (A lor (lnot A land lnot B land lnot C)) land C &textabsortion law \
&equiv (A lor lnot A) land (A lor lnot B) land (A lor lnot C) land C &textdistributivity law \
&equiv (A lor lnot B) land (A lor lnot C) land C &textidentity law \
&equiv (A lor (lnot B land lnot C)) land C &textdistributivity law \
&equiv (Aland C) lor (lnot B land lnot C land C) &textdistributivity law \
&equiv Aland C &textidentity law
endalign
where the first identity law can be applied since $A lor lnot A$ is a tautology, and the second identity law can be applied because $lnot B land lnot C land C$ is a contradiction.
Remark. Pay attention that a CNF of a given formula is not unique, and similarly for DNF. For instance, also $A land C land (B lor lnot B)$ is a CNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. So, properly speaking it is not clear what you refer to when you talk of the CNF (or the DNF) of a given formula.
More interesting remarks about the non-uniqueness of CNF (or DNF) of a given formula are in this question.
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
The short answer is: yes!
Indeed, $A land C$ is both a CNF (because it is a conjunction of two disjunctive clauses, each one made of just one literal) and a DNF (with just one conjunctive clause).
To prove that $A land C$ is a CNF and a DNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$, it remains to prove that $A land C$ is logically equivalent to $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. To prove it, I use logical equivalences listed here as rewriting rules (the use of the associativity is left implicit):
beginalign
(A lor (A land B) lor (lnot A land lnot B land lnot C)) land C &equiv (A lor (lnot A land lnot B land lnot C)) land C &textabsortion law \
&equiv (A lor lnot A) land (A lor lnot B) land (A lor lnot C) land C &textdistributivity law \
&equiv (A lor lnot B) land (A lor lnot C) land C &textidentity law \
&equiv (A lor (lnot B land lnot C)) land C &textdistributivity law \
&equiv (Aland C) lor (lnot B land lnot C land C) &textdistributivity law \
&equiv Aland C &textidentity law
endalign
where the first identity law can be applied since $A lor lnot A$ is a tautology, and the second identity law can be applied because $lnot B land lnot C land C$ is a contradiction.
Remark. Pay attention that a CNF of a given formula is not unique, and similarly for DNF. For instance, also $A land C land (B lor lnot B)$ is a CNF of $(A lor ((A land B) lor (lnot A land lnot B land lnot C))) land C$. So, properly speaking it is not clear what you refer to when you talk of the CNF (or the DNF) of a given formula.
More interesting remarks about the non-uniqueness of CNF (or DNF) of a given formula are in this question.
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
edited Aug 3 at 6:43
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
answered Aug 2 at 16:54
Taroccoesbrocco
3,31941330
3,31941330
add a comment |Â
add a comment |Â
up vote
0
down vote
A conjunctive normal form is a conjunction of a sequence of disjunctions of a sequence of literals or their negations. Â Abreviated as: a conjunction of disjunctions of literals or their negations.
A single literal is a conjunction of a sequence of one literal. Â It is also a disjunction of a sequence of one literal.
Thus $Awedge C$ is a conjunction of two disjunctions of one literal; and also a disjunction of two conjunctions of one literal. Â That is it is both a conjunctive normal form and a disjunctive normal form.
Now, is it a CNF/DNF for $(Avee((Awedge B)vee(neg Awedgeneg Bwedgeneg C)))wedge C$?
Well, $C$ must be true for the statement to hold. Â When we substitue $top$ for $C$, that becomes $(Avee((Awedge B)vee(neg Awedgeneg Bwedge bot)))wedge top$ which simpliefies to $A$. Â So $A$ must be true too. Â The value of $B$ is irrelevant.
Therefore $Awedge C$ is indeed a CNF/DNF equivalent to the statement.
answered Aug 2 at 23:39
Graham Kemp
80k43275
add a comment |Â
up vote
0
down vote
A conjunctive normal form is a conjunction of a sequence of disjunctions of a sequence of literals or their negations. Â Abreviated as: a conjunction of disjunctions of literals or their negations.
A single literal is a conjunction of a sequence of one literal. Â It is also a disjunction of a sequence of one literal.
Thus $Awedge C$ is a conjunction of two disjunctions of one literal; and also a disjunction of two conjunctions of one literal. Â That is it is both a conjunctive normal form and a disjunctive normal form.
Now, is it a CNF/DNF for $(Avee((Awedge B)vee(neg Awedgeneg Bwedgeneg C)))wedge C$?
Well, $C$ must be true for the statement to hold. Â When we substitue $top$ for $C$, that becomes $(Avee((Awedge B)vee(neg Awedgeneg Bwedge bot)))wedge top$ which simpliefies to $A$. Â So $A$ must be true too. Â The value of $B$ is irrelevant.
Therefore $Awedge C$ is indeed a CNF/DNF equivalent to the statement.
answered Aug 2 at 23:39
Graham Kemp
80k43275
add a comment |Â
up vote
0
down vote
up vote
0
down vote
A conjunctive normal form is a conjunction of a sequence of disjunctions of a sequence of literals or their negations. Â Abreviated as: a conjunction of disjunctions of literals or their negations.
A single literal is a conjunction of a sequence of one literal. Â It is also a disjunction of a sequence of one literal.
Thus $Awedge C$ is a conjunction of two disjunctions of one literal; and also a disjunction of two conjunctions of one literal. Â That is it is both a conjunctive normal form and a disjunctive normal form.
Now, is it a CNF/DNF for $(Avee((Awedge B)vee(neg Awedgeneg Bwedgeneg C)))wedge C$?
Well, $C$ must be true for the statement to hold. Â When we substitue $top$ for $C$, that becomes $(Avee((Awedge B)vee(neg Awedgeneg Bwedge bot)))wedge top$ which simpliefies to $A$. Â So $A$ must be true too. Â The value of $B$ is irrelevant.
Therefore $Awedge C$ is indeed a CNF/DNF equivalent to the statement.
answered Aug 2 at 23:39
Graham Kemp
80k43275
A conjunctive normal form is a conjunction of a sequence of disjunctions of a sequence of literals or their negations. Â Abreviated as: a conjunction of disjunctions of literals or their negations.
A single literal is a conjunction of a sequence of one literal. Â It is also a disjunction of a sequence of one literal.
Thus $Awedge C$ is a conjunction of two disjunctions of one literal; and also a disjunction of two conjunctions of one literal. Â That is it is both a conjunctive normal form and a disjunctive normal form.
Now, is it a CNF/DNF for $(Avee((Awedge B)vee(neg Awedgeneg Bwedgeneg C)))wedge C$?
Well, $C$ must be true for the statement to hold. Â When we substitue $top$ for $C$, that becomes $(Avee((Awedge B)vee(neg Awedgeneg Bwedge bot)))wedge top$ which simpliefies to $A$. Â So $A$ must be true too. Â The value of $B$ is irrelevant.
Therefore $Awedge C$ is indeed a CNF/DNF equivalent to the statement.
answered Aug 2 at 23:39
Graham Kemp
80k43275
answered Aug 2 at 23:39
Graham Kemp
80k43275
answered Aug 2 at 23:39
Graham Kemp
80k43275
answered Aug 2 at 23:39
Graham Kemp
80k43275
80k43275
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870147%2fis-it-possible-for-the-dnf-and-cnf-to-be-the-same%23new-answer', 'question_page');
);
Post as a guest
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
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
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
2
Can you add your work to show how you simplified the highlighted expression to $Aland C$?
– amWhy
Aug 2 at 14:56
Yes, the formula $A land C$ can both be interpreted as CNF and DNF.
– Sudix
Aug 2 at 16:39