# Propositional and predicate logic, with quantifiers: Is there any research when it is ideal to explicitly teach in mathematics education?

In terms of helping students to understand propositional and predicate logic, with quantifiers, is there any research regarding when it is most advantageous for students studying mathematics, to first be explicitly taught the basics in logic?

In part, my question is motivated now, in relation to this question revealing a student's lack of understanding of basic propositional logic, and specifically, their lack of understanding of implication.

I understand that in undergraduate mathematics education, propositional and predicate logic with quantifiers may be covered over four weeks of a discrete math class, or first formally introduced in the early portion of an "introduction to proof" class offered in a math department, or first introduced after Calc I- III, DE, perhaps in a proof-based linear algebra course. But there are many undergraduate math programs that don't explicitly require majors to complete a full semester (or two) in logic, or math logic.

I am concerned that perhaps students are not taught early enough about logical operators like implication, or that $$\leq$$ means $$\lt$$ OR $$=$$, so that any expression $$a\leq b$$ means $$a \lt b$$, or $$a=b$$, and if either is true, then $$a\leq b$$ is true. Not to mention, there are students struggling with $$0\lt x \lt 12$$, which relies on, implicitly, an understanding of the logical operation of "AND": If $$0\lt x \lt 12$$, then $$(x> 0$$ AND $$x\lt 12)$$, that is, $$0\lt x \lt 12$$ is only true if BOTH $$x>0$$ AND $$x\lt 12$$ are true.

