Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [propositional-logic]

The tag has no usage guidance.

3
votes
1answer
130 views

Is there a known way to convert any $QBF_2$-formula into an equisatisfiable $QBF_2$-formula in CNF in polynomial time?

It is easy to turn any boolean formula and any quantified boolean formula into an equisatisfiable formula in CNF using Tseitin transformation: $$ Q_1 z_1 Q_2 z_2 \ldots Q_n z_n \Phi \Rightarrow Q_1 ...
1
vote
0answers
59 views

Efficiently decidable logics

So propositional logic (PL) is efficiently (in P) decidable because I can convert formulas to an equisatisifiable CNF-formula, negate and convert (efficiently, by De Morgans laws) to DNF. I can then ...
0
votes
1answer
58 views

If $F$ is valid then $F \cup \{res(C_1,C_2,A_i)\}$ is valid

I have to prove the following problem in propositional logic: Let $F$ be a set of clauses and let $F' = F \cup \{res(C_1,C_2,A_i)\}$ be the extension of $F$ by a resolvent of some clauses $C_1,C_2 \...
3
votes
2answers
442 views

Getting a variable assignment of a Tseitin transformed formula

Let $\phi$ be a Boolean formula and $\mathrm{Tseitin}(\phi)$ the corresponding Tseitin transformed equisatifiable formula. It is well-known that one can get a variable assignment for $\phi$ by ...
3
votes
1answer
219 views

FP^NP-complete problems

Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?
3
votes
1answer
68 views

Can a propositional threshold connective be expressed by standard connectives?

We are given a finite set of propositional atoms $\{x_1, \dots, x_n\}$ and an integer $k$. Can we capture through a propositional formula $\varphi$ (built from the standard connectives $\neg, \wedge, \...
2
votes
0answers
53 views

What is the difference between the situation calculus and the propositional logic of context?

I have been reading a lot of papers by John McCarthy lately. As early as 1963, he developed the situation calculus, but then starting in 1987, he developed what came to be known as the propositional ...
-1
votes
1answer
521 views

Resolution refutation [closed]

This is an assignment so I don't want the answer, just maybe a push in the right direction. The question is: Suppose you are given an algorithm $R$ that can test for any propositional formula in ...
0
votes
1answer
37 views

Prove the existence of a proposition logical formula so that following conditions are fulfilled

For two proposition logical formulas $\phi$ and $\chi$ so that $\phi\implies\chi$ is generally valid. How can I prove that there is a formular $\psi$ with $var(\psi )\subseteq var(\phi )\cap var(\chi )...
0
votes
1answer
676 views

Meaning of empty clause

Why does the empty clause is logically equivalent to a contraddiction: $\square \cup \square \Longleftrightarrow \perp$ and why the empty cube is logically equivalent to a tautology: $\square \cap \...
1
vote
2answers
93 views

Using the rules of inferences

I know the rules of inferences and logical equivalence but I cannot seem to validate this argument. I rewrote the first premise as $\neg p\vee q$ other from that I am stuck. Any help will be ...
3
votes
1answer
238 views

Propositional logic — syntactical completeness

Lets consider propositional logic. We say a proof system for propositional logic is syntactically (negation) complete if for every $\alpha$, either $\alpha$ or $\neg \alpha$ are provable within the ...
1
vote
5answers
228 views

Real life description for (~A->A)->A

It can be shown that the logical preposition [ :- (~A->A)->A ] is a theorem (always true). I want to know if anybody knows a real life description for the preposition above? I mean an expression in ...
1
vote
1answer
68 views

Satisfiabilty 2-sat

Im trying to work out whether the following clause is satisfiable: {x, y},{x,¬y},{¬x, y},{¬x,¬y},{x, z},{x,¬z},{y, z},{y,¬z} My basic understanding is to work ...
1
vote
0answers
87 views

Propositional logic of arguments and undercuts [closed]

The setting An argument from a set of formulas $\Delta$ is a pair $\langle \Phi, \alpha \rangle$ such that $\Phi \subseteq \Delta$ $\Phi \nvdash \bot$ $\Phi \vdash \alpha$ (this is what I am ...
2
votes
1answer
535 views

3-coloring a graph with propositional formulas

I am trying to tackle a specific problem so any help would be greatly appreciated: Let $G = (V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. A 3-coloring of $G$ is a map $\chi:V\...
1
vote
4answers
249 views

How can I prove $P \rightarrow (Q \rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
5
votes
2answers
462 views

P, Q, ((P→Q)→R) ⊢ R using only modus ponens

Can $R$ be inferred from $P$, $Q$, and $(P \to Q) \to R$ using only modus ponens? My understanding is that it can, as shown below, but I was told this was incorrect. Proof of ${P, Q, (P \to Q) \to R} ...
2
votes
3answers
1k views

Resolution and what it means to derive the empty set

When using resolution, if the empty set {Ø} is derived from a formula like {¬x,¬y} {x,y}, does that mean the formula is unsatisfiable? If this is the case, why is ...