discrete structure assignment 2

CS202: Discrete Structures

Course introduction.

• Time: 44 hours
• Free Certificate

Understanding the terms "single-membership" and "discrete" are important as you begin this course. "Single-Membership" refers to something that is grouped within only one set and systems that can be in only one state at a time, at the same hierarchical level. Similarly, "discrete" refers to that which is individually separate and distinct. Each element of anything can be in only one set or one state at a time. This is a result of Aristotelian philosophy, which holds that there are only two values of membership, 0 or 1. An answer is either no or yes, false or true, 0% membership or 100% membership, entirely in a set or state, or entirely not. There are no shades of gray. This is much different from Fuzzy Logic (due to Lofti Zadeh), where something can be a member of any set or in any state to some degree or another. Degrees of membership are measured in percentage, and those percentages add to 100%. But, even in Fuzzy Logic (multiple-membership, multiple-state, non-discrete logic), one ultimately comes to a crisp decision so whether some specific action is taken or not. For this course, it is enough to understand the difference between single-state and multi-state logic.

As you progress through the units of this course, you will develop the mathematical foundation necessary for more specialized subjects in computer science, including data structures, algorithms, cryptology, and compiler design. Upon completion of this course, you will have the mathematical know-how required for an in-depth study of the science and technology that is foundational to the computer age.

Course Syllabus

First, read the course syllabus. Then, enroll in the course by clicking "Enroll me". Click Unit 1 to read its introduction and learning outcomes. You will then see the learning materials and instructions on how to use them.

Unit 1: Sets, Set Relations, and Set Functions

Computer scientists often find themselves working with groups of homogeneous or heterogeneous entities. Mathematicians devised single-membership set theory to respond to these situations. In this unit, we will cover the theoretical background of sets and take a look at associated definitions, notations, relations, and functions. This is a fundamental tool of mathematics and computer science, and is essential to understanding the other topics in this course.

Completing this unit should take you approximately 5 hours.

Unit 2: Counting Theory

"How many elements do we expect to find within a given set?" This is a simple question, but hard to answer correctly without guessing. Counting theory (also known as combinatorics) lets us do that through several different approaches that depend on the circumstances of the given problem. These approaches are not difficult, but you have to know when to use each one, and which circumstances each approach applies to. In this unit, we will carefully walk through these considerations.

Unit 3: Mathematical Logic

In this unit, we will discuss basic concepts that are part of the foundation of mathematical logic. As you seek to fully understand these concepts, you must be able to recognize valid logical arguments. Although these arguments will usually be applied to mathematics, they are the same techniques used by lawyers in the courtroom, physicians examining a patient, or engineers trying to solve a difficult problem. The circuits of computers are designed using the same algebra of propositions that we will discuss in this unit. Often, embedded computers (that is, the data processing units within a larger machine) are programmed by using binary, gate-level logic, machine code, or ladder logic. These rely on the basic concepts we will discuss here.

Unit 4: Mathematical Induction and Proofs

So far, we have learned about symbology, truth tables, writing equations, and determining how many units could be in a set under specific circumstances. We have done all of this has under the assumption that we can easily see the results of our efforts. However, in practical situations that you will encounter in real life with serious applications, we cannot always see our results quickly, or necessarily even traverse the situation easily. For that, we must turn to the methods behind mathematical systems and proofs. These allow us to "get the big picture" without having to visualize it all at once. Proofs also give us a way to consider all of the available information in a given arrangement of facts, even when some of the "facts" might not actually be true. They also have the added advantage of letting us ignore whole portions of a situation when we know they do not hold the answer we seek.

Unit 5: Probability

Probability is an important component of discrete mathematics. For instance, if you consider a population of 10 and then take four at a time, without duplicates, what is the chance that a certain combination within the subsets of four will occur? Or, given the set of all possible events, what is the chance that a certain event will occur, given that the event can result from various causes? The construction of trees and graphs , which we will discuss later, depends on the probability of combinations of events. Since we want to traverse trees and graphs in order of the most likely and most important events, we need to know probability.

Completing this unit should take you approximately 4 hours.

Unit 6: Recursion

Using recursion, we can arrive at a succession of elements (such as numbers or events) by operating on one or more of the elements that came earlier. We do this using a rule or formula with a finite number of steps. In computer programming, we implement recursion with procedures, subroutines, functions, or algorithms that run one or more times until a specified condition is met. At that point, the remaining code in each procedure is processed from the last procedure called to the first.  From a practitioner's perspective, recursive procedures are simple to write, but they are extremely memory-intensive, and it can be difficult to predict how much memory will be required.

Recursion is common, so you will need to understand it at a fundamental level. A basic example of a recursive sequence is Dt = f(D[t-1]). The data at time t is a function of the data at the previous unit of time. In practice, this can be implemented as a recursive function or an explicit (that is, non-recursive) function. This unit will delve deeper into this topic.

Unit 7: Graphs

Graphs are formal mathematical representations of networks, collections of objects, events, or set elements that lead naturally from one to another. In this unit, we will examine the formality of graphs. Graphs are extremely useful in business, science, and engineering. In this unit, we will discuss how to understand graphs, how to build them, how to manipulate them, and how to use them.

Completing this unit should take you approximately 9 hours.

Unit 8: Trees

Trees are a special case of graphs. Certain assumptions are made about the structure of trees, so various actions can be taken with them that would not work with graphs. Put simply, a tree is a nondirected graph where any two nodes are connected by exactly one path. There are no cycles in a tree. Although this definition is very simple, it has powerful consequences within graph theory and in the real world. In this unit, we will explore trees further.

Unit 9: Finite-State Automata

A finite-state machine (FSM) is a mathematical model of computation that describes an abstract machine in one of a finite number of states at any point in time. The FSM can change from one state to another as it responds to data inputs, or when some condition is satisfied. The change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition. Often, state machines are illustrated as graphs whose nodes are the states and whose links are the transition conditions.

Completing this unit should take you approximately 2 hours.

Study Guide

This study guide will help you get ready for the final exam. It discusses the key topics in each unit, walks through the learning outcomes, and lists important vocabulary. It is not meant to replace the course materials!

Course Feedback Survey

Please take a few minutes to give us feedback about this course. We appreciate your feedback, whether you completed the whole course or even just a few resources. Your feedback will help us make our courses better, and we use your feedback each time we make updates to our courses.

If you come across any urgent problems, email [email protected].

Certificate Final Exam

Take this exam if you want to earn a free Course Completion Certificate.

To receive a free Course Completion Certificate, you will need to earn a grade of 70% or higher on this final exam. Your grade for the exam will be calculated as soon as you complete it. If you do not pass the exam on your first try, you can take it again as many times as you want, with a 7-day waiting period between each attempt.

Once you pass this final exam, you will be awarded a free Course Completion Certificate .

Course Information and Catalog Description

An introduction to discrete mathematical structures including functions, relations, sets, logic, matrices, elementary number theory, proof techniques, basics of counting, graphic theory, discrete probability, digital logic, finite state machines, integer and floating point representations.

