All Questions
55
questions
0
votes
2
answers
824
views
Proof of "Induction proof method"
So I have been proving various logical statements using induction method (like structural induction , strong induction , weak induction etc ).I was wondering If there is a proof of this "...
- 861
1
vote
1
answer
48
views
A problem: Exists a proposition $r \in Prop(A \cup B)$ such that $\vDash (p \rightarrow r) \land (r \rightarrow q)$
Let $A,B$ two arbitrary iof propositions. Show that if $p \in Prop(A)$ and $q \in Prop(B)$ are two propositions such that $\vDash p \rightarrow q$ then exists a proposition $r \in Prop(A \cup B)$ such ...
- 169
0
votes
3
answers
190
views
Can we assume the property is true for some n in proof by induction?
When you're doing a proof by induction and you want to show that the property P(n) holds for all natural numbers n, in the induction step you say: Let n be a natural number and assume P(n) is true. I ...
2
votes
1
answer
185
views
What is the problem with this proof of the PMI?
Principle of Mathematical Induction (PMI). Let $P(n)$ be a statement depending on some $n\in \mathbb{N}$. Suppose that $P(1)$ is true and that $P(n)$ true implies $P(n+1)$ true for each $n\in \mathbb{...
- 4,827
3
votes
1
answer
169
views
Length of the well formed formula $(((p_0)\rightarrow ((p_1)∧(p_{32}))) \rightarrow ((((p_{13})∧(p_6))∨(p_{317})) \rightarrow (p_{26})))$
How is the length of this well formed formula defined as $5$?
$\big(((p_{0})\rightarrow ((p_1) \land (p_{32}))) \rightarrow ((((p_{13}) \land (p_6)) \lor (p_{317})) \rightarrow (p_{26}))).$
(from ...
- 99
3
votes
1
answer
90
views
Are there any strong forms of "clamped" induction?
So in normal induction, we say that if $P(a)$ is true, and $P(n)\implies P(n+1)$, then $P(n)$ is true $\forall n\geq a$.
Then we have strong induction where you assume all preceeding values of the ...
- 3,055
3
votes
2
answers
114
views
Proof by induction of inadequacy of a propositional connective
I have the following truth table of a newly defined logical operator and have to prove its functional incompleteness via structural induction.
My idea is that that you cannot express the always true ...
- 51
2
votes
0
answers
136
views
Circular Induction
Question: Suppose you have
a circle with equal numbers of 0’s and 1’s on it’s boundary, there is
some point I can start at such that if and travel clockwise around the
boundary from that point, I will ...
user693646
2
votes
1
answer
67
views
Show that $A_1,...,A_n\vDash_{taut} B \leftrightarrow \vDash_{taut} A_1 \to A_2\to ...\to A_n\to B$
I'm having a hard time understanding the iff part of this proof by induction (is this vacuously true?), below is my attempt:
Base Case: Let $n = 1$, therefore $A_1\vDash_{taut} B \leftrightarrow \...
2
votes
1
answer
147
views
Showing two sets of formulas are logically equivalent using induction.
Can someone let me know if my proof is okay for showing the following two sets are logically equivalent (in propositional logic)? I asked this a day or so ago but the post was very long, disorganized, ...
user482939
0
votes
1
answer
121
views
How to solve propositional logic problems by induction
I'm trying to solve a bunch of problems like this one and every time I get stuck. So I don't need an actual solution but to understand how you solve this kind of problems. I know they're usually ...
- 543
2
votes
1
answer
69
views
By induction prove $ P(n) := $ "$ B \rightarrow \varphi_{n}(B,\rightarrow)$"
Define $\varphi_{n}(B,\rightarrow)$ to be the statement form comprised of only the particular statement $B$ and connectives $\rightarrow$ such that $B$ occurs exactly $n$ times.
So I'm actually ...
- 790
1
vote
2
answers
522
views
Defining a formula inductively using structural induction
If I'm given a well formed formula $\varphi$ that only has the logic symbols $\land,\lor,\neg$.
I want to define a formula $\varphi^*$ that is a result of switching every sign $\land$ to $\lor$ and ...
- 785
-1
votes
1
answer
206
views
Logic in Computer Science - Define inclusive XOR by induction [closed]
What is the formal definition by induction for iterated exclusive or (XOR) from $i = 1$ to $n$. Thanks
This is the notation: $\bigoplus_{i=1}^n A_i$.
-2
votes
2
answers
80
views
Mathematical Induction, Step after base case.. [closed]
I need to prove the following by mathematical Induction. I have the base case where n=1, and that hold true. However, the step after this have been confusing me. Any help would be great.
- 73