Talk:Propositional calculus/Archive 2

Classical and Non-Classical Propositional Calculus

So this article, as well as the Rule of replacement articles, treat the Propositional Calculus as inherently classical. There is mention of Intuitionist logic on this page, but not, say, the pages for Transposition (logic) or De Morgan's laws. (It does get mentioned on Double negative elimination.) I wanted to know if this was deliberate and well-motivated, or an oversight.

Is there any reason I (or others, if they like) should not go ahead and point out places where classical logic differs from prominent non-classical logics, and add the adjective classical in appropriate places?

Notapipe (talk) 04:50, 5 June 2012 (UTC)

You speak as if those other logics are just as good as classical logic. They are not. Classical logic is the true logic. The others such as intuitionistic logic are just crippled variants which might better be described as logic-like algebras. Any competent person uses classical logic when dealing with serious problems.

If you want to add a brief paragraph at the end of those articles saying how things are different in this or that non-classical logic, then you may do so. But I would not advise changing the bulk of the articles, especially the leads. JRSpriggs (talk) 07:51, 5 June 2012 (UTC)

This is a misunderstanding of the difference between intuitionistic and classical logic. Intuitionistic logic does not oppose to classical logic. It is just a refinement of it, where $\vee$, $\exists$ and the atoms have a stronger meaning which is not accessible from within classical logic. Indeed, the formula $A\vee B$ in classical logic is not interpreted differently from $\neg \neg (A\vee B)$, and similarly for $\exists x~A$ which is not interpreted differently from $\neg \neg \exists x~A$, and similarly for an atom $p$ which is not interpreted differently from $\neg \neg p$.

This is obvious when intuitionistic logic and classical logic are both expressed in the more fine-grained framework of linear logic. In linear logic, intuitionistic $A\vee B$ is written $A\oplus B$ while classical $A\vee B$ is interpreted as $?(A\oplus B)$ (and similarly for $\exists$ and atoms).

Intuitionistic logic is a refinement of classical logic in that it does support two distinct forms of $A\vee B$, namely $A\vee B$ meaning $A\oplus B$, from which we have the syntactic knowledge that one side of the disjunction actually holds and $\neg \neg (A\vee B)$ from which we have no way to ensure that at least one side of the disjunction actually holds, while classical logic only supports one form of $A\vee B$, simply written $A\vee B$ but meaning $\neg \neg (A\oplus B)$, of which no information is accessible on whether one side actually holds (and similarly for $\exists x~A$ and the atoms).

Another way to see that intuitionistic is a refinement of classical logic is that any Boolean algebra is a Heyting algebra, but not conversely. Otherwise said, intuitionistic logic is rich enough to interpret classical logic but not conversely. I.e. classical logic is a subset of intuitionistic logic and this is obvious as soon as we accept to think about $A\vee B$ in classical logic as $\neg (\neg A\wedge \neg B)$ and $\exists x~A$ as $\neg (\forall x~\neg A)$, and atom $p$ as $\neg \neg p'$ for p' a more elementary "intuitionistic" atom. Indeed, intuitionistic logic and classical logic coincide on the negative sub-language of logic which avoids $\vee$ and $\exists$, and which assumes that any occurrence of an atom itself is prefixed by a negation. By the way, this inclusion of classical logic within intuitionistic logic is what expresses Double-negation translation.

Classical logic has accordingly a very simple two-value semantics which makes it a very appealing subset of intuitionistic logic, of which the algebraic semantics is move involved, consistently with its more fine-grained structure. However, proof-theoretically speaking, intuitionistic logic is simpler than classical logic as it is just defined from a smaller set of inference rules: excluded-middle is discarded and it holds only on the restriction of intuitionistic logic to its purely negative, i.e. classical, subset. Hugo Herbelin (talk) 14:09, 25 March 2014 (UTC)

You apparently don't understand intuitionistic logic. I also don't know where you got the non-logical symbols. — Arthur Rubin (talk) 06:57, 26 March 2014 (UTC)

