Efficient Algorithm for Solving CNF/DNF Logic Problem with 9 Input Literals

  • Thread starter DrAlexMV
  • Start date
  • Tags
    Logic
In summary: In CNF, every clause has three literals. These three literals are known as the left-hand side, the right-hand side, and the head. In DNF, every term has three literals. These three literals are known as the head, the left-hand side, and the right-hand side. The head is the first literal in a term, the left-hand side is the second literal in a term, and the right-hand side is the third literal in a term.
  • #1
DrAlexMV
25
0

Homework Statement



There exists a function f. Assume that you are given f's CNF representation and f's DNF representation. The CNF representation has some number of clauses, and each clause has 3 literals. The DNF representation has some number of terms where each term has 3 literals. The CNF representation and the DNF representation correspond to the same function f. Now you are also given an input x = x_1,...,x_n. Give an algorithm for determining f(x) (either T or F) that only looks at 9 literals within x.


Homework Equations



Just the definition of CNF and DNF

The Attempt at a Solution



CNF is formatted such as: (A and B and C) or (D and E and F).
DNF is formatted such as: (A or B or C) and (D or E or F).

Somehow since you only need to look at one literal in a term of the CNF to know whether that term will be false, you can look also look at that same literal in the DNF to see if that term will be true in the DNF.

I am not sure what else to do.
 
Physics news on Phys.org
  • #2
DrAlexMV said:

Homework Statement



There exists a function f. Assume that you are given f's CNF representation and f's DNF representation. The CNF representation has some number of clauses, and each clause has 3 literals. The DNF representation has some number of terms where each term has 3 literals. The CNF representation and the DNF representation correspond to the same function f. Now you are also given an input x = x_1,...,x_n. Give an algorithm for determining f(x) (either T or F) that only looks at 9 literals within x.


Homework Equations



Just the definition of CNF and DNF

The Attempt at a Solution



CNF is formatted such as: (A and B and C) or (D and E and F).
DNF is formatted such as: (A or B or C) and (D or E or F).

Somehow since you only need to look at one literal in a term of the CNF to know whether that term will be false, you can look also look at that same literal in the DNF to see if that term will be true in the DNF.

I am not sure what else to do.

What do CNF and DNF mean?
 
  • #3
Disjunctive normal form and Conjunctive normal form
 

FAQ: Efficient Algorithm for Solving CNF/DNF Logic Problem with 9 Input Literals

What is CNF/DNF logic problem?

CNF/DNF logic problem refers to a type of logical problem in which the given statements are represented in either Conjunctive Normal Form (CNF) or Disjunctive Normal Form (DNF). These are two standard forms used to represent logical statements, where CNF consists of a conjunction of clauses and DNF consists of a disjunction of clauses.

What is the purpose of using CNF/DNF logic problem?

The purpose of using CNF/DNF logic problem is to simplify and analyze complex logical statements. By converting the statements into either CNF or DNF form, it becomes easier to identify patterns and inconsistencies in the logic. This is particularly useful in fields such as computer science and artificial intelligence.

What are the differences between CNF and DNF?

The main difference between CNF and DNF is the way logical statements are represented. In CNF, the statements are expressed as a conjunction of clauses, where each clause is a disjunction of literals. In DNF, the statements are expressed as a disjunction of clauses, where each clause is a conjunction of literals. In simpler terms, CNF focuses on the common elements among the statements, while DNF focuses on the differences.

What are the advantages of using CNF/DNF logic problem?

One of the main advantages of using CNF/DNF logic problem is that it allows for easier analysis and manipulation of complex logical statements. It also helps in identifying patterns and inconsistencies in the logic, making it useful in fields such as computer science and artificial intelligence. Additionally, converting statements into CNF or DNF form can also help in simplifying and reducing the complexity of logical problems.

What are some examples of CNF/DNF logic problem?

An example of CNF logic problem could be "(A ∨ B) ∧ (¬A ∨ C)". This statement can be simplified by converting it into CNF form, which would result in "(A ∧ ¬A) ∨ (A ∧ C) ∨ (B ∧ ¬A) ∨ (B ∧ C)". An example of DNF logic problem could be "(A ∧ B) ∨ (¬A ∧ C)". Similarly, this statement can be simplified by converting it into DNF form, which would result in "(A ∨ ¬A) ∧ (A ∨ C) ∧ (B ∨ ¬A) ∧ (B ∨ C)".

Similar threads

MHB Please help with bool algebra and logic things
Replies
2
Views
1K
Comp Sci Complexity for generating strings of length k from CNF grammar
Replies
3
Views
1K
Solve 3x3 Matrix Equation: x, y, z Variables
Replies
4
Views
2K
The integral of a function ##f(x)## from its graph
Replies
15
Views
2K
Fourier Series Coefficient Symmetries
Replies
8
Views
2K
Base 8 Logic Puzzle: Finding Solutions to Divisibility Rules
Replies
9
Views
2K
Extreme value theorem, proof question
Replies
12
Views
2K
MHB Representation of signed integers of base B
Replies
17
Views
1K
Is the function v(r) = (e^(-mr))/r a solution to the Yukawa PDE equation?
Replies
1
Views
1K
Solve Complex Integral: Find Residues & Singularities
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top