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
0
votes
1answer
237 views

Convert minterm formula to nor and not formula

If I had the following equation, it is easy to convert to only NAND and NOT gates $$(A\land \neg B) \lor (C\land B) \iff (A\text{ NAND } \neg B) \text{ NAND } (C\text{ NAND } B)$$ Just replace all ...
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 \...
0
votes
2answers
343 views

Show that every well formed formula has a disjunctive and a conjunctive normal form.

If $\varphi$ is a $wff$, then there exist $\varphi^c$ and $\varphi^d$ on conductive normal form and disjunctive normal form respectively, such that $\varphi \sim \varphi^c$ and $\varphi \sim \varphi^d$...
1
vote
2answers
540 views

Converting predicate logic formulas into Skolem Normal Form

I would like to transform the following predicate logic formulas into Skolem Normal Form, simplifying them as much as possible. I am trying to show my working clearly, writing each step in a line of ...
0
votes
0answers
199 views

Convert to Conjunctive Normal Form

I am trying to covert the following to Conjunctive Normal Form (CNF) and cannot get the answer. (¬A ∨ C) → B Can anybody explain how to get the correct answer? Many thanks
0
votes
1answer
46 views

Transform a logical function into conjunctive form

For this function, i need to find the clause form for $A\Rightarrow B$ where $$A \equiv (A\land B\land \sim C) \lor (\sim A \land C)$$ and $$B\equiv (\sim A \land \sim B\land \sim C)$$ I understand ...
0
votes
1answer
414 views

Reduce the Compound Proposition to a Conjunctive Normal Form

I would like to know how to reduce the following compound proposition to a Conjunctive Normal Form please? $$(P∨Q)→(R∧(S∧T))$$
3
votes
0answers
240 views

Does every CNF formula have an equivalent 2-CNF formula?

From Wolfram MathWorld: A statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consisting of one or more conjuncts, each of which is a disjunction (OR) of one or more ...
1
vote
1answer
38 views

Why is my teacher converting CNF this way?

I am learning CNF and I have a teacher who is doing something I truly don't understand. I want to ask him later on, yet I am struggling to finish my coursework so ...
0
votes
1answer
69 views

What is the difference between (P=>Q)=>R and ((P=>Q)=>R)

Currently, I am enrolled in logic as undergraduate student. For assignment, the lecturer gave us the assignment to convert the problem in CNF. And, there were two questions: $$(P\:=>\:Q)\:=>\:R$...
0
votes
2answers
66 views

First Order Logic - Negation in embed functions

Given the First Order Logic Sentence : ¬SubsetOf((Intersection(s,t),s) where Constants : s,t are Sets and Functions: SubsetOf(.,.) , Intersection(.,.) are Sets ...
1
vote
1answer
370 views

How to determine if a propositional formula is in DNF or CNF or both

How can I determine if a propositional formula is in DNF or CNF or both. What conditions must a propositional formula satisfy? For example, why is $(a \land b)$ both in CNF and DNF?
3
votes
1answer
96 views

Transform formula to conjunctive normal form.

I need help with conjunctive normal form. Can you give me some tips? I have following formula. I did the first few steps. $$ [(p \implies q) \land (r \implies q)] \implies [( \neg q \vee \...
-2
votes
1answer
74 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
102 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
86 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 ...
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
813 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?
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) \...
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 ...
2
votes
1answer
269 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 ...
1
vote
1answer
264 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
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 ...

1 2 3