# Questions tagged [propositional-logic]

The tag has no usage guidance.

159 questions
Filter by
Sorted by
Tagged with
243 views

### Proving unsatisfiability of a propositional formula

I have a propositional formula $F$ and an assignment of truth variables $A$. The assignment $A$ assigns a truth value to each variable in $F$ and then it can be evaluated. I have a function which for ...
471 views

### Is this possible to solve 4SAT in polynomial time? [closed]

I know and admit that this is long, but please read it slow and understand everything. I think that this is one of the most interesting questions asked in computer science ever. I don't expect for ...
70 views

### Refutation of pigeonhole using resolution

I am trying to find a way to refute the pigeonhole formula using resolution. Lets assume that $x_{ij}$ is true if $i^{th}$ pigeon is in $j^{th}$ hole. Thus, with $n$ holes and $n+1$ pigeons, the ...
261 views

### “Implied atomic propositions” in propositional boolean formula

Suppose we have a propositional boolean formula F and let M be the set of all models of that formula. I am wondering if there is an efficient way to find all atomic propositions that are implied by ...
47 views

### Logic, “and” operator between a set of formulas and a formula

Consider a set $S$ of formulas $\beta_i$ and a formula $\alpha$, if we have a condition such as $S \land \alpha$ is inconsistent what we have to calculate to check the inconsistency of $S \land \alpha$...
381 views

### Why is learning DNF harder than learning CNF?

In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables. We go through each positive sample, and eliminate every clause that contradicts the ...
262 views

### Propositional logic in an SMA* algorithm

I'm trying to implement an SMA* graph search algorithm that I found in a paper here(Rong Zhou, Eric A. Hansen: Memory-Bounded A* Graph Search. FLAIRS-02 Proceedings 203-209) and I would like to ...
461 views

197 views

275 views

### Show that the following tautology is a theorem of natural deduction

I'm struggling to apply the theorems of natural deduction to these two examples. $$((p \to q) \land (p \to \neg q)) \to \neg p$$ $$((p \to q) \land (p \to r)) \to (p \to (q \land r))$$ Can anyone ...
584 views

### Deciding which logical proposition is stronger

I am studying propositional logic and I am trying to solve some exercise related to the following definition: Given two logical propositions $\alpha$ and $\beta$, we say that $\alpha$ is stronger ...
2k views

### Find hamilton cycle in a directed graph reduced to sat problem

I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to ...
83 views

### Is there any precedence for symbols for constructing parse trees? [duplicate]

I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees. For example, the sentence: p ā§ q ā r, ...
342 views

### What are the differences between parse and decision trees?

I have created a parse tree for the formula: aā§Ā¬(bāØc)āØĀ¬dā§(Ā¬b) successfully. I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a ...
301 views

### All output functions of a truth table

http://www.cim.mcgill.ca/~langer/273/3-notes.pdf I can name one more: XNOR. But besides these, what other output functions are there?
1k views

### How to read out a double negation in propositional logic

How would one verbally say ~~R where R = my program is correct? The tildes are negation symbols. I'm not sure if it just cancels out and comes out as 'my program is correct' or if it's something else. ...
197 views

### How to find a minimum set of axioms within a set of propositions?

I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want ...
227 views

### Equivalent formulae with different CNF

I was not able to find or come up with two formulae which are equivalent but have different CNF. All my ideas reduce to the same formula after applying transformations. The requirements are the ...
33 views

### Derivation of implicational propositional axioms

Is there a way to subtract and add properties of axioms to generate new axioms? For example: {L} = {P S K} // natural deduction {P S K} = {P H K I} // natural deduction {S K} = {?} // constructive ...
491 views

### What are the differences between propositional logic and temporal logic?

I am currently studying temporal logic and find it much similar to propositional logic. However, temporal logic seems to be slightly more specific because it encapsulates more precise meaning symbols, ...
76 views

### a program discovering himself how to solve propositional calculus

it is well-known that propositional logic problems such as $$(p\leftrightarrow q) \lor r \quad\overset{?}{\vdash}\quad (((p\lor q)\to(p\land q)) \land \lnot r)\lor r$$ can be simply solved by ...
124 views

### complexity of modal logic axioms

I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper. At the moment I have the following: K- no restrictions ...
253 views

### Which formula corresponds to this K-Map?

I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map. $f(w,x,y,z) = \sum(3,7,9,11,13,15) + \Phi(4,5,6)$ We know that both options (a) and (b) are ...
368 views

### Relations between statements involving universal quantifier, conditional and biconditional

If we consider two predicates: $b(x)$: x is a boy $c(x)$: x is clever Then, there are four statements involving $ā, b(x), c(x), ā$ and $ā$ . These are below along with my interpretation of their ...
49 views

### Transform $A\land B \Leftrightarrow B\lor A$ into conjunctive normal form [closed]

How do I transform the following formula into conjunctive normal form? $$A \land B \Leftrightarrow B \lor A$$
1k views

### How to decide if a propositional formula is a well formed?

So, I have the following propositional formula: (((P ā Q) āØ S) ā T) How do I decide if it's well formed?
84 views

### Non-deterministic algorithms and Tautologies

I am studying the lecture The Complexity of Propositional Proofs. āHere there is a definition together with a discussion (page 3). I don't understand that discussion. Let $F$ denote the set of ...
520 views

### Size of Propositional Formula

I am study this lecture The Complexity of Propositional Proofs. Here there is a term size of propositional formula (page 2), Every tautology $\tau$ on $n$ variables has an $F$-proof in which thera ...
103 views

### Complexity of a SAT related problem

Given a set of (propositional) formulae $\Phi$, two formulae $\phi$ and $\xi$, determine whether there exists $\Psi\subseteq \Phi$ such that $\Psi\models \phi$ and $\Psi\not\models \xi$. Question: ...
11k views

### Operator precedence in propositional logic

there is some kind of priorities for the elements in propositional logic ? for example : p ā§Ā¬q ā r , given this ,we there may be two options (p ā§Ā¬q) ā r OR p ā§ (Ā¬q ā r) , which one is the correct ?...
114 views

### Learning a small disjunction

I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form $$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$ but I don't know the values of $i_1,\dots,i_k$. ...
156 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 ...
75 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 ...
60 views