Course notes for CS-1382: Discrete Computational Structures. Texas Tech University, Whitacre College of Engineering. Spring 2023.

Key Topics:

- Sets, functions, sequences
- Algorithms
- Number Theory
- Introduction to logic and proofs
- Mathematical induction
- Counting and probability
- Graphs

**Logic** is the basis of all mathematical reasoning, and of all automated reasoning. To understand mathematics, we must understand what makes up a correct mathematical argument, that is, a **proof**. Many people find it surprising how important proofs are in computer science.

**Propositional logic** is a branch of mathematical logic which studies the logical relationships between propositions taken as a whole, and connected via logical connectives.

A **proposition** is a declarative sentence (a statement) that is either true or false, but not both.

We use letters to denote **propositional variables** (or sentential variables)—variables that represent propositions—just as letters are used to denote numerical variables. The conventional letters used for propositional variables are $p$, $q$, $r$, $s$, … .

The **truth value** of a proposition is **true**, denoted by T, if it is a true proposition, and the truth value of a proposition is **false**, denoted by F, if it is a false proposition.

Propositions that cannot be expressed in terms of simpler propositions are called **atomic propositions**. The area of logic that deals with propositions is called the **propositional calculus** or **propositional logic**.

New propositions, called **compound propositions**, are constructed from existing propositions using **logical operators** or **logical connectives**.

- The
**negation**of $p$, written $\neg p$, is the opposite of the truth value of $p$. - The
**conjunction**of $p$ and $q$, written $p \land q$, is true when both $p$ and $q$ are true and is false otherwise. - The
**disjunction**of $p$ and $q$, written $p \lor q$, is false when both $p$ and $q$ are false and is true otherwise. - The
**exclusive or**of $p$ and $q$, written $p \oplus q$, is true when exactly one of $p$ and $q$ are true and is false otherwise.

**Conditional statements** (also called an **implication**) are formed by combining two statements. The statement asserts that $q$ is true on the condition that $p$ holds.

- The
**conditional statement**$p \rightarrow q$ is false when $p$ is true and $q$ is false and is true otherwise.

**Converse, contrapositive, and inverse** statements can be formed from the conditional statement $p \rightarrow q$.

- The
**converse**is $q \rightarrow p$ - The
**inverse**is $\neg p \rightarrow \neg q$ - The
**contrapositive**is $\neg q \rightarrow \neg p$

A conditional statement and its contrapositive are equivalent. The converse and inverse of a conditional statement are equivalent, but neither is equivalent to the original statement.

**Biconditional statements** express that two propositions have the same truth value.

- The
**biconditional statement**$p \leftrightarrow q$ is true when $p$ and $q$ have the same truth values and is false otherwise.

Biconditionals are not always explicit in natural language. In particular, the “if and only if” construction used in biconditionals is rarely used in common language. Instead, biconditionals are often expressed using an “if, then” or an “only if” construction.

We can use the five introduced logical connectives to build up complicated compound propositions involving any number of propositional variables. We can use truth tables to determine the truth values of these compound propositions. Use a separate column to find the truth value of each compound expression that occurs in the compound proposition as it is built up.

**Example:** For the compound proposition

$(p \lor \neg q) \rightarrow (p \land q)$

the truth table is

$p$ | $q$ | $\neg q$ | $p \lor \neg q$ | $p \land q$ | $(p \lor \neg q) \rightarrow (p \land q)$ |
---|---|---|---|---|---|

T | T | F | T | T | T |

T | F | T | T | F | F |

F | T | F | F | F | T |

F | F | T | T | F | F |

Generally, parentheses are used to specify the order in which logical operators in a compound proposition are to be applied. However, to reduce the number of parenthesis, the following rules of precedence are applied.

Operator | Precedence |
---|---|

$\neg$ | 1 |

$\land$ | 2 |

$\lor$ | 3 |

$\rightarrow$ | 4 |

$\leftrightarrow$ | 5 |

A **bit** is a symbol with two possible values, `0`

(zero) and `1`

(one), and can be used to represent a truth value. Customarily, a `1`

bit represents true and a `0`

bit represents false. A variable is called a **Boolean variable** if its value is either true or false.

Computer **bit operations** correspond to the logical connectives. The notation *OR*, *AND*, and *XOR* correspond to the operators $\lor$, $\land$, and $\oplus$ respectively.

A **bit string** is a sequence of zero or more bits. The **length** of this string is the number of bits in the string. We can extend bit operations to bit strings. We define the **bitwise OR**,

Statements in mathematics and the sciences and in natural language are often imprecise or ambiguous. To make such statements precise, they can be translated into the language of logic.

Translating sentences into compound statements removes ambiguity and allows us to apply the rules of inference.

System and software engineers take requirements in natural language and produce precise and unambiguous specifications that can be used as the basis for system development.

Logical connectives are used extensively in searches of large collections of information, such as indexes of Web pages. Because these searches employ techniques from propositional logic, they are called boolean searches.

Puzzles that can be solved using logical reasoning are known as logic puzzles.

