All Questions
55
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 ...
- 95k
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
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 ...
- 1,413
0
votes
1
answer
255
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 ...
- 126k
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
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, ...
- 348
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 ), ...
- 2,406
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 \...
- 319
1
vote
1
answer
887
views
Structural induction: Every propositional formula without negation is true under interpretation
I have to proof the following statement.
Let $L$ be a language of propositional logic where formulas are built only from atomic formulas using the primitive connectives $¬$, $∧$, $∨$, $→$, and $↔$. ...
- 334k
0
votes
1
answer
128
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, ...
- 2,730
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$ ...
- 95k
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,658
2
votes
1
answer
157
views
Prove $((\phi_1 \land \phi_2 \land \cdots \land \phi_n) \rightarrow \psi) \rightarrow \cdots$
I am trying to do the following exercise from the book Logic Programming for computer scientists by Michael Huth and Mark Ryan.
$$((\phi_1 \land \phi_2 \land \cdots \land \phi_n) \rightarrow \psi) \...
- 683
1
vote
1
answer
505
views
Understanding the induction principle in mathematical logic.
I'm reading from Dirk Van Dalen's Logic and Structure and in that the following theorem occurs
Let $A$ be a property, then $A(\varphi)$ hold for all $\varphi \in PROP$ if
$A(p_i)$, for all i and $A(\...
- 95k
2
votes
1
answer
115
views
proof that all formulas that can be deduced from Hilbert-style deductive system for propositional calculus have at least one connective
I got stuck trying to prove that statement. I am sorry if I got some terms wrong. I did my best to look for the equivalent terms in English, but I study in different language. So just to be on the ...
- 11.2k