A question on XOR
in [Logic]
|
Prev: Accounting Information Systems 11E Romney Solutions manual
Next: Godel had no idea what truth is so incompleteness theorem is meaningless
From: Nam Nguyen on 11 Aug 2010 12:42 Nam Nguyen wrote: > Jan Burse wrote: >> Nam Nguyen wrote: >>> Be that as it may, a contraction could also be defined >>> as a formula of the form (F /\ ~F) for some formula F. > > Despite what you said below, (F /\ ~F) can be defined as > a contraction purely on the semantics of the logical symbols > /\, and ~ (and no theory needs to be involved). Well, OK, let's take your hints below and define a contradiction as a formula that's logically equivalent to (F /\ ~F) for some F. > >> >> Well you may find the definition that a theory T is >> contradictory iff there is a formula B, such that >> B and ~B are derivable from it. >> >> But this is not the same as to say that a contradictory >> formula A has the form B /\ ~B. For example the following >> formulae are all also contradictory in itself, but do >> not have this form: >> >> f (i) >> p /\ (p -> ~p) (ii) >> ~(p \/ ~p) (iii) >> p /\ ~~~p (iv) >> Etc... >> >> They are contradictory in the sense that their negation >> can be derived, and in the sense that they are always >> false and in the sense when taken as a theory, i.e. >> a theory consisting of this single formula A, then we >> can find formula B and ~B that are derivable from this >> theory. >> >> In fact it happens that we can pick A itself as a witness >> B for a contradiction. Because when A is contradictory >> its negation can be derived: >> >> |- ~A >> >> And by weakening we have trivially: >> >> A |- ~A >> >> Further by identity we have: >> >> A |- A >> >> So indeed A and ~A follow from the theory A, when A is >> contradictory. More meta reasoning would show that we >> can pick any formula C as a witness, since classical >> logic explodes upon inconsistency. >> >> Best Regards >> > > -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Jan Burse on 11 Aug 2010 16:19 Nam Nguyen schrieb: > Well, OK, let's take your hints below and define a contradiction > as a formula that's logically equivalent to (F /\ ~F) for some F. Well logically equivalent means: |- A <-> F /\ ~F (i) Which can be shown to be the same as: |- A <-> f (ii) Which can be shown to be the same as: |- ~A (iii) Agreed! Bye BTW: The xor, is the same as ~(A <-> B). I have been seeing your xor pattern A xor ~A in the modal representation of the problem you posed. The modal representation was: ~<2>(~[1]A -> ~<2>A) (a) Which can be shown to be the same as (by contraposition): ~<2>(<2>A -> [1]A) (b) Now if we know from an other source that the following holds: [1]A -> <2>A Then we could add this to (b), i.e., we would have ~<2>((<2>A -> [1]A) & t) (c) And then: ~<2>((<2>A -> [1]A) & ([1]A -> <2>A)) (d) And thus: ~<2>(<2>A <-> [1]A) There is a relationship between diamond and box, thus we would have: ~<2>(<2>A <-> ~<1>~A) Now dropping both modal operators I arrive at: ~(A <-> ~~A) Hm, not quite what you said. This would be A xor ~~A, and not A xor ~A. And it is not a tautology, but a contradiction. Ok forget about it, this was just an idea. Well a further idea: In intuitionistic logic respectively minimal logic or even super intuitionistic logic the implication has a modal operator built in(*). So the above might be really a formula signifying what you are looking for, but in a non classical logic. Bye (*) Inituitionistic (minimal, super intuitionistic) A ~> B can be view as [](A -> B), where -> is classical.
From: Nam Nguyen on 11 Aug 2010 16:41 Jan Burse wrote: > Nam Nguyen schrieb: >> Well, OK, let's take your hints below and define a contradiction >> as a formula that's logically equivalent to (F /\ ~F) for some F. > > Well logically equivalent means: > > |- A <-> F /\ ~F (i) No. It means: {A} |- (F /\ ~F) is true _and_ {F /\ ~F} |- (A) is true. Which means you have to _prove_ them both. > > Which can be shown to be the same as: > > |- A <-> f (ii) > > Which can be shown to be the same as: > > |- ~A (iii) > > Agreed! Again No. "|-" is context sensitive, and shouldn't be as obscured as a combination of the 3 usages you showed above. > > Bye > > BTW: The xor, is the same as ~(A <-> B). I have been seeing > your xor pattern A xor ~A in the modal representation of > the problem you posed. The modal representation was: > > ~<2>(~[1]A -> ~<2>A) (a) > > Which can be shown to be the same as (by contraposition): > > ~<2>(<2>A -> [1]A) (b) > > Now if we know from an other source that the following holds: > > [1]A -> <2>A > > Then we could add this to (b), i.e., we would have > > ~<2>((<2>A -> [1]A) & t) (c) > > And then: > > ~<2>((<2>A -> [1]A) & ([1]A -> <2>A)) (d) > > And thus: > > ~<2>(<2>A <-> [1]A) > > There is a relationship between diamond and box, thus we > would have: > > ~<2>(<2>A <-> ~<1>~A) > > Now dropping both modal operators I arrive at: > > ~(A <-> ~~A) > > Hm, not quite what you said. This would be A xor ~~A, > and not A xor ~A. And it is not a tautology, but a > contradiction. Ok forget about it, this was just > an idea. > > Well a further idea: In intuitionistic logic respectively > minimal logic or even super intuitionistic logic the > implication has a modal operator built in(*). So the > above might be really a formula signifying what you are > looking for, but in a non classical logic. > > Bye > > (*) > Inituitionistic (minimal, super intuitionistic) A ~> B > can be view as [](A -> B), where -> is classical. -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Jan Burse on 11 Aug 2010 17:00 Nam Nguyen schrieb: > Jan Burse wrote: >> Nam Nguyen schrieb: >>> Well, OK, let's take your hints below and define a contradiction >>> as a formula that's logically equivalent to (F /\ ~F) for some F. >> >> Well logically equivalent means: >> >> |- A <-> F /\ ~F (i) > > No. It means: {A} |- (F /\ ~F) is true _and_ {F /\ ~F} |- (A) is true. > Which means you have to _prove_ them both. Yes I know the above, it is also sometimes denoted as: A -||- F /\ ~F Well if you have a logic where the deduction theorem is always available (such FOL logics do exist), then you can apply it, and you will see: {A} |- F /\ ~F (1) Is the same as: {} |- A -> F /\ ~F (2) And: {F /\ ~F} |- A (3) Is the same as: {} |- F /\ ~F -> A (4) Now if your logic behaves correctly with respect to conjunction we see that (2) and (4) are the same as: {} |- (A -> F /\ ~F) & (F /\ ~F -> A) Is the same as: {} |- A <-> F /\ ~F I am showing you this because I also needed some moment in my live to convince myself about this. So please take also your time to convice yourself about this. It is quite handy and gives the <-> in logic a special role. The rest of my previous post then follows. Bye
From: Nam Nguyen on 11 Aug 2010 17:13
Jan Burse wrote: > Nam Nguyen schrieb: >> Jan Burse wrote: >>> Nam Nguyen schrieb: >>>> Well, OK, let's take your hints below and define a contradiction >>>> as a formula that's logically equivalent to (F /\ ~F) for some F. >>> >>> Well logically equivalent means: >>> >>> |- A <-> F /\ ~F (i) >> >> No. It means: {A} |- (F /\ ~F) is true _and_ {F /\ ~F} |- (A) is true. >> Which means you have to _prove_ them both. > > Yes I know the above, it is also sometimes denoted as: > > A -||- F /\ ~F I think I'm OK with this notation as long as we're clear on the 2 formal systems involved. > > Well if you have a logic where the deduction theorem is always > available (such FOL logics do exist), then you can apply it, > and you will see: > > {A} |- F /\ ~F (1) I'm not familiar with the deduction theorem, but isn't it true {A} |- F /\ ~F would already follow the definition we both stipulated above? If the definition of equivalence says that A <-> B iff: {A} |- B is true _and_ {B} |- A is true and if we already prove A to be equivalent to F /\ ~F then we could further define A to be a contradiction. Why make things more complicated than it should be? Also Part of what I'm not clear below is what you'd mean by "{}": what formal system would that be? > > Is the same as: > > {} |- A -> F /\ ~F (2) > > And: > > {F /\ ~F} |- A (3) > > Is the same as: > > {} |- F /\ ~F -> A (4) > > Now if your logic behaves correctly with respect to conjunction > we see that (2) and (4) are the same as: > > {} |- (A -> F /\ ~F) & (F /\ ~F -> A) > > Is the same as: > > {} |- A <-> F /\ ~F > > I am showing you this because I also needed some moment in my live > to convince myself about this. So please take also your time to convice > yourself about this. It is quite handy and gives the <-> in logic > a special role. > > The rest of my previous post then follows. > > Bye -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt ----------------------------------------------------------- |