Conjuctive & Disjunctive Form Conversion - Is My Sollution Correct?

C

clytaemnestra

New member
Joined
Mar 7, 2021
Messages
7
Hi, I've solved a task, but I'm not sure if it's correct or not, as I'm doing it for the first time, thus I'd like to ask someone, if I got it correct.

Task: convert the following formula to the conjuctive, disjunctive and full disjunctive form:
(ϕ ⇒ ψ) ⇒ (¬ϕ ⇒ ¬ψ)

I went through Wiki and some materials on the internet and the method to solve it seems to be the following:
  • get rid of implication - p -> q = ¬ p ∨ q
  • use de Morgan's laws to get rid of negations
Solution: I've done the following:
(ϕ ⇒ ψ) ⇒ (¬ϕ ⇒ ¬ψ)
¬ (¬ϕ ∨ ψ) ∨ (¬¬ϕ ∨ ¬ψ)
(ϕ ∧ ¬ ψ) ∨ (ϕ ∨ ¬ψ) // this is disjunctive form
(ϕ ∧ ¬ ψ) ∨ ¬ (ϕ ∨ ¬ψ) // here I'm not sure if I can negate only one side, in order to change OR to AND?
(ϕ ∧ ¬ ψ) ∨ (¬ϕ ∧ ψ) // this is full disjunctive form
(ϕ ∨ ¬ ψ) ∧ (¬ϕ ∨ ψ) // this is (full) conjuctive form

Is this correct? Thank you in advance!
 
to go from line 3 to line 4, keeping logical equivalence, double negate the second bracket
(ϕ ∧ ¬ ψ) ∨ ¬¬ (ϕ ∨ ¬ψ)
(ϕ ∧ ¬ ψ) ∨ ¬ (¬ϕ ∧ ψ) // (de Morgan)
(ϕ ∧ ¬ ψ) ∨ ( (ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) ) // the negation of the bracket, being disjunction of the three other combinations of conjunctions of ϕ, ψ, ¬ϕ, ¬ψ
(ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) //full DNF
¬ (¬ϕ ∧ ψ) // reversing the substitution of the bracket just performed in the step before last
(ϕ ∨ ¬ψ) // (de Morgan) full CNF, also DNF (not full)


You could have gone straight from your line 3 DNF to full DNF:
(ϕ ∧ ¬ ψ) ∨ (ϕ) ∨ (¬ψ) // DNF
(ϕ ∧ ¬ ψ) ∨ ((ϕ ∧ ψ) ∨ (ϕ ∧ ¬ ψ)) ∨ ((ϕ ∧ ¬ ψ) ∨ (¬ϕ ∧ ¬ ψ)) // e.g. introducing the missing letter by replacing (ϕ) with ((ϕ ∧ ψ) ∨ (ϕ ∧ ¬ ψ)) etc...
(ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) //full DNF
 
Hello, I have similar task to solve - to convert my formula into CNF, DNF and full DNF:
(φ ∧ ψ) ⇒ (¬φ⇒¬ψ)

My solution:
¬ ( φ ∧ ψ) ∨ (¬φ⇒¬ψ)
(¬ φ ∨ ¬ ψ) ∨ (¬φ⇒¬ψ)
(¬ φ ∨ ¬ ψ ) ∨ (ψ ⇒ φ)
(¬ φ ∨ ¬ ψ ) ∨ (¬ψ ∨ φ)
¬ φ ∨ ¬ ψ ∨ ¬ψ ∨ φ DNF, KNF
(¬ φ ∧ ψ) ∨ (¬φ ∧ ¬ψ) ∨ (¬ψ ∧ φ) ∨ (¬ψ ∧ ¬φ) ∨ (¬ φ ∧ ψ) ∨ (¬φ ∧ ¬ψ) ∨ (ψ ∧ φ) ∨ (ψ ∧ ¬φ) -> -> (¬ φ ∧ ψ) ∨ (¬φ ∧ ¬ψ) full DNF

Thanks for helping me out! :)
 
The fifth line reduces to
φ ∨ ¬ φ //(CNF and DNF)
which is a tautology. Therefore there is no full CNF and the full DNF is
( φ ∧ ψ) ∨ (φ ∧ ¬ψ) ∨ (¬φ ∧ ψ)∨ (¬φ ∧ ¬ψ)
 
