1
vote
2answers
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 ...
3
votes
2answers
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 ...
1
vote
5answers
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 ...
0
votes
1answer
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 ...
4
votes
5answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
3answers
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 ...
3
votes
1answer
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 ...
1
vote
4answers
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 ...
0
votes
1answer
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$ ...
1
vote
1answer
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 ...
0
votes
2answers
213 views

Providing a counter example for a Logic Statement

How do I give a counter-example of the following logic statement (I think the statement is false): There exists $x$ $\geq$ 0 s.t. (For All real $y$, $x$ = $y$$^2$) Since the statement has a "There ...
3
votes
2answers
170 views

Is the set of self-dual connectives incomplete?

A $n$-ary connective $\$$ is called self-dual if $f_\$(x_1^*, \ldots , x_n^*) = (f_\$(x_1, \ldots , x_n))^*$ where $0^* = 1$ and $1^* = 0$. How to show that the set of such self-dual connectives ...
0
votes
1answer
236 views

propositional logic - substitution

Prove: $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies \varphi_1[\psi/p] =\!\mathrel|\mathrel|\!= \varphi_2[\psi/p]$. We've proven that $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies ...
0
votes
2answers
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)" ...
1
vote
2answers
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 ...
0
votes
3answers
142 views

Logical Equivalance

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 ...
1
vote
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 ...
2
votes
3answers
399 views

Understanding this proof by contradiction

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 ...