Write up on Discrete Mathematics in an educational Curriculum for grade school and high school students (Revision 2)

Literature Review
1.1 Discrete Mathematics used for Computer Science as a Fundamental basics to learn Algorithms
The Need for Computer Science
This is largely based on how exposed students are to computational thinking and computer science concepts. Additionally, educating students in computer science is beneficial for all students. With the digital age rising, there is a need to develop logical thinking and problem-solving which are all a part of learning computer science.
Computer Science Standards and Model Curriculum give students experiences that help them discover and take part in a world continually influenced by technology and to understand the role of computing
What is Discrete Mathematics?
Discrete Mathematics is an area of mathematics that most closely connects with the field of computer science. It is the study of mathematical structures that are countable or otherwise distinct and separable (as opposed to continuous quantities like in algebra or calculus).

What Is Discrete Mathematics?
Discrete Mathematics is a rapidly growing and increasingly used area of mathematics, with many practical and relevant applications.
• Because it is grounded in real-world problems, discrete mathematics lends itself easily to implementing the recommendations fo the National Council of Teachers of Mathematics (NCTM) standards. (The recently published Standards and Principles for School Mathematics notes that “As an active branch of contemporary mathematics that is widely used in business and industry, discrete mathematics should be an integral part of the school mathematics curriculum.”)
• Because many discrete math problems are simply stated and have few mathematical prerequisites, they can be introduced at all grade levels, even with children who are not yet fluent readers.
Discrete mathematics will make math concepts come alive for your students. It’s an excellent tool for improving reasoning and problem-solving skills, and is appropriate for students at all levels and of all abilities. Teachers have found that discrete mathematics offers a way of motivating unmotivated students while challenging talented students at the same time.
Because many discrete math problems are simply stated and have few mathematical prerequisites, they can be easily be introduced at the middle school grade level.

1.2 How Discrete Mathematics Can Help Students
The National Council of Teachers of Mathematics (NCTM) recommends that discrete mathematics be implemented into the curriculum as early as the seventh 4 grade, because it benefits students and helps maintain their interest in mathematics [5, p. 362]. But beyond what the NCTM recommends, is discrete mathematics really advantageous to students, and if so, why? Discussed below are some of the reasons. First, it keeps students interested in mathematics. It helps entice them to regularly attend and participate in class. When students are interested in the material, it is easier for them to learn and stay focused when presented with tough, complex problems. While solving problems in discrete mathematics can be complicated, the problems themselves can be easily understood. The students, therefore, are able to understand and work the problems, which gives them a much needed confidence [12, pp. 35-36].

 Many students are lost from mathematics forever during high school. Discrete mathematics is a great way to help these students stay interested and involved in mathematics. Second, discrete mathematics benefits students by allowing them to see the connections between the mathematics they are studying and the real world. “For example, we might be able to convince our students that calculus can be used to help civil engineers build better bridges, but the students still might not see how it really works. But in graph theory [and other areas of discrete mathematics], we can explain the applications, the students can see how they work, and they can actually see real problems” [7, p. 94]. Teachers need to help students dismiss the idea that there is nothing new left to discover in mathematics and help them to look beyond basic arithmetic computation.

 Discrete mathematics is the mathematical foundation of computer science and is “used extensively in business, industry, and government. For example, difference equations are an essential mathematical tool for high-technology engineering firms, and matrices are indispensable for computer graphics” [4, p. 75].

 Another benefit of discrete mathematics is that it enriches the traditional curriculum. It places more emphasis on teaching students to think mathematically and less emphasis on certain computational skills [1, p. 83]. Discrete mathematics lends itself to group work more easily than does traditional mathematics. It is also helpful to teachers because it gives them a new way of teaching elements in the curriculum, which may make the traditional concepts easier to teach and learn.

By using discrete mathematics to teach already existing elements in the curriculum, it can help to change the way students view mathematics altogether. Below are some of the ways that discrete mathematics complements topics already in the traditional secondary-school curriculum: · Algebraic skills are needed and reinforced throughout discrete mathematics. · In geometry, graph theory can be used to enrich the study of polygons and polyhedral. · Difference equations give use to the fascinating new geometry of fractals [4, p. 75]. The NCTM does not provide teachers with detailed guidelines. They only provide a set of goals and topics to cover in high school for discrete mathematics. Therefore, it is up to each individual teacher, or the mathematics department within each school, to decide how these topics should be implemented.

Unfortunately, many teachers are unfamiliar, and even uncomfortable, with discrete mathematics. Thus, it can be difficult for them to know how to incorporate these topics into the curriculum. Because discrete mathematics can be used to teach traditional elements in the curriculum, these topics can be covered in different ways throughout the school year, without having to set aside extra time to cover them. 6 While the implementation of discrete mathematics into the curriculum is not discussed here in detail, many references cited in this thesis give numerous ideas on how to do so. Some also give sample lessons and projects for different skill levels. Some excellent resources are: · DIMACS Series in Discrete Mathematics and Theoretical Computer Science 36 (eds. J.G. Rosenstein, D.S. Franzblau, and F.S. Roberts), American Mathematical Society; 1997. · Discrete Mathematics Across the Curriculum, K–12 (eds. M.J. Kenney, and C.R. Hirsch), NCTM, Inc, Reston, Virginia; 1991. · Mathematics Teacher, a monthly journal magazine.

https://repository.lsu.edu

---

These political battles over the mathematics curriculum resulted in discrete mathematics largely being ignored in these countries. Of the discrete mathematics topics specifed above, very few are part of the standard curriculum in most of the countries we are familiar with. Through personal communication, it appears that:

• Combinatorics is included in the secondary curriculum of several countries, including Spain, US, England, Germany, Hungary, Brazil, Israel.
• Connecting recursive patterns and sequences with algebraic formulas is taught, to some degree, in Spain, Germany, and the United States.
  • Graph theory is included in Italy and some isolated state curriculum in the US. In England, students focusing on mathematics can take a special track in which they have extensive exposure to discrete mathematics. In many countries, it appears that the opportunities for dealing with discrete mathematics in schools, especially when it goes beyond combinatorics, are often only seen on the level of optional recreational mathematics (Colipan & Liendo, 2022; Gravier & OuvrierBufet, 2022; Greefrath et al., 2022). We wonder if one contributing issue for the lack of discrete topics taught in the schools may be that the term discrete mathematics’ is not well understood. Perhaps, each of the discrete topics mentioned above should be considered individually. For example, fair division algorithms and economic game theory are almost self-explanatory. While combinatorics sounds complicated, counting is clearly important. Instead of using the termgraph theory’ which may be misleading to some, we could talk about vertex-edge graphs or networks, which most people are familiar with. Iteration can be described in terms of simple recursive situations, such as repeatedly folding a piece of paper or compounding of interest, along with its accessibility through the use of spreadsheets. Therefore, it might be more productive to talk about the individual discrete topics than the discipline as a whole. This is also intended to describe the mentioned topic areas of discrete mathematics for school more clearly once again. We therefore shortly go into a little more detail on the most common discrete topics and how they may support mathematical competencies.

Reference:
https://repository.lsu.edu/
https://link.springer.com/article/10.1007/s11858-022-01399-7

1.3  Potential benefits of discrete mathematics topics for mathematics education
We see the potential benefits of teaching discrete mathematical topics in three broad areas, and some of these benefits have been highlighted in existing literature. The first potential benefit is offered by the content, which is accessible and offers interesting and relevant topics for teaching and learning (Anderson et al., 2004; DeBellis & Rosenstein, 2004).

Potential benefits of discrete mathematics topics for mathematics education
The second potential benefit is the learning of mathematics and the acquisition of general mathematical competencies (Coenen et al., 2018; Vorhölter et al., 2019) including afect (Goldin, 2018) that influences the learning of mathematics and the third potential is the relevance of discrete mathematics for living in the modern world (Hart & Martin, 2018; Rosenstein, 2007). In this section, we will discuss general benefts and in Sect. 6, the benefts resulting from specifc discrete mathematics topics.

Accessible topics for teaching and learning As early as the end of the 1980s, there were calls to integrate discrete mathematics into teaching, not only in higher education but also in schools (Dolgos, 1990). Advocates of discrete mathematics have noted that problems in discrete mathematics are relatively accessible, in the sense that a student may be able to understand what a problem is asking or can explore a situation without needing a lot of prior mathematical experience (Anderson et al., 2004; Devaney, 2018; Ferrarello & Mammana, 2018; Rosenstein, 2007). This is often because the problems themselves do not require knowledge of technical definitions or specific mathematical knowledge, and students can exemplify and explore objects.

The discrete nature of the objects would seem to lend itself to this accessibility. This accessibility of discrete mathematics is something that seems to be agreed upon by many mathematicians, mathematics educators and mathematics education researchers, and it is often used as an argument for the importance of the inclusion of discrete mathematics in curriculum (Anderson et al., 2004; Burghes, 1995; Dolgos, 1990; Hart & Martin, 2018). While we note that this is an aspect of discrete mathematics that would benefit from more systematic study and research, this accessibility has come through in some research studies, but not as an explicit focus of the study. Some of the research on the teaching and learning of discrete mathematics with younger students highlights not only the accessibility of topics but that this accessibility can help students make sense of the current curriculum.

 For example, iterative problems and difference equations can help students learn algebra (Amit & Neria, 2008; Blanton & Kaput, 2005; Carraher et al., 2008; Radford, 2008; Rivera & Becker, 2008; Sandefur et al., 2018; Steele, 2008; Yeap & Kaur, 2008). Even very young students can reason about combinatorial problems in meaningful ways (de Beer et al., 2015; Maher et al., 2011). English (1991, 1993) reports on young children’s strategies as they engage with combinatorial problems. As another example, students can naturally `invent’ graph theory to solve a problem (Ferrarello & Mammana, 2018; Greefrath et al., 2022; van den Heuvel & Krabbendam, 1991). We can only wonder how much better would the students’ work be if they already knew some graph theory or had previous experience with counting or recursive problems?

For many topics in discrete mathematics, students ranging from young children to undergraduate students can be posed similar questions and have a reasonable chance at investigating the problem at their different levels. This results in self differentiating tasks that allow individual approaches to the problem (Ostkirchen & Greefrath, 2022). For example, how many 2-color towers can I make of height 5, can be extended to more complicated problems for older students by increasing the number of colors and the height of the tower. Maher et al. (2011) describe the use of combinatorial problems in such contexts among students in a longitudinal study. Students as young as the third grade can investigate recursive structures they build with toothpicks and stickers while high school students can develop recursive models of bacteria growth and the spread of epidemics, which is a simplified version of models studied by epidemiologists (Radford, 2008; Sandefur & Manaster, 2022; Yeap & Kaur, 2008).

https://link.springer.com/article/10.1007/s11858-022-01399-7
Chapter 2:

Write up on Discrete Mathematics Logic, Tree, and Lambda Equations could be utilized in Highschool Computer Science Curriculum

Discrete Mathematics

2.1

The key aspect to rooted trees — which is both their greatest advantage and greatest limitation — is that every node has one and only one path to the root. This behavior is inherited from free trees: as we noted, every node has only one path to every other.

Trees have a myriad of applications. Think of the files and folders on your hard drive: at the top is the root of the filesystem (perhaps “/” on Linux/Mac or “C:\\” on Windows) and underneath that are named folders. Each folder can contain files as well as other named folders, and so on down the hierarchy. The result is that each file has one, and only one, distinct path to it from the top of the filesystem. The file can be stored, and later retrieved, in exactly one way.

An “org chart” is like this: the CEO is at the top, then underneath her are the VP’s, the Directors, the Managers, and finally the rank-and-file employees. So is a military organization: the Commander in Chief directs generals, who command colonels, who command majors, who command captains, who command lieutenants, who command sergeants, who command privates.

The human body is even a rooted tree of sorts: it contains skeletal, cardiovascular, digestive, and other systems, each of which is comprised of organs, then tissues, then cells, molecules, and atoms. In fact, anything that has this sort of part-whole containment hierarchy is just asking to be represented as a tree.

In computer programming, the applications are too numerous to name. Compilers scan code and build a “parse tree” of its underlying meaning. HTML is a way of structuring plain text into a tree-like hierarchy of displayable elements. AI chess programs build trees representing their possible future moves and their opponent’s probable responses, in order to “see many moves ahead” and evaluate their best options. Object-oriented designs involve “inheritance hierarchies” of classes, each one specialized from a specific other. Etc. Other than a simple sequence (like an array), trees are probably the most common data structure in all of computer science.

Rooted tree terminology

root.

Figure 2-1

in our example. Note that unlike trees in the real world, computer science trees have their root at the top and grow down. Every tree has a root except the empty tree, which is the “tree” that has no nodes at all in it. (It’s kind of weird thinking of “nothing” as a tree, but it’s kind of like the empty set ∅∅, which is still a set.)

parent.

Every node except the root has one parent: the node immediately above it. D’s parent is C, C’s parent is B, F’s parent is A, and A has no parent.

child.

Some nodes have children, which are nodes connected directly below it. A’s children are F and B, C’s are D and E, B’s only child is C, and E has no children.

sibling.

A node with the same parent. E’s sibling is D, B’s is F, and none of the other nodes have siblings.

ancestor.

Your parent, grandparent, great-grandparent, etc., all the way back to the root. B’s only ancestor is A, while E’s ancestors are C, B, and A. Note that F is not C’s ancestor, even though it’s above it on the diagram: there’s no connection from C to F, except back through the root (which doesn’t count).

descendent.

Your children, grandchildren, great-grandchildren, etc., all the way the leaves. B’s descendents are C, D and E, while A’s are F, B, C, D, and E.

leaf.

A node with no children. F, D, and E are leaves. Note that in a (very) small tree, the root could itself be a leaf.

internal node.

Any node that’s not a leaf. A, B, and C are the internal nodes in our example.

depth (of a node).

A node’s depth is the distance (in number of nodes) from it to the root. The root itself has depth zero. In our example, B is of depth 1, E is of depth 3, and A is of depth 0.

height (of a tree).

A rooted tree’s height is the maximum depth of any of its nodes; i.e., the maximum distance from the root to any node. Our example has a height of 3, since the “deepest” nodes are D and E, each with a depth of 3. A tree with just one node is considered to have a height of 0. Bizarrely, but to be consistent, we’ll say that the empty tree has height -1! Strange, but what else could it be? To say it has height 0 seems inconsistent with a one-node tree also having height 0. At any rate, this won’t come up much.

level.

All the nodes with the same depth are considered on the same “level.” B and F are on level 1, and D and E are on level 3. Nodes on the same level are not necessarily siblings. If F had a child named G in the example diagram, then G and C would be on the same level (2), but would not be siblings because they have different parents. (We might call them “cousins” to continue the family analogy.)

subtree.

Finally, much of what gives trees their expressive power is their recursive nature. This means that a tree is made up of other (smaller) trees. Consider our example. It is a tree with a root of A. But the two children of A are each trees in their own right! F itself is a tree with only one node. B and its descendents make another tree with four nodes. We consider these two trees to be subtrees of the original tree. The notion of “root” shifts somewhat as we consider subtrees — A is the root of the original tree, but B is the root of the second subtree. When we consider B’s children, we see that there is yet another subtree, which is rooted at C. And so on. It’s easy to see that any subtree fulfills all the properties of trees, and so everything we’ve said above applies also to it.

Binary trees (BT’s)

The nodes in a rooted tree can have any number of children. There’s a special type of rooted tree, though, called a binary tree which we restrict by simply saying that each node can have at most two children. Furthermore, we’ll label each of these two children as the “left child” and “right child.” (Note that a particular node might well have only a left child, or only a right child, but it’s still important to know which direction that child is.)

The left half of is a binary tree, but the right half is not (C has three children). A larger binary tree (of height 4) is shown in  .

Traversing binary trees

There were two ways of traversing a graph: breadth-first, and depth-first. Curiously, there are three ways of traversing a tree: pre-order, post-order, and in-order. All three begin at the root, and all three consider each of the root’s children as subtrees. The difference is in the order of visitation.

Figure 2-2

The node at the top of the tree, which is A

Rules in Prolog

Using rules, we can build a relationships among facts.

% Define what a mother, father, and a grandparent is

mother(M, C) :- parent(M, C), female(M).

father(F, C) :- parent(F, C), male(F).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

The rule named mother defines the meaning of the mother relationship: If M is a parent of C, and if M is female, then M is a mother.

Similarly, the father rule defines the meaning of the father relationship: If F is a parent of C, and if F is male, then F is a father.

Lastly, the grandparent rule defines the meaning of the grandparent relationship: if X is a parent of Y, and Y is a parent of Z, then X is a grandparent of Z.

Rules in Prolog

Using rules, we can build a relationships among facts.

% Define what a mother, father, and a grandparent is

mother(M, C) :- parent(M, C), female(M).

father(F, C) :- parent(F, C), male(F).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

The rule named mother defines the meaning of the mother relationship: If M is a parent of C, and if M is female, then M is a mother.

Similarly, the father rule defines the meaning of the father relationship: If F is a parent of C, and if F is male, then F is a father.

Lastly, the grandparent rule defines the meaning of the grandparent relationship: if X is a parent of Y, and Y is a parent of Z, then X is a grandparent of Z.

                                                Logical Programming

Logic is the discipline concerned with unassailably valid reasoning. By valid we mean that if we start with true statements and from them deduce new statements, following the given logical laws of deduction, we will always end up with new statements that are also true. Logics are thus systems of symbols and rules for manipulating them that have the property that syntactic deduction, involving mechanical manipulation of strings, is always a semantically valid operation, involving the truths of derived statements.

There is not just one logic. There are many. First-order predicate logic with equality is central to everyday mathematics. Propositional logic is equivalent to the language of Boolean expressions as found in conditional expressions in most programming languages. Temporal logics provide ways to reason about what statements remain true in evolving worlds. Dependent type theory is a logic, a richer form of predicate logic, in which propositions are formalized as types and proofs are essentially programs and data structures written in pure, typed, functional programming languages, and so can be type checked for correctness.

Logic is a pillar of computer science. It has been said that logic is to computer science as calculus is to natural science and engineering. As scientists and engineers use everyday mathematics to represent and reason about properties of physical things, so computer scientists use various logical languages to specify and reason about properties of programs, algorithms, the states of programs as they execute, problems to be solved by algorithms, and even about the real world in which software is meant to operate.

Propositional logic , essentially the language of Boolean expressions, is ubiquitous in programming. First-order predicate logic is widely used to reason about many issues that arise in computer science, from the complexity of algorithms to the correctness of programs. Hoare logic is a specialized extension of first-order predicate logic that is especially well suited to specifying how programs must behave and for showing that they do behave according to given logical specifications. Dependent type theory is the logic of modern proof assistant tools, including Lean (as well as Coq and Agda), which we will use in this class.

Dependent type theory and the tools that support it now play important roles in both the development of programming languages and in the production of trustworthy software. In lieu of testing of a given computer program to see if it works correctly on some inputs, one proves that it works correctly on all possible inputs. A tool then checks such proofs for correctness. Mathematicians are increasingly interested in the possibilities for automated checking of complex proofs as well.

At the heart of logic are the concepts of propositions and proofs. A proposition is an expression that we interpret as making a claim that some particular state of affairs holds in some particular domain of discourse (some world of interest). A proof is a compelling argument, in a precise form, that shows beyond any doubt that such a proposition is true. The existence of a valid proof of a proposition shows that it is true. In mathematical logic, the arbiter of truth is the existence of a proof. Proof implies truth; truth demands proof.

This first section of this course, on logic, provides a rigorous survey of forms of propositions and the construction and use of corresponding proofs in the language of predicate logic. You will learn how to write propositions in predicate logic, and how to both construct and use proofs of them in a logical reasoning system called natural deduction. As you will also quickly see, natural deduction is essentially a form of computation in a typed, pure functional programming language in which all programs terminate (there can be no infinite loops). To learn logic in this style is thus also learn a very important style of programming: functional programming. You will learn to compute with propositions and proofs.

 propositions need not be a true statement. Propositions only need to be declarative. Their truth value may be true or false. However, all propositions must have a particular truth value. The statement cannot be both true and false. The statement must be able to be interpreted as true or false.

From the previous definition and examples, propositions are therefore not questions, general statements, demands, or hypotheses. Propositions do not have any variables, quantifiers, or parameters (e.g. the words “some” or “any” typically do not appear). Consider now a few non-examples.

Examples of statements that are not propositions

• Do you have a dog?
• Let’s go!
• Some coffee mug with a mermaid on it.
• x+2=3
• y=x2−1

Checkpoint

Are each of these propositions?

1. I am a dolphin.
2. Supercalifragilisticexpialidocious.
3. Jupiter is the 5th planet from the sun.
4. On Thursdays, van Gogh painted landscapes.
5. 11+56∗3−819=9

Solution

Constructing Propositions

An entire proposition is often denoted by a single propositional variable. Propositional variables are typically among p,q,r,s,t,….

Using propositional variables

p:= “The sky is blue”

q:= “The sun rises from the west”

We also denote truth values in particular ways. “True” may be denoted by T. “False” may be denoted by F. When a proposition (or proposition variable) is known to always be true, we can replace it by T. When a proposition (or proposition variable) is known to always be false, we can replace it by F.

Connectives

We can combine propositions (and propositional variables) into compound propositions or propositional formulas. This is akin to compound sentences and other logical connectives in natural language.

In propositional logic, we have 5 main connectives. Each connective has a corresponding meaning in natural language as we will soon see.

• Negation: ¬
• Conjunction: ∧
• Disjunction: ∨
• Implication: →
• Biconditional: ↔

Logical connectives are like arithmetic operators (+,−,×,÷).

Negation

The negation of a proposition results in a proposition with the opposite truth value. It is akin to adding “not” into a sentence, or starting a sentence with “it is not that case that…”.

Given a proposition p its negation is ¬p and has the following truth values.

Table 1.1 Negation truth table
p	¬p
F	T
T	F

Negation

• Let p:= “the sky is blue”.

¬p is “the sky is not blue” or “it is not the case that the sky is blue”.

• Let q:= “2+2=5”.

¬q is “2+2≠5.

Notice in these examples that negation does not necessarily make a proposition false. Rather, it makes the proposition have the opposite truth value.

Conjunction

The conjunction of two propositions is the logical “and” of the two propositions. The conjunction of two proposition is only true if both the propositions are individually true, otherwise the conjunction is false.

Given proposition p and q their conjunction is denoted p∧q and has the following truth values.

Table 1.2 Conjunction truth table
p	q	p∧q
F	F	F
F	T	F
T	F	F
T	T	T

Conjunction

Let p be “birds lay eggs” and q be “my eyes are blue”. p∧q is then “birds lay eggs and my eyes are blue”.

Disjunction

The disjunction of two propositions is the “or” of the two propositions. The disjunction is true if at least one of the propositions is individually true, otherwise the disjunction is false.

Given proposition p and q their disjunction is denoted p∨q and has the following truth values.

Table 1.3 Disjunction truth table
p	q	p∨q
F	F	F
F	T	T
T	F	T
T	T	T

Disjunction

Let p be “it is raining” and q be “I am wearing sunglasses”. p∨q is then “it is raining or I am wearing sunglasses”.

Notice that in this previous example, it is may be true that it is both raining and that I am wearing sunglasses. While that may be silly, p∨q is still true! In logic, we only require that at least one of the propositions in a disjunction is true. That means both are allowed to simultaneously be true.

Caution

In natural language, “or” is often interpreted as an exclusive or.

Language “or”

“You can have a cookie or a piece of cake.” Most people assume that this means you can have a cookie or a piece of cake, but not both.

In logic, “or” is not exclusive. You can have a cookie, a piece of cake, or both!

If you want logical exclusive or, we use the symbol ⊕. However, we will not use that in this course.

---

Checkpoint

What is the truth value of these compound propositions?

1. “The earth is round and the sky is blue.”
2. “Dogs or cats make great pets.”
3. “It is 20∘ Celsius outside and it is snowing.”
4. “Lemons are purple or grass is green”

Solution

---

Implication

Implication is one of the most challenging connectives to understand. Yet it is arguably the most important for creating logical arguments).

An implication is a conditional statement. For two propositions p and q, p→q is an implication which is read “if p, then q”. You can also say “p implies q”.

Implication

Let p be “it is raining” and q be “the ground is wet”. p→q can be read “if it is raining, then the ground is wet”.

In an implication p→q, the first proposition p is known as the hypothesis, antecedent, or premise. The second proposition q is known as the conclusion or consequence.

Because an implication is a conditional, the truth value of the implication as a whole changes depending on the truth value of the premise. The following truth table summarizes the truth values of an implication.

Table 1.4 Implication truth table
p	q	p→q
F	F	T
F	T	T
T	F	F
T	T	T

An implication can be viewed as an obligation, a contract, or a commitment. The implication p→q is false (the contract is broken; the obligation is unmet) only when p is true and q is false.

There are several important observations from this truth table about logical implication.

• If q is true, then p→q is always true.
• If p is true and the implication correct (the obligation is upheld), then q can never be false.
• “Falsity can imply anything.” If the hypothesis is false, then the implication is always true, regardless of the whether or not the conclusion is true.

Some of these observations may seem counter-intuitive at first. Let us clarify with some examples.

The truth value of implications

Let p be “that animal is a panda bear” and q be “that animal is black and white”. p→q can be read as “if that animal is a panda bear, then that animal is black and white”.

If p is true, and that animal is indeed a panda bear (and the implication is correct),
then it is also black and white. If q is true, and the animal is black and white, it might be a panda bear, but it might also be a cow.

From p→q, we can say that knowing the animal is a panda bear is sufficient to know that the animal is black and white.

Valid implications can be formed from completely unrelated propositions. Moreover, if you begin with a nonsensical hypothesis, then one can construct valid (but equally nonsensical) implications. Falsity implies anything.

Absurd but valid implications

• “If pigs can fly, then I am the pope.”
• “If 2+2=5, then lemons are purple.”
• “If the sun is made of ice, then my father is Morgan Freeman”.

There are many equivalent ways to think about the implication p→q.

• If p, then q
• p implies q
• q when p
• q, if p

• q whenever p
• q follows from p
• p is sufficient for q
• q is necessary for p

Necessity and Sufficiency

An implication connects propositions by a necessary or sufficient condition. From p→q we get two relations:

• p is sufficient for q
• q is necessary for p

That is, “if sufficient condition, then necessary condition”.

Necessary and Sufficient

“If all birds have feathers, then a chicken is a type of bird.”

Knowing birds have feathers is sufficient information to conclude that a chicken is a type of bird. If a chicken is a type of bird, then chickens necessarily have feathers.

Fig. 1.1 Being in the inner circle is sufficient for being in the outer circle. Being in the outer circle is necessary for being in the inner circle.

Biconditional

For two propositions p and q, they can be connected by a biconditional as p↔q.

A biconditional is an double implication. A biconditional is true if both propositions have the same truth value. p↔q can be read as “p if and only if q”. A biconditional has the following truth table.

Table 1.5 Biconditional truth table
p	q	p↔q
F	F	T
F	T	F
T	F	F
T	T	T

The biconditional p↔q can be expressed in many ways:

• “p if and only if q”
• “if p then q, and if q then p”
• “p is necessary and sufficient for q”
• “p iff q”

Biconditional

Let p be “2 is an even number”. Let q be “4 is an even number”. p↔q is a biconditional and its truth value is true, since both p and q are true.

Tip (thinking in memes)

“The venn diagram is a circle” exactly means that the two subjects form a biconditional.

Checkpoint

What is the truth value of these compound propositions?

1. “The Earth is flat” → “Pigeons are robots”
2. “Bats have wings” → “Bats are birds”
3. “A square is a rectangle” ↔ “A square had four 90∘ interior angles”
4. “Spinach is green” ↔ “Penguins can fly”

Solution

---

Propositional Formulas

In the previous section we saw 5 different logical connectives: ¬, ∧, ∨, →, and ↔. Much like arithmetic formulas using addition, multiplication, division, etc., propositional formulas may use several connectives simultaneously.

Remember BEDMAS or PEDMAS? Now we have “PaNCo DIB” (“Panko Dib”)?

For logical connectives we have a similar order of precedence.

1. Parenthesis: always perform operations on expressions inside parentheses first.
2. Negation: apply negation to a proposition before binary connectives.
3. Conjunction: conjunction before disjunction
4. Disjunction: disjunction after conjunction, but before implication
5. Implication: → after ∧, ∨
6. Biconditional: ↔ after ∧,∨,→.

Logical order of precendence

• p∨q→¬r   is the same as   (p∨q)→(¬r)
• p∨¬q∧r   is the same as   p∨( (¬q) ∧r)

Propositional variables need not be associated with a particular proposition or truth value. A propositional variable could be just that: a variable. Replacing the variables in a propositional formula with a truth value is called a truth assignment.

Definition (truth assignment)

A truth assignment is the assignment of a truth value (true or false) to a propositional variable. Equally, it is the replacement of a propositional variable with a truth value.

Much like logical connectives, propositional formulas will result in different truth values depending on the particular truth assignment on its consituent propositional variables. When at least one truth assignment exists so that a formula is true, that formula is said to be satisfiable.

Definition (satisfiable)

A propositional formula is satisfiable if its truth value can be true under some truth assignment. If every possible truth assignment makes the formula have false as its truth value, that formula is said to be unsatisfiable.

In order to determine the truth value of a propositional formula, and to determine if it is satisfiable, we can create a truth table.

---

Truth Tables

Truth tables are tools for determining the truth values of propositional formulas.

• The table is separated into two sets of columns:
  • The first set of columns represent each proposition (or propositional variable) in a formula.
  • The second set of columns represents the sub-formulas and formulas whose truth values are to be determined.
• There must be one row in the table for every possible combination of truth values of the propositional variables. For example, in a formula with two variables, the possible combinations are: (T,T),(T,F),(F,T),(F,F).

3-variable truth table

Let p,q,r be propositional variables. A truth table for the formula (p∧q)∨r is:

p	q	r	p∧q	(p∧q)∨r
F	F	F	F	F
F	F	T	F	T
F	T	F	F	F
F	T	T	F	T
T	F	F	F	F
T	F	T	F	T
T	T	F	T	T
T	T	T	T	T

Notice that every possible combination of truth values for p, q, and r is contained in this table. Since at least one choice of truth value for p, q, and r results in the formula being true, then this formula is satisfiable.

In a truth table, you begin by filling out the columns corresponding to each propositional variable. These columns represent every possible combination of truth values on those variables. Then, you add columns for each sub-formula, one at a time, building up to the final formula.

Consider the formula p∧q∧r ∨ ¬q∧r→p. By order of precendence, this is equal to ( (p∧q∧r) ∨ ((¬q)∧r) )→p This contains several sub-formulas which we can parse:

• ¬q
• ¬q∧r
• p∧q
• (p∧q)∧r
• (p∧q∧r)∨(¬q∧r)
• ( (p∧q∧r)∨(¬q∧r) )→p

To be as explicit as possible, we could create a truth table with 3 + 6 = 9 columns (3 variables, 6 sub-formulas). But this is excessive. For example, we could directly compute (¬q∧r) and (p∧q∧r). This gives the following truth table.

A large truth table

A truth table for the propositional formula p∧q∧r ∨ ¬q∧r→p.

p	q	r	p∧q∧r	¬q∧r	(p∧q∧r)∨(¬q∧r)	(p∧q∧r)∨(¬q∧r)→p
F	F	F	F	F	F	T
F	F	T	F	T	T	F
F	T	F	F	F	F	T
F	T	T	F	F	F	T
T	F	F	F	F	F	T
T	F	T	F	T	T	T
T	T	F	F	F	F	T
T	T	T	T	F	T	T

---

Checkpoint

Construct a truth table

Give a truth table for the propositional formula p∧r→q∨¬r

Solution

---

Implication, Inverse, Converse, and Contrapositive

Now that we have seen propositional formulas and truth tables, let’s revisit implications. This connective has many related conditionals.

Consider the propositional formula p→q. Then, we have:

• Converse: q→p
• Inverse: ¬p→¬q
• Contrapositive: ¬q→¬p

A conditional and its inverse

The proposition “if it is raining, then I wear a jacket” is a conditional statement. Its inverse is “if it is not raining I do not wear a jacket”.

Notice from this previous example than an implication and its inverse are not exactly the same. If the conditional “if it is raining, then I wear a jacket” is true, that is not the same as its inverse. Indeed, you might still wear a jacket even if its not raining. Maybe you’re just cold.

Important

An implication is not equivalent to its converse or inverse. However, it is equivalent to its contrapositive.

---

 Logical laws are similar to algebraic laws. For example, there is a logical law corresponding to the associative law of addition, a+(b+c)=(a+b)+c.a+(b+c)=(a+b)+c. In fact, associativity of both conjunction and disjunction are among the laws of logic. Notice that with one exception, the laws are paired in such a way that exchanging the symbols ∧,∧, ∨,∨, 1 and 0 for ∨,∨, ∧,∧, 0, and 1, respectively, in any law gives you a second law. For example, p∨0⇔pp∨0⇔p results in p∧1⇔p.p∧1⇔p. This is called a duality principle. For now, think of it as a way of remembering two laws for the price of one. We will leave it to the reader to verify a few of these laws with truth tables. However, the reader should be careful in applying duality to the conditional operator and implication since the dual involves taking the converse. For example, the dual of p∧q⇒pp∧q⇒p is p∨q⇐p,p∨q⇐p, which is usually written p⇒p∨q.p⇒p∨q.

Example : Verification of an Identity Law

The Identity Law can be verified with this truth table. The fact that (p∧1)↔p(p∧1)↔p is a tautology serves as a valid proof.

Table 3.4.13.4.1: Truth table to demonstrate the identity law for conjunction.

pp	11	p∧1p∧1	(p∧1)↔p(p∧1)↔p
00	11	00	11
11	11	11	11

Some of the logical laws in Table 3.4.33.4.3 might be less obvious to you. For any that you are not comfortable with, substitute actual propositions for the logical variables. For example, if pp is “John owns a pet store” and qq is “John likes pets,” the detachment law should make sense.

Table 3.4.23.4.2: Basic Logical Laws – Equivalences

Commutative Laws
p∨q⇔q∨pp∨q⇔q∨p	p∧q⇔q∧pp∧q⇔q∧p
Associative Laws
(p∨q)∨r⇔p∨(q∨r)(p∨q)∨r⇔p∨(q∨r)	(p∧q)∧r⇔p∧(q∧r)(p∧q)∧r⇔p∧(q∧r)
Distributive Laws
p∧(q∨r)⇔(p∧q)∨(p∧r)p∧(q∨r)⇔(p∧q)∨(p∧r)	p∨(q∧r)⇔(p∨q)∧(p∨r)p∨(q∧r)⇔(p∨q)∧(p∨r)
Identity Laws
p∨0⇔pp∨0⇔p	p∧1⇔pp∧1⇔p
Negation Laws
p∧¬p⇔0p∧¬p⇔0	p∨¬p⇔1p∨¬p⇔1
Idempotent Laws
p∨p⇔p∨p⇔	p∧p⇔pp∧p⇔p
Null Laws
p∧0⇔0p∧0⇔0	p∨1⇔1p∨1⇔1
Absorption Laws
p∧(p∨q)⇔pp∧(p∨q)⇔p	p∨(p∧q)⇔pp∨(p∧q)⇔p
DeMorgan’s Laws
¬(p∨q)⇔(¬p)∧(¬q)¬(p∨q)⇔(¬p)∧(¬q)	¬(p∧q)⇔(¬p)∨(¬q)¬(p∧q)⇔(¬p)∨(¬q)
Involution Laws
¬(¬p)⇔p¬(¬p)⇔p

Table 3.4.33.4.3: Basic Logical Laws – Common Implications and Equivalences

Detachment (AKA Modus Ponens)	(p→q)∧p⇒q(p→q)∧p⇒q
Indirect Reasoning (AKA Modus Tollens)	(p→q)∧¬q⇒¬p(p→q)∧¬q⇒¬p
Disjunctive Addition	p⇒(p∨q)p⇒(p∨q)
Conjunctive Simplification	(p∧q)⇒p(p∧q)⇒p and (p∧q)⇒q(p∧q)⇒q
Disjunctive Simplification	(p∨q)∧¬p⇒q(p∨q)∧¬p⇒q and (p∨q)∧¬q⇒p(p∨q)∧¬q⇒p
Chain Rule	(p→q)∧(q→r)⇒(p→r)(p→q)∧(q→r)⇒(p→r)
Conditional Equivalence	p→q⇔¬p∨qp→q⇔¬p∨q
Biconditional Equivalences	(p↔q)⇔(p→q)∧(q→p)⇔(p∧q)∨(¬p∧¬q)(p↔q)⇔(p→q)∧(q→p)⇔(p∧q)∨(¬p∧¬q)
Contrapositive	(p→q)⇔(¬q→¬p)

Lambda

Function terms, called lambda abstractions, are literal expressions that represent mathematical functions. Yes, you can and should now think of functions as being values, too. Function definitions are terms in predicate logic and in functional programming languages. As we will see later on, we can pass functions as arguments to other functions, and receive them as results. Functions that take functions as arguments or that return functions as results are called higher-order functions. We will get to this topic later on.

Consider the simple lambda expression, . It’s a term that represents a function that takes one argument, n, of type, nat. When applied to an actual parameter, or argument, it returns the value of that argument plus one.

Here’s the example in Lean. It first shows that the literal function expression reduces to the value that it represents directly. It then shows that this function can be applied to an actual parameter, i.e., an argument, 5, reducing to the value 6. Third, it shows that a literal function term can be bound to an identifier, here f, and finally that this makes it easier to write code to apply the function to an argument.

#reduce (λ n : ℕ, n + 1)

#eval (λ n : ℕ, n + 1) 5

def f := (λ n : ℕ, n + 1)

#eval f 5

Lambda calculus terms can be viewed as a kind of binary tree. A lambda calculus term consists of:

• Variables, which we can think of as leaf nodes holding strings.
• Applications, which we can think of as internal nodes.
• Lambda abstractions, which we can think of as a special kind of internal node whose left child must be a variable. (Or as a internal node labeled with a variable with exactly one child.)

It’s slightly annoying to have to define a helper procedure add-three just so we can use it as the argument to every. We’re never going to use that procedure again, but we still have to come up with a name for it. We’d like a general way to say “here’s the function I want you to use” without having to give the procedure a name. In other words, we want a general-purpose procedure-generating procedure!

Lambda is the name of a special form that generates procedures. It takes some information about the function you want to create as arguments and it returns the procedure. It’ll be easier to explain the details after you see an example.

(define (add-three-to-each sent)

  (every (lambda (number) (+ number 3)) sent))

> (add-three-to-each ‘(1 9 9 2))

(4 12 12 5)

The first argument to every is, in effect, the same procedure as the one we called add-three earlier, but now we can use it without giving it a name. (Don’t make the mistake of thinking that lambda is the argument to every. The argument is the procedure returned by lambda.)

Perhaps you’re wondering whether “lambda” spells something backward. Actually, it’s the name of the Greek letter L, which looks like this: λ. It would probably be more sensible if lambda were named something like make-procedure, but the name lambda is traditional.[1]

Creating a procedure by using lambda is very much like creating one with define, as we’ve done up to this point, except that we don’t specify a name. When we create a procedure with define, we have to indicate the procedure’s name, the names of its arguments (i.e., the formal parameters), and the expression that it computes (its body). With lambda we still provide the last two of these three components.

As we said, lambda is a special form. This means, as you remember, that its arguments are not evaluated when you invoke it. The first argument is a sentence containing the formal parameters; the second argument is the body. What lambda returns is an unnamed procedure. You can invoke that procedure:

> ((lambda (a b) (+ (* 2 a) b)) 5 6)

16

> ((lambda (wd) (word (last wd) (first wd))) ‘impish)

It’s slightly annoying to have to define a helper procedure add-three just so we can use it as the argument to every. We’re never going to use that procedure again, but we still have to come up with a name for it. We’d like a general way to say “here’s the function I want you to use” without having to give the procedure a name. In other words, we want a general-purpose procedure-generating procedure!

Lambda is the name of a special form that generates procedures. It takes some information about the function you want to create as arguments and it returns the procedure. It’ll be easier to explain the details after you see an example.

(define (add-three-to-each sent)

  (every (lambda (number) (+ number 3)) sent))

> (add-three-to-each ‘(1 9 9 2))

(4 12 12 5)

The first argument to every is, in effect, the same procedure as the one we called add-three earlier, but now we can use it without giving it a name. (Don’t make the mistake of thinking that lambda is the argument to every. The argument is the procedure returned by lambda.)

Perhaps you’re wondering whether “lambda” spells something backward. Actually, it’s the name of the Greek letter L, which looks like this: λ. It would probably be more sensible if lambda were named something like make-procedure, but the name lambda is traditional.[1]

Creating a procedure by using lambda is very much like creating one with define, as we’ve done up to this point, except that we don’t specify a name. When we create a procedure with define, we have to indicate the procedure’s name, the names of its arguments (i.e., the formal parameters), and the expression that it computes (its body). With lambda we still provide the last two of these three components.

As we said, lambda is a special form. This means, as you remember, that its arguments are not evaluated when you invoke it. The first argument is a sentence containing the formal parameters; the second argument is the body. What lambda returns is an unnamed procedure. You can invoke that procedure:

> ((lambda (a b) (+ (* 2 a) b)) 5 6)

> ((lambda (wd) (word (last wd) (first wd))) ‘impish)

Searching algorithms are used to find a specified element within a data structure. For example, a searching algorithm could be used to find the name “Alan Turing” in an array of names. Numerous different searching algorithms exist, each of which is suited to a particular data structure of format of data. Different searching algorithms are used depending on each individual scenario. Binary Search The binary search algorithm can only be applied on sorted data and works by finding the middle element in a list of data before deciding which side of the data the desired element is to be found in. The unwanted half of the data is then discarded and the process repeated until the desired element is found or until it is known that the desired element doesn’t exist in the data.

 Pseudocode for binary search is shown below. A ​ = Array of data x ​ = Desired element low = 0  high = A.length -1  while low <= high:  mid = (low + high) / 2  if A[mid] == x:  return mid  else if

A[mid] > x:  high = mid -1  else:  low = mid + 1  endif  endwhile  return

 “Not found in data”  With each iteration of binary search, half of the input data is discarded, making the algorithm very efficient. In fact, the time complexity of binary search is O(log n)​ .

www.pmt.education Example 1 Find the location of “Dylan” in the data below.

 0  Alice

1 Bob

2  Charlie

3 Dylan

5 Ellie

 6  Franz

Gabbie Hugo Ingrid To start with, our values for high and low and 8 and 0 respectively. The first step is to find the middle position.

 In this case, it’s (0 + 8) / 2 = ​4​ . Next we inspect the data in position 4: Ellie. This is higher than the desired data and so we discard elements 4-8, setting high as 3. 0  Alice 1  2  3  4  5  6  7  8  Bob Charlie Dylan Ellie Franz Gabbie Hugo Ingrid Again, we calculate the value of the middle position.

This time it’s (0 + 3) / 2 = ​2 (We have to round to the nearest whole number). Inspecting the data at this position we find Charlie, which is lower than the. This breaks the condition of low being less than or equal to high, and so breaks the while loop in the pseudocode. The algorithm then returns “Not found in data” before terminating. Example 3 Look at how the algorithm finds the letter R in the first 20 characters of the alphabet. It’s clear from this example that the algorithm halves the remaining data to be searched with each iteration, gradually reducing the size of the problem to be solved. A B C D E F G H I J K L M N O P Q R S T  A B C D E F G H I J K L M N O P Q R S T  A B C D E F G H I J K L M N O P Q R S T  A B C D E F G H I J K L M N O P Q R S T 

.pmt.education

Linear Search Linear search is the most basic searching algorithm. You can think of it as going along a bookshelf one by one until you come across the book you’re looking for. Sometimes the algorithm gets lucky and finds the desired element almost immediately, while in other situations, the algorithm is incredibly inefficient.

 It’s time complexity is O(n)​ . There’s a lot of pot luck involved with linear search, but it’s incredibly easy to implement. Unlike binary search, linear search doesn’t require the data to be sorted. A ​ = Array of data x ​ = Desired element i = 0  while i < A.length:  if A[i] == x:  return i  else:  i = i + 1  endif  endwhile  return “Not found in data”  Example 1

 Find the position of Apple in the data. 0  Banana

1  Orange

2  3  4  Apple

Kiwi First we inspect position 0,

 and find Banana.

Not the element we’re after.

0  1  2  3  Mango

 4  Banana

Orange

 Apple

 Kiwi

Next we inspect position 1, finding Orange.

Again, not what we’re looking for. 0  1  2  3 

www.pmt.education Example 2 Look at how this algorithm finds the letter R in the first 20 characters of the alphabet and compare it to binary search above. It’s clear from this example that the algorithm is much less efficient than binary search, particularly when the search value is towards the end of the data to be searched.

A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

 A B C D E F G H I J K L M N O P Q R S T

A B C D E F G H I J K L M N O P Q R S T A B C D E F G H I J K L M N O P Q

Conclusion:
While we note that this is an aspect of discrete mathematics that would benefit from more systematic study and research, this accessibility has come through in some research studies, but not as an explicit focus of the study. Some of the research on the teaching and learning of discrete mathematics with younger students highlights not only the accessibility of topics but that this accessibility can help students make sense of the current curriculum. For example, iterative problems and difference equations can help students learn algebra (Amit & Neria, 2008; Blanton & Kaput, 2005; Carraher et al., 2008; Radford, 2008; Rivera & Becker, 2008; Sandefur et al., 2018; Steele, 2008; Yeap & Kaur, 2008). Even very young students can reason about combinatorial problems in meaningful ways (de Beer et al., 2015; Maher et al., 2011). English (1991, 1993) reports on young children’s strategies as they engage with combinatorial problems. As another example, students can naturally `invent’ graph theory to solve a problem (Ferrarello & Mammana, 2018; Greefrath et al., 2022; van den Heuvel & Krabbendam, 1991).

