# Tagged Questions

For questions on the subject of "satisfiability", that is, whether there exists an interpretation/model in which a given (logical) formula is true.

31 views

### Prove $\neg(p=q)$ satisfiability [on hold]

I am trying to prove using a $Herbrand$ model that, given 2 different expressions $q$ and $p$, $\neg(p = q)$ is satisfiable. How can this be proven?
19 views

### is this k-SAT or 3-SAT reduction?

On introduction to the theory of computation - 2nd edition by Michael Sipser, there's this question with the solution: Question: "7.31: In the following solitaire game, you are given an m x m board. ...
82 views

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

As we see on page $10,11$ and $12$ on Google Books we know about Unit Clause (UC) and Pure Literal (PL) in DPLL Algorithms. in the following example if assign value $0$ to variables is prior to ...
29 views

70 views

### How to Solve Boolean Matrix System?

I have a Boolean Matrix System (BMS) as described below $$Ax=c$$ where $A$ is a $n\times n$ Boolean matrix (i.e., all entries are either 0 or 1), $c$ and $x$ are two $n$-dimensional Boolean column ...
18 views

### Showing a reduction between decision problems

I asked a similar question on cs.stackexchange, but I'd like to ask it a tad more specifically, and thought this would be a better place for it. I'm looking through a text on logic, and the problem is ...
46 views

304 views

### reduction from 3sat to 3 dimensional matching.

I've been reading about the standard reduction from 3sat to 3DM and my question was regarding the 'clean up gadgets'. So suppose i take an instance of 3-Sat with $n$ variables and $k$ clauses. Once we ...
50 views

### Is $P^{SAT}$ equal to NP $\cup$ co-NP?

I have following problem: Is $P$ with a $SAT$ oracle equal to $NP \cup coNP$ assuming that $NP \neq co-NP \neq P$? I can show that $NP \subseteq P^{SAT}$ and $coNP \subseteq P^{SAT}$. But it is much ...
113 views

### Rule of inference - Biconditional proposition

I'm having trouble with one of the questions given as an assignment which is to prove: $$(p\land q)\leftrightarrow(r\land s), \neg r\land q \vdash \neg p$$ I guess I should use proof by ...
82 views

### What is satisfiable by a reduct of a model is satisfiable by the original model (and vice versa)?

My professor told me that any formula that is satisfiable by a reduct of a model is satisfiable by the model it is a reduct of, and vice versa (as long as the formula is interpretable on the reduct(?))...
49 views

### Proof by contradiction that $P \rightarrow Q$ is true

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. So let's say the statement can be expressed by $P \rightarrow Q$. To prove that this statement is true, we look at the assumption ...
87 views

### Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable.

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. Okay can prove this by contradiction. So we say that a tableau $\tau$ is $\textit{satisfiable}$ iff there exists an ...
59 views

### Interpretation and truth table is enough to showing validity or a better way?

I'm so glad that find this useful site. anyway, I ran into some challenging ways to find a formula is valid. Here is two example in my note that called valid. I ran into such a problem with making ...
89 views