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

206 questions
Filter by
Sorted by
Tagged with
41 views

### Find Conjunctive Normal Form of a compound proposition [duplicate]

I want to find CNF (Conjunctive Normal Formula) of the following proposition: $(¬p∨¬q∨¬r)→¬ ((a→¬b) ∨q)$ My attempt: If I use the result that $p→q ≡¬p ∨q$ then $(¬p∨¬q∨¬r)→¬ (¬a∨¬b ∨q)$. Again if I ...
• 4,570
40 views

### Given a formula how can we figure out if it is CNF or DNF

Can anyone please help me understand if the following formulas are DNF, CNF, both CNF and DNF, and neither CNF nor DNF? From my understanding, CNF is a conjunction of disjunction literals and DNF is a ...
1 vote
58 views

### I've found the minimal AND-OR expression for a function, but I can't find the minimal OR-AND function

I am given a function $f(W,X,Y,Z)$ that only outputs $1$ if exactly three inputs are $1$. The AND-OR function is easy enough to find: $$W'X\,YZ + WX'YZ + WX\,Y'Z + WX\,YZ'$$ I think that function is ...
• 71
43 views

### Provide a clause set representation of a formula in CNF with a minimal number of clauses which is semantically equivalent to the KV map provided.

$KV$ map: So far I have tried brute forcing to generate a CNF formula, but that obviously doesn't give me the minimal CNF. I am left with $6$ sets with $4$ elements each and I can't simplify them. ...
72 views

### What is the Tseitin transformation of a single literal?