Instructor Contact Information

Course content and goals.

The CS 227-228 sequence lays the foundation for students to succeed in upper-level CS courses, most of which require understanding of concepts from discrete mathematics. This course is designed for students to learn how to think logically and mathematically, as well as practice fundamental techniques for solving problems in computer science. Our main goals are based on the five themes of the textbook (see pages vii-viii). By the end of this course, you should be able to:

• Read, comprehend, and construct mathematical arguments. (Mathematical Reasoning)
• Solve arithmetic and counting problems. (Combinatorial Analysis)
• Demonstrate how abstract mathematical ideas like graphs, trees, and finite-state machines relate to real-world computational problems. (Discrete Structures)
• Illustrate basic mathematical techniques for specifying, verifying, and analyzing computer algorithms. (Algorithmic Thinking)
• Identify a variety of natural and relevant uses of discrete math in the real world. (Applications and Modeling)

Methods of Evaluation

Course grades will be based on weekly homework assignments, class participation and three exams. Assignment specifications and due dates will be posted to the course schedule page . The final grade will be computed as follows:

Letter grades will be assigned on the scale A=90-100, B=80-89, C=70-79, D=60-69, F=0-59, with potential minor adjustments after considering the overall performance of the class and actual distribution of numeric scores. I will use "+" and "-" grades at my discretion. I do not assign WP or WF grades except under extraordinary circumstances.

Homework Assignments

Weekly homework assignments will be due on Fridays at 1:00PM. Late submissions will not be accepted. In recognition of the fact that there may unforeseen circumstances that prevent you from submitting some assignments, I will drop the two lowest homework grades.

Solutions to homework assignments must be prepared in LaTeX and submitted through Canvas. Some homework assignments will include short programming exercises to be completed in the Python programming language (version 2.7).

I encourage you to discuss homework assignments with other students and to work collaboratively to find solutions. "Collaboration" in this context means that all participants are actively engaged in solving the problem. Simply copying another students answer would be considered a violation of the honor code. Your final submission must be written entirely by you, based on your own understanding of the material. If you choose to work with another student on a homework assignment, the name of that student and the nature of the collaboration must be included in an acknowledgment statement at the top of your submission.

Class Participation and Quizzes

Regular attendance and fully engaged participation is expected of all students. Several students will be chosen each week to present solutions to selected homework problems. Your participation grade will be partly determined by the clarity and correctness of your presentations.

You should complete all assigned readings before each class session. I will post occasional reading quizzes to Canvas. These quizzes will be due before the beginning of class.

All exams will be cumulative with an emphasis on material covered since the previous exam.

If you are unable to take an exam at the scheduled time because of illness or other problems, you must contact me beforehand to arrange to take the exam at a different time. Failure to make prior arrangements for a missed exam will result in a grade of 0 for the exam.

Course Policies

Academic integrity.

Your work in this course must comply with the provisions of the JMU honor code: http://www.jmu.edu/honor/code.shtml . Representing someone else's work as your own, in any form, constitutes an honor code violation. It is also a violation of the honor code to "render unauthorized assistance to another student by knowingly permitting him or her to see or copy all or a portion of an examination or any work to be submitted for academic credit."

If you are in doubt about what is allowed, ask me. You are responsible for understanding the boundary between appropriate collaboration and academic misconduct.

Adding/Dropping

Students are responsible for adding and dropping courses via MyMadison. The last day to add a course for Spring 2014 is January 30th (signatures required after January 21st). The last day to drop a course for the Spring 2014 semester with a "W" grade is March 21st.

Disability Accommodations

If you need an accommodation based on the impact of a disability, you should contact the Office of Disability Services (Wilson Hall, Room 107, www.jmu.edu/ods, 540-568-6705) if you have not previously done so. Disability Services will provide you with an Access Plan Letter that will verify your need for services and make recommendations for accommodations to be used in the classroom. Once you have presented me with this letter, you and I will sit down and review the course requirements, your disability characteristics, and your requested accommodations to develop an individualized plan, appropriate for this course.

Inclement Weather Policy

This class will operate in accord with JMU's inclement weather policy available at http://www.jmu.edu/JMUpolicy/1309.shtml

Religious Observation Accommodations

I will give reasonable accommodations to students requesting them on grounds of religious observation. If you require such accommodations you must notify me at least two weeks in advance.

Acknowledgments

The design of this course borrows extensively from previous offerings by Dr. Chris Mayfield . Many of the course materials that we will use (including this syllabus) are either borrowed or adapted from Dr. Mayfield's originals.

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

2.5.8: Truth in a Structure

• Last updated
• Save as PDF
• Page ID 86105

• Christopher Leary and Lars Kristiansen
• SUNY Geneseo and University of Oslo via OpenSUNY

It is at last time to tie together the syntax and the semantics. We have some formal rules about what constitutes a language, and we can identify the terms, formulas, and sentences of a language. We can also identify \(\mathcal{L}\)-structures for a given language \(\mathcal{L}\). In this section we will decide what it means to say that an \(\mathcal{L}\)-formula \(\phi\) is true in an \(\mathcal{L}\)-structure \(\mathfrak{A}\).

To begin the process of tying together the symbols with the structures, we will introduce assignment functions. These assignment functions will formalize what it means to interpret a term or a formula in a structure.

Definition 1.7.1. If \(\mathfrak{A}\) is an \(\mathcal{L}\)-structure, a variable assignment function into \(\mathfrak{A}\) is a function \(s\) that assigns to each variable an element of the universe \(A\). So a variable assignment function into \(\mathfrak{A}\) is any function with domain \(Vars\) and codomain \(A\).

