# Tagged Questions

73 views

### How to deal with equivalences in proofs?

There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: $(p \equiv q) \equiv (q \equiv p)$. Given p and q ...
94 views

### Law of excluded middle. Do we need it in proofs?

Quite often when I am making a natural deduction proof, and I have no fixed idea on how to continue. I find myself thinking: "lets start with some form of the law of the excluded middle (LEM) and ...
69 views

### If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
80 views

### A finite set of wffs has an independent equivalent subset

This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ...
155 views

### Are $p \to (q \to r)$ and $p \to (q \wedge r)$ logically equivalent?

Is $p \to (q \to r)$ logically equivalent to $p \to (q \wedge r)$? I simplified each one, I got $\neg\, p \vee(q \vee r)$ and $\neg\, p ∨(\neg\, q \wedge r)$ respectively. Not sure if my ...
100 views

### Propositional Logic questions about tableau method

Hello i am learning for my exam from logic, I came across the question which i don't know how to solve it. Can tableau for a propositional formula containing an infinite path exist? Can be tableau ...
58 views

### Rooted Trees & Induction

So I am a little stumbled upon this question: A full binary tree is a rooted tree where each leaf is at the same distance from the root and each internal node has exactly two children. Inductively, a ...
94 views

### Natural Deduction: $p \to (\neg q \leftrightarrow (r \lor s)), \neg s \vdash (p \land \neg q) \to r$ [duplicate]

I have the following formula and need to prove it with natural deduction: $$p \to (\neg q \leftrightarrow (r \lor s)), \neg s \vdash (p \land \neg q) \to r$$ I was able to get the below finished but ...
149 views

### Proof by contradiction by first assuming proposition true?

In a proof by contradiction, we first assume a proposition $P$ false, then prove some known truth to be false, then that would imply the assumption $P$ should really be true. Do we really need to ...
275 views

### Can mathematical induction be used to disprove something?

I saw this to be the rule of inference for mathematical induction : Now consider : as L.H.S. and as R.H.S.. Now if suppose, while trying to prove P(k) -> P(k+1), in the left hand side of ...
2k views

### Proving/Disproving Product of two irrational number is irrational

I saw this question where I had to prove/disprove that: Ques. Product of two irrational number is irrational. I tried 'Proof by Contraposition'. Product of two irrational number is irrational. p ...
78 views

### is this argument true?

i had a puzzle and used a logical argument to show a point but some says that my argument is wrong but i can't understand the reason they provide ! the puzzles says , Given four cards laid out on a ...
144 views

### How to prove this with induction

$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q$$ is the same as $$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$ Do I ...
116 views

### Prove that a formal system is absolutely inconsistent

I'm using the book An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, and it does not have any solutions and barely any examples. I want to understand how to prove that all ...
474 views

### Prove equivalence $(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$

Prove equivalence $$(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$$ What is the step by step for the equivalence of these equations. I can first break down the ...
78 views

### Verify these logical equivalences by writing an equivalence proof?

I have two parts to this question - I need to verify each of the following by writing an equivalence proof: $p \to (q \land r) \equiv (p \to q) \land (p \to r)$ $(p \to q) \land (p \lor q) \equiv q$ ...
129 views

### Prove/disprove this logical equivalence using basic equivalences?

I need to prove/disprove the logical equivalences of the following statement using basic equivalences: p→(q→r) and q→(p→r). I can do everything apart from the proofs in my work :/ Thank you if you ...
213 views

2k views

### I want a clear explanation for the Principle of Strong Mathematical Induction

I understood the Principle of Mathematical Induction. I know how to make a recursive definition. But I am stuck with how the "Principle of Strong Mathematical Induction (- the Alternative Form)" ...
264 views

### Predicate Logic Argument Validity

My question is whether or not the following is a validly structured argument: (P→T)→Q Q → ¬Q ∴ P I'm getting hung up on the Q→¬Q part by itself as a premise, it doesn't seem like that is ...
Determine whether the following pairs of statements are logically equivalent or not. Give a reason. (i) $p \to (q \to r)$ and $(p \to q) \to r$ (ii) $p \to (q \to r)$ and $q \to (p \to ... 3answers 539 views ### inference rules application (introduction / elimination): two examples Got stuck while trying out how to apply inference rules (introduction and elimination) for the following examples: From$\lnot(P\land Q)$and$P$infer$\lnot Q$From$P\lor Q$and$Q$infer$\lnot ...
Let $c$ be a positive integer that is not prime. Show that there is some positive integer $b$ such that $b \mid c$ and $b \leq \sqrt{c}$. I know this can be proved by contradiction, but I'm not ...