Proving associativity in propositional logic
up vote
0
down vote
favorite
$(p∧q) ∧ r ⊢ p ∧ (q∧r)$
In the sequent above, the only thing that happens is switching brackets between p&q and r, to q&r and separating out p. I could use the elimination rule between p&q and r, and get these separately, combine them with the introduction rule to get the conclusion.. But what step do I take to replace the brackets from p&q to q&r? Is their a rule that would help me move brackets?
propositional-calculus
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
asked Nov 13 at 12:45
haris.a.amin
11
add a comment |
up vote
0
down vote
favorite
$(p∧q) ∧ r ⊢ p ∧ (q∧r)$
In the sequent above, the only thing that happens is switching brackets between p&q and r, to q&r and separating out p. I could use the elimination rule between p&q and r, and get these separately, combine them with the introduction rule to get the conclusion.. But what step do I take to replace the brackets from p&q to q&r? Is their a rule that would help me move brackets?
propositional-calculus
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
asked Nov 13 at 12:45
haris.a.amin
11
1
The "rule that would help me move brackets" is the associativity property : but it seems that you have to prove it.
– Mauro ALLEGRANZA
Nov 13 at 12:50
As Mauro says: moving the brackets is typically a basic rule ... and it is typically not derivable from other rules of boolean algebra ... but it all depends on what rules you do have: so, which rules can or must you use? Maybe you have to give a formal proof but then once again: what rules are given to you to use?
– Bram28
Nov 13 at 12:55
See the post Natural deduction: Derive (ϕ ∨ ψ) ∨ σ → ϕ ∨ (ψ ∨ σ).
– Mauro ALLEGRANZA
Nov 13 at 13:20
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
$(p∧q) ∧ r ⊢ p ∧ (q∧r)$
In the sequent above, the only thing that happens is switching brackets between p&q and r, to q&r and separating out p. I could use the elimination rule between p&q and r, and get these separately, combine them with the introduction rule to get the conclusion.. But what step do I take to replace the brackets from p&q to q&r? Is their a rule that would help me move brackets?
propositional-calculus
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
asked Nov 13 at 12:45
haris.a.amin
11
$(p∧q) ∧ r ⊢ p ∧ (q∧r)$
In the sequent above, the only thing that happens is switching brackets between p&q and r, to q&r and separating out p. I could use the elimination rule between p&q and r, and get these separately, combine them with the introduction rule to get the conclusion.. But what step do I take to replace the brackets from p&q to q&r? Is their a rule that would help me move brackets?
propositional-calculus
propositional-calculus
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
asked Nov 13 at 12:45
haris.a.amin
11
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
asked Nov 13 at 12:45
haris.a.amin
11
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
edited Nov 13 at 13:15
Mauro ALLEGRANZA
63.4k448110
63.4k448110
asked Nov 13 at 12:45
haris.a.amin
11
asked Nov 13 at 12:45
haris.a.amin
11
asked Nov 13 at 12:45
haris.a.amin
11
11
1
The "rule that would help me move brackets" is the associativity property : but it seems that you have to prove it.
– Mauro ALLEGRANZA
Nov 13 at 12:50
As Mauro says: moving the brackets is typically a basic rule ... and it is typically not derivable from other rules of boolean algebra ... but it all depends on what rules you do have: so, which rules can or must you use? Maybe you have to give a formal proof but then once again: what rules are given to you to use?
– Bram28
Nov 13 at 12:55
See the post Natural deduction: Derive (ϕ ∨ ψ) ∨ σ → ϕ ∨ (ψ ∨ σ).
– Mauro ALLEGRANZA
Nov 13 at 13:20
add a comment |
1
The "rule that would help me move brackets" is the associativity property : but it seems that you have to prove it.
– Mauro ALLEGRANZA
Nov 13 at 12:50
As Mauro says: moving the brackets is typically a basic rule ... and it is typically not derivable from other rules of boolean algebra ... but it all depends on what rules you do have: so, which rules can or must you use? Maybe you have to give a formal proof but then once again: what rules are given to you to use?
– Bram28
Nov 13 at 12:55
See the post Natural deduction: Derive (ϕ ∨ ψ) ∨ σ → ϕ ∨ (ψ ∨ σ).
– Mauro ALLEGRANZA
Nov 13 at 13:20
1
1
The "rule that would help me move brackets" is the associativity property : but it seems that you have to prove it.
– Mauro ALLEGRANZA
Nov 13 at 12:50
The "rule that would help me move brackets" is the associativity property : but it seems that you have to prove it.
– Mauro ALLEGRANZA
Nov 13 at 12:50
As Mauro says: moving the brackets is typically a basic rule ... and it is typically not derivable from other rules of boolean algebra ... but it all depends on what rules you do have: so, which rules can or must you use? Maybe you have to give a formal proof but then once again: what rules are given to you to use?
– Bram28
Nov 13 at 12:55
As Mauro says: moving the brackets is typically a basic rule ... and it is typically not derivable from other rules of boolean algebra ... but it all depends on what rules you do have: so, which rules can or must you use? Maybe you have to give a formal proof but then once again: what rules are given to you to use?
– Bram28
Nov 13 at 12:55
See the post Natural deduction: Derive (ϕ ∨ ψ) ∨ σ → ϕ ∨ (ψ ∨ σ).
– Mauro ALLEGRANZA
Nov 13 at 13:20
See the post Natural deduction: Derive (ϕ ∨ ψ) ∨ σ → ϕ ∨ (ψ ∨ σ).
– Mauro ALLEGRANZA
Nov 13 at 13:20
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
If you want to prove it formally, you have to stay at the formal rules of the syntax, like e.g. :
The set well-formed propositional formulas is the smallest set $X$ with the properties
(i) $p_i ∈ X, i ∈ mathbb N$,
(ii) if $ϕ,ψ ∈ X$, then $(ϕ ∧ ψ) ∈ X$, and so on.
Thus, the correct formula will be :
$((p land q) land r)$,
and the proof will be :
1) $(p land q)$ --- from premise by $land$-elim
2) $r$ --- from premise by $land$-elim
3) $p$ --- from 1) by $land$-elim
4) $q$ --- from 1) by $land$-elim
5) $(q land r)$ --- from 4) and 2) by $land$-intro
and so on...
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
If you want to prove it formally, you have to stay at the formal rules of the syntax, like e.g. :
The set well-formed propositional formulas is the smallest set $X$ with the properties
(i) $p_i ∈ X, i ∈ mathbb N$,
(ii) if $ϕ,ψ ∈ X$, then $(ϕ ∧ ψ) ∈ X$, and so on.
Thus, the correct formula will be :
$((p land q) land r)$,
and the proof will be :
1) $(p land q)$ --- from premise by $land$-elim
2) $r$ --- from premise by $land$-elim
3) $p$ --- from 1) by $land$-elim
4) $q$ --- from 1) by $land$-elim
5) $(q land r)$ --- from 4) and 2) by $land$-intro
and so on...
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
add a comment |
up vote
1
down vote
If you want to prove it formally, you have to stay at the formal rules of the syntax, like e.g. :
The set well-formed propositional formulas is the smallest set $X$ with the properties
(i) $p_i ∈ X, i ∈ mathbb N$,
(ii) if $ϕ,ψ ∈ X$, then $(ϕ ∧ ψ) ∈ X$, and so on.
Thus, the correct formula will be :
$((p land q) land r)$,
and the proof will be :
1) $(p land q)$ --- from premise by $land$-elim
2) $r$ --- from premise by $land$-elim
3) $p$ --- from 1) by $land$-elim
4) $q$ --- from 1) by $land$-elim
5) $(q land r)$ --- from 4) and 2) by $land$-intro
and so on...
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
add a comment |
up vote
1
down vote
up vote
1
down vote
If you want to prove it formally, you have to stay at the formal rules of the syntax, like e.g. :
The set well-formed propositional formulas is the smallest set $X$ with the properties
(i) $p_i ∈ X, i ∈ mathbb N$,
(ii) if $ϕ,ψ ∈ X$, then $(ϕ ∧ ψ) ∈ X$, and so on.
Thus, the correct formula will be :
$((p land q) land r)$,
and the proof will be :
1) $(p land q)$ --- from premise by $land$-elim
2) $r$ --- from premise by $land$-elim
3) $p$ --- from 1) by $land$-elim
4) $q$ --- from 1) by $land$-elim
5) $(q land r)$ --- from 4) and 2) by $land$-intro
and so on...
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
If you want to prove it formally, you have to stay at the formal rules of the syntax, like e.g. :
The set well-formed propositional formulas is the smallest set $X$ with the properties
(i) $p_i ∈ X, i ∈ mathbb N$,
(ii) if $ϕ,ψ ∈ X$, then $(ϕ ∧ ψ) ∈ X$, and so on.
Thus, the correct formula will be :
$((p land q) land r)$,
and the proof will be :
1) $(p land q)$ --- from premise by $land$-elim
2) $r$ --- from premise by $land$-elim
3) $p$ --- from 1) by $land$-elim
4) $q$ --- from 1) by $land$-elim
5) $(q land r)$ --- from 4) and 2) by $land$-intro
and so on...
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
edited Nov 14 at 7:49
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
answered Nov 13 at 13:04
Mauro ALLEGRANZA
63.4k448110
63.4k448110
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2996676%2fproving-associativity-in-propositional-logic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
The "rule that would help me move brackets" is the associativity property : but it seems that you have to prove it.
– Mauro ALLEGRANZA
Nov 13 at 12:50
As Mauro says: moving the brackets is typically a basic rule ... and it is typically not derivable from other rules of boolean algebra ... but it all depends on what rules you do have: so, which rules can or must you use? Maybe you have to give a formal proof but then once again: what rules are given to you to use?
– Bram28
Nov 13 at 12:55
See the post Natural deduction: Derive (ϕ ∨ ψ) ∨ σ → ϕ ∨ (ψ ∨ σ).
– Mauro ALLEGRANZA
Nov 13 at 13:20