Variable assignment functions need not be injective or bijective. For example, if we work with \(\mathcal{L}_{NT}\) and the standard structure \(\mathfrak{N}\), then the function \(s\) defined by \(s \left( v_i \right) = i\) is a variable assignment function, as is the function \(s'\) defined by

\[s' \left( v_i \right) = \: \text{the smallest prime number that does not divide} \: i.\]

We will have occasion to want to fix the value of the assignment function \(s\) for certain variables.

Definition 1.7.2. If \(s\) is a variable assignment function into \(\mathfrak{A}\) and \(x\) is a variable and \(a \in A\), then \(s \left[ x | a \right]\) is the variable assignment function into \(\mathfrak{A}\) defined as follows:

\[s \left[ x | a \right] = \begin{cases} s \left( v \right) \: \: \: \text{if} \: v \: \text{is a variable other than} \: x \\ a \: \: \: \: \: \: \: \: \: \: \: \text{if} \: v \: \text{is the variable} \: x \end{cases}\]

We call the function \(s \left[ x | a \right]\) an \(x\)-modification of the assignment function \(s\) .

So an \(x\)-modification of \(s\) is just like \(s\), except that the variable \(x\) is assigned to a particular element of the universe.

What we will do next is extend a variable assignment function \(s\) to a term assignment function, \(\bar{s}\). This function will assign an element of the universe to each term of the language \(\mathcal{L}\).

Definition 1.7.3. Suppose that \(\mathfrak{A}\) is an \(\mathcal{L}\)-structure and \(s\) is a variable assignment function into \(\mathfrak{A}\). The function \(\bar{s}\), called the term assignment function generated by \(s\) , is the function with domain consisting of the set of \(\mathcal{L}\)-terms and codomain \(A\) defined recursively as follows:

• If \(t\) is a variable, \(\bar{s} \left( t \right) = s \left( t \right)\).
• If \(t\) is a constant symbol \(c\), then \(\bar{s} \left( t \right) = c^\mathfrak{A}\).
• If \(t : \equiv f t_1 t_2 \ldots t_n\), then \(\bar{s} \left( t \right) = f^\mathfrak{A} \left( \bar{s} \left( t_1 \right), \bar{s} \left( t_2 \right), \ldots, \bar{s} \left( t_n \right) \right)\).

Although we will be primarily interested in truth of sentences, we will first describe truth (or satisfaction) for arbitrary formulas, relative to an assignment function.

Definition 1.7.4. Suppose that \(\mathfrak{A}\) is an \(\mathcal{L}\)-structure, \(\phi\) is an \(\mathcal{L}\)-formula, and \(s : Vars \rightarrow A\) is an assignment function. We will say that \(\mathfrak{A}\) satisfies \(\phi\) with assignment \(s\) , and write \(\mathfrak{A} \models \phi \left[ s \right]\), in the following circumstances:

• If \(\phi : \equiv t_1 t_2\) and \(\bar{s} \left( t_1 \right)\) is the same element of the universe \(A\) as \(\bar{s} \left( t_2 \right)\), or
• If \(\phi : \equiv R t_1 t_2 \ldots t_n\) and \(\left( \bar{s} \left( t_1 \right), \bar{s} \left( t_2 \right), \ldots, \bar{s} \left( t_n \right) \right) \in R^\mathfrak{A}\), or
• If \(\phi : \equiv \left( \neg \alpha \right)\) and \(\mathfrak{A} \not\models \alpha \left[ s \right]\), (where \(\not\models\) means "does not satisfy"), or
• If \(\phi : \equiv \left( \alpha \lor \beta \right)\) and \(\mathfrak{A} \models \alpha \left[ s \right]\), or \(\mathfrak{A} \models \beta \left[ s \right]\) (or both), or
• If \(\phi : \equiv \left( \forall x \right) \left( \alpha \right)\) and, for each element \(a\) of \(A\), \(\mathfrak{A} \models \alpha \left[ s \left( x | a \right) \right]\).

If \(\Gamma\) is a set of \(\mathcal{L}\)-formulas, we say that \(\mathfrak{A}\) satisfies \(\Gamma\) with assignment \(s\), and write \(\mathfrak{A} \models \Gamma \left[ s \right]\) if for each \(\gamma \in \Gamma\), \(\mathfrak{A} \models \gamma \left[ s \right]\).

Chaff: Notice that the symbol \(\models\) is not part of the language \(\mathcal{L}\). Rather, \(\models\) is a metalinguistic symbol that we use to talk about formulas in the language and structures for the language.

Chaff: Also notice that we have at last tied together the syntax and semantics of our language! The definition above is the place where we formally put the meanings on the symbols that we will use, so that \(\lor\) means "or" and \(\forall\) means "for all".

Example 1.7.5. Let us work with the empty language, so \(\mathcal{L}\) has no constant symbols, no function symbols, and no relation symbols. So an \(\mathcal{L}\)-structure is simply a nonempty set, and let us consider the \(\mathcal{L}\)-structure \(\mathfrak{A}\), where \(A = \{ \text{Humphrey, Ingrid}\}\). Consider the formula \(x = y\) and the assignment function \(s\), where \(s \left( x \right)\) is Humphrey and \(s \left( y \right)\) is also Humphrey. If we ask whether \(\mathfrak{A} \models x = y \left[ s \right]\), we have to check whether \(bar{s} \left( x \right)\) is the same element of \(A\) as \(\bar{s} \left( y \right)\). Since the two objects are identical, the formula is true.

To emphasize this, the formula \(x = y\) can be true in some universes with some assignment functions. Although the variables \(x\) and \(y\) are distinct, the truth or falsity of the formula depends not on the variables (which are not equal) but rather, on which elements of the structure the variables denote, the values of the variables (which are equal for this example). Of course, there are other assignment functions and other structures that make our formula false. We are sure you can think of some.

To talk about the truth or falsity of a sentence in a structure, we will take our definition of satisfaction relative to an assignment function and prove that for sentences, the choice of the assignment function is inconsequential. Then we will say that a sentence \(\sigma\) is true in a structure \(\mathfrak{A}\) if and only if \(\mathfrak{A} \models \sigma \left[ s \right]\) for any (and therefore all) variable assignment functions \(s\).

Chaff: The next couple of proofs are proofs by induction on the complexity of terms or formulas. You may want to reread the proof of Theorem 1.4.2 if you find these difficult.

Lemma 1.7.6. Suppose that \(s_1\) and \(s_2\) are variable assignment functions into a structure \(\mathfrak{A}\) such that \(s_1 \left( v \right) = s_2 \left( v \right)\) for every variable \(v\) in the term \(t\). Then \(\bar{s_1} \left( t \right) = \bar{s_2} \left( t \right)\).

Proof. We use induction on the complexity of the term \(t\). If \(t\) is either a variable or a constant symbol, the result is immediate. If \(t : \equiv f t_1 t_2 \ldots t_n\), then as \(\bar{s_1} \left( t_i \right) = \bar{s_2} \left( t_i \right)\) for \(1 \leq i \leq n\) by the inductive hypothesis, the definition of \(\bar{s_1} \left( t \right)\) and the definition of \(\bar{s_2} \left( t \right)\) are identical, and thus \(\bar{s_1} \left( t \right) = \bar{s_2} \left( t \right)\).

Proposition 1.7.7. Suppose that \(s_1\) and \(s_2\) are variable assignment functions into a structure \(\mathfrak{A}\) such that \(s_1 \left( v \right) = s_2 \left( v \right)\) for every free variable \(v\) in the formula \(\phi\). Then \(mathfrak{A} \models \phi \left[ s_1 \right]\) if and only if \(\mathfrak{A} \models \phi \left[ s_2 \right]\).

Proof. We use induction on the complexity of \(\phi\). If \(\phi : \equiv = t_1 t_2\), then the free variables of \(\phi\) are exactly the variables that occur in \(\phi\). Thus Lemma 1.7.6 tells us that \(\bar{s_1} \left( t_1 \right) = \bar{s_2} \left( t_1 \right)\) and \(\bar{s_1} \left( t_2 \right) = \bar{s_2} \left( t_2 \right)\), meaning that they are the same element of the universe \(A\), so \(\mathfrak{A} \models \left( = t_1 t_2 \right) \left[ s_1 \right]\) if and only if \(\mathfrak{A} \models \left( = t_1 t_2 \right) \left[ s_2 \right]\), as needed.

The other base case, if \(\phi : \equiv R t_1 t_2 \ldots t_n\), is similar and is left as part of Exercise 6.

To begin the first inductive clause, if \(\phi : \equiv \neg \alpha\), notice that the free variables of \(\phi\) are exactly the free variables of \(\alpha\), so \(s_1\) and \(s_2\) agree on the free variables of \(\alpha\). By the inductive hypothesis, \(\mathfrak{A} \models \alpha \left[ s_1 \right]\) if and only if \(\mathfrak{A} \models \alpha \left[ s_2 \right]\), and thus (by the definition of satisfaction), \(\mathfrak{A} \models \phi \left[ s_1 \right]\) if and only if \(\mathfrak{A} \models \phi \left[ s_2 \right]\). The second inductive clause, if \(\phi : \equiv \alpha \lor \beta\), is another part of Exercise 6.

If \(\phi : \equiv \left( \forall x \right) \left( \alpha \right)\), we first note that the only variable that might be free in \(\alpha\) that is not free in \(\phi\) is \(x\). Thus, if \(a \in A\), the assignment functions \(s_1 \left[ x | a \right]\) and \(s_2 \left[ x | a \right]\) agree on all of the free variables of \(\alpha\). Therefore, by inductive hypothesis, for each \(a \in A\), \(\mathfrak{A} \ = \alpha \left[ s_1 \left[ x | a \right] \right]\) if and only if \(\mathfrak{A} \models \alpha \left[ s_2 \left[ x | a \right] \right]\). So, by Definition 1.7.4, \(\mathfrak{A} \models \phi \left[ s_1 \right]\) if and only if \(\mathfrak{A} \models \phi \left[ s_2 \right]|). This finishes the last inductive clause, and our proof.

Corollary 1.7.8 If \(\sigma\) is a sentence in the language \(\mathcal{L}\) and \(\mathfrak{A}\) is an \(\mathcal{L}\)-structure, either \(\mathfrak{A} \models \sigma \left[ s \right]\) for all assignment functions \(s\), or \(\mathfrak{A} \models \sigma \left[ s \right]\) for no assignment function \(s\).

Proof. There are no free variables in \(\sigma\), so if \(s_1\) and \(s_2\) are two assignment functions, they agree on all of the free variables of \(\sigma\), there just aren't all that many of them. So by Proposition 1.7.7, \(\mathfrak{A} \models \sigma \left[ s_1 \right]\) if and only if \(\mathfrak{A} \models \sigma \left[ s_2 \right]\), as needed.

Definition 1.7.9. If \(\phi\) is a formula in the language \(\mathcal{L}\) and \(\mathfrak{A}\) is an \(\mathcal{L}\)-structure, we say that \(\mathfrak{A}\) is a model of \(\phi\), and write \(\mathfrak{A} \models \phi\), if and only if \(\mathfrak{A} \models \phi \left[ s \right]\) for every assignment function \(s\). If \(\Phi\) is a set of \(\mathcal{L}\)-formulas, we will say that \(\mathfrak{A}\) models \(\Phi\), and write \(\mathfrak{A} \models \Phi\), if and only if \(\mathfrak{A} \models \phi\) for each \(\phi \in \Phi\).

Notice that if \(\sigma\) is a sentence , then \(\mathfrak{A} \models \sigma\) if and only if \(\mathfrak{A} \models \sigma \left[ s \right]\) for any assignment function \(s\). In this case we will say that the sentence \(\sigma\) is true in \(\mathfrak{A}\) .

Example 1.7.10. Let's work in \(\mathcal{L}_{NT}\), and let

\[\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right)\]

be the standard structure. Let \(s\) be the variable assignment function that assigns \(v_i\) to the number \(2i\). Now let the formula \(\phi \left( v_1 \right)\) be \(v_1 + v_2 = SSSS0\).

To show that \(\mathfrak{N} \models \phi \left[ s \right]\), notice that

\[\begin{align} \bar{s} \left( v_1 + v_1 \right) \: &\text{is} \: +^\mathfrak{N} \left( \bar{s} \left( v_1 \right), \bar{s} \left( v_1 \right) \right) \\ &\text{is} \: +^\mathfrak{N} \left( 2, 2 \right) \\ &\text{is} \: 4 \end{align}\]

\[\begin{align} \bar{s} \left( SSSS0 \right) \: &\text{is} \: S^\mathfrak{N} \left( S^\mathfrak{N} \left( S^\mathfrak{N} \left( S^\mathfrak{N} \left( 0^\mathfrak{N} \right) \right) \right) \right) \\ &\text{is} \: 4 \end{align}\]

Now, in the same setting, consider \(\sigma\), the sentence

\[\left( \forall v_1 \right) \neg \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_1 \right),\]

