# conjunctive normal form

Watch
#1
Rewrite this expression in conjunctive normal form:

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

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

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

Is this right?
0
1 year ago
#2
(Original post by E--)
Rewrite this expression in conjunctive normal form:

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

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 , and without brackets as they are unambiguous.

However, requires brackets, as it could mean or , 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.
0
#3
(Original post by ghostwalker)
No.

You can write , and without brackets as they are unambiguous.

However, requires brackets, as it could mean or , 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.
0
1 year 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.
Generally fine - what were you unsure of?

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.
0
#5
(Original post by ghostwalker)
Generally fine - what were you unsure of?

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
1 year 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.
0
1 year 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

Edit:

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; 1 year ago
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### Poll

Join the discussion

Yes (50)
22.73%
No (170)
77.27%