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
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 ...
- 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,262
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
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
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, ...
- 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,704
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,262
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 ...
- 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
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(\...
- 167
1
vote
1
answer
349
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
167
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,328
0
votes
2
answers
824
views
Proof of "Induction proof method"
So I have been proving various logical statements using induction method (like structural induction , strong induction , weak induction etc ).I was wondering If there is a proof of this "...
- 861
1
vote
1
answer
48
views
A problem: Exists a proposition $r \in Prop(A \cup B)$ such that $\vDash (p \rightarrow r) \land (r \rightarrow q)$
Let $A,B$ two arbitrary iof propositions. Show that if $p \in Prop(A)$ and $q \in Prop(B)$ are two propositions such that $\vDash p \rightarrow q$ then exists a proposition $r \in Prop(A \cup B)$ such ...
- 169
0
votes
3
answers
190
views
Can we assume the property is true for some n in proof by induction?
When you're doing a proof by induction and you want to show that the property P(n) holds for all natural numbers n, in the induction step you say: Let n be a natural number and assume P(n) is true. I ...
2
votes
1
answer
185
views
What is the problem with this proof of the PMI?
Principle of Mathematical Induction (PMI). Let $P(n)$ be a statement depending on some $n\in \mathbb{N}$. Suppose that $P(1)$ is true and that $P(n)$ true implies $P(n+1)$ true for each $n\in \mathbb{...
- 4,827
3
votes
1
answer
169
views
Length of the well formed formula $(((p_0)\rightarrow ((p_1)∧(p_{32}))) \rightarrow ((((p_{13})∧(p_6))∨(p_{317})) \rightarrow (p_{26})))$
How is the length of this well formed formula defined as $5$?
$\big(((p_{0})\rightarrow ((p_1) \land (p_{32}))) \rightarrow ((((p_{13}) \land (p_6)) \lor (p_{317})) \rightarrow (p_{26}))).$
(from ...
- 99
3
votes
1
answer
90
views
Are there any strong forms of "clamped" induction?
So in normal induction, we say that if $P(a)$ is true, and $P(n)\implies P(n+1)$, then $P(n)$ is true $\forall n\geq a$.
Then we have strong induction where you assume all preceeding values of the ...
- 3,055
3
votes
2
answers
114
views
Proof by induction of inadequacy of a propositional connective
I have the following truth table of a newly defined logical operator and have to prove its functional incompleteness via structural induction.
My idea is that that you cannot express the always true ...
- 51
2
votes
0
answers
136
views
Circular Induction
Question: Suppose you have
a circle with equal numbers of 0’s and 1’s on it’s boundary, there is
some point I can start at such that if and travel clockwise around the
boundary from that point, I will ...
user693646
2
votes
1
answer
67
views
Show that $A_1,...,A_n\vDash_{taut} B \leftrightarrow \vDash_{taut} A_1 \to A_2\to ...\to A_n\to B$
I'm having a hard time understanding the iff part of this proof by induction (is this vacuously true?), below is my attempt:
Base Case: Let $n = 1$, therefore $A_1\vDash_{taut} B \leftrightarrow \...
2
votes
1
answer
147
views
Showing two sets of formulas are logically equivalent using induction.
Can someone let me know if my proof is okay for showing the following two sets are logically equivalent (in propositional logic)? I asked this a day or so ago but the post was very long, disorganized, ...
user482939
0
votes
1
answer
121
views
How to solve propositional logic problems by induction
I'm trying to solve a bunch of problems like this one and every time I get stuck. So I don't need an actual solution but to understand how you solve this kind of problems. I know they're usually ...
- 543
2
votes
1
answer
69
views
By induction prove $ P(n) := $ "$ B \rightarrow \varphi_{n}(B,\rightarrow)$"
Define $\varphi_{n}(B,\rightarrow)$ to be the statement form comprised of only the particular statement $B$ and connectives $\rightarrow$ such that $B$ occurs exactly $n$ times.
So I'm actually ...
- 790
1
vote
2
answers
522
views
Defining a formula inductively using structural induction
If I'm given a well formed formula $\varphi$ that only has the logic symbols $\land,\lor,\neg$.
I want to define a formula $\varphi^*$ that is a result of switching every sign $\land$ to $\lor$ and ...
- 785
-1
votes
1
answer
206
views
Logic in Computer Science - Define inclusive XOR by induction [closed]
What is the formal definition by induction for iterated exclusive or (XOR) from $i = 1$ to $n$. Thanks
This is the notation: $\bigoplus_{i=1}^n A_i$.
-2
votes
2
answers
80
views
Mathematical Induction, Step after base case.. [closed]
I need to prove the following by mathematical Induction. I have the base case where n=1, and that hold true. However, the step after this have been confusing me. Any help would be great.
- 73