Questions tagged [propositional-logic]

The tag has no usage guidance.

123 questions
Filter by
Sorted by
Tagged with
8k 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 ...
2k 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. ...
294 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 ...
463 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 ...
115 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 ...
255 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: ...
78 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, ...
371 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 ...
256 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 ...
96 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 ...
223 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?
239 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 ...
4k 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 ...