Articles of natural deduction

Countable set of truth assignments satisfying set of well formed formulas

I am trying to answer the following question posed in my logic class: (throughout we work in propositional logic) is there a set $S$ of well-formed-formulas (wffs) satisfied by countable set $V$ of truth assignments such that any truth assignment satisfying $S$ lies in $V$? My guess is no. My first reaction to this was […]

Proving 'Law of Excluded Middle' in Fitch system

I’m taking a course from Stanford in Logic. I’m stuck with an exercise where I’m doing some proof. The Fitch system I’m given only allows $ \land $ introduction and elimination $ \lor $ introduction and elimination $ \to $ introduction and elimination $ \equiv $ introduction and elimination $ \lnot$ introduction and $ \lnot […]

**Ended Competition:** What is the shortest proof of $\exists x \forall y (D(x) \to D(y)) $?

The competition has ended 6 june 2014 22:00 GMT The winner is Bryan Well done ! When I was rereading the proof of the drinkers paradox (see Proof of Drinker paradox I realised that $\exists x \forall y (D(x) \to D(y)) $ is also a theorem. I managed to proof it in 21 lines (see […]

“Modus moron” rule of inference?

This is an exercise I got from the book “First Order Mathematical Logic” by Angelo Margaris (1967). I have never heard of this rule before, the question is whether what Margaris calls the modus moron rule of inference is correct or not and to explain why I think so. $$\frac{P\Rightarrow Q, Q}{\therefore P}\qquad \text{(modus moron)}$$ […]

Propositional Logic – Can you Derive $C \to A$ from $A$ alone, given the introduction rule?

Apparently, according to the Conditional Introduction rule, this is valid: Prove $C \to A$ Source:–files/logic/W12R Page 5 So before this, the way I viewed the CI rule, was that it allowed us to prove that if we assume the antecedent is true, we can prove the consequent can derived from the antecedent, by referring […]

How to prove this sequent using natural deduction?

How do I prove $$S\rightarrow \exists xP(x) \vdash \exists x(S\rightarrow P(x))$$ using natural deduction? Just an alignment of which axioms or rules that one could use would be much appreciated.

Natural deduction proof / Formal proof : Complicated conclusion with no premise

Find a formal proof for the following: $\vdash [(\neg p \land r)\rightarrow (q \lor s )]\longrightarrow[(r\rightarrow p)\lor(\neg s \rightarrow q)]$ As you can see. No premise to use. We have to use assumptions and eliminate them. This also means no using equivalent formulas. Because we can easily end the problem by finding a shorter and […]

Peano/Presburger axioms – “find” numbers lower or equal than another number

[EDIT/CONCLUSION] It turns out it was actually working.. I was just like too stupid to let the prover run for more time and assumed it would take a lot / not be able to prove with what I’ve provided because it wasn’t doing it fast and because it took it ~1 minute with a similar […]

natural deduction: introduction of universal quantifier and elimination of existential quantifier explained

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\phi_1,\dots, \phi_n,\phi$ are formulas, then $\phi_1\dots\phi_n\vdash\phi$, often abbreviated by $\Gamma\vdash\phi$, is called a sequent. Can somebody please explain to me the following two inference rules? Introduction of the universal quantifier. $$ \begin{array}{c} […]

Need Hints Prove “$((\neg \alpha \to \alpha) \to \alpha) $” Using Axiom 1,2,3 and MP and deduction theorem

$((\neg \alpha \to \alpha) \to \alpha) $ Hi, I am trying to prove this. Can someone gives me some hints to start the question… My friend told me I might need to use deduction theorem here, but I have no clue to approach it.. Axiom 1: A→(B→A). Axiom 2: (A→(B→C))→((A→B)→(A→C)). Axiom 3: (¬B→¬A)→((¬B→A)→B). To clarify: […]