All Questions
55
questions
6
votes
1
answer
2k
views
How to prove Post's Theorem by induction?
The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
- 173
6
votes
2
answers
6k
views
Induction proof for the lengths of well-formed formulas (wffs)
Use induction to show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible.
The wffs in question are those associated with sentential/propositional logic. So, ...
- 281
5
votes
2
answers
100
views
Proof swapping logical connectors transforms tautology to contradiction
I was given the following exercise:
For a formula $ϕ$ built up using the connectives ¬,∧,∨, let $ϕ^∗$ be constructed by swapping all ∧ by ∨ and viceversa (e.g. $ϕ=p_1 \lor \neg p_1$, $ϕ^*=p_1 \land \...
- 355
5
votes
1
answer
157
views
Can we prove "induction on wffs" in a non-circular way?
I've always had the question of whether formal logic, number theory, or set theory "comes first" in foundations, and I've seen questions asking this. However, I recently came to what I think ...
- 2,461
4
votes
1
answer
2k
views
Proof of Principle of Duality: Show that $φ$' is logically equivalent to $¬φ$
Could anyone check if my proof is ok/ suggest any improvement please? I couldn't find a way to utilise the induction hypothesis so I am not sure if this is ok.
Let $φ$ be a formula built up using ...
- 1,458
3
votes
3
answers
13k
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)" ...
- 421
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
190
views
Substitution of formula in propositional logic.
I have a question about something in the book "Mathematical logic for Computer Science". I will post something from the book, where I have highlighted what I do not understand, after I have ...
- 1,262
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
3
answers
992
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 ...
- 503
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
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
145
views
How to prove? Propositional Calculus
I'm having trouble proving this:
Let $\alpha$ be a wff such that the only possible connectives in it are $\lnot, \land, \lor$. Let $\alpha^{\ast}$ be the result of changing every $\land$ in $\alpha$ ...
- 1,225
2
votes
1
answer
688
views
Structural Induction, Propostitonal formulae problem
I am kind of overwhelmed by this question. Can anyone give me some hints about where to start?
Propositional formulae PF are inductively defined over
the Boolean constants B := {1, 0} (true and ...
- 23