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