Using Conjunctive Normal form to find when wff is true

  • Thread starter Thread starter member 731016
  • Start date Start date
  • Tags Tags
    Form Normal
member 731016
Homework Statement
I am trying to understand how to tell which values for a proposition need to be taken on to make a CNF true.
Relevant Equations
CNF notation
For this,
1689831998459.png

Does someone please know how setting ##P_1## and ##P_2## true makes the CNF true? If I see ##P_2## true, then it ##(true + false)## since it is negated. Therefore, should they be setting ##P_1## true and ##P_2## false?

Many thanks!
 
Physics news on Phys.org
ChiralSuperfields said:
Homework Statement: I am trying to understand how to tell which values for a proposition need to be taken on to make a CNF true.
Relevant Equations: CNF notation

For this,
View attachment 329444
Does someone please know how setting ##P_1## and ##P_2## true makes the CNF true? If I see ##P_2## true, then it ##(true + false)## since it is negated. Therefore, should they be setting ##P_1## true and ##P_2## false?

Many thanks!
As it says, "+" specifies OR (##\vee##),
so (true + false) = (true OR false) = true.
So setting P1 and P2 true gives:
(T + F) (T + ? + ?) (T + ?)
which is (T) (T) (T)
since (True OR anything) is True
so the overall result is T.
 
  • Informative
Likes member 731016
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...

Similar threads

Back
Top