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

173 questions
Filter by
Sorted by
Tagged with
19 views

### Integral involving the multivariate normal

Let $X$ be a random vector such that $X|\alpha\sim N_p(\alpha\mu,\Sigma)$ (ie $X$ given $\alpha$ follow a $p$ variate normal distribution with pdf $p(x|\alpha)$), where $\mu$ is the vector of means ...
42 views

### Given KB as follows: $P \lor Q$, $Q \Rightarrow (R \wedge S)$, $(P \lor R) \Rightarrow U$. Check whether $U$ is entailed by $KB$ using PL-Resolution. [closed]

Given a knowledge base as follows: $P \lor Q$, $Q \Rightarrow (R \wedge S)$, $(P \lor R) \Rightarrow U$ Check whether $U$ is entailed by $KB$ using PL-Resolution. No Sentences Explanation 1 P ∨ Q ...
89 views

### what does this notation mean

If $p_1, p_2, ⋯, p_n$ are $n$ propositions, explain why $$\bigwedge_{i=1}^{n-1}\bigwedge_{j=i+1}^n(\lnot{p_i}\lor\lnot{p_j})$$ is true iff at most one of $p_1, p_2, ⋯, p_n$ is true. My questions are: ...
39 views

### How do I expand this sigma/summation notation?

I don't know if it's correct to refer to this as summation notation since the operation is not addition so please correct me if that's inaccurate. How do I expand this notation? I believe it's for <...
23 views

58 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 ...
15 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 ...
18 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 ...
29 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 ...
51 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 ...
56 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 ...
28 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: ...
32 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 ...
26 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 ...
49 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$ ...
42 views

### Explain into disjunctive normal form

Can anyone tell me how to Express the following formula into disjunctive normal form ⌐ (p V q) ↔ (p ^ q). I have done few steps but I need your help.
30 views

29 views

### DNF to CNF of a simple expression

I have a formula like this: $$\bigvee_{\substack{i \in [1,...,m] \\ j \in [1,...,m]}} x_{i} \wedge x_{j}$$ What is the equivalent formula in CNF (conjunctive normal form)?
53 views

### Is the following boolean expression a tautology?

I have the following boolean Expression: ...
53 views

### CNF formula for manipulating words

I am trying to create CNF formula for manipulation of a word. word is a sequence of letters from a $\Sigma$ alphabet. A word is encoded by variables like $x_{i,a}$ which means that the letter $a$ is ...
29 views

### CNF for modilisation of a word

Imagine that we are interested in problem of words. A word is a sequence of letters from a $\Sigma$ alphabet. For encoding a word in SAT we are using variable like $x_{i,a}$ which means that in ...
63 views

### Converting a 4cnf clause into one with not all equal literals

Given a 3cnf clause $$(a \lor b \lor c)$$ we can construct an equivalent conjunction $$(a\lor b\lor d) \land (\lnot d \lor c \lor \bot)$$ such that the second clause has a valid truth assignment if ...
71 views

### Is it possible to get from a propositional formula a CNF with clause (¬A ∨ ¬B ∨ ¬C), if formula doesn't have negations in it?

If i have a propositional formula consisting of conjunctions, disjunctions and implications and no negations of three literals $A, B, C$, is it possible to get a CNF from that formula which include ...
85 views

### Apply resolution algorithm to check SAT for CNF

I have a CNF: $$(\neg p \lor \neg q \lor r) \land (\neg p \lor \neg r) \land p \land q$$ I need to check SAT for it using resolution algorithm, but i don't know how. I know how to check it with truth ...
41 views

112 views

### CNF and DNF form of single logical variable

I am learning boolean algebra. So apologies for this naive question. During our discussion among friends, we came across following puzzle, How can I convert following statement into CNF and DNF?  ...
61 views

### First order logic translation from the sentence “Nobody who loves every dog loves any armadillo.”

i'm new to first order logic and i'm having some confusion with translating the sentence above. My solution for the sentence is : ∀x ∀y ∀z ((DOG(y) ∧ LOVES(x, y) ∧ ARMADILLO(z)) → ¬LOVES(x, z)) (1) ...
89 views

### First Order Logic: How to transform to prenex conjunctive normal form and Skolem form?

This is the sentence that needs to be transformed: ∃x∀y(Ax → (Bxy ∨ ¬Cy)) → ∀x∃y(Py → Qyx) I have gotten to the point where I eliminated all occurrences of → and imported all negations inside all ...
93 views

### CNF-SAT is NP-complete if and only if CNF-UNSAT is co-NP-complete?

I have shown that a language $A$ is NP-complete $\iff$ its complement $\overline{A}$ is co-NP-complete. Also, I have shown that CNF-SAT is NP-complete. Since UNSAT is the complement of SAT, then ...
336 views

### CNF unsatisfiability NP-complete?

I have two problems, CNF-SAT and CNF-UNSAT, that decide if a formula $\phi$ on Conjunctive Normal Form is satisfiable and unsatisfiable, respectively. I have already shown that CNF-SAT is $NP$-...
Are we allowed to resolve two variables at a time in CNF resolution? For e.g. we have: what will be the resolution of: $(P \lor \lnot Q \lor R) \land (\lnot P \lor Q \lor R)$ and what will be the ...