A logic circuit receives input signals as bits [0 (off) or 1 (on)] and produces output signals as bits.

Cf. Logic gates

An important step used in a mathematical argument is the replacement of a statement with another statement with the same truth value.

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a **tautology**. A compound proposition that is always false is called a **contradiction**. A compound proposition that is neither a tautology nor a contradiction is called a **contingency**.

**Examples of a tautology and a contradiction**

$p$ | $\neg p$ | $p \lor \neg p$ | $p \land \neg p$ |
---|---|---|---|

T | F | T | F |

F | T | T | F |

Compound propositions that have the same truth values in all possible cases are called **logically equivalent**.

The compound propositions $p$ and $q$ are called logically equivalent if $p \leftrightarrow q$ is a tautology (if and only if the columns giving their truth values agree).

For example, $p \rightarrow q$ and $\neg p \lor q$ are logically equivalent

$p$ | $q$ | $\neg p$ | $\neg p \lor q$ | $p \rightarrow q$ |
---|---|---|---|---|

T | T | F | T | T |

T | F | F | F | F |

F | T | T | T | T |

F | F | T | T | T |

because the truth values of $p \rightarrow q$ and $\neg p \lor q$ agree.

**Logical equivalences**

Equivalence | Name |
---|---|

$p \land \text{T} \equiv p \\ p \lor \text{T} \equiv p$ | Identity laws |

$p \lor \text{T} \equiv \text{T} \\ p \land \text{F} \equiv \text{F}$ | Domination laws |

$p \lor p \equiv p \\ p \land p \equiv p$ | Idempotent laws |

$\neg(\neg p) \equiv p$ | Double negation law |

$p \lor q \equiv q \lor p \\ p \land q \equiv q \land p$ | Commutative laws |

$(p \lor q) \lor r \equiv p \lor (q \lor r) \\ (p \land q) \land r \equiv p \land (q \land r)$ | Associative laws |

$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) \\ p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ | Distributive laws |

$\neg (p \land q) \equiv \neg p \lor \neg q \\ \neg(p \lor q) \equiv \neg p \land \neg q$ | De Morgan’s laws |

$p \lor (p \land q) \equiv p \\ p \land (p \lor q) \equiv p$ | Absorption laws |

$p \lor \neg p \equiv \text{T} \\ p \land \neg p \equiv \text{F}$ | Negation laws |

The two logical equivalences known as De Morgan’s laws are particularly important. They tell us how to negate conjunctions and how to negate disjunctions.

The negation of a disjunction is the conjunction of negations of the component propositions.

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

The negation of a conjunction is the disjunction of negations of the component propositions.

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

The extended version of De Morgan’s laws can be written concisely as

$\neg \left( \bigwedge_{j=1}^{n} p_j \right) = \bigvee_{j=1}^{n} \neg p_j
\\[16pt]
\neg \left( \bigvee_{j=1}^{n} p_j \right) = \bigwedge_{j=1}^{n} \neg p_j$

A compound proposition is **satisfiable** if there is an assignment of truth values to its variables that makes it true (that is, when it is a tautology or a contingency). When no such assignments exist, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is **unsatisfiable**.

Propositional logic cannot adequately express the meaning of all statements in mathematics and in natural language. A more powerful type of logic called **predicate logic** can be used to express the meaning of a wide range of statements in mathematics and computer science in ways that permit us to reason and explore relationships between objects.

The statement ”$x$ is greater than 3” has two parts.

- ”$x$” - subject
- “is greater than $3$” - predicate

The **predicate** refers to a property that the subject of the statement can have. We can denote the statement ”$x$ is greater than 3” by $P(x)$, where $P$ denotes the predicate and $x$ is the variable.

For example, if $P(x)$ denotes the statement ”$x > 3$”, then $P(4)$ is true because $4 > 3$. However, $P(2)$ is false because $2 \ngtr 3$.

**Quantification** expresses the extent to which a predicate is true over a range of elements. In English, the words *all*, *some*, *many*, *none*, and *few* are used in quantifications. The area of logic that deals with predicates and quantifiers is called the **predicate calculus**.

Statement | When true? | When false? |
---|---|---|

$\forall x P(x)$ | $P(x)$ is true for every $x$. | There is an $x$ for which $P(x)$ is false. |

$\exists x P(x)$ | There is an $x$ for which $P(x)$ is true. | $P(x)$ is false for every $x$. |

Many mathematical statements assert that a property is true for all values of a variable in a particular domain. Such a statement is expressed using universal quantification. The domain must always be specified when a universal quantifier is used; without it, the universal quantification of a statement is not defined.

The universal quantification of $P(x)$ is the statement ”$P(x)$ for all values of $x$ in the domain.”

The notation

$\forall x P(x)$

read “for all $x P(x)$”, denotes the universal quantification of $P(x)$.

Many mathematical statements assert that there is an element with a certain property. Such statements are expressed using existential quantification. With existential quantification, we form a proposition that is true if and only if $P(x)$ is true for at least one value of $x$ in the domain.

The existential quantification of $P(x)$ is the proposition “There exists an element $x$ in the domain such that $P(x)$.”

