1. Aim and Context
This century has seen massive advances in the methods of formal logic and this has lead to equally massive changes in the content of courses on logic. At the same time, a wealth of research has shown that human cognition rarely follows the patterns of formal logic and that, consequently, formal logic is difficult to learn. (See [GILH88] for a well-balanced review of research into the extent to which people use logic in their normal thought patterns, especially Chapter 5.)
The research presented in this paper was motivated by the desire to develop new approaches to teaching logic which would enhance both the learning of formal logic and the transfer of that learning to practical situations. The research addresses propositional logic and the problems associated with the use of truth tables to define logical operations. For instance, it is well established that people have difficulty reasoning about conditional statements and that the truth-functional definition of material implication is not intuitively obvious [see for instance OBRI72, OBRI73, SHAP73, GILH88 pp113-123, EVAN82 Chapter 9, WASO83]. Various explanations have been offered to account for this and various techniques have been used to justify the truth-functional definition [CLAR96].
The first year computer science course at the University of Natal (Pietermaritzburg) includes an introductory logic module which covers various aspects of informal logic, set theory, propositional logic, predicate logic and brief glimpses of modal, multi-valued and probabilistic logics. Approximately 12 class sessions are spent on propositional logic over a period of four weeks.
A variety of teaching techniques were developed within the context of this course, but one in particular involved a major shift away from the traditional approach. Whereas most courses on propositional logic focus on truth tables, this course uses Possible Models Diagrams to both define logical operators and to construct logical proofs. Possible Models Diagrams (PMDs) are simple graphs which may be used to represent propositional expressions. Technically, these graphs are hypercubes in which the vertices are partitioned into two sets: one representing the possible models in which the propositional expression turns out to be true, and the other representing the possible models in which the propositional expression turns out to be false. PMDs can be used to define boolean operators, to analyse whether a propositional expression is tautological, contingent or inconsistent, and to determine the validity of propositional sequents.
Another significant difference between this course and many other introductions to propositional logic is that the logical operators are explained in terms of set operations. This immediately removes the confusion over whether the logical disjunction should be inclusive or exclusive, and gives a strong intuitive justification for the problematic truth-functional definition of material implication.
This paper commences with a student’s-eye-view of Possible Models Diagrams, excerpted from [CLAR93]. For a more technical description, see [CLAR94]. This description is followed by an evaluation of the method, based on classroom data collected over three years.
2. A Description of the PMD Approach
2.1 Elementary Possible Models Diagrams
Suppose P and Q represent two propositions. Then there are four possible states of the world: the state in which both P and Q are true; the state in which P is true but Q is false; the state in which P is false but Q true; and the state in which both P and Q are false. We could represent this situation by the simple graph shown in Figure 1.
Figure 1 — The Four Possible Models of P and Q
Each of these possible situations is called a model (or an interpretation) of P and Q and hence the graph is called a Possible Models Diagram (PMD). We show that some expression of propositional logic is true for a particular model by filling in the corresponding node of the graph. Thus the simple propositions P and Q are represented by the PMDs shown in Figure 2a and Figure 2b respectively. Note that here we have abbreviated the vertex labels. Once we are used to the PMD structure, the labels can be completely omitted — as long as the standard orientation is used, the labels can be inferred when necessary.
Figure 2a — PMD for P Figure 2b — PMD for Q
2.2 Combining Rules
We have seen that Possible Models Diagrams are an easy way of visualising simple propositions and now show a number of ways of combining these diagrams to represent compound propositional statements.
• Overlaying two diagrams has the same effect as disjunction (Figure 3). Note the similarity between overlaying and the set union operation.
or
becomes
Figure 3 — Overlay — the Visual Operation for Disjunction
• Finding the corners which match on two diagrams has the same effect as conjunction (Figure 4). Note the similarity with the set intersection operation.
and
becomes
Figure 4 — Match — the Visual Operation for Conjunction
• Reversing each corner of a diagram has the same effect as negation (Figure 5). Note the similarity with set complementation.
not becomes
Figure 5 — Reverse — the Visual Operation for Negation
• Reversing one PMD and overlaying it on a second has the same effect as material implication[1] (Figure 6). Note the similarity with the subset operator. It is easy to remember that material implication has the diagram because the three dots resemble an arrow pointing to the right.
if then
becomes
Figure 6 — Reverse-and-overlay — the Visual Operation for Material Implication
Overlay, match, reverse and reverse-and-overlay can be presented to students as visual operations which correspond to the notions of disjunction, conjunction, negation and material implication respectively, if such notions have already been defined. Alternatively, these visual operations may be presented as definitions of the corresponding logical operations.
2.3 More Complex Expressions
Set equivalence PºQ is reflected in propositional logic by the bi-conditional: PÛQ is defined as (PÞQ)&(QÞP). This can be diagrammed by appropriate combinations of the previous operations, as shown in Figure 7.
(P Þ Q) & (Q Þ P)
— Reverse and overlay
— Match
Figure 7 — Visual Operations for the Bi-conditional
The final outcome is intuitively sensible, since it shows those models in which the truth of P is exactly the same as the truth of Q.
In fact a PMD can be constructed using the three basic combining rules (reverse, overlay and match) for any well-formed formulae which uses only two propositional variables. Figures 8a, 8b and 8c show three examples.
P Þ ( P v Q) P Þ ~ Q (P v Q) & ~ (P v Q)
Fig 8a — PMD for PÞ(PvQ) Fig 8b — PMD for PÞ~Q Fig 8c — PMD for (PvQ)&~(PvQ)
Every well-formed formulae falls into one of three categories —
i) Tautology — a formula whose PMD has every corner filled in (e.g. Figure 8a), i.e. a formula which is true however you interpret it.
ii) Contingent — a formula whose PMD has some corners filled in but not all (e.g. Figure 8b), i.e. a formula which is sometimes true and sometimes false.
iii) Inconsistent — a formula whose PMD has no corner filled in (e.g. Figure 8c), i.e. a formula which is always false.
2.4 Converting Between Truth Tables and Possible Models Diagrams
Whereas a PMD represents all possible models as nodes on a graph, a truth table represents them as lines in a table. Given a PMD, it is simple to construct an equivalent truth table: for each node in the diagram, if the node is filled-in, place a T in the corresponding row of the table, otherwise place an F in the corresponding row of the truth table. Converting in the opposite direction is equally trivial. An example is shown in Figure 9.
| P Q | P & Q | ||
| | T TT FF TF F | TFFF |
Figure 9 — Translating Between a PMD and a Truth Table
2.5 Generalising to more than Two Propositional Variables
If there are three propositional variables (say P, Q, R) in a formula, there will be eight possible models. These are best visualised as the corners of a cube whose opposing faces represent P and ~P, Q and ~Q, R and ~R respectively[2]. However, this can be shown diagrammatically as a two-dimensional graph (Figure 10).
Figure 10 — A PMD for Three Variables
Similar two-dimensional diagrams can be formed for formulae containing any number of propositional variables. In general, if a formula contains n distinct propositional variables, then its PMD will have 2n nodes (just as the corresponding truth table will have 2n rows).
In teaching situations it is rare to set a truth table problem with more than three or possibly four variables, and the same would apply to PMDs. Both methods generalise in theory, but in practice we would rarely use either method for cases where the number of variables is larger than four.
The combining rules (reverse, overlay and match) can all be used as before.
2.6 Provable Sequents
After showing how complex statements may be represented as symbolic propositional formulae, a course in logic is then likely to proceed to the concept of a structured argument. We first describe a sequent in some form like A1,A2,A3,…,An \ B (meaning “the premises A1,A2,A3,…,An entail the conclusion B”). We then describe a range of derivation rules which allow one to proceed logically from one statement to the next in a proof of the sequent.
In any propositional calculus, a sequent A1,A2,A3,…,An \ B may be shown to be valid by showing that (A1Þ(A2Þ(A3Þ…(AnÞB)…))) is a tautology, however, this is rather cumbersome in general. PMDs provide an alternate way to check whether a sequent is valid. Suppose we want to test whether the sequent P, ~(P&Q) \ ~Q is valid. First, construct a PMD for the formulae on the left-hand side (the comma is treated as an implicit conjunction) and a separate diagram for the right-hand side (Figure 11).
P, ~ (P & Q) \ ~ Q
Figure 11 — Validation of the Sequent P, ~(P&Q) \ ~Q by PMD
Now apply this simple rule: a sequent is valid if and only if the diagram for the premises is a subset of the diagram for the conclusion.[3] In the example above, the possible models represented by are a subset of those represented by
and hence the sequent is valid.
3. Evaluation
Once these techniques described above were fully developed and used in the first year computer science course for several years, the developer sought to evaluate how effective the approach had been. Data from past tests, assignments and exams was analysed both quantitatively and qualitatively to compare problem-solving accuracy using truth tables and PMDs. Questionnaires were used to investigate student satisfaction with the new approach.
3.1 Quantitative Analysis
Since the analysis was largely retrospective rather than following an previously devised experimental design, the quantitative data is incomplete and poorly structured. Furthermore, the attempt to establish whether students learn logical concepts from PMDs more readily than from truth tables is confounded by the fact that the teacher is an enthusiastic proponent of PMDs. For these reason, statistical analysis of the available data yields ambiguous results.
In a variety of tests, exams and assignments over three years, students were set questions which required either truth tables, PMDs or both to be constructed. For instance, 50 students answered the following question in a Class Test during 1992 —
Draw either a possible models diagram or a truth table for each of the following formulae. Classify each formula as either contingent, tautologous or inconsistent.
i) (PÞQ)Þ(Qv~P)
ii) ~(PvQ)&(PvQ)
iii) (P&~R)ÞQ
In the two-variable examples (i and ii), 89% of students chose to draw PMDs rather than truth tables, and those who did choose the PMD approach were more likely to produce correct answers (with an odds ratio of 7.90 compared to 2.67 for truth tables). With the three-variable example (iii), 52% chose to draw PMDs and those who did choose the PMD approach were more likely to produce correct answers (with an odds ratio of 1.36 compared to 0.38 for truth tables).
These statistical results are typical in several aspects —
• With both two- and three-variable formulae, the majority of students chose PMDs rather than truth tables, but this preference for PMDs is less pronounced in the three-variable examples;
• Those who chose to use PMDs have a higher success rate than those who use truth tables;
• However, these differences are often not statistically significant.
In summary, the tendency of the quantitative analysis suggests that students perform at least as well when they use PMDs as when they use truth tables. Furthermore, students showed some preference for using PMDs rather than truth tables, especially for simple examples.
3.2 Qualitative Analysis
The same data used for the quantitative analysis above yielded several useful qualitative features. For instance, several students voluntarily doodled PMDs while working with truth tables, and it may be deduced that they were using this as an aid to remembering the truth-functional definitions.
More significantly, the sort of mistakes made while using PMDs differ from the those made when using truth tables. This gives a clear indication that the two representations give rise to different learning biases, even though they are technically equivalent. Furthermore, an examination of typical mistakes can suggest modifications to the teaching process to either avoid or address those mistakes.
• With truth tables, the vast majority of mistakes occur when processing the Þ sign, reflecting the conceptual difficulties related to the truth-functional definition of material implication. Some mistakes indicate confusion about the order of columns of a truth table. Some mistakes relate to processing conjunctions. Some students fail to construct the correct number of rows in the table or label the rows incorrectly.
• By comparison, mistakes involving material implication with PMDs are rare. The most common mistakes relate to the orientation of the PMD (i.e. confusion about the positioning of labels) but these are often not fatal. Occasionally students use a two-variable PMD when they should use a three-variable one. Some students confuse the diagram for Q with the diagram for ~P. Some mistakes result from not following the visual procedures correctly. In some complex cases, a student may incorrectly omit one or more diagrams.
In addition to the student assessment data, an indication of student satisfaction can be inferred from the course evaluation questionnaire. Once again, this data was not collected with the primary intention of quantitatively evaluating PMDs. Rather, the questionnaires were designed to give feedback about the quality of the overall course content and of the lecturer. However, the data indicates that student satisfaction with PMDs and with the overall approach compared quite favourably with other courses taught by the same lecturer. There was a clear improvement in student satisfaction from 1992 to 1993 as the approach was refined.
4. Conclusions
The PMD approach is technically as sound as the traditional truth table approach. Further, it appears from this research that the PMD approach has some pedagogical advantages. Although further testing is required, we may make the following tentative conclusions —
1. Students have less difficulty accepting truth-functional definitions of logical operations when they are introduced by analogy with set operations.
2. The data collected suggests both that students prefer to use PMDs rather than truth tables and that when they do use PMDs they have a higher likelihood of giving correct answers. However, it must be stressed that the nature of the data makes these conclusions uncertain.
3. The combination of a set-theoretical justification for material implication and the use of PMDs reduces the number of mistakes relating to material implication.
4. The advantage of PMDs for the purpose of teaching is possibly because they are iconic, that is, they are symbolic pictures which combine the expressive power of symbolism with the memorability of visual images.
5. The issue of whether this approach improves the students’ ability to transfer formal logical concepts to informal domains still requires further study. My hunch is that transfer is neither more nor less encouraged by any single representation, but is substantially more encouraged when a number of different representations are taught together.
Bibliography
[CLAR93] Clarke, M.; Possible Models Diagrams: a visual alternative to truth tables in the SIGCSE Bulletin, vol. 25, # 1, March 1993
[CLAR94] Clarke, M.; Visualising Boolean Operations on a Hypercube in Mathematical and Computer Modelling, vol. 20, #9, pp97–103, 1994
[CLAR96] Clarke, M.; A Comparison of Techniques for Introducing Material Implication, forthcoming.
[COPI67] Copi, I.; Introduction to Logic, Macmillan, 1967
[EVAN82] Evans,J.St.B.T.; The Psychology of Deductive Reasoning, Routledge and Kegan Paul, 1982
[GILH88] Gilhooly,K.J.; Thinking: directed, undirected and creative, Academic, 1988
[OBRI72] O’Brien,T.C.; Logical thinking in adolescents in Educational Studies in Mathematics, vol. 4, 1972, pp401-428
[OBRI73] O’Brien,T.C.; Logical thinking in college students in Educational Studies in Mathematics, vol. 5, 1973, pp71-79
[SHAP73] Shapiro,B.J. and O’Brien,T.C.; Quasi-child logics in Educational Studies in Mathematics, vol. 5, 1973, pp181-184
[WASO83] Wason,P.C.; Realism and rationality in the selection task in Thinking and Reasoning: psychological approaches, ed. Evans,J., Routledge and Kegan Paul, 1983
[1] To the student, the procedure “reverse and overlay” is an easy habit to learn and it is only later that they discover that PÞQ is logically equivalent to ~PvQ. Some teachers may prefer to use this equivalence as a definition of material implication, in the same way that [COPI67] uses ~(P&~Q) as a definition. I find that students rebel against this use of fiat, but are more ready to accept the parallel between material implication and subset.
[2] In teaching this section a real cube is a useful visual aid.
[3] At least, that is a simplified statement of the rule which is easily remembered by students. The fully stated rule is “A sequent is valid if and only if the set of models which satisfy the conjunction of the premises (as indicated by the PMD) is a subset of the models which satisfy the conclusion (as indicated by the PMD).”
——