Never mind. You assume linear logic is an appropriate context/proof system for discussing propositional calculus. As you point out, classical logic can be embedded in intuitionistic logic. Intuitionistic logic can be embedded in (modal) classical logic, as well. — Arthur Rubin (talk) 09:43, 26 March 2014 (UTC)

Sure, modal classical logic is a refinement of classical logic which is refined enough to express the meaning of the connectives of intuitionistic logic. In particular, in modal classical logic, $\Box A$ is in general not equivalent to $\neg \neg \Box A$ allowing to recover in modal classical logic an intuitionistic disjunction $A\vee B$, namely $\Box (A\vee B)$ in modal classical logic, and an intuitionistic existential quantification $\exists x\,A$, namely $\Box \exists x\,A$, which satisfy the disjunction and existence properties and are hence de facto more informative than their double negation, what (non modal) classical logic is not able to provide.

Maybe, one way to better explain the difference between intuitionistic logic and classical logic is that intuitionistic logic has more connectives, and more atoms, than classical logic, and in particular that $\vee$ and $\exists$, despite similar notations, are not the same connectives in intuitionistic and classical logic.

The common idea that intuitionistic logic proves less theorems than classical logic is an illusion, based on the belief that the notations $\vee$, or $\exists$, or $p$ (for $p$ an atom) mean the same in intuitionistic and classical logic. In particular, excluded-middle holds in intuitionistic logic for the combined connective $\neg \neg (A\vee B)$, and this is consistent with the view that the notation $A\vee B$ in classical logic is nothing but an abbreviation for $\neg \neg (A\vee B)$ where $\vee$ is now the intuitionistic connective. Hugo Herbelin (talk) 11:39, 29 March 2014 (UTC)

Yes, intuitionistic logic makes more distinctions than classical logic. That is the problem! It makes unnecessary distinctions where the underlying reality does not. Making fewer distinctions is a sign of the strength of classical logic, not a defect. JRSpriggs (talk) 09:09, 30 March 2014 (UTC)

I do not consider classical logic to be faulty (it has actually been a research subject of mine for quite a number of years). In particular, its two-valued model is extremely appealing. I would not claim however that intuitionistic $\vee$ and $\exists$ are not part of the "reality". When you intuitionistically assert $\exists x\,A(x)$ you assert more about the underlying reality (existence of an effective witness $t$ such that $A(t)$) than when you classically assert $\exists x\,A(x)$. Hugo Herbelin (talk) 21:26, 31 March 2014 (UTC)

JRSpriggs, please expand on what you think the "underlying reality" is. Also, you seem to think that the assumption of arbitrary stuff is a sign of strength of a theory. I don't follow. Please explain. --Daniel5Ko (talk) 01:34, 5 April 2014 (UTC)

To Daniel5Ko: Certain things exist. They can be described (at least in part), but there are other descriptions which do not apply to any existent. In other words, every potential thing or condition either exists or it does not. There are just those two alternatives. Hence two-valued logic is appropriate. I am not the one who is introducing "arbitrary stuff", you are. One theory is stronger than another if it gives you more of the truth about the subject. So the strongest theory is the one which proves the most theorems without proving a falsehood (as in the case of a contradiction).

If you disagree, then I challenge you to provide a real-world example where ¬¬P holds, but P does not. JRSpriggs (talk) 06:20, 5 April 2014 (UTC)

Of course, if you define that the "underlying reality" is classical logic, then classical logic is the best match to the underlying reality.

