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.

123 questions
Filter by
Sorted by
Tagged with
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?
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?
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?
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" ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
522 views

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 ...