# Questions tagged [propositional-logic]

The tag has no usage guidance.

142 questions
Filter by
Sorted by
Tagged with
11k views

### Why is A implies B true if A is false and B is false?

It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday ...
4k views

### Why is $A \lor (A \land \neg B) \equiv A$?

I would like to know if there is a rule to prove this. For example, if I use the distributive law I will get only $(A \lor A) \land (A \lor \neg B)$.
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 ...
3k views

### Why does soundness imply consistency?

I was reading the question Consistency and completeness imply soundness? and the first statement in it says: I understand that soundness implies consistency. Which I was quite puzzled about ...
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. ...
5k views

### Boolean algebraic expression vs Propositional logic expression

There is a lot of similarity between Propositional logic and Boolean algebraic expressions. Similar aspects : 1) Both has variables of two states. 2) Operations of Boolean algebra and ...
359 views

### Implementing mathematical theory of arithmetic in Haskell via Curry-Howard correspondence

I have to ask for forgiveness in advance if the whole question doesn't make a lot of sense, but unfortunately, I have no better intuition as of right now and this seems like the best starting point I ...
475 views

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 ...
216 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 ...
43 views

### Is there a correspondence of steps between DPLL and sequent-calculus?

Is there a correspondence between the steps in using DPLL to find out that a formula in propositional logic is unsatisfiable and using sequent calculus to prove that its negation is valid? And given ...
326 views

### Does mutual exclusion hold in this case?

I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds: Consider two processes: $s_1$ and $s_2$ are two variables, set equal initially. P1: ...
84 views

### Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?

Recently I was reading again this propositions as types paper by Philip Wadler: http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf It gives an impression, ...
539 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 ...
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 ...
98 views

### Contingent sentences can always be true

I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions. In a textbook I read that a sentence might always be ...
262 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?
254 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 ...
78 views

654 views

### Is it necessary to learn how to prove Mathematical theorems as a CS Student? [closed]

I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem: ...