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: Jan Burse on 8 Aug 2010 06:12 Nam Nguyen schrieb: > I have a question: Let A be an atomic formula of an L. > As far as FOL proof is concerned, if (A \/ ~A) signifies > a tautology and (A /\ ~A) a contradiction, what would > (A xor ~A) signify? > A xor ~A is also a tautology, in the same sense that A \/ ~A is a tautology. You can define a tautology as a formula having a T in each row of the truth table: A ~A A xor ~A F T T T F T A ~A A \/ ~A F T T T F T There a lot more formulae based only on one propositional variable, that are tautologies in classical logic. Here are some examples: (~A -> A) -> A ~~A -> A f -> A Etc.. Bye
From: Nam Nguyen on 8 Aug 2010 11:46 Jan Burse wrote: > Nam Nguyen schrieb: >> I have a question: Let A be an atomic formula of an L. >> As far as FOL proof is concerned, if (A \/ ~A) signifies >> a tautology and (A /\ ~A) a contradiction, what would >> (A xor ~A) signify? >> > > A xor ~A is also a tautology, in the same sense that > A \/ ~A is a tautology. You can define a tautology > as a formula having a T in each row of the truth table: > > A ~A A xor ~A > F T T > T F T > > A ~A A \/ ~A > F T T > T F T Please note the word "proof" in my "As far as FOL proof is concerned". Are we then saying in _all_ formal systems there's a _proof_ for (A xor ~A)? > > There a lot more formulae based only on one propositional > variable, that are tautologies in classical logic. > Here are some examples: > > (~A -> A) -> A > ~~A -> A > f -> A > Etc.. > > Bye -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Nam Nguyen on 8 Aug 2010 11:51 William Elliot wrote: > On Sun, 8 Aug 2010, Nam Nguyen wrote: >> William Elliot wrote: >>> On Sat, 7 Aug 2010, Nam Nguyen wrote: >>> >>>> I have a question: Let A be an atomic formula of an L. >>>> As far as FOL proof is concerned, if (A \/ ~A) signifies >>>> a tautology and (A /\ ~A) a contradiction, what would >>>> (A xor ~A) signify? >>>> >>> A xor ~A <-> A&~~A v ~A&~A >> >> So, then, what does e.g. (A or ~A) signify to you? > > A v ~A <-> ~(~A & ~~A) So, to you, (A or ~A) would NOT signify the formula is provable in all formal system? And (A and ~A), to you, would NOT signify the formula is provable in all inconsistent systems? What do you think the word "signify" would mean in this context? -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Nam Nguyen on 8 Aug 2010 12:30 PiperAlpha167 wrote: > On Aug 7, 5:42 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: >> I have a question: Let A be an atomic formula of an L. >> As far as FOL proof is concerned, if (A \/ ~A) signifies >> a tautology and (A /\ ~A) a contradiction, what would >> (A xor ~A) signify? > > (A V ~A) & ~(A & ~A) > > You might take a look at: > > http://www.earlham.edu/~peters/courses/logsys/pnc-pem.htm Thanks for the link. As mentioned with JB, the context here is "FOL proof". My intention is to claim (A xor ~A) _signify_ the impossibility to syntactically prove the consistency of a consistent system. But I'm not so sure the formula would be a correct characterization of such. The scodnary intention is to go from there and find a replacement for CON(T) that doesn't depend on the notion of the natural numbers. (A very long shot though, imho). -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Jan Burse on 8 Aug 2010 15:19
Nam Nguyen schrieb: > Please note the word "proof" in my "As far as FOL proof is > concerned". Are we then saying in _all_ formal systems > there's a _proof_ for (A xor ~A)? Your saying "As far as FOL proof is concerned (A \/ ~A) signifies a tautology" doesn't make much sence. Since the notion tautology is not related to derivability in a proof system, it is related to a notion of truth. A tautology(*) is a formula that is true under all interpretations. A proof system does not primarly define a notion of interpretation. A proof system usually defines a notion of derivation. A tautology in a first order language is not simply a tautology in propositional language where we replace the propositional variables by some first order formulae and eventually prepend quantifiers. This would give a too small a set of always true sentences. But if your proof system is sound and complete, i.e. if we have A is a valid consequence (we only need to exhibit one derivation) in the proof system from the empty set of premisses iff A is a tautology (i.e. true in all interpretation, not only in one interpretation, but in all!) Then I might interpret your saying "As far as FOL is concerned (A \/ ~A) signifies a tautology", as meaning A \/ ~A is a valid consequence. I currently don't know exactly how the notion of tautology in the narrow sense, i.e. propositional tautology with first order formula substituted and quantifiers prended, would relate. But what should your saying "As far as FOL is concerned (A /\ ~A) signifies a contradiction" mean? The difficulty here is the same. The notion of contradiction, as a property of a formula, is not related to derivability in a proof system, it is related to a notion of truth. A contradiction(*) is a formula that is false under all interpretations. There is now an easy relationship between this truth notion and the derivation notion of a proof system, provided it is sound and complete: ~A is a valid consequence iff A is a contradiction Bye (*) http://en.wikipedia.org/wiki/Tautology_(logic) |