All Questions
55
questions
1
vote
1
answer
590
views
Show that a set of connectives {∨, ∧} through structural induction is not a complete set of connectives
I understand how a set of connectives such as {∨,∧,¬}, can be considered adequate, but I'm not fully understanding how one would go proving something that is not adequate
The full problem is as ...
- 33
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
1
vote
1
answer
184
views
Need help finding a proof strategy for a propositional logic theorem
Textbook is Ben-Ari's Mathematical Logic for Computer Science. This question is taken directly from the homework that my professor assigned, not from the textbook. Definitions of interpretations and ...
- 235
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
1
vote
1
answer
556
views
Proof by induction of propositional formulas
I have two inductively defined operations:
$\text{bin}$
base case:
If $p$ is a propositional letter, then $\text{bin}(p) = 0$
inductive step
$\text{bin}(\neg \phi) = \text{bin} (\phi)$
$\text{...
- 1,125
1
vote
1
answer
1k
views
Using induction to prove universality of gate
Can we use induction to prove gate(like NAND) is universal. If so how?
- 275
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
2
votes
2
answers
258
views
Structural Induction: Base case leads to a contradiction
To make my question clear, I will start with some definitions and notation from the book I am studying:
Definition:
A function $\theta$ from the set of formulas into the set of formulas is a ...
- 2,176
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
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