# Tag Info

### What is the $3$-SAT problem?

There are a bunch of teddy bears A, B, C, D and so on that are red on one side and blue on the other! (You choose how to color them) AND there are a bunch of 3 armed aliens with really long arms. ...

### Why does Skolemming not preserve validity?

When the existentials that are being removed in the process of Skolemization are not preceded y universals, you simply use a new constant for the respective variables. As such, consider the formula: ...
Accepted

### Why does Skolemming not preserve validity?

A sentence is valid if it is true in every interpretation of its logical language. A sentence is satisfiable if it is true in some interpetation of its logical language. Since Skolemization adds new ...
Accepted

### FOL - If two models agree on every sentence are they isomorphic?

Your intuition is exactly right - elementary equivalence (= satisfy the same first-order sentences) is not the same as isomorphism. Moreover, you're right that the place to look is cardinality ...
Accepted

Accepted

### Is Boolean Satisfiability Problem for CNF is NP? What about DNF?

Yes, for DNF it is trivial ... but note that converting a CNF into DNF is very costly: you have to do a general distribution of all terms over all terms. For example, suppose you have a CNF with $5$ ...
Accepted

### Is XOR-SAT + $2$-SAT in P?

There is no polynomial-time procedure for deciding the satisfiability of 2-SAT + XOR-SAT unless P = NP. So, probably not. 2-SAT + XOR-SAT is easily proven NP-complete by direct polynomial reduction ...

### Why does Skolemming not preserve validity?

When you Skolemize, you drop the existential quantifier in front of $f$. Every structure that is a model of the original formula can be extended by providing an interpretation of $f$. Such an ...
Accepted

### What's the meaning of "$F \models \bot$" in propositional logic?

$F \models \bot$ means that there is no valuation $v$ that satisfies the formula $F$. If $F \models \bot$, then it is vacuously true that every valuation that satisfies $F$ satisfies $G$ as well (...
Accepted

### What symbol should be used to indicate that two propositions are consistent with each other?

I'm sorry to disappoint your expectations, but the widely used notation to say that two propositions $p$ and $q$ are consistent with each other is $p,q \not\vdash \bot$ or $\text{Con}(\{p,q\})$. This ...
Accepted

### Take a 3-SAT system and compute its symmetry group, what can we say? How does this group relate to satisfiability?

It seems to me that there are two reasonable notions of "symmetry group" here. I would call them "intensional" and "extensional". Let me make this precise. Let $P$ be a ...
Accepted

### How to prove tautology

First, suppose that $\Gamma \models F$. This means that for every interpretation $I$ such that $\phi[I]$ is true for all $\phi \in \Gamma$ we have that $F[I]$ is true. In other words, there is no ...
Accepted

### Definition of a model?

See Resolution: the set $\phi$ of formulas can be read as a single formula in Conjunctive normal form, i.e. as $(a \lor b) \land (a \lor c) \land (\lnot d \lor \lnot e \lor \lnot f)$. An implicant ...

Accepted

### Expressing 3SAT clause as a 2SAT formula

Suppose you have a representation of $x_1\lor x_2\lor x_3$ as 2CNF clauses, possibly involving with hidden variables. (This would "represent" the three-way disjunction in the sense that the 2CNF is ...
Accepted

### Contradiction in Davis–Putnam–Logemann–Loveland (DPLL) Method?!

Let $\Phi$ the initial set of four clauses as above. Def 15. A pure literal is a literal $l$ that appears in at least one clause of $\Phi$ while $\lnot l$ doers not appear in any clause of $\Phi$. ...

### In satisfiability, what is the difference between the empty clause and the empty clause set?

You can get an intuition why this is so by observing that: A disjunction is true iff there exists a member which is true. In an empty disjunction (empty clause) there is no such member, so it is ...
Accepted

### How to prove that 3-CNF is satisfiable using Hall's marriage theorem?

You've already set the problem up, and the rest is a classic corollary of Hall's theorem: Every $k$-regular bipartite graph has a perfect matching. In case you are unfamiliar: here $k$-regular ...
Accepted

### First Order Logic - Logical Consequence and Paradox

When you derive the empty clause from a set of clauses that indeed means that that set of clauses is not satisfiable. However, when you try to figure out whether some statement $\varphi$ follows from ...
Do the row reduction on the augmented matrix $$\left[\begin{array}{ccc|c} 1 & -3 &2 & b_1\\ -2 & 5 &-1 & b_2\\ 3&-3 &-12 &b_3\end{array} \right]$$ instead.