Questions tagged [conjunctive-normal-form]

A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals.

Filter by
Sorted by
Tagged with
-2
votes
1answer
72 views

Coverting clauses to CNF [closed]

How would I start converting these given clauses: p ∧ q, p ∧ ¬q, ¬p ∧ q, ¬p ∧ ¬q to CNF?
0
votes
0answers
57 views

How does checking for CNF satisfiability by going via DNF compare to using a truth table or DPLL?

In terms of efficiency, I know DPLL would be most efficient, and probably going via a DNF would be least efficient, but my question is asking for reasons why and trying to understand by how much?
0
votes
2answers
41 views

Conjuction big sign

I have a difficult time understand how 1: this large conjunction and disjunction symbols relates to that simpler, same conjunction expression.What these big conjunction and disjunction symbols mean?
0
votes
1answer
97 views

Some confusing steps with Resolution by refutation FOL

Here is the thing.. There are two step that confuses me In the famous example "Everyone who loves all animals is loved by someone etc..." We need to prove that who killed the cat "curiosity or jack" ...
0
votes
0answers
85 views

How to turn this formula into CNF?

This formula $$(p \land q) \lor ( \neg q \lor r) \land ( \neg p \lor r)$$ has the CNF $$(\neg p \lor q \lor r) \land ( p \lor \neg q \lor r)$$ I understand how CNF works, but I can't seem to ...
2
votes
0answers
4k views

Converting DNF to CNF and vice versa

I am fairly confident of the definition of CNF and DNF (e.g. why $ (P \land Q)$ in both CNF and DNF. However, I'm a little shaky when it comes to converting between the two normal forms. Is it ...
4
votes
1answer
795 views

Is the minimal conjunctive normal form for positive formula unique? If so, how do you calculate it?

I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms. $$A$$ $$A \land (A \lor B)$$ The minimal example is $A$. Does ...
1
vote
1answer
779 views

Show that this formula is a tautology by converting to CNF

I'm working through some refutation proof questions for propositional logic, and I've come across the following question: Show that the following formula is a tautology by negating it and then ...
0
votes
1answer
49 views

Optimal assignment for an unsatisfiable formula

Given an unsatisfiable formula $F$ in CNF, are there any methods to find an assignment that can satisfy as many clauses as possible?
2
votes
1answer
96 views

CNF Conversion and one $2015$ exam questions?!

if $\text{likes}(x,t)$ means that person $t$ likes food $x$, and $\text{food}(x)$ means $x$ is a food, $\text{CNF}$ of sentence "No food is liked by all person", and $F$ is Skolem function. The ...
4
votes
1answer
522 views

Turning CNF into DNF

I have a formula $(L\Leftrightarrow (A\vee J))$ and I am to turn it into DNF and CNF. When I use de Morgan rules and so on, the formula looks like $(L\Rightarrow (A\vee J))\wedge ((A\vee J)\...
1
vote
2answers
1k views

Convert form from CNF to DNF

I have a few question about converting forms to DNF, CNF and from CNF to DNF. 1) How can I convert this to DNF $(p \vee q) \wedge (q \vee \neg r) $ 2) How can I convert this to CNF $(p \wedge q) \...
0
votes
1answer
5k views

Difference between DNF and CNF

I'm stuck on this particular question: Let $A$ be the following propositional formula $$(\lnot p \rightarrow q) \leftrightarrow\ (\lnot q \rightarrow \lnot r)$$ Find a propositional formula $B$ in ...
0
votes
1answer
1k views

Reduction from Circuit-Sat to 3-Sat

I'm reading the following notes on reduction from circuit-sat to 3-sat http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf On the third page i'm unsure how they arrived at the following In ...
1
vote
1answer
6k views

Disjunctive normal form (BOTH dnf and cnf) example help

Consider $$T \vee ( \neg x \wedge y ) \vee ( x \wedge y )\tag{1}$$ In class we went over examples of how many things can be both DNF and CNF... e.g., $(\neg z) \vee y$ can be thought of as both $...
1
vote
1answer
262 views

Conversion to CNF - eliminate implications

On the web I found a solution to an exercise on resoulution. Basically, it asks to use resolution refutation to prove $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P ...
-1
votes
2answers
583 views

Conversion of disjunctive normal form to conjunctive normal form

Explain how $ (p \lor q \lor r \lor s) $ can be re-written into an equivalent CNF formula such that each clause contains exactly $3$ variables or negations of variables.
2
votes
1answer
268 views

Write $(p\land q)\leftrightarrow (\neg p\lor \neg q)$ in CNF

I need to convert the below for a homework question and I am not entirely sure if it's correct. The last part is that I am not sure how to use the distributive laws in this scenario. Any guidance ...
12
votes
4answers
63k views

Find DNF and CNF of an expression

I want to find the DNF and CNF of the following expression $$ x \oplus y \oplus z $$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...
3
votes
3answers
2k views

Apply equivalence rules to convert to CNF

I am having trouble seeing how I could apply the equivalence rules mentioned here to the following formula in order to convert it into Conjunctive Normal Form (CNF). $$(p \wedge q) \vee (\neg p \...
3
votes
2answers
3k views

From DNF to CNF

What is the most efficient way to switch from DNF to CNF?.
3
votes
3answers
8k views

Every sentence in propositional logic can be written in Conjunctive Normal Form

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question: Any propositional logic sentence is logically equivalent to ...
1
vote
1answer
1k views

First order logic, CNF

What steps do I need to follow to convert the next statements into CNF? Wich are the resulting clauses? $H \leftrightarrow C \vee D$ $R \rightarrow \neg D$ $R \wedge H$ $H \leftrightarrow C$ Thank ...