# Questions tagged [formal-proofs]

For questions about proofs within a formal system, such as natural deduction or Hilbert system.

537 questions
Filter by
Sorted by
Tagged with
2answers
36 views

### Natural deduction - formal proof troubles

I'm pretty new to the topic of natural deduction using the Fitch method. I found a very helpful site (http://proofs.openlogicproject.org/) in which you can construct your proofs, but I'm having a lot ...
4answers
64 views

### Natural deduction proof of $(A \to \lnot B \lor C), ((\lnot D \land A) \to B), (\lnot E \to A) \vdash D \lor (C \lor E)$

I'm struggling to proof this both if I use or introduction rule $\lor_{I_1}$ (to work on $D$) or or introduction rule $\lor_{I_2}$ (to work on $C \lor E$). Could you help me?
2answers
46 views

### Need help with tautology proof without truth tables.

I am trying to prove $$[(p\to q)~\&~(q\to r)]\to (p\to r)$$ is a tautology using only logical laws. I have gotten part-way there but I got stuck and am not sure how to proceed. Please state ...
1answer
77 views

### Natural deduction in first-order logic

I've sat for more than an hour now and I don't understand how I'm supposed to solve the task below. $\{\forall x(P(x) \land Q(x)), \exists x\neg P(x)\} \vdash \exists x \neg Q(x)$ So I'm a bit ...
1answer
66 views

### Most adequate logic system to formally prove Euler's identity (and what would the proof look like)?

If we were given the task of proving Euler's identity using a formal logic system, which logic system out there would be the most convenient for such a task? And more or less what would the proof look ...
1answer
102 views

### Proof of $\forall x \forall y(x+x \neq y+y+1)$ in Peano arithmetic

How to prove $\forall x \forall y(x+x \neq y+y+1)$ using the axioms of Peano arithmetic?
1answer
92 views

### Proving $∀x (x ≠ 0 → gcd(x, 0) = x)$ formally attempt

I have proved $a≤gcd(a,0)$ in my attempt to prove $∀x (x ≠ 0 → gcd(x, 0) = x)$ but I am having trouble proving $gcd(a,0)≤a$ see below: I have access to the normal rules of natural deduction and the ...
1answer
59 views

### Proof by Induction Help: Prove that there are unique integers $a\geq 0$ and $k>0$ such that $n=(3^a)\cdot k$ and $k$ is not divisible by $3$.

Suppose $n$ is a positive integer. Using induction, prove that there are unique integers $a\geq 0$ and $k>0$ such that $n=(3^a)\cdot k$ and $k$ is not divisible by $3$. Note: I have already proven ...
1answer
212 views

### Stuck on Formal Proofs

I'm trying to figure out this formal proof. This is what I have so far but I'm stuck in trying to reach the goal. I'm not sure if what I did is correct so far since I'm still trying to learn this on ...
1answer
694 views

### What is a judgment?

I have a hard time trying to understand the concept of a judgment in natural deduction. One distinguishes between propositions and judgments. As I understand it, propositions are just well-formed ...
1answer
411 views

### Spivak Calculus 3rd. Edition Chapter 1 Problem 12 (v) and (vi) Proofs Critique

Here are my "proofs" for Spivak's Calculus Chapter 1 Problem 12. I am new to this level of rigour and I am attempting to intimate myself with more advanced topics of mathematics to prepare for next ...
2answers
98 views

### How to give a formal proof for $\exists \space x\space \forall \space y(P(x) \rightarrow P(y))$ in fitch

To practice for my exams, my teacher gave us several exercises to practice but didn't supply us any answers. Now after looking at this problem for 2 nights I have no idea left on how to solve it. If ...
1answer
372 views

### $A⇒(B \lor C)$ and $[(A \Rightarrow B) \lor (A \Rightarrow C)]$

[(A⇒ B∨C)] ⇒ [A⇒(¬B⇒C)] ⇒[(A⇒¬B)⇒(A⇒C)] ⇒ [¬(A⇒¬B)∨(A⇒C)]⇒[(A∧B)∨(A⇒C)] [(A⇒B)∨(A⇒C)] is equivalent to A⇒(B∨C). Can I prove [(A∧B)∨(A⇒C)] ⇒ [A⇒(B V C)]? or is there problem in the proof above ...
1answer
85 views

### Another topology question

This is a two part question. The first part, part (i), I present with the solution I reached. The second part, part (ii) is where I need help. (i) Let $B$ be a basis for a topology $T$ on a non-empty ...
1answer
2k views

### Modulo Congruence Prime Proofs

Let p be an element of {2,3,4...}. Sppose that for all x,y (integers) if xy ≡ 0 mod p, then x ≡ 0 mod p or y ≡ 0 mod p. Show p is prime. I did some work on this problem but I have gotten stuck. (p|...
1answer
107 views