The notation

$\exists x P(x)$

read “for some $x P(x)$”, denotes the existential quantification of $P(x)$.

When the domain of a quantifier is finite, quantified statements can be expressed using propositional logic. When the elements of the domain are $x_1, x_2, \ldots , x_n$

$\forall x P(x) \equiv P(x_1) \land P(x_2) \land \ldots \land P(x_n)$

Negation of a universal quantifier

$\neg \forall x P(x) \equiv \exists x \neg P(x)$

Negation of an existential quantifier

$\neg \exists x Q(x) \equiv \forall x \neg Q(x)$

**Example:** Express the statement “Every student in this class has studied calculus.”

- Let $C(x)$ be the statement ”$x$ has studied calculus”
- Domain is all students in this class:
- $\forall x C(x)$

- Domain is all people:
- $\forall x (S(x) \rightarrow C(x))$
*Caution!*This statement*cannot*be expressed as $\forall x (S(x) \land C(x))$ because this statement says “all people are students and have studied class.”

**Example:** Express the statement “Some student in this class has visited Mexico.”

- Let $M(x)$ be the statement ”$x$ has visited Mexico.”
- Domain is all students in this class:
- $\exists x M(x)$

- Domain is all people:
- $\exists x (S(x) \land M(x))$
*Caution!*This statement*cannot*be expressed as $\forall x (S(x) \rightarrow M(x))$ which is true when there is someone not in the class.

A **nested quantifier** is where one quantifier is within the scope of another. The rules studied in Section 1.4 can help to use them.

The statement $\forall x \exists y (x + y = 0)$ says that for every real number $x$ there is a real number $y$ such that $x + y = 0$.

The order of the quantifiers is important, unless all the quantifiers are universal quantifiers or all are existential quantifiers.

**Example:** Let $P(x, y)$ be the statement $x + y = y + x$. The quantifications $\forall x \forall y P(x, y)$ and $\forall y \forall x P(x, y)$ have the same meaning and both are true.

**Example:** Let $Q(x, y)$ be the statement $x + y = 0$. The quantification $\exists y \forall x Q(x, y)$ is false because no matter what value of $y$ that is chosen, there is *only one* value of $x$ for which $x + y = 0$. However, the quantification $\forall x \exists y Q(x, y)$ is true because given any value of $x$, there is a value of $y$ for which $x + y = 0$.

Express the negation of a statement so that no negation precedes a quantifier by successively applying De Morgan’s laws for quantifiers. Doing so moves the negation inside all the quantifiers.

Before we study mathematical proofs, we will look at arguments that involve only compound propositions. We will define what it means for an argument involving compound propositions to be valid. Then we will introduce a collection of rules of inference in propositional logic. These rules of inference are among the most important ingredients in producing valid arguments.

After studying rules of inference in propositional logic, we will introduce rules of inference for quantified statements. Finally, we will show how rules of inference for propositions and for quantified statements can be combined.

An **argument** in propositional logic is a sequence of propositions. All but the final proposition in the argument are called **premises** and the final proposition is called the **conclusion**. An argument is **valid** if the truth of all its premises implies that the conclusion is true.

An **argument form** in propositional logic is a sequence of compound propositions involving propositional variables. An argument form is valid if no matter which particular propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true.

Using a truth table to show that an argument form is valid can be a tedious approach. Instead, we can first establish the validity of some relatively simple argument forms, called **rules of inference**. These rules of inference can be used as building blocks to construct more complicated valid argument forms.

Rule of Inference | Tautology | Name |
---|---|---|

$p \\ p \rightarrow q \\ \rule{24px}{1px} \\ \therefore q$ | $(p \land (p \rightarrow q)) \rightarrow q$ | Modus ponens |

$\neg q \\ p \rightarrow q \\ \rule{24px}{1px} \\ \therefore \neg p$ | $(\neg q \land (p \rightarrow q)) \rightarrow \neg p$ | Modus tollens |

$p \rightarrow q \\ q \rightarrow r \\ \rule{32px}{1px} \\ \therefore p \rightarrow r$ | $((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r)$ | Hypothetical syllogism |

$p \lor q \\ \neg p \\ \rule{24px}{1px} \\ \therefore q$ | $((p \lor q) \land \neg p) \rightarrow q$ | Disjunctive syllogism |

$p \\ \rule{32px}{1px} \\ \therefore p \lor q$ | $p \rightarrow (p \lor q)$ | Addition |

$p \land q \\ \rule{24px}{1px} \\ \therefore p$ | $(p \land q) \rightarrow p$ | Simplification |

$p \\ q \\ \rule{32px}{1px} \\ \therefore p \land q$ | $((p) \land (q)) \rightarrow (p \land q)$ | Conjunction |

$p \lor q \\ \neg p \lor r \\ \rule{32px}{1px} \\ \therefore q \lor r$ | $((p \lor q) \land (\neg p \lor r)) \rightarrow (q \lor r)$ | Resolution |

When there are many premises, several rules of inference are often needed to show that an argument is valid.