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

189 questions
Filter by
Sorted by
Tagged with
13 views

33 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,242
15 views

### Number of distinct unsatisfiable 3CNF formula consisting of n variables

I'm interested to know if anyone knows the number of unsatisfiable 3SAT formulae in CNF consisting of $n>3$ variables. Specially, formulae where no clause contains the same literal twice, either ...
24 views

### Converting First-Order Logic to CNF

I am having a lot of trouble using the rules of converting First-Order Logic to CNF. I have this statement: ∀x∃y : ([P(x, y) → Q(y, x)] ∧ [Q(y, x) → S(x, y)]) → ∃x∀y : [P(x, y) → S(x, y)] After ...
1 vote
66 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
63 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$ ...
• 55
51 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 ...
32 views

33 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 (...
1 vote
33 views

91 views

### Find conjunctive normal form of propositional formula

I need to find conjunctive normal form (CNF) of this propositional formula: $$\lnot((p \implies (q \implies r)) \implies ((p \implies \lnot r) \implies (p \implies \lnot q)))$$ How could i do that? I ...
502 views

### Ways to write CNF for an implication with disjunction?

I have the following statement before it's converted to CNF: p → (s ∨ q). When I initially convert this to a CNF, I get the following: ¬p ∨ (s ∨ q). I'm wondering if I could use laws of associativity ...
52 views

### How to convert $(A \vee B) \wedge (C \vee D)$ to CNF?

Wikipedia states that all propositional logic statements can be transformed into CNF. However, I'm not so sure how we can further simplify $(A \vee B) \wedge (C \vee D)$? Or if this is CNF, why is it ...
• 322
1 vote
659 views

### Calculus 1: Limits at negative infinity of quotients with square root, why introduce a negative when trying to simply

Why do we introduce a negative when trying to simplify? (circled in orange) If x approaches -$\infty$ for both, the negative sign should cancel out..? Khan acad's working: Edit, removed my workings ...
• 643
73 views

• 605