lex said:
The fifth line reduces to
φ ∨ ¬ φ //(CNF and DNF)
which is a tautology. Therefore there is no full CNF and the full DNF is
( φ ∧ ψ) ∨ (φ ∧ ¬ψ) ∨ (¬φ ∧ ψ)∨ (¬φ ∧ ¬ψ)
Click to expand...

If I correctly understood, when I process from 4th to 5th line I do not have to write ¬ φ ∨ ¬ ψ ∨ ¬ψ ∨ φ. I simply get rid of both Psi's (since they are both negated) and only φ ∨ ¬ φ will remain? This is very helpful feedback, thank you Lex!
 
¬ ψ ∨ ¬ψ is clearly equivalent to ¬ ψ
so ¬ φ ∨ ¬ ψ ∨ ¬ψ ∨ φ is equivalent to φ ∨ ¬ ψ ∨ ¬ φ
but φ ∨ ¬ φ is already a tautology (it is always true) so any disjunction with it (e.g. ∨ ¬ ψ) is superfluous (it adds nothing) (it can't add any extra 'T' results to the truth table values, as they're all T already)
therefore the line is logically equivalent to simply φ ∨ ¬ φ
 
lex said:
to go from line 3 to line 4, keeping logical equivalence, double negate the second bracket
(ϕ ∧ ¬ ψ) ∨ ¬¬ (ϕ ∨ ¬ψ)
(ϕ ∧ ¬ ψ) ∨ ¬ (¬ϕ ∧ ψ) // (de Morgan)
(ϕ ∧ ¬ ψ) ∨ ( (ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) ) // the negation of the bracket, being disjunction of the three other combinations of conjunctions of ϕ, ψ, ¬ϕ, ¬ψ
(ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) //full DNF
¬ (¬ϕ ∧ ψ) // reversing the substitution of the bracket just performed in the step before last
(ϕ ∨ ¬ψ) // (de Morgan) full CNF, also DNF (not full)


You could have gone straight from your line 3 DNF to full DNF:
(ϕ ∧ ¬ ψ) ∨ (ϕ) ∨ (¬ψ) // DNF
(ϕ ∧ ¬ ψ) ∨ ((ϕ ∧ ψ) ∨ (ϕ ∧ ¬ ψ)) ∨ ((ϕ ∧ ¬ ψ) ∨ (¬ϕ ∧ ¬ ψ)) // e.g. introducing the missing letter by replacing (ϕ) with ((ϕ ∧ ψ) ∨ (ϕ ∧ ¬ ψ)) etc...
(ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) //full DNF
Click to expand...

thank you very much for your help! :)
 
lex said:
(ϕ ∧ ¬ ψ) ∨ ¬¬ (ϕ ∨ ¬ψ)
(ϕ ∧ ¬ ψ) ∨ ¬ (¬ϕ ∧ ψ) // (de Morgan)
(ϕ ∧ ¬ ψ) ∨ ( (ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) ) // the negation of the bracket, being disjunction of the three other combinations of conjunctions of ϕ, ψ, ¬ϕ, ¬ψ
(ϕ ∧ ψ) ∨ (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ¬ψ) //full DNF
¬ (¬ϕ ∧ ψ) // reversing the substitution of the bracket just performed in the step before last
(ϕ ∨ ¬ψ) // (de Morgan) full CNF, also DNF (not full)
Click to expand...

I'd like to ask about the negation of the bracket, being disjunction of the three other combinations of conjunctions of ϕ, ψ, ¬ϕ, ¬ψ
I'm not sure I understand it completely. Which law or rule is it? How do I know how to combine these elements?
 

Convert Conjunctive normal form to disjunctive normal form

Hello, I have the following formula in CNF: If I negate this formula twice, I can convert this formula to DNF. The next three steps are clear to me: However there is one more step that I do not understand: De Morgan's law has been used to get from step 2 to step 3. However, I do not...
www.freemathhelp.com
I'll write out something later this evening. In the meantime if you are in a hurry the same issue (with three 'letters') occurred in the above thread. (It may not help)!
 
clytaemnestra said:
I'd like to ask about the negation of the bracket, being disjunction of the three other combinations of conjunctions of ϕ, ψ, ¬ϕ, ¬ψ
I'm not sure I understand it completely. Which law or rule is it? How do I know how to combine these elements?
Click to expand...
@clytaemnestra
I hope this makes it a bit clearer. (Maybe!) See attached
 

Attachments

  • negation.pdf
    239.6 KB · Views: 2
You must log in or register to reply here.
Top