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
0answers
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 ...
-1
votes
1answer
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 ...
2
votes
2answers
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: ...
0
votes
0answers
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 <...
0
votes
1answer
23 views

Find the CNF of the following formular

I am looking at the CNF of $((A \to B) \to (B \to A)) \to A$. For this I tried the following: $${\quad((A \to B ) \to (B \to A)) \to A\\ \equiv ((\neg A \vee B) \to (\neg B \vee A) \to A \\\equiv (\...
0
votes
1answer
24 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 (...
0
votes
0answers
22 views

Convert $\displaystyle \phi \lor \overline{\phi }$ expression to CNF

Suppose $\displaystyle \phi $ is a bolean expression of CNF form, I create a new bolean expression as: $\displaystyle \phi \lor \overline{\phi }$. Where the $\displaystyle \overline{\phi }$ is a ...
1
vote
1answer
25 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
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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: ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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$ ...
0
votes
1answer
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.
0
votes
1answer
30 views

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 $...
0
votes
1answer
26 views

How to prove that a given disjunctive or conjuctive normal form is minimal?

what is the argument that a given canonical normalform cannot be reduced any further? For example have a look at this $dnf(f) = (\neg a \wedge b \wedge c) \vee (a \wedge \neg b \wedge c) \vee(a \...
0
votes
1answer
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)?
0
votes
1answer
53 views

Is the following boolean expression a tautology?

I have the following boolean Expression: ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
2answers
41 views

Can I rewrite propositional formula in this way?

I have a propositional formula: $$(\neg p \lor \neg q \lor r)$$ Can i rewrite it in this way?: $$(\neg p \lor \neg q \lor r) = (\neg p \lor (q \land \neg r))= (\neg p \lor q) \land (\neg p \lor \neg r)...
-1
votes
1answer
64 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 ...
0
votes
1answer
163 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 ...
-1
votes
1answer
37 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 ...
1
vote
3answers
189 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 ...
0
votes
3answers
64 views

Why is $P \rightarrow Q$ equivalent to $\lnot P \vee Q$ in propositional logic CNF? [duplicate]

According to wikipedia, when we compute the CNF of propositional logic, we substitute $P \rightarrow Q$ with $\lnot P \vee Q$. However, it seems to that when $P$ is False and $Q$ is True, then $P \...
0
votes
1answer
24 views

Is there an algorithm for reducing CNFs further

I have a boolean formula in conjunctive normal form (CNF): $(a\vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge (x \vee y)$ I know that this can be simplified to: $(a\vee b)\wedge (x \vee y)$. a) Is ...
1
vote
1answer
161 views

How to obtain the empty clause from CNF?

I have the following formula $\mathcal{F} = A(c, y) \wedge A(c, z) \wedge \neg E(c, z) \wedge \neg A(z, c)$ from which I've derived the clauses $\{A(c, y)\},\{A(c, z)\},\left\{\neg E\left(c, z_{1}\...
0
votes
1answer
52 views

Need help for turn this form $\neg ((p \Rightarrow q) \Rightarrow r)$ into DNF

How can I turn this form $\neg( ( p \Rightarrow q ) \Rightarrow r )$ to disjunctive normal form and to the disjunctive normal form fully developed ? I have done the truth table see below I ...
2
votes
0answers
110 views

How can I find the CNF of ($A$ and $B$ or $C$) and ($B$ or not $C$) using a Karnaugh map?

$$(A\land B \lor C) \land (B \lor \lnot C)$$ I know how to create the truth table and Karnaugh map of a logic expression. But I couldn't find exactly how to calculate the simplified CNF of it using ...
0
votes
1answer
61 views

What is the conjunctive normal form for $(\neg Q\land P) \lor (\neg Q\land R) \lor (\neg P \land \neg R)$

$(\neg Q\land P) \lor (\neg Q\land R) \lor (\neg P \land \neg R)$ i have calculated this using wolframalpha and the output of CNF was $(\neg Q \lor\neg P) \land (\neg Q \lor\neg R) $ but all i ...
1
vote
1answer
108 views

Conjunctive Normal Form evaluates true when atleast half of the clauses are true.

This is an Exam question. Which of the Following is TRUE about formulae in Conjunctive Normal form? -For any formula, there is a truth assignment for which at least half the clauses evaluate true. -...
1
vote
1answer
74 views

Simplify the given boolean expression into the "Canonical Conjunctive Normal Form“.

Simplify the boolean expression, into the “Canonical Conjunctive Normal Form": $$x_0\overline{x_0} + x_1\overline{x_1} + \overline{x_2}+x_3$$ Here's my attempt: $$\begin{align} x_0\overline{x_0} ...
1
vote
1answer
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? $$ ...
0
votes
1answer
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) ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
1
vote
2answers
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$-...
0
votes
1answer
49 views

Can we resolve two variables at a time in CNF resolution

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 ...
1
vote
1answer
64 views

Convert $A⟺B⟺C$ into Conjunctive Normal Form.

Eliminate implications and bi-conditionals using formulas: $A⟺B⟺C$ Attempt: $≡ (A⟹B)∧(B⟹A)⟺C$ $≡ (((A⟹B)∧(B⟹A))⟹C)∧(C⟹((A⟹B)∧(B⟹A)))$ $≡ ¬((A⟹B)∧(B⟹A))∨C ∧ ¬C∨((A⟹B)∧(B⟹A))$ $≡ ¬((¬A∨B)∧(¬B∨A))∨C ...
2
votes
2answers
103 views

Converting to conjunctive normal form?

How to convert to conjunctive normal form? If i have a formula: $(\neg Q\land P) \lor (\neg Q\land R) \lor (Q \land \neg P \land \neg R) \lor (\neg P \land \neg R)$ The formula is in disjunctive ...
0
votes
1answer
31 views

How many subsets of size $n$ in $S=\{x_1,\dots ,x_{2n}\}$ under restrictions

Let $S=\{x_1,\dots ,x_{2n}\}$. How many subsets of size $n$ are in $S$ such that $\forall1\le i\le n: x_i$ and $x_{n+i}$ are not in the same set. I ran into this problem when thinking how many ...