All Questions
Tagged with propositional-calculus induction
76
questions
0
votes
1
answer
48
views
Structural induction on NAND (propositional logic)
Answer:
Case ¬ϕ: the equivalence holds, since f(ϕ) ⊼ f(ϕ) is false if and only if
f(ϕ) is true, thus it negates f(ϕ), which is equivalent to ϕ.
In the truth table below, where we get the valuation in ...
- 59
0
votes
0
answers
26
views
The number of left parentheses is greater than or equal to the number of right parentheses. [duplicate]
Using induction on the complexity of formulas, let's assume that in every proper non-empty initial segment of a propositional formula, the number of left parentheses is greater than or equal to the ...
- 35
1
vote
1
answer
60
views
How to prove that if $\vdash_{ax} A$, then, for every formula B that is an instance of A, $\vdash_{ax} B$?
$\vdash_{ax} A$ means that $A$ is a theorem - a formula such that there's a derivation $A_1, \ldots, A_n = A$. A derivation is a sequence of formulas $A_1, \ldots, A_n$ such that each formula in the ...
- 307
1
vote
0
answers
25
views
Proving all vertices of a binary tree satisfy a certain property
While proving statements about formation trees for WFF's, I tried to prove the following Lemma:
Let $T$ be a binary tree with root $r$,and Denote the set of vertices of $T$ by $V$. assume $S \...
- 318
0
votes
1
answer
243
views
induction for finite cases from 1 to n. How is this possible?
hi guys I have a question.
SECOND PROOF. We will repeat the argument, but without the trees.
Consider an arbitrary wff α. It is the last member of some construction sequence ε1,...,εn
. By ordinary ...
- 297
1
vote
0
answers
109
views
How to Complete this Proof about wffs in Propositional Logic?
For any wff $\mathfrak{F}$, define $\mathfrak{F}^*$ as the wff derived from $\mathfrak{F}$ by replacing all $\wedge$ with $\vee$ and all $\vee$ with $\wedge$.
Claim: If all of the connectives of wff $...
- 515
0
votes
1
answer
78
views
How to prove that the set only contain these elements(propositional logic)
The set of propositional formulas, $X$, is defined as the smallest set such that
Every atomic formula is in $X$.
If $F$ is in $X$ then $\neg F$ is in $X$.
If $F$ and $G$ is in $X$ than $(F\land G ), ...
- 1,222
5
votes
2
answers
99
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
0
votes
1
answer
62
views
Prove a function on the set of propositional formulas is well-defined
I define the set $X$ of propositional formulas as the smallest set such that:
Every atomic formula is in $X$.
If $F$ is in $X$ then $\neg F$ is in $X$.
If $F$ and $G$ is in $X$ than $(F\land G ), (F\...
- 1,222
1
vote
1
answer
57
views
Is there a way to define universal quantification in such a way, that I can prove$\forall xPx\land Q\iff \forall x(Px\land Q)$ and similar statements?
What I've tried so far:
Under the assumption that the domain of discourse has a finite number of elements, I defined universal quantification with the help of a recursive function:
$\forall x\in A:P(x)...
- 678
0
votes
1
answer
30
views
Proof strong induction with help of well-ordering theorem of $\mathbb{N}$
I am preparing for my exam and need help/someone who could check my solutions for the following tasks.
Let $P(n), n\in \mathbb{N}$ (without $0$) be a propositional formula (if this is the correct ...
- 400
5
votes
1
answer
156
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
0
votes
1
answer
126
views
Is there a set-theoretic proof of Induction on the complexity of formulae? [closed]
The Induction on the complexity of formulae is a theorem on the syntax of PL that states the following:
Suppose an arbitrary property holds for all atomic formulae in PL, and, if it holds for A and B, ...
- 13
1
vote
1
answer
114
views
If a wff is longer then the sum occurrences of atoms and connectives is bigger.
Let $\#(\phi)$ denote the sum of (not necessarily distinct) occurrences of atoms and connectives of the wff $\phi$.Let $l(\phi)$ denote length of the wff $\phi$.
Is it true that for all wff's $\phi$ ...
- 5,724
3
votes
1
answer
188
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,222