Using Conjunctive Normal form to find when wff is true

  • Thread starter member 731016
  • Start date
  • Tags
    Form Normal
In summary, setting ##P_1## and ##P_2## to true will make the CNF true because the negation of ##P_2## will become true and the other clauses will also evaluate to true.
  • #1
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
  • #2
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

FAQ: Using Conjunctive Normal form to find when wff is true

What is Conjunctive Normal Form (CNF)?

Conjunctive Normal Form (CNF) is a way of structuring logical formulas in propositional logic. A formula is in CNF if it is a conjunction (AND) of one or more clauses, where each clause is a disjunction (OR) of literals. A literal is either a variable or its negation. For example, the formula (A OR B) AND (NOT C OR D) is in CNF.

Why is CNF important in determining the truth value of a well-formed formula (wff)?

CNF is important because many algorithms for solving logical problems, such as the SAT (satisfiability) problem, are designed to work with formulas in this form. Converting a wff to CNF allows these algorithms to be applied efficiently. Additionally, CNF simplifies the process of checking whether a wff is satisfiable (i.e., whether there is some assignment of truth values to variables that makes the formula true).

How do you convert a wff to CNF?

Converting a wff to CNF involves several steps:1. Eliminate biconditionals (↔) and implications (→) by rewriting them using only AND, OR, and NOT.2. Move NOTs inward using De Morgan's laws and double negation elimination to ensure that NOTs only apply to literals.3. Distribute ORs over ANDs to get a conjunction of disjunctions.This process can be complex, but it systematically transforms any wff into an equivalent CNF.

What is the role of the distributive property in converting to CNF?

The distributive property is crucial in converting a wff to CNF. It allows you to distribute OR over AND to ensure that the formula is a conjunction of disjunctions. For example, to convert (A AND B) OR C into CNF, you would use the distributive property to rewrite it as (A OR C) AND (B OR C). This step ensures that the formula adheres to the structure required for CNF.

Can every wff be converted to CNF without changing its truth value?

Yes, every wff can be converted to an equivalent CNF without changing its truth value. However, the CNF form may be exponentially larger than the original formula in some cases. Despite this potential increase in size, the CNF form preserves the logical equivalence of the original wff, meaning that the truth value of the wff remains unchanged across all possible truth assignments.

Similar threads

Replies
4
Views
1K
Replies
4
Views
1K
Replies
2
Views
2K
Replies
11
Views
2K
Replies
6
Views
1K
Replies
1
Views
1K
Back
Top