1
vote
5answers
64 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
47 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
145 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
98 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
54 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
82 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
122 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
212 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
1k 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
75 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
135 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
112 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
433 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
75 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
115 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
195 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
165 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
225 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
248 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
140 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
528 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
383 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 ...