The wikipedia page for Tseitin transformation includes a nice example of the transform itself. In the example, it is implied that there is no need to create a fresh variable for a single literal (that ...
• 521
28 views

• 149
62 views

### How to form a CNF of following formula [closed]

We got an exercise to make a CNF out of the following formula: $$G = ((A \vee \neg B \vee C) \wedge (C \vee D)) \vee ((A \vee \neg C) \wedge (B \wedge D))$$ I've tried to make an equivalent equation ...
99 views

### Is there a "standard" normal form for formulas in linear logic?

For propositional logic, for every formula, there is an equivalent formula in the CNF and DNF. These normal forms have the advantage of being representable in a "tabular" form rather than a &...
• 300
158 views

### Resolution when CNF form has multiple conjoined disjunctive clauses

I've seen multiple examples of how resolution works when one has two disjunctive clauses with one having a negated literal present in the other clause. And when you resolve the two, you eliminate the ...
65 views

The propositional logic textbook I'm working through explains how to convert a formula in conjunctive normal form to clausal form, for instance: ((p ∨ ¬p ∨ r) ∧ (¬p ∨ ¬q ∨ r)) ∧ ((p ∨ ¬p ∨ q) ∧ (¬r ∨ ¬...
39 views

### Trouble with converting the negation of a formula to CNF

I'm trying to convert the negation of the following formula to CNF: (p → (q → r)) → ((p → q) → (p → r)) These are the steps I am following: ¬((p → (q → r)) → ((p → q) → (p → r))) ¬(¬(¬p ∨ (¬q ∨ r)) ∨ (...
93 views

### CNF form of the logical $exactly(2) x_{i}$

Let's say, in order to linearize the product of the two binary variables the logical condition would be, z <=> (x and y), where x, y, and z are binary. The corresponding CNF form is as follows: \...
• 149
124 views

### Any proposition is equivalent to a formula in CNF.

A proposition is said to be in conjunctive normal form (CNF) if it is $\land_{i=1}^{k}\lor_{j=1}^{n} \psi_{ij}$ where each $\psi_{ij}$ is either an atom or is the negation of an atom. Show that any ...
1 vote
42 views

### How to define disjunctive normal form and conjunctive normal form?

The question is here: (1) Obtain the disjunctive normal form of $(p\to q)\to(q\to p)$ (2) Obtain the conjunctive normal form of $(p\to q)\to(q\to p)$ I obtain the form $\lnot q\lor p$. Is it a ...
1 vote
432 views

### How to convert this CNF to a DNF?

(((p ∨ q) ∧ (¬q ∨ ¬r)) ∧ (¬p ∨ r)) I know we can use a truth table, but I'm trying to convert by equivalences. It seems like it will blow up, but I may be doing this wrongly. Could someone let me know ...
113 views

### Prove 20-3-SAT is NP-Complete

so I have this problem that I can't figure out. 20-3-SAT={All satusfiable 3-CNF formulas where each variable appears at most 20 times} I was able to prove it's in NP using verifier, but for NP-Hard ...
• 189
1 vote
286 views

### Duality in Disjunctive Normal Form and Conjunctive Normal Form

In my understanding, duality $s ^{*}$ of a compound proposition $s$ is obtained by replacing each $\vee$ to $\wedge$, each $\wedge$ to $\vee$, each $T$ to $F$, and each $F$ to $T$. I have been looking ...
• 143
52 views

### At most $k$ contiguous $\mbox{true}$ values in a Boolean array using SAT

Given an integer $k > 0$ and a Boolean array $A$ of length $n$, find a simplified and efficient CNF formula to ensure that there is not more than $k$ contiguous $\mbox{true}$ values in this array. ...
• 1,254
143 views

### Is there a method to solve 3SAT problems using loss function?

Loss function seems to be used to solve optimization problems. I assumed that 3SAT problems can be treated as them. I would like to know whether there is a good loss function that is defined by ...
1 vote
122 views

### I'm studying boolean algebra in the discrete mathematics

problem Let $a_4a_3a_2a_1a_0$ be a 5- bits binary numbers (each $a_i=0$ or $1$). Write an expression in Boolean algebra that evaluates to $1$ when odd number of bits of the number is $1$ and $0$ ...
• 159
233 views

### Why doesn't Krom's method apply to solving the 3SAT in polynomial time?

In the paper "The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary", Krom suggested a method to solve 2SAT problem. My understanding is this. Use ...
64 views

380 views

### How do I re-write this propositional formula in conjunctive normal form (CNF)?

I'm struggling with this problem -- though it would seem simple enough. I think it's the parentheses that are getting me confused here. I need to convert (p→(q⋁r))⋁(s↔t) to conjunctive normal form (...
• 103
1 vote
44 views

### Conjunctive Normal Form of a clause

Can the following clause be converted to conjunctive normal form? If so how? $$(a \implies b) \implies (c \implies d)$$ I tried applying DeMorgans laws and am unable to get the result.  (a \...
• 1,079
1 vote
174 views

### Help with Resolution Refutation Problem

I'm trying to convert Solve a Resolution Refutation problem. The problem states: Knowledge Base is ∀𝑥𝑦 𝐹(𝑥, 𝑦). Prove using resolution-refutation that ∀𝑥𝑦 𝐹(𝑦, 𝑥). Note: β = F(y, x) This ...
• 11
24 views

### expanding disjunctive pairs of conjunctives using distributive law

I am having a bit of a brain malfunction. I am working through a functional programming class and I am trying to in parallel fake some knowledge of discrete mathematics. I am working through a simple ...
236 views

### Can clause normal form include true/false constants?

As Wikipedia puts it, ... the only propositional connectives a formula in CNF can contain are and, or, and not. The not operator can only be used as part of a literal, which means that it can only ...
• 245
289 views

### How to get CNF of propositional formula form DNF of its complement?

Explain how to read off a CNF for propositional formula directly from a DNF from its complement. I've managed to explain it in words, but can't write a rigorous proof of that. How to show this in ...
148 views

### Generalisation of DNF to CNF for DNF of m choose l clauses

Given two values $m$ and $l$, I can create corresponding DNF formula which is a disjunction of all $m \choose l$ combinations, where each number corresponds to a variable. Each combination is, in ...
1 vote
334 views

### The Explanation on how to form CNF

I am currently reading Logic in Computer Science Modelling and Reasoning About Systems (by Michael Huth & Mark Ryan). They introduced a fairly easy way to form conjunctive normal form (CNF) of an ...
• 39
189 views

### HORN algorithm - clarity needed

I have been spending some time studying the HORN algorithm, but my textbook, as well as most posts online, are quite vague around the steps taken. These are the steps from my textbook: My questions: ...
672 views

### How to introduce conjunctions into a conditional statements so as to get the CNF and DNF?

I have the following conditional statement: ((p → q) → p) → p Knowing that CNF is a conjunction of disjunctions (and that DNF is a disjunction of conjunctions), we will obviously have to introduce ...
135 views

### Converting propositional logic formula to CNF

I have been trying to do this all day but I am not getting anywhere with it, could anyone help me? My formula is r → (p ↔ ¬q) And I want to convert it into CNF ...
142 views

### Dominant set of a Graph - Convert to Conjunctive Normal Form

I am supposed to convert this problem to a Satisfiability Problem in Conjunctive Normal Form, but I have no idea how. The Problem: Determine, if there exists any dominant set for a Graph $G$ ...
• 13
### Converting $3$-variable truth table to 3CNF
I have a truth table for length $3$ binary strings, say $110$ and $001$ map to $1$ and everything else to $0$. Is there an an algorithm to represent this table as a 3CNF which is satisfied only by \$...