conjunctive normal form Watch

E--
Badges: 7
Rep:
?
#1
Report Thread starter 1 month ago
#1
Rewrite this expression in conjunctive normal form:

~(X ∨ Y) ∨ (X ∧ Y ∧ Z)

Check my answer

De Morgan's law ~X ∧ ~Y ∨ (X ∧ Y ∧ Z)

Distributive law ~X ∧ (~Y ∨ X) ∧ (~Y ∨ Y) ∧ (~Y ∨ Z)

Is this right?
0
reply
ghostwalker
  • Study Helper
Badges: 15
#2
Report 1 month ago
#2
(Original post by E--)
Rewrite this expression in conjunctive normal form:

~(X ∨ Y) ∨ (X ∧ Y ∧ Z)

Check my answer

De Morgan's law ~X ∧ ~Y ∨ (X ∧ Y ∧ Z)

Distributive law ~X ∧ (~Y ∨ X) ∧ (~Y ∨ Y) ∧ (~Y ∨ Z)

Is this right?
No.

You can write A\land B\land C, and A\lor B\lor C without brackets as they are unambiguous.

However, A\land B\lor C requires brackets, as it could mean (A\land B)\lor C or A\land(B\lor C), which are logically different.

The result of your de Morgan's law application produces the first form, and you then treat it as if it is the second form, which it is not.
reply
E--
Badges: 7
Rep:
?
#3
Report Thread starter 3 weeks ago
#3
(Original post by ghostwalker)
No.

You can write A\land B\land C, and A\lor B\lor C without brackets as they are unambiguous.

However, A\land B\lor C requires brackets, as it could mean (A\land B)\lor C or A\land(B\lor C), which are logically different.

The result of your de Morgan's law application produces the first form, and you then treat it as if it is the second form, which it is not.
I did it again. It is in conjunctive normal form now, but I don't know if what I did was correct.
Name:  IMG_0794.jpg
Views: 4
Size:  77.9 KB
0
reply
ghostwalker
  • Study Helper
Badges: 15
#4
Report 3 weeks ago
#4
(Original post by E--)
I did it again. It is in conjunctive normal form now, but I don't know if what I did was correct.
Name:  IMG_0794.jpg
Views: 4
Size:  77.9 KB
Generally fine - what were you unsure of?

Couple of comments:

1. BRACKETS!!!! Or lack there of, in the first two lines. Even if everything else was right, I'd doc a mark for ambiguous/incorrect mathematical expression.

2. In your final step, you could do with splitting it up into two smaller steps. Distributive law would produce 6 terms, 2 of which can be deleted, leaving the 4 you have.

Aside: If I recall correctly, the formula can be reduced to 3 terms in CNF, though it's not obvious, and doesn't leap out at me after two weeks.
reply
E--
Badges: 7
Rep:
?
#5
Report Thread starter 3 weeks ago
#5
(Original post by ghostwalker)
Generally fine - what were you unsure of?

Couple of comments:

1. BRACKETS!!!! Or lack there of, in the first two lines. Even if everything else was right, I'd doc a mark for ambiguous/incorrect mathematical expression.

2. In your final step, you could do with splitting it up into two smaller steps. Distributive law would produce 6 terms, 2 of which can be deleted, leaving the 4 you have.

Aside: If I recall correctly, the formula can be reduced to 3 terms in CNF, though it's not obvious, and doesn't leap out at me after two weeks.
But you said brackets are not needed. Ok so i need to put brackets around the (X ∧ Y ∧ Z) in the first 2 lines.
And I know I did miss out the tautologies in the second distributive laws - I coundn't fit it on the whiteboard
formula can be reduced to 3 terms in CNF - does that mean I can reduce it more?
0
reply
ghostwalker
  • Study Helper
Badges: 15
#6
Report 3 weeks ago
#6
(Original post by E--)
But you said brackets are not needed. Ok so i need to put brackets around the (X ∧ Y ∧ Z) in the first 2 lines.
Brackets are not needed within the expression X ^ Y ^ Z itself, but when you combine it with another expression via "v" (you're effectively saying A v B ^ C, which is what my first post was highlighting).

(~X ^ ~Y ) v X ^ Y ^ Z could mean:

(~X ^ ~Y ) v (X ^ Y ^ Z)

or

((~X ^ ~Y ) v X) ^ Y ^ Z

or a few other interpretations which are rather torturous.

And I know I did miss out the tautologies in the second distributive laws - I coundn't fit it on the whiteboard
formula can be reduced to 3 terms in CNF - does that mean I can reduce it more?
Can't recall the details, and the further reduction may be clearer from keeping the tautologies in to start, and seeing a different reduction from there, rather than working from the 4 terms.
reply
ghostwalker
  • Study Helper
Badges: 15
#7
Report 3 weeks ago
#7
(Original post by E--)
formula can be reduced to 3 terms in CNF - does that mean I can reduce it more?
Just running it through Wolfram, produces a minimal CNF of

(\lnot X\lor Y)\land (X \lor \lnot Y)\land (\lnot X \lor Z )

Edit:

(\lnot X\lor Y)\land (X \lor \lnot Y)\land (\lnot Y \lor Z )

would also work, so it's the latter two terms you had - one of which is redundant in this particular formula.
Last edited by ghostwalker; 3 weeks ago
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of Roehampton
    Department of Humanities; Department of Drama, Theatre and Performance; Department of Social Sciences; Department of English and Creative Writing Undergraduate
    Wed, 20 Feb '19
  • Keele University
    Postgraduate Open Afternoon Postgraduate
    Wed, 20 Feb '19
  • Manchester Metropolitan University
    Postgraduate Open Day Postgraduate
    Wed, 20 Feb '19

Do unconditional offers make teenagers lazy?

Yes (112)
58.64%
No (79)
41.36%

Watched Threads

View All