All Questions
11
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
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
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
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
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
2
votes
1
answer
307
views
By replacing proposition variables by its negation and flipping the truth values of all prop. variables, show $v(\phi)=v^*(\phi^*)$
This is Exercise 2.28 from Propositional and Predicate Calculus: A Model of Argument by Derek Goldrei:
For a formula built up using the connectives $\neg,\land,\lor$, let $\phi^*$ be constructed by ...
user524154
1
vote
1
answer
168
views
Use induction to show that a truth assignment on $\Gamma\cup\Lambda$ satisfies all theorem from $\Gamma$
Definitions: Let $\Lambda$ be a set of logical axioms and $\Gamma$ be a sets of well-formed formulas (in propositional logic).
We say that $\Gamma\cup\Lambda$ tautologically implies $\varphi$ if for ...
- 15.8k
4
votes
1
answer
2k
views
Proof of Principle of Duality: Show that $φ$' is logically equivalent to $¬φ$
Could anyone check if my proof is ok/ suggest any improvement please? I couldn't find a way to utilise the induction hypothesis so I am not sure if this is ok.
Let $φ$ be a formula built up using ...
- 1,458
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 $↔$. ...
- 137
1
vote
0
answers
896
views
Show that the number of occurrences of the symbol $\land$ in a formula $\phi$ is less than or equal to the number of left brackets ( in the forumla.
Use mathematical induction on the length of a formula to show that the number of occurrences of the symbol $\land$ in a formula $\phi$ is less than or equal to the number of left brackets ( in the ...
- 1,458