Linked Questions

7
votes
3answers
2k views

Give a proof that “p & ~p” implies “q”?

Context: This is not a textbook or homework problem. I was hoping you younger folks could help my tired old brain. "Everybody knows" a contradiction implies anything. What I'm looking for is a ...
4
votes
3answers
3k views

Use Fitch system to proof ((p ⇒ q) ⇒ p) ⇒ p without any premise. ONLY FOR FITCH SYSTEM.

I know here has few similar questions, but I cannot figure out with those answer. Since for Fitch system, I can only use And Intro, And Elim, Or Inro, Or Elim, Neg Intro, Neg Elim, Impl Intro, Impl ...
5
votes
2answers
1k views

How to prove consistency of Natural Deduction systems

In Dag Prawitz, Natural Deduction A Proof-Theoretical Study (1965), we have the system I of intuitionistic (first-order) logic based on eleven introduction- and elimination-rules : the 3 couples for ...
3
votes
2answers
664 views

How is the law of excluded middle necessary for proofs by contradiction?

It is claimed that the law of excluded middle : $A \lor \neg A$, is a necessary principle for proving statements by contradiction (i.e. non constructively). However, in first order logic, at least, ...
3
votes
1answer
577 views

Intuitionistic Logic: introduction and elimination rules for the universal and existential quantifiers

Are the natural deduction introduction and elimination rules for the universal and existential quantifiers in Intuitionistic Logic the same as those for Classical Logic?
0
votes
2answers
58 views

Why are constants considered $0$-arity functions in logic?

I always come across this idea. It seems that constants can be considered nullary/$0$-arity functions. What is the intuition behind that?
2
votes
2answers
294 views

Natural Deduction rules for $\lnot$ in classical and intuitionstic logic

Following the very useful answer by Peter Smith to my prevoius post , I'm still reflecting about the "imperfection" connected with the Intro- ans Elim-rules for $\lnot$ in Natural Deduction (I mean ...
4
votes
1answer
348 views

What is the purpose of defining the negation of a proposition A as A $\rightarrow \bot$?

I know that this definition is unrelated to the law of the excluded middle, but as a beginner in logic (I've studied the first half of Chiswell and Hodges' Mathematical Logic), the use of the name '...
3
votes
1answer
234 views

Show that the set of all positive L-formulas is consistent.

I am given the following definition of L-formulas: "Positive formulas are defined with the following properties: (i) Every atomic formula is positive. (ii) If $\phi,\psi$ are positive that $\phi\...
2
votes
2answers
127 views

Proof by Contradiction with Multiple Axioms

Looking at proofs by contradiction and it seems I've run into something that does not sit well with me. I am fine with the law of the excluded middle (thus not an intuitionist) and more fundamentally ...
3
votes
2answers
90 views

Proof, is $\lnot p \land \lnot q \vdash p \iff q$?

I have derived the proof to some extent, mentioned below:- $$\begin{array}{rll} 1. &\lnot p \land \lnot q &\text{Premise} \\ 2. &\lnot p &\land\text{elim}...
0
votes
2answers
141 views

Falsehood in a calculus of natural deduction

How does the introduction rule and the elimination rule of falsehood ⊥ look like in a calculus of natural deduction?
1
vote
1answer
140 views

Is this the reasoning behind $\bot\vdash B$ (rule of explosion)?

Assuming that a $\bot$ indicates we have two contradictory statements $A$ and $\neg A$, according to wikipedia this can be the reasoning behind $\bot\vdash B$: since $A$ is true, "$A$ or $B$" is also ...
1
vote
1answer
178 views

Why do people say RAA(Reductio Ad Absurdum) is the same as $(\bot E)$?

$(\bot E)$ is $\bot\vdash\psi$. RAA(Reductio Ad Absurdum) says If $\{\Gamma,\neg\psi\}\vdash\bot$, then $\{\Gamma\}\vdash\psi$. Yet, one of the solutions to my textbook exercises uses $(\bot E)...
1
vote
1answer
116 views

Truth constants are considered as atomic formulas?

This is a purely terminological (and tedious) question. Given a language of first-order logic that includes the truth constant $\bot$ (falsehood), is this constant considered as an atomic formula or ...

15 30 50 per page