All Questions
55
questions
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.9k
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
0
votes
1
answer
54
views
Prove Every Axiom Instance Has A Property
Consider an axiom form $\phi \rightarrow \phi$. I need to show that every instance of this has an even number of $\neg$'s.
I'm not sure how to proceed.
Here is what I've tried. I've assumed some ...
- 255
1
vote
0
answers
42
views
Structural Induction Proof of Compositional Semantics [duplicate]
I need to show by structural induction on WFFs that every WFF, $\theta$, has the following property: For any PL (Propositional Logic) interpretations $I$ and $I'$ if $I(\alpha) = I'(\alpha)$ for every ...
- 255
0
votes
1
answer
2k
views
Proof by induction on wffs
Here is an extra problem form Enderton: Let $\alpha$ be a formula in sentential logic. Prove that there is some tautologically equivalent formula in which negation (if it occurs at all) is applied ...
- 4,174
2
votes
1
answer
145
views
How to prove? Propositional Calculus
I'm having trouble proving this:
Let $\alpha$ be a wff such that the only possible connectives in it are $\lnot, \land, \lor$. Let $\alpha^{\ast}$ be the result of changing every $\land$ in $\alpha$ ...
- 1,225
1
vote
0
answers
442
views
Proof by induction, logic
I'd like you to comment if my following proof by induction is correct ($\mathbb{N} = \{0, 1, 2, \ldots\}).$
Thesis: Every formula constructed from variable $p$ and connectives $\land$, $\lor$, $\top$ ...
- 393
1
vote
1
answer
350
views
Every $n$-ary logical connective has a DNF
I'm trying to solve the following exercise:
Let $A_1,...,A_n$ be propositions, $n \in \mathbb N$. Show that every $n$-ary logical connective $J(A_1,...,A_n)$ considered as a function $J:\{t,f\}^n \...
- 2,825
0
votes
1
answer
104
views
How to prove the that no formula can be represented in the form (F . G),
"No formula can be represented in the form (F . G), where F and G are
formulas and is a binary connective, in more than one way.
By representing a formula in the form ¬F or (F . G) we start “parsing”...
- 171
1
vote
1
answer
87
views
Prove that $ \text{len}(q^*) \le 3\text{len}(q) -2 $
Prove by induction where q is a formula in proposition logic:
$$ \text{len}(q^*) \le 3\text{len}(q) -2 $$
Where the star property (*) is defined as follows:
$$ \text{atom}^* = \text{atom} $$
$$ (\...
- 27
1
vote
2
answers
400
views
How to generalize the principle of mathematical induction for proving statements about more than one natural number?
Suppose that $P(n_1, n_2, \ldots, n_N)$ be a proposition function involving $N >1$ positive integral variables $n_1, n_2, \ldots, n_N$. Then how to generalise the familiar induction to prove this ...
- 26.9k
1
vote
1
answer
1k
views
Truth table and induction
It is true that every truth table can be represented by some wff built using only the connectives $\neg, \implies$ and $\iff$ - let's call it "negation-arrow-wff" for convenience. I want to be able to ...
- 405
0
votes
0
answers
493
views
Proof of Replaceability of Equivalent Formulas by Structural Induction
My class discussed the following theorem for which I wasn't able to make it to class. Its proof is supposed to involve structural induction but I am stuck in the inductive step...
Let B |=| C. If A' ...
- 1,180