All Questions
Tagged with propositional-calculus induction
76
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
0
votes
1
answer
2k
views
CNF formula induction proof
I am trying to prove the following theorem: Every proposition formula is logically equivalent to a formula in CNF.
As a hint, they say that this can by proven by an induction on the structure of the ...
- 297
0
votes
2
answers
42
views
Formalized attempt of proof that well ordered-ness ( of subsets of $\mathbb{Z}$ that are bounded below) implies induction seems to have issue?
I want to prove that well-orderedness on the integers implies induction. The proof is the classical "assume a contradiction" and see what happens.
So begin with an intended contradiction:
\begin{...
- 2,652
2
votes
1
answer
271
views
Predicated needed for proof using structural induction
I have a set, $F$, of boolean formulas defined inductively as follows:
$X_{i} \in F, \: \forall i \in \mathbb{N} \: \text{(variables)}\\
A \in F \implies \neg A \in F\\
A, B \in F \implies A \land B \...
- 125
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
1
vote
1
answer
135
views
Readings on more general/abstract notions of induction related to logic
Can someone suggest references to understand the more general/abstract
concept of induction?
Specifically, I am trying to justify to myself what is called induction on the "complexity of a formula" ...
- 10.1k
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
555
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
2
votes
2
answers
3k
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 the ...
- 423
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
1
vote
1
answer
296
views
Proof through induction that all formulas with a certain characteristic are a tautology or logical equivalence of p
First, sorry for the long title but I couldn't figure out how to summarize it better. This is a homework question for my course "Introduction to Logic" and I can't figure out how to solve it.
The ...
- 163
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