which states that everything is even. [That is hard to see unless you know to look for that \(\neg \left( \forall v_2 \right) \neg\) and to read it as \(\left( \exists v_2 \right)\). See the last couple of paragraphs of this section.] You know that \(\sigma\) is false in the standard structure, but to show how the formal argument goes, let \(s\) be any variable assignment function and notice that

\[\begin{align} \mathfrak{N} \models \sigma \left[ s \right] \: &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \mathfrak{N} \models \neg \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_2 \right) s \left[ v_1 | a \right] \\ &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \mathfrak{N} \not\models \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_2 \right) s \left[ v_1 | a \right] \\ &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \text{there is a } b \in \mathbb{N}, \: \mathfrak{N} \models v_1 = v_2 + v_2 \: s \left[ v_1 | a \right] \left[ v_2 | b \right]. \end{align}\]

Now, if we consider the case when \(a\) is the number 3, it is perfectly clear that there is no such \(b\), so we have shown \(\mathfrak{N} \not\models \sigma \left[ s \right]\). Then, by Definition 1.7.9, we see that the sentence \(\sigma\) is false in the standard structure. As you well knew.

When you were introduced to symbolic logic, you were probably told that there were five connectives. In the mathematics that you have learned recently, you have been using two quantifiers. We hope you have noticed that we have not used all of those symbols in this book, but is now time to make those symbols available. Rather than adding the symbols to our language, however, we will introduce them as abbreviations. This will help us to keep our proofs slightly less complex (as our inductive proofs will have fewer cases) but will still allow us to use the more familiar symbols, at least as shorthand.

Thus, let us agree to use the following abbreviations in constructing \(\mathcal{L}\)-formulas: We will write \(\left( \alpha \land \beta \right)\) instead of \(\left( \neg \left( \left( \neg \alpha \right) \lor \left( \neg \beta \right) \right) \right)\), \(\left( \alpha \rightarrow \beta \right)\) instead of \(\left( \left( \neg \alpha \right) \lor \beta \right)\), and \(\left( \alpha \leftrightarrow \beta \right)\) instead of \(\left( \left( \alpha \rightarrow \beta \right) \land \left( \beta \rightarrow \alpha \right) \right)\). We will also introduce our missing existential quantifier as an abbreviation, writing \(\left( \exists x \right) \left( \alpha \right)\) instead of \(\left( \neg \left( \forall x \right) \left( \neg \alpha \right) \right)\). It is an easy exercise to check that the introduced connectives \(\land\), \(\rightarrow\), and \(\leftrightarrow\) behave as you would expect them to. Thus \(\mathfrak{A} \models \left( \alpha \land \beta \right) \left[ s \right]\) if and only if both \(\mathfrak{A} \models \alpha \left[ s \right]\) and \(\mathfrak{A} \models \beta \left[ s \right]\). The existential quantifier is only slightly more difficult. See Exercise 7.

