# Questions tagged [propositional-logic]

The tag has no usage guidance.

133 questions
Filter by
Sorted by
Tagged with
31 views

### Complexity of negation cancellation

Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. Notation: $| \alpha |$ is the length of formula $\alpha$. We are given a formula $\phi$. Cancel all cancellable ...
19 views

### Significance of quantifier ordering in quantified boolean formulas (kQBF vs. QBF)

I am studying solvers of quantified boolean formulas (QBF) as a generalization of SAT solving. The standard DIMACS format of SAT specification is extended to QDIMACS, which adds "a ..." and "e ..." ...
38 views

### Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity?

I am reading the naive conversion to CNF, this procedure is explaining in this book book, but I have not found a conplexity analysis of this algorithm: elimination of equivalence Elimination of ...
32 views

### How to correctly negate a predicate bounded by some quantifiers?

this is a problem which was asked in GATE CS 2010. This is question statement: Q: Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. which ...
38 views

### How to write negation of an 'AND' statement in logic

Suppose the given proposition is: "Zach blocks emails and texts from Jennifer" Where, P implies "Zach blocks emails from Jennifer". Q implies "Zach blocks texts from Jennifer". So it's P AND Q in ...
63 views

### The optimized numbers of variables and clauses to encode a graph coloring problem in CNF

Problem Statement Given a finite graph $G = \langle V, E\rangle$, consisting of vertice set $V$ and edge set $E$, and a finite set of colors $C$, a problem instance of graph coloring is to assign ...
27 views

### Non-Boolean SAT

I was wondering about the complexity of SAT tests with variables $x_i = 0 \lor 1 \lor 2 \dots \lor n$, with clauses being of the form $x_i = a \implies x_j \neq b$. When $n=2$, we have 2SAT, which has ...
40 views

### prove that {$↔,⊕$} is incomplete set?

How do i prove that Is {$↔,⊕$} not a complete set ? I have no clue how to prove it .
374 views

### Iota combinator and implicational propositional calculus

There is are two esoteric languages with minimally functionally complete operators, iota and jot, that are closely related to SK combinators. I'm attempting to understand the relationship between ...
107 views

### Are these 2 equivalent?

Is ∀x∀y∀z[φ(x,y)∧p(y,z)->p(x,z)] equivalent to ∀x∀y∀z[φ(x,y)∧p(x,z)->p(y,z)] ? The only thing I can think of is that this question can be answered if we show that ...
153 views

427 views

### Does exist any horn formula that is equisatisfiable to the clause that is disjunction of two literals? Does also exist equivalent?

I just and simply want to know if whether or not exist any horn formula that is equisatisfiable to $(p\lor q)$. I would also be interested to know if there also exists equivalent.
172 views

### Knight and knaves

I have these in my lecture notes, its about the rules where knights always tell the truth and knaves always lie: If A says “The statement ‘there is gold on the island’ and the statement ‘I am a ...
76 views

67 views

### What is the definition of the property of Canonicity for a logic?

I'm trying to understand "A Systematic Approach to Canonicity in the Classical Sequent Calculus" by Kaustuv Chaudhuri, Stefan Hetzl, Dale Miller. The article discusses a property called "canonicity" ...
90 views

### How to construct an NFA Ai for the given Regular property P1 and P2?

Let AP = {a; b; c}. Consider the following regular safety properties: (a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds. (b) P2: Between two ...
5k views

### Can proof by contradiction work without the law of excluded middle?

I was recently thinking about the validity of proof by contradiction. I’ve read for the past few days things on intuitionistic logic and Godel’s theorems to see if they would provide me answers to my ...