By your definition of strength of theory, intuitionistic logic is stronger than classical logic. It can prove everything classical logic can (modulo some trivial coding; see bits of Hugo's text for a summary). In addition, it can talk about things which are invisible classically. The invisibility results from making the assumption that P is the same as ¬¬P.

About the proposed challenge: Let's say I can't give an example or that you are able to prove that no such example can be given. Does it follow that P and ¬¬P are equivalent? No!, Only classical reasoning would enable that :P --Daniel5Ko (talk) 02:20, 6 April 2014 (UTC)

I have never heard of a modal classical logic in which $\Box A$ is different from $\neg \neg \Box A$ or $\Box \neg \neg A$. (Well, not exactly the case. There are examples of epistemic logic and doxastic logic where $\Box A$ may be different then $\Box \neg \neg A$, but that's not what I would call "classical" modal logic.) — Arthur Rubin (talk) 15:17, 30 March 2014 (UTC)

You are right, I too hastly looked at the definition of classical modal logic and misunderstood it. If I now hopefully understand it correctly, what does not hold in general is the equivalence of $\Box \neg \Box \neg A$ and $A$. Nevertheless, as modal classical logic is able to simulate intuitionistic logic, it can only be because it has the power to express the intuitionistic versions of $A\vee B$ and $\exists x\,A$ (which actually are presumably $\Box A\vee \Box B$, rather than $\Box (A\vee B)$, and $\exists x\,\Box A$, rather than $\Box \exists x\,A$, is that correct?). Hugo Herbelin (talk) 21:26, 31 March 2014 (UTC)

I don't recall the precise embedding, something like that (where $\Box$ distributes over $\wedge$and "commutes" with $\forall$. Suffice it to say that intuitionistic logic#Relation to modal logic is not the embedding I had in mind; it appears not to handle quantifiers correctly. — Arthur Rubin (talk) 17:27, 14 January 2015 (UTC)

Maybe a missing rule in Basic_and_derived_argument_forms

I cannot remember the name of the rule

x OR (x AND y)

reduces to

x

A truth table to help verify this

x   y   x&y   x|(x&y)

0   0   0   0

0   1   0   0

1   0   0   1

1   1   1   1

similarly

x AND (x OR y)

reduces to

x

A truth table to help verify this

x   y   x|y   x&(x|y)

0   0   0   0

0   1   1   0

1   0   1   1

1   1   1   1
— Preceding unsigned comment added by 65.129.216.147 (talk) 09:03, 29 January 2015 (UTC)

It's generally called "absorption", and you are probably correct that it should be a derived rule. — Arthur Rubin (talk) 10:04, 29 January 2015 (UTC)

See "Proven Properties" / "Abs1" in Boolean algebra (structure)#Axiomatics for a derivation, however in algebraic style. - Jochen Burghardt (talk) 15:26, 29 January 2015 (UTC)

Original source for the section "Generic description of a propositional calculus"?

Could the author of the section "Generic description of a propositional calculus" please give a reference to the (an) original source? Thanks! — Preceding unsigned comment added by 83.76.55.163 (talk) 13:38, 10 November 2015 (UTC)

Which Basic and derived argument forms are theorems?

In the article section Basic and derived argument forms, a list of 31 well-known classical deduction rules. I'm assuming that these rules are not all independent. For example, rule 2, Modus tollens follows from rule 1, modus ponens, plus rule 22, transposition. It would be nice if the article could choose a short list of logical axioms which the rest can be derived from. I thought maybe the 11 axioms in the section Example 2. Natural deduction system, which includes Modus Ponens for example. I was confused because some of the axioms are in both lists (eg Modus ponens, conjunction elimination, conjunction introduction) are in both lists, although with different names. Several of the axioms are not in the list at all. Is there a good logical axiom list to derive these 31 tautologies from? -lethe ^{talk +} 23:19, 23 October 2017 (UTC)

See Mendelson's axiom system at List of logic systems for one fairly simple set of axioms. Part of the problem is that your choice of which logical operations are primitive affects which axioms you need to include. Mendelson uses implication and negation as his primitive operations. I also like the Tarski–Bernays–Wajsberg axiom system. JRSpriggs (talk) 02:16, 24 October 2017 (UTC)

Wow ok we only need three axioms. Is Mendelson's three axioms the same as the Hilbert system? Also, does Tarski–Bernays–Wajsberg axiom include modus ponens as an explicit axiom, while all the others have it implicit? Thinking here of ((A→B)→A)→B) listed on that page. PS thanks for the reply. -lethe ^{talk +} 05:31, 4 December 2017 (UTC)

No and No. JRSpriggs (talk) 06:00, 4 December 2017 (UTC)

Thanks for answering a few questions, it was helpful. -lethe ^{talk +} 19:43, 5 January 2018 (UTC)

Why 10 rules? (natural deduction)

I just made an edit where I changed "ten" to "eleven" and "the first nine" to "the first 10". Why did the original author say that there are only 10 rules? There are obviously 11 listed there. Maybe you didn't mean to include the double negation one, which is a derived/variant rule?

I searched through the revision history to find how it happened. Imagine my amazement when I discovered that I was responsible. Originally, there were ten rules. Then someone changed the name of "negation introduction" to "modus tollens" which correctly described the rule as then stated, but was not what was wanted. So I changed the name back and corrected the rule instead. In the process, I added "negation elimination". However, I failed to change the number of rules in the paragraph above. Please see here. Thank you for fixing the numbers. JRSpriggs (talk) 01:32, 29 October 2018 (UTC)

Actually, the double negation elimination rule is necessary to make it classical logic rather than intuitionistic logic. All the other rules are compatible with intuitionism. JRSpriggs (talk) 03:02, 29 October 2018 (UTC)

Right, I see. Thank you, too, I was not aware of the last thing you mentioned, and it is good to know. 86.127.147.251 (talk) 20:14, 29 October 2018 (UTC)

Negation elimination can be deduced from the other rules (including double negation elimination). I presume that is why the original author of the rules left it out. However, I wanted to have a list of rules which would be adequate for intuitionistic logic, if double negation elimination were removed. JRSpriggs (talk) 21:20, 30 October 2018 (UTC)

I see. Thank you! I was unaware of this distinction since I didn't study logic as a mathematician (I studied CS), so most of the theoretical aspects were rushed over in my course. Your reply fortunately opened lots of new questions for me, since I realized there was more to this subject of PL than natural deduction and that my grasp on this subject is very weak. I see that mathematical logic is a very interesting subject and I'm surprised that it's not more popular considering all the contributions it had to Math and CS, such as the λ-calculus. It's odd that I heard about Bachelor's in Mathematics that don't even teach logic at all. 86.127.147.251 (talk) 23:44, 30 October 2018 (UTC)

By "CS" do you mean computer science, elliptic functions, or something else?

If you have become interested in propositional logic, you might want to look at: list of logic systems, implicational propositional calculus, and deduction theorem. They are my favorites. And there are many other articles related to it.

I recently added a section paraconsistent logic#An ideal three-valued paraconsistent logic (although I do not recommend paraconsistent logic generally). JRSpriggs (talk) 03:53, 31 October 2018 (UTC)

Computer Science.86.127.147.251 (talk) 16:46, 31 October 2018 (UTC)

Thank you for your suggestions! It's a coincidence that I recently found out about the deduction theorem and I found it interesting since it explained conditional proofs in math and =>-intro in natural deduction. 86.127.147.251 (talk) 16:46, 31 October 2018 (UTC)

I read a bit and it sounds interesting, thanks for the suggestion! 86.127.147.251 (talk) 16:46, 31 October 2018 (UTC)

Please do not insert your comments in the middle of my comment. It makes it hard to read my comment and to know who wrote what. It is also insulting (unintentionally, I am sure). If you are going to continue editing Wikipedia, you should register an account. I am glad that you are now signing your comments. JRSpriggs (talk) 17:42, 31 October 2018 (UTC)

Oops, sorry. I thought those were 3 different replies (because of the extremely short, 1-line paragraphs) from different people: you and 2 (ironically) unsigned anonymous repliers.188.27.66.126 (talk) 14:52, 9 November 2018 (UTC)

I always check the revision history to avoid making such mistakes. JRSpriggs (talk) 01:40, 10 November 2018 (UTC)

That's a good point, I'll remember that in the future.188.26.138.131 (talk) 21:47, 15 November 2018 (UTC)

Basic and derived argument forms

 Comment: The purpose of section Propositional calculus#Basic and derived argument forms is not quite clear, and I guess this is the reason for the dispute between Ans and JRSpriggs. The table lists more than a minimal ("basic") set of rules; there are many such minimal sets, anyway (one of them is the Huntington 1904 axiomatization, given, in algebraic form, in Boolean algebra (structure)#Axiomatics). On the other hand, the set of derived rules is infinite, so we can't list all of them. Which ones to select is then a matter of taste. Maybe, restricting to those rules that have an own article is (1) a good idea, and (2) closest to the current state of the table; however, I'm afraid some WP:EASTEREGGs need to be removed. — As for double negation elimination, if it is listed, I suggest to mention that it is not accepted in intuitionistic logic. - Jochen Burghardt (talk) 10:56, 3 February 2020 (UTC)

Merger proposal

I propose to merge Zeroth-order logic into Propositional calculus. I think that the content in the Zeroth-order logic article can easily be explained in the context of Propositional calculus, given that it is a synonym of propositional calculus, and the propositional calculus article is of a reasonable size that the merging of zeroth order logic will not cause any problems as far as article size is concerned. KazMalKen (talk) 20:35, 16 July 2020 (UTC)

Proving completeness

@Dan Gluck: In light of your recent change to the section on completeness, you may be interested in Talk:List of Hilbert systems#How to establish completeness in a two-valued (i.e. classical) logic. I am wondering whether you need to show p→¬¬p. JRSpriggs (talk) 00:48, 22 July 2020 (UTC)

Interesting, I'll try to have a thorough look at that. I'm currently working on inserting proofs for "simple" theorems in the Hilbert system propositional part (i.e. the one with only negation and "if-then"). Seems to me in place since this is a kind of a "standard" system but the proofs are highly non trivial. As a by-product, it will be a reference for this article to show that the theorems required for completeness indeed hold. The p→¬¬p proof happen to be extremely lengthy... It is needed as an intermediate for showing the several theorems needed for completeness indeed hold for that system. Not sure if you can circumvent it, but I don't think it's required by itself in the particular completeness proof appearing in this article (I think it IS needed for another proof I have seen).Dan Gluck (talk) 17:11, 22 July 2020 (UTC)

sidetable top-row issue

the "Transformation rules" seems to point to "Rules of inference" 2A02:2149:8B8D:A500:F8EB:7B5:F565:4A87 (talk) 16:36, 7 July 2022 (UTC)

Commutation (3) description change

I propose to change the description of Commutation (3) to "(p iff q) is equiv. to (q iff p)" instead of the current "(p is equiv. to q) is equiv. to (q is equiv. to p)". Jochen Burghardt says this introduces "inconsistent" style, however it is consistent with the descriptions of Material Equivalence (1) thru (3), in which "iff" refers to the biconditional connective, whilst "is equiv. to" refers to metalogical equivalence. NicolinoChess31415926 (talk) 22:16, 23 May 2023 (UTC)

Sorry for the late reply. I see your point now: you distinguish between $\leftrightarrow$ ("iff") and a $\vdash$ holding in both directions ("is equiv. to"). My fault, please apologize. I'll redo your edits.

As another, related, issue, what about replacing in the Sequent column $\vdash$ by e.g. $\dashv \vdash$ whenever metalogical equivalence holds? - Jochen Burghardt (talk) 16:23, 31 May 2023 (UTC)

Yeah, I agree it would be good to use $\dashv \vdash$ for that. NicolinoChess31415926 (talk) 20:43, 9 June 2023 (UTC)

 Done - Jochen Burghardt (talk) 16:34, 10 June 2023 (UTC)