(But notice in all these scenarios, it is assumed that students already understand the definition of material implication: "if p, then q". And that isn't always the case for many students.)

I've just listed only a few important concepts that students seem to struggle with in understanding, even in high school.

If anyone has significant experience with respect to teaching logic, or is aware of programs that introduce basic logic explicitly, to students prior to college, or is aware of research in math education relating to when it is most advantageous to introduce logic to students studying math, I'd love to hear your input.

• Note, I just noticed this wonderful question and answer. I don't think my question is an exact duplicate of that question, but I find the question and answer very helpful and relevant to my question. – amWhy Jun 7 '19 at 15:58
• This is an excellent question, but "it seems students are not taught early enough..." is begging the question. Students struggling is not evidence that something has gone wrong. Perhaps high students who struggle with inequalities would benefit from having seen a more formal introduction to "AND" and "OR" - or perhaps that struggle to understand ≤ is valuable preparation for later understanding the more abstract notion of logical "OR". (I would guess that there are at least some students in both camps, though research might give some information about which is more common.) – Henry Towsner Jun 7 '19 at 16:10
• Sorry if my post seems to "beg the question", @HenryTowsner. Personally, I do believe that at least some components of propositional logic, (and similarly, at least some components of predicate logic with quantifiers) may be best introduced earlier. Especially if, in subsequent exposure to logic, those familiar examples are used as a stepping stone to help bridge students to more more abstract learning. Thanks for your comment! – amWhy Jun 7 '19 at 16:19
• (1) I believe the common opinion is that for centuries Elements by Euclid was a traditional path to logic, abstract thinking, "pure mathematics", proofs, etc. In particular, Kiselev's Planimetry has a section called Mathematical Propositions in the very first chapter, page 20. It talks about definitions, axioms, theorems, corollaries and lemmas. It mentions that any theorem can be rephrased in "if .... then" fashion. It mentions converse theorem (thus "if ... then" is a direct theorem) but does not mention "if and only if". – Rusty Core Jun 7 '19 at 17:36
• Possibly somewhat relevant is my answer to Logic and set theory textbook for high school. – Dave L Renfro Jun 8 '19 at 7:43

I'm afraid I don't know of any research that has been done to my satisfaction on this pedagogical issue of teaching logic, because all of those that I found so far (over many years) investigate methods that I consider very pedagogically unsuitable. Based on my experience in teaching mathematics, there are a few important aspects if one wishes to teach logic to every student (not just those who can figure it out on their own) so that they are capable of utilizing it in all their subsequent mathematical work:

1. There are many levels of logic (including both syntax and reasoning), and different levels are suitable for different kinds of people/students. At the basic level, one must be able to use full classical logic (including quantifiers, equality and predicate/function-symbols), which requires complete grasp of the intended meaning of the syntax (including the meaning of variables and scoping and contexts) as well as the deductive rules and why they are sound. This basic level should be taught early, and must be taught before calculus! I call this "using logic" (in contrast with "studying logic"). It would be foolish to try to teach students about logic (namely invoking mathematical tools to define and analyze first-order logic) before they even know how to use it.

2. There are many different possible variants of syntax and deductive systems, and choosing the wrong ones will spell pedagogical failure for almost all except students who already know how to reason logically (i.e. use classical logic, even though they don't know the name). I think that it is necessary to use a Fitch-style system because we want students to be able to use logic for more than trivial toy exercises.

3. But the exact syntax need not be the standard one. After all, it is true that the strange symbols "$$∀∃¬∧∨⇒$$" can be intimidating because it results in a significant compression of expressed meaning and requires decoding, which is not actually a crucial part of logic. For young students, even before learning any mathematical symbols, we can use standard English words. Of course, propositional logic should be taught first, and the only non-English we need to explain is brackets for indicating which parts of the sentence is evaluated first in the intended interpretation.

4. For students with programming background, it is especially easy to show how propositional logic can be expressed in terms of programs that comprise solely assertions and if-structures, corresponding to statements and if-subcontexts in the Fitch-style system respectively. I have personally used this to ensure that students have a 100% grasp of the deductive rules as well as have no problem with proof-by-contradiction. Even for students without programming background, one can do almost as well by showing them how to validate a Fitch-style proof given any truth-values of the atomic statements, in the same way the program would, and the goal is to ensure that every statement validated is in fact true. (See below for a fuller example.)

5. To move on to classical logic, one must teach variables properly as placeholders for objects, making sure to emphasize that different variables may refer to the same object. Again, there is a choice of variants in syntax and semantics. I think the pedagogically correct choice is to enforce that every variable must be declared (i.e. bound), whether in a universal-subcontext header such as "Given apple x:" or an existential instantiation such as "Let c be an apple such that ...". One concrete deductive system with all these features can be found here, which includes axiomatizations of PA and set theory.

6. Related to quantifiers, I do not think it is wise to use unrestricted quantifiers. Not only does natural language use restricted quantifiers all the time, unrestricted quantifiers are unwieldy and result in asymmetric representations of restricted quantification. When I want to affirm "Every fruit comes from a flower.", I do not want to have to say "For every object x, if x is a fruit then x comes from a flower.", if I want to deny it I want to simply say "Some fruit does not come from a flower.". Also, we cannot easily put together various axiomatizations of common structures if we do not use restricted quantifiers. Equivalently, we should work within multi-sorted first-order logic, even though one-sorted first-order logic is in theory sufficient.

7. I think we should teach game semantics, because it would solidify the meaning of quantifiers and the effect of their order, and because it works perfectly even for an infinite domain. This ties in nicely with the Fitch-style semantics as well, since a universal-subcontext is of the same nature; "Given apple x:" literally introduces a subcontext in which you are given an arbitrary apple x, and all you know about x is that it is an apple. Also, students would not make the common logical error of invalid quantifier switch. This clearly can be taught as early as students understand 2-player games.

8. Certainly all syntactic sugar must be explained in full at some point. For example, precedence rules for boolean operations, condensed quantifiers over the same type (e.g. "∀x,y∈S ( ... )"), chained relations (e.g. "A < B ≤ C = D"), short-forms (e.g. "A ≤ B" for "A < B ∨ A = B" and "A ≠ B" for "¬ A = B"). Also, chained relations may be written over multiple lines, and students must be made aware of how exactly to extract the desired conclusion (e.g. from "A < B ≤ C = D" to "A < D") that is often omitted from a proof.

9. I believe induction should actually be considered a core part of logic, rather than just being part of some mathematical theories. The litmus test of whether a student has complete grasp of basic logic is whether they can perform induction over predicates with quantifiers. Naturally, induction is best taught only after the students have a complete understanding of full classical logic and can prove simple theorems of PA−.

10. Finally, and most importantly, the teacher must strive to be 100% precise. The age at which the teacher should expect 100% precision in the Fitch-style proofs by the student is the same age at which the student can do simple programming (including for-loops). There is a sad reason why after one semester, almost all undergraduate CS students can write programs that the compiler accepts, but almost no undergraduate mathematics student can write perfect proofs in an actual deductive system. Incidentally, I often say that students who can easily use a deductive system no longer need to do so on paper, because they can do it mentally. Unfortunately, it is invariably people who cannot actually perform rigorous reasoning that fail to see the benefit of a deductive system, and often do not want to learn to use any (if it is not going to be tested in the exam).

11. I don't think 4 weeks is enough for a proper teaching of logic. I think an entire semester is just nice, because one should cover everything in my above points. Also, ideally all introductory mathematics courses should be done within the same deductive framework (such that the teacher skips steps but can furnish any omitted steps if asked). Without this, there is always a tendency for students to compartmentalize logic as "just another topic to be learned and later forgotten". Of course, if one really covers everything up to PA, and a little bit of real analysis, students may get a vague idea of really how everything in mathematics can be expressed in logical form. But if one fails to convey that all-encompassing nature of logic, one cannot expect students to really learn to use it. (It is like teaching them Latin for one semester but teaching all other subjects in English.)

Based on all the above points, as well as my personal experience in learning and teaching, I estimate that an optimal pedagogy would enable us to teach propositional logic at age 9-10, classical logic at age 11-12, along with programming, and then full PA at age 13-14. Note that basic logic should be applied across all subjects whenever applicable, and not just confined to "mathematics".

But since we will probably never get what we want, the next best is to have a whole semester-length course (≈50 hours over 4 months) dedicated to it, right at the beginning of undergraduate studies. I do not think it should be restricted to mathematics majors either, since basic logic is a critical component in any serious pursuit of knowledge. In my opinion, mathematics majors ought to be taught a fair bit more than basic logic, probably up to the completeness and compactness theorems for countable first-order theories, spanning two courses in total, but that is for another discussion. =)

As an example of proof-by-contradiction (i.e. using ⊥-elim), consider the following Fitch-style proof:

If P:
If not P:
P.
not P.
false.
not not P.


By definition of subcontext, the first subcontext under "If P:" represents the subcontext (sub-scenario) in which (P) is true. The second subcontext under "If not P:" is nested inside the first subcontext, so it represents the further subcontext in which (not P) is true. Well, can this inner subcontext be possible? No, that scenario simply cannot occur, and we can see that from the proof itself since both (P) and (not P) are true within it. Thus we can conclude that the negation of the innermost subcontext header (not P) is true in its context. Note that we cannot claim "not not P" in the global context (i.e. under no conditions). The outer subcontext may occur, and it is just the inner subcontext that is impossible, so within the scenario where (P) is true, we can conclude that (not P) is false.

Of course, this kind of explanation must be done slowly and repeated until it clicks. People who meet logical reasoning for the first time need time to warm up their brains.

• Re: "There is a sad reason why after one semester, almost all undergraduate CS students can write programs that the compiler accepts, but almost no undergraduate mathematics student can write perfect proofs in an actual deductive system." Students would not learn to write programs without immediate feedback from the compiler. Perhaps they should use proof-checking software to give them immediate feedback on their proofs. May I humbly suggest my proof-checking freeware available at my homepage: http//www.dcproof.com It is designed to introduce students to the basic methods of proof. – Dan Christensen Jun 13 '19 at 15:27