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 ...
- 59
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
0
votes
1
answer
245
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,218
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
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,218
2
votes
1
answer
114
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 ...
- 65
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) \...
- 593
1
vote
1
answer
497
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(\...
- 167
1
vote
1
answer
345
views
Rank-Induction Principle (following Van Dalen's Logic and Structure, 4th edition)
This post contains questions on understanding Van Dalen's proof of the Rank-Induction principle and questions concerning its wording and presentation. Please don't feel obliged to answer everything. ...
- 605
1
vote
1
answer
166
views
Relationship between the number of atomic formulas in a given formula and the number of right arrows
Here's the problem I'm doing;
Let $L_P$ be the language of propositional logic (consisting of parentheses, $\lnot$, $\rightarrow$ and a countable set of atomic formulae). Let $\alpha$ be any formula ...
- 6,318