• We suggested after Definition 1.5.3 that the truth or falsity of the sentences \(1 + 1 = 2\) and \(\left( \forall x \right) \left( x + 1 = x \right)\) might not be automatic. Find a structure for the language discussed there that makes the sentence \(1 + 1 = 2\) true. Find another structure where \(1 + 1 = 2\) is false. Prove your assertions. Then show that you can find a structure where \(\left( \forall x \right) \left( x + 1 = x \right)\) is true, and another structure where it is false.
• Let the language \(\mathcal{L}\) be \(\{ S, C \}\), where \(S\) is a unary function symbol and \(<\) is a binary relation symbol. Let \(\phi\) be the formula \(\left( \forall x \right) \left( \exists y \right) \left( Sx < y \right)\). (a) Find an \(\mathcal{L}\)-structure \(\mathfrak{A}\) such that \(\mathfrak{A} \models \phi\). (b) Find an \(\mathcal{L}\)-structure \(\mathfrak{B}\) such that \(\mathfrak{B} \models \left( \neg \phi \right)\). (c) Prove that your answer to part (a) or part (b) is correct. (d) Write an \(\mathcal{L}\)-sentence that is true in a structure \(\mathfrak{A}\) if and only if the universe \(A\) of \(\mathfrak{A}\) consists of exactly two elements.
• Consider the language and structure of Example 1.6.4. Write two nontrivial sentences in the language, one of which is true in the structure and one of which (not the denial of the first) is false in the structure. Justify your assertions.
• Consider the sentence \(\sigma\): \(\left( \forall x \right) \left( \exists y \right) \left[ x < y \rightarrow x + 1 \neg y \right]\). Find two structures for a suitable language, one of which makes \(\sigma\) true, and the other of which makes \(\sigma\) false.
• One more bit of shorthand. Assume that the language \(\mathcal{L}\) contains the binary relation symbol \(\in\), which you are intending to use to mean the elementhood relation (so \(p \in q\) will mean that \(p\) is an element of \(q\)). Often, it is the case that you want to claim that \(\phi \left( x \right)\) is true for every element of a set \(b\). Of course, to do this you could write \[\left( \forall x \right) \left[ \left( x \in b \right) \rightarrow \phi \left( x \right) \right].\] We will abbreviate this formula as \[\left( \forall x \in b \right) \left( \phi \left( x \right) \right).\] Similarly, \(\left( \exists x \in b \right) \left( \phi \left( x \right) \right)\) will be an abbreviation for the formula \(\left( \exists x \right) \left[ \left( x \in b \right) \land \phi \left( x \right) \right]\). Notice that this formula has a conjunction where the previous formula had an implication!. We do that just to see if you are paying attention. (Well, if you think about what the abbreviations are supposed to mean, you'll see that the change is necessary. We'll have to do something else just to see if you're paying attention.) Now suppose that \(\mathfrak{A}\) is a structure for the language of set theory. So \(\mathcal{L}\) has only this one binary relation symbol, \(\in\), which is interpreted as the elementhood relation. Suppose, in addition, that \[A = \{ u, v, w, \{ u \}, \{ u, v \}, \{ u, v, w \} \}.\] In particular, notice that there is no element \(x\) of \(A\) such that \(x \in x\). Consider the sentence \[\left( \forall y \in y \right) \left( \exists x \in x \right) \left( x = y \right).\] Is this sentence true or false in \(\mathfrak{A}\)?
• Fill in the details to complete the proof of Proposition 1.7.7.
• Show that \(\mathfrak{A} \models \left( \exists x \right) \left( \alpha \right) \left[ s \right]\) if and only if there is an element \(a \in A\) such that \(\mathfrak{A} \models \alpha \left[ s \left[ x | a \right] \right]\).

© Alexander Brandt 2023

Theme by the Executable Book Project

Propositional Logic

1.1. propositional logic #.

Propositional Logic is the logical system built around proposition s. From such propositions one can build logical arguments and implications.

In this section we will explore the language of propositions, their applications, and deriving logical equivalences.

The Language of Propositions

Propositions

Constructing Propositions

Connectives

Conjunction

Disjunction

Implication

Biconditional

Propositional Formulas

Truth Tables

Implication, Inverse, Converse, and Contrapositive

Applications

Translating English to Propositional Logic

Boolean Searches

Formal Specifications

Solving logic puzzles

Logical Equivalences

Logically Equivalent

Equivalence proof

Basic Propositions

1.1.1. The Language of Propositions #

Propositions are all about truth. Is a statement true or false? Is a statement correct or incorrect?

Propositions #

Definition (Proposition)

A proposition is a declarative sentence or statement has a truth value. It is a statement which is either true or false. Each proposition has a “truth value”: either true or false.

To get acquainted with propositions, let us see some examples and counterexamples.

Examples of propositions

Socrates was a human.

Socrates was a pigeon.

It is raining today.

The logo of Starbucks is a green mermaid.

\(1 + 1 = 2\)

\(1 + 1 = 4\)

Notice that 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?

Some coffee mug with a mermaid on it.

\(x + 2 = 3\)

\(y = x^2 - 1\)

Are each of these propositions?

I am a dolphin.

Supercalifragilisticexpialidocious.

Jupiter is the 5th planet from the sun.

On Thursdays, van Gogh painted landscapes.

\(\frac{11+56*3-8}{19} = 9\)

Yes. This is a statement which is false. The author and the reader are both humans, right?

No. A single adjective on its own can not be true or false.

Yes. This is a statement which is true.

Yes. While I do not personally know the truth value of this statement, it certainly has one.

Yes. A formula with no variables precisely stating an equality. The equality is true .

Constructing Propositions #

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

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 formula s. 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: \(\neg\)

Conjunction: \(\land\)

Disjunction: \(\lor\)

Implication: \(\rightarrow\)

Biconditional: \(\leftrightarrow\)

Logical connectives are like arithmetic operators ( \(+, -, \times, \div\) ).

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 \(\neg p\) and has the following truth values.

Let \(p := \) “the sky is blue”.

\(\neg p\) is “the sky is not blue” or “it is not the case that the sky is blue”.

Let \(q := \) “ \(2 + 2 = 5\) ”.

\(\neg q\) is “ \(2 + 2 \neq 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 \land q\) and has the following truth values.

Let \(p\) be “birds lay eggs” and \(q\) be “my eyes are blue”. \(p \land 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 \lor q\) and has the following truth values.

Let \(p\) be “it is raining” and \(q\) be “I am wearing sunglasses”. \(p \lor 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 \lor 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.

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 \(\oplus\) . However, we will not use that in this course.

What is the truth value of these compound propositions?

“The earth is round and the sky is blue.”

“Dogs or cats make great pets.”

“It is \(20^{\circ}\) Celsius outside and it is snowing.”

“Lemons are purple or grass is green”

True. Both propositions are individually true.

True. You may not like dogs, or you may not like cats, but at least one of dogs or cats make a great pet.

False. Both “it is \(20^{\circ}\) Celsius outside” and “it is snowing” cannot simultaneously be true. Therefore, their conjunction is false.

True. Lemons may not be purple, but (healthy) grass is green.

Implication #

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

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

Let \(p\) be “it is raining” and \(q\) be “the ground is wet”. \(p \rightarrow q\) can be read “if it is raining, then the ground is wet”.

In an implication \(p \rightarrow 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.

An implication can be viewed as an obligation , a contract , or a commitment . The implication \(p \rightarrow 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 \rightarrow 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 \rightarrow 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 \rightarrow 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 \rightarrow 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 \rightarrow q\) we get two relations:

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 \leftrightarrow q\) .

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

The biconditional \(p \leftrightarrow 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\) ”

Let \(p\) be “ \(2\) is an even number”. Let \(q\) be “ \(4\) is an even number”. \(p \leftrightarrow 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.

“The Earth is flat” \(\rightarrow\) “Pigeons are robots”

“Bats have wings” \(\rightarrow\) “Bats are birds”

“A square is a rectangle” \(\leftrightarrow\) “A square had four \(90^{\circ}\) interior angles”

“Spinach is green” \(\leftrightarrow\) “Penguins can fly”

True. “The Earth is flat” is false, and false implies anything!

False. An implication is false if the hypothesis is true meanwhile the conclusion is false. Bats have wings but are not birds. Therefore, the implication is false.

True. Both sides of the biconditional are true.

False. The left-hand side is true meanwhile the right-hand side is false.

Propositional Formulas #

In the previous section we saw 5 different logical connectives: \(\neg\) , \(\land\) , \(\lor\) , \(\rightarrow\) , and \(\leftrightarrow\) . 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 .

Parenthesis: always perform operations on expressions inside parentheses first.

Negation: apply negation to a proposition before binary connectives .

Conjunction: conjunction before disjunction

Disjunction: disjunction after conjunction, but before implication

Implication: \(\rightarrow\) after \(\land\) , \(\lor\)

Biconditional: \(\leftrightarrow\) after \(\land, \lor, \rightarrow\) .

Logical order of precendence

\(p \lor q \rightarrow \neg r\ \ \) is the same as \(\ \ (p \lor q) \rightarrow (\neg r)\)

\(p \lor \neg q \land r\ \ \) is the same as \(\ \ p \lor ( \ (\neg q)\ \land 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 \land q) \lor r\) is:

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 \land q \land r \ \lor\ \neg q \land r \rightarrow p\) . By order of precendence, this is equal to \((\ (p \land q \land r) \ \lor\ ((\neg q) \land r)\ ) \rightarrow p\) This contains several sub-formulas which we can parse:

\(\neg q \land r\)

\(p \land q\)

\((p \land q) \land r\)

\((p \land q \land r) \lor (\neg q \land r)\)

\((\ (p \land q \land r) \lor (\neg q \land r)\ ) \rightarrow 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 \((\neg q \land r)\) and \((p \land q \land r)\) . This gives the following truth table.

A large truth table

A truth table for the propositional formula \(p \land q \land r \ \lor\ \neg q \land r \rightarrow p\) .

Construct a truth table

Give a truth table for the propositional formula \(p \land r \rightarrow q \lor \neg r\)

\(p \land r \rightarrow q \lor \neg r\ \ \ \) is equal to \(\ \ \ (p \land r) \rightarrow (q \lor (\neg r)\ )\)

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 \rightarrow q\) . Then, we have:

Converse : \(q \rightarrow p\)

Inverse : \(\neg p \rightarrow \neg q\)

Contrapositive : \(\neg q \rightarrow \neg 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.

An implication is not equivalent to its converse or inverse. However, it is equivalent to its contrapositive. See Logical Equivalences and Exercises .

1.1.2. Applications #

There are many many applications of propositional logic. You will explore many more of them in other courses on logic, computer architecture, theoretical computer science, and more.

In this section we review a small sampling of applications:

Translating English to logic.

Boolean searches.

Formal specifications of software and computer systems.

Solving logic puzzles.

Translating English to Propositional Logic #

To convert an English sentence to a propositional formula, there are two significant steps. First, find the atomic propositions , the smallest clauses of the sentence which do not contain connectives. Represent each such proposition as a unique variable. Second, determine the appropriate logical connectives for those propositions.

A first logical translation

“If it is raining and I am going outside, I bring an umbrella.”

Let \(p\) be “it is raining”

Let \(q\) be “I am going outside”

Let \(r\) be “I bring an umbrella”

Choosing the corrective connectives gives the logical translation of this sentence:

A second logical translation

“The dog is large and friendly or small and boisterous”

Let \(p\) be “the dog is large”

Let \(q\) be “the dog is friendly”

Let \(r\) be “the dog is small”

Let \(t\) be “the dog is boisterous”

Note the ambiguity of the previous example. Did the English sentence assume an exlusive or ? Probably. Then, a correct translation might be \((p \land q) \oplus (r \land t)\) .

Boolean Searches #

Boolean , from mathematician George Boole, refers to a special kind of mathematics that deals with turth values: true and false . Boolean algebra is a set of rules for manipulating formulas containing variables and truth values. This is very similar to, but slightly distinct from propositional logic. We will not explore Boolean algebra in this course.

Boolean searches are about using logical connectives to help search through datasets and filter pieces of data. This includes databases and internet search engines.

Consider a search using two keywords “foo” and “bar”.

AND is used to find records which contain both “foo” and “bar”.

OR is used to find records which contain “foo” or “bar” or both.

NOT is used to exclude records which do contain a keyword.

Web Searches

Consider the key words “London”, “Beer”, “England”, and “Cider”

If we are looking for places to find beer in London, England we might search:

London AND England AND Beer

In most search engines, the AND is implicit, and we can simply search “London England Beer”.

If we are looking for places to find beer or cider in London, England we might search:

London England Beer | Cider

The AND s are implicit: “London AND England AND (Beer OR Cider)”

If we are looking for places to find beer in London, Ontario we might try to exclude entries for London, England. Searching for:

(London AND Beer) NOT England

Search engines often use the minus sign to denote NOT : “London Beer -England”

Formal Specifications #

In software, computer, and electrical engineering, the requirements of a system, software, or defice must often meet very precise specifications.

These specifications are sometimes easy to express. For example, “the circuit carries 115-125 volts”. For softare in particular, its requirements are often expressed as (ambiguous) natural language requirements. Those requirements must be translated into precise logical statements.

Logical Specification

“Mute all notifications during buisness hours when the user’s status is not available.”

Let \(p\) be “it is during business hours”.

Let \(q\) be “the user’s status is set to available”.

Let \(r\) be “mute all notifications”.

A propositional formula for this specification is:

Propositional logic can also be used to determine if the collection of all requirements for a system is consistent .

Definition (consistent)

A set of propositional formulas is consistent if there exsists at least one truth assignment so that every proposition is simultaneously true.

Notice that consistency is not the same as every formula in a set being satisfiable. The formulas must be simultaneously satisfied by the same truth assignment.

One way to determine consistency is as follows. Given a collection of propositions \(p_1,p_2,\ldots,p_n\) , the propositions are consistent if their conjunction is satisfiable. That is, the following formula has at least one truth assignment that makes it true:

To determine the consistency of a requirement set, we must first build propositional formulas for each requirement. Where the same “clause” exists in multiple requirements (recall Translating English to Propositional Logic ), we should re-use that propositional variable. Second, we must assign true or false to each variable so that every formula is simultaneously true. If no such assignment exists, the set of requirements is said to be inconsistent .

Let us consider an electronic messaging network which requires that all sent messages are certain to be received. This behaviour might be modelled as the following specifications:

Messages remain in the outbound message queue until they have been received by the recipient.

An unreceived message is either a draft or is in the outbound message queue.

Received messsages cannot be drafts.

Is this set of requirements consistent?

Let \(p\) be “message is in the outbound message queue”.

Let \(q\) be “message is received”.

Let \(r\) be “message is a draft”.

\(p \rightarrow \neg q\)

\(\neg q \rightarrow (p \lor r)\)

\(q \rightarrow \neg r\)

Since at least one truth assignment simultaneously satisfies all equations, namely \(p := F, q := T, r := F\) , this set of requirements is consistent . In the language of this problem, that means the message is received and is not a draft and is not in the outbound queue.

Solving logic puzzles #

Many puzzles are based around logical arguments and reasoning. So solve such puzzles, propositional logic is a very useful tool. The idea is to model the elements of the puzzle as propositional formula(s), and use those formulas to determine if the formula(s) are satisfiable, consistent, etc., depending on the puzzle.

Let’s see an example.

Activity (Knights and Knaves)

Suppose you are on an island with two kinds of people:

knights , who always tell the truth; and

knaves , who always lie.

You meet two people, \(A\) and \(B\) . \(A\) says “ \(B\) is a knight.” \(B\) says “the two of us are different kinds of people”.

What kind of people are \(A\) and \(B\) ?

\(A\) and \(B\) are both knaves.

Let \(p\) be “ \(A\) is a knight”. Let \(q\) be “ \(B\) is a knight”. The statement “the two of us are different kinds of people” can be represented as \((p \land \neg q) \lor (\neg p \land q)\) .

Assume \(A\) is a knight and therefore \(p\) is true. Then, their statement “ \(B\) is a knight” must be true and therefore \(q\) is true. If \(B\) is a knight, then the formula \((p \land \neg q) \lor (\neg p \land q)\) should be true. However, this formula is false if both \(p\) and \(q\) are true.

Assume \(A\) is a knave (i.e. \(\neg p\) is true). Then, their statement “ \(B\) is a knight” must be false (i.e. \(\neg q\) is true). Therefore, \(B\) is a knave and their statement should be a lie. Both \(p\) and \(q\) being false makes \((p \land \neg q) \lor (\neg p \land q)\) false, which is consistent.

1.1.3. Logical Equivalences #

Propositional logic is the foundation of more complex logical systems and of formal mathematical proofs. One particular kind of proof, an “equivalence proof”, proves that one thing is equivalent to another through a sequence of equivalences.

What is an equivalence? Well, the first quesiton to ask is: what is a tautology?

Definition (tautology)

A propositional formula that is always true, for every possible truth assignment, is a tautology .

A proposition that is not a tautology is either a contradiction or a contingency .

Definition (contradiction)

A propositional formula that is always false, for every possible truth assignment, is a contradiction .

Definition (contingency)

A propositional formula that is neither a tautology nor a contradiction is a contingency .

Logically Equivalent #

Two propositional formulas, say \(p\) and \(q\) , are logically equivalent if \(p \leftrightarrow q\) is a tautology. When this is the case, we may write \(p \iff q\) or \(p \equiv q\) .

A simple and explicit way to determine if two expressions are logically equivalent is if their two columns in a truth table are identical.

Logically equivalent truth table

There are several logical equivalences which would be good to memorize . They are similar to many laws of arithmetic. For example, we know \(x \times 0 = 0\) regardless of the value of \(x\) .

Identity Laws

Annihilation Laws

Idempotent Laws

Complementation Laws

Double negation

\(p \land T \equiv p\)

\(p \land F \equiv F\)

\(p \land p \equiv p\)

\(p \land \neg p \equiv F\)

\(\neg (\neg p) \equiv p\)

\(p \lor F \equiv p\)

\(p \lor T \equiv T\)

\(p \lor p \equiv p\)

\(p \lor \neg p \equiv T\)

There are also interesting properties of logical connectives between two or more propositional variables.

Commutativity

Associativity

Distributivity

De Morgan’s Laws

\(p \land q \equiv q \land p\)

\(p \land (q \land r) \equiv (p \land q) \land r\)

\(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)

\(p \land (p \lor q) \equiv p\)

\(\neg (p \land q) \equiv \neg p \lor \neg q\)

\(p \lor q \equiv q \lor p\)

\(p \lor (q \lor r) \equiv (p \lor q) \lor r\)

\(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)

\(p \lor (p \land q) \equiv p\)

\(\neg (p \lor q) \equiv \neg p \land \neg q\)

De Morgan’s Laws are very important. These laws explain how negation distributes over a conjunction and disjunction. In particular, it turns disjunctions into conjunctions, and vice versa.

In these laws and properties, we can replace any propositional variable with an entire propositional formula, and the law is still correct.

Variable-expression replacement

Let \(p := (\neg a \land b) \lor c\) .

These laws and properties can be used as building blocks to prove that certain expressions are logically equivalent. Before we see that process, let’s see some more interesting logical equivalences.

More logical equivalences

\((p \rightarrow q) \equiv \neg p \lor q\)

\((p \rightarrow q) \land (p \rightarrow r) \equiv p \rightarrow (q \land r)\)

\((p \rightarrow r) \land (q \rightarrow r) \equiv (p \lor q) \rightarrow r\)

\(p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)\)

\(p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q\)

\(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\)

Draw the truth table for some of the above examples to prove to yourself that the two expressions are logically equivalent.

Equivalence proof #

We can show two expressions, say \(A\) and \(B\) , are logically equivalent by constructing a sequence of logically equivalent statements \(E_i\) , beginning with \(A\) and ending with \(B\) .

A first equivalence proof

Prove that \(p \land (\neg p \lor q) \equiv p\land q\) .

Whenever we use propositional logic, we will return to equivalence proofs and truth tables. It is important that you really understand the manipulation and equivalency of propositional truth tables.

Prove that \(p \lor (p \land q) \lor (\neg p \land r) \equiv (p\land q) \lor p \lor r\) .

1.1.4. Exercises #

Basic propositions #.

Exercise 1.1

If a propositional formula has 5 variables, how many rows are needed in its truth table?

Solution to Exercise 1.1

\(\mathbf{32}\) . Each variable has two choices: true of false. 5 variables means there are \(2 \times 2 \times 2 \times 2 \times 2 = 2^5 = 32\) possible combinations of truth values.

Exercise 1.2

Express the following English sentence as a propositional formula. “If it is snowing I wear a jacket and I wear mittens.”

Solution to Exercise 1.2

\(p\) : It is snowing

\(q\) : I wear a jacket

\(r\) : I wear mitterns

Exercise 1.3

Express the following English sentence as a propositional formula. “When I am at the beach or I go swimming, I wear a swimsuit.”

Solution to Exercise 1.3

\(p\) : I am at the beach

\(q\) : I go swimming

\(r\) : I wear a swimsuit

Exercise 1.4

Classify each of the following statements as true or false.

“ \(4 = 2+2\) and \(7 < \sqrt{50}\) ”

“ \(4 = 2+2 \rightarrow 7 < \sqrt{50}\) ”

“ \(4 \neq 2 +2 \rightarrow 7 < \sqrt{50}\) ”

“ \(4 = 2 +2 \rightarrow 7 \geq \sqrt{50}\) ”

Solution to Exercise 1.4

True . Both clauses are true.

True . Both premise and conclusion are true.

True . The hypothesis is false, therefore true.

False . The premise is true, but the conclusion is false.

Exercise 1.5

Give the negation of each of the following compound statements.

“Either \(a^2 > 0\) or \(a\) is not a real number.”

“ \(x = \pm 1\) ”

“ \(x\) is a real number and \(x^2 + 1 = 0\) ”

Solution to Exercise 1.5

“ \(a^2 \leq 0\) and \(a\) is a real number”; also “ \(a = 0\) ”

“ \(x \neq 1\) and \(x \neq -1\) ”

“ \(x\) is not a real number or \(x^2 + 1 \neq 0\) ”

Exercise 1.6

Give the converse, inverse, and contrapositive of each of the following implications.

“If \(\frac{a}{b}\) and \(\frac{b}{c}\) are integers, then \(\frac{a}{c}\) is an integer.”

“Every Eulerian graph is connected”.

“ \(ab = 0 \rightarrow a = 0\) or \(b = 0\) ”.

Solution to Exercise 1.6

Converse: “If \(\frac{a}{c}\) is an integer then \(\frac{a}{b}\) and \(\frac{b}{c}\) are integers”

Inverse: “If \(\frac{a}{b}\) is not an integer or \(\frac{b}{c}\) is not an integer then \(\frac{a}{c}\) is not an integer.”

Contrapositive: “If \(\frac{a}{c}\) is not an integer then \(\frac{a}{b}\) is not an integer or \(\frac{b}{c}\) is not an integer”

Converse: “Every connected graph is Eulerian”

Inverse: “Every non-Eulerian graph is not connected.”

Contrapositive: “Every non-connected graph is not Eulerian.”

Converse: “ \(a=0\) or \(b=0\) \(\rightarrow\) \(ab=0\) ”

Inverse: “ \(ab \neq 0 \rightarrow a \neq 0\) and \(b \neq 0\) ”

Contrapositive: “ \(a \neq 0\) and \(b \neq 0 \rightarrow ab \neq 0\)

Exercise 1.7

For each of the following propositional formulas, determine which are satisfiable. If they are satisfiable, give a truth assignment which satisfies the formula.

\(p \land (\neg q \lor \neg r) \land (q \lor \neg p)\)

\(p \land (q \lor \neg p) \land (\neg q \lor \neg p) \land r\)

\((p \land q \land \neg r) \lor (p \land \neg q \land \neg r)\)

Solution to Exercise 1.7

\((p, q, r) := (T, T, F)\)

Not satisfiable

\((p,q,r) := (T, T, F)\) or \((T, F, F)\)

Applications #

Exercise 1.8

Julie and Jamie are identical twins. One of then always lies and one of them always tells the truth. Suppose you meet one of them. What 3-word question (with a yes/no answer) can you ask to determine which twin is in front of you? You do not know which twin lies.

Solution to Exercise 1.8

“Does Julie lie?”

Suppose you meet Julie and Julie tells the turth. Julie will reply “no”.

Suppose you meet Julie and Julie lies. Julie will reply “no” (i.e. “no, Jamie lies”).

Suppose you meet Jamie and Jamie tells the truth. Jamie will reply “yes”.

Suppose you meet Jamie and Jamie lies. Jamie will reply “yes” (i.e. “yes, Julie lies”).

Exercise 1.9

Define the basic clauses of each of the following statements as propositional variables. Then, express each of the following compound statements as propositional formulas. Finally, is this set of propositions consistent? If so, give a truth assignment which shows they are consistent.

The campus server does not work if the internet is off.

Students can skype during the test when the prof is distracted.

If the classroom phone does not ring then the prof is not distracted.

Students cannot skype during the test unless the internet is on.

If the classroom phone rings then the campus server works.

Solution to Exercise 1.9

\(I :=\) “internet is on”

\(C :=\) “the campus server works”

\(D :=\) “the professor is distracted”

\(S :=\) “students can Zoom during the test”

\(R :=\) “the classroom phone rings”

\(\neg I \rightarrow \neg C\)

\(D \rightarrow S\)

\(\neg R \rightarrow \neg D\)

\(S \rightarrow I\) ; \(\neg I \rightarrow \neg S\) ; “A unless B” translates logically to “A if not B”

\(R \rightarrow C\)

To check consistency, we need to see if the following conjunction is satisfiable.

This is satisfiable with: \((I, S, R, D, C) := (T, T, T, T, T)\)

Logical Equivalences #

Exercise 1.10

Show that \(p \rightarrow q\) is logically equivalent to \(\neg q \rightarrow \neg p\) .

Exercise 1.11

Prove De Morgan’s law \(\neg (p \land q) \equiv \neg p \lor \neg q\) by a truth table.

Solution to Exercise 1.11

Exercise 1.12

If \((p \land q) \lor ((\neg p) \land q \land r)\) is logically equivalent to \((p \land q \land r) \lor (p \land q)\) , show their biconditional is a tautology. If not, give a truth assignment which results in different truth values for each formula.

Exercise 1.13

Show that the following expressions are logically equivalent. Do this by (a) truth tables, and (b) logical equivalences.

Exercise 1.14

Prove that \(p \lor (p \land q) \lor (\neg p \land r) \equiv p \lor r\) .

Solution to Exercise 1.14

Exercise 1.15

Prove that \(\neg (p \lor (\neg p \land q)) \equiv \neg p \land \neg q\) .

Solution to Exercise 1.15

Let \(A\) be \(\neg p \land q\) .

Exercise 1.16

Prove that \(p \land r \land (\neg q \lor p) \equiv p\land r\) .