We can only wonder how much better would the students’ work be if they already knew some graph theory or had previous experience with counting or recursive problems? For many topics in discrete mathematics, students ranging from young children to undergraduate students can be posed similar questions and have a reasonable chance at Investigating the problem at their different levels.

This results in self differentiating tasks that allow individual approaches to the problem (Ostkirchen & Greefrath, 2022). For example, how many 2-color towers can I make of height 5, can be extended to more complicated problems for older students by increasing the number of colors and the height of the tower. Maher et al. (2011) describe the use of combinatorial problems in such contexts among students in a longitudinal study. Students as young as the third grade can investigate recursive structures they build with toothpicks and stickers while high school students can develop recursive models of bacteria growth and the spread of epidemics, which is a simplified version of models studied by epidemiologists (Radford, 2008; Sandefur & Manaster, 2022; Yeap & Kaur, 2008).

This highlights what we mean by accessibility – students can have access to mathematical topics and ideas regardless of background and prerequisite knowledge (DeBellis & Rosenstein, 2004; Ferrarello & Mammana, 2018). Although we have several examples of empirical research that implicitly demonstrates the accessibility of discrete mathematics and the value of this accessibility, we note that there is also more work to be done. There is a need for the field to focus on the issue of accessibility more systematically and explicitly.

Bottom of Form