Discrete Math - The MKD Remix

"I am not an astronaut."

The negation of a proposition \(p\), denoted in mathematics by \(\neg p\) and read as "not \(p\)", is the proposition "It is not the case that \(p\)". The proposition \(\neg p\) has the opposite truth value to \(p.\)
Other textbooks and sources may use \(\overline{p}\) or \(\sim \! p\) to represent \(\neg p.\)

For example, the negation of the proposition "Today is Friday." would be "It is not the case that today is Friday." or more succinctly "Today is not Friday."
For a proposition \(p,\) exactly one of \(p\) and \(\neg p\) is True and exactly one is False. Two propositions can be contrary (that is, they could not both be True) without being negations of each other: As an example, both of the propositions "Today is Friday." and "Today is Saturday." could be False, so "Today is Saturday." is not the negation of "Today is Friday."

Notice that the two propositions \(p\) and \(\neg (\neg p)\) must always have the same truth value (You can see this by inserting a column for \(\neg (\neg p)\) in the truth table shown earlier in this subsection.)

"I am a rock and I am an island."

Let \(p\) and \(q\) be propositions. The conjunction of \(p\) and \(q\), denoted in mathematics by \(p \land q\) and read as "\(p\) and \(q\)", is True when both \(p\) and \(q\) are True and is False otherwise.

Notice that the two propositions \(p \land q\) and \(q \land p\) always have the same truth value.

"They studied hard or they are extremely bright."

Let \(p\) and \(q\) be propositions. The disjunction of \(p\) and \(q\), denoted in mathematics by \(p \lor q\) and read as "\(p\) or \(q\)", is True when at least one of \(p\) and \(q\) are True and is False otherwise.

Notice that the two propositions \(p \lor q\) and \(q \lor p\) always have the same truth value.

" If you get a 100 on the final exam, then you earn an A in the class."

Let \(p\) and \(q\) be propositions. The conditional statement \(p \rightarrow q\), read as "if p then q ", " p implies q ", or, more formally, "the conditional with hypothesis p and conclusion q ", is the proposition that is False when p is True and q is False, and True otherwise. The conditional statement \(p \rightarrow q\) is also called "the implication \(p \rightarrow q\)".
The conditional \(p \rightarrow q\) can also be denoted by \(p \Rightarrow q\) or \(p \implies q.\) In addition, there are many other ways to express the conditional \(p \rightarrow q\) in English, two of which are " p only if q " and " q if p ".

"It is raining outside if and only if it is a cloudy day."

Let \(p\) and \(q\) be propositions. The biconditional \(p \leftrightarrow q\), read as " p if and only if q ", is the proposition that is True when p and q have the same truth value, and False otherwise. The biconditional is also called "the bi-implication". Note that \(p \leftrightarrow q\) can also be denoted by \(p \Leftrightarrow q\) or \(p \iff q.\)

You can use a truth table to show that two propositions \(p \leftrightarrow q\) and \(q \leftrightarrow p\) always have the same truth value.

It is important to contrast the conditional with the biconditional. Consider the conditional example "If you get a 100 on the final exam, then you earn an A in the class." This means that when you get a 100 on the final you also get an A in the class. The conditional represents a one-way contract: You earn an A in the class if you get a 100 on the final exam. There is nothing said about the result (the grade you earn in the class) if you do NOT meet the condition (get a 100 on the final exam).

As a biconditional the example would say "You get a 100 on the final exam if and only if you earn an A in the class." This becomes a two-way contract: You earn an A in the class if you get a 100 on the final, but you do not earn an A in the class if you do not get a 100 on the final.

The negation, disjunction, conjunction, conditional, and biconditional are the most commonly-used logical operators for forming compound propostions and will be the ones used throughout the rest of this chapter. However, there are at least three others you should know about.

A well-formed formula (or wff for short) is a string of symbols that represents a compound propsition.

Here is a recursive definition of wff:

The definition of wff allows you or, even better, a computer to analyze any string of symbols to determine whether the string of symbols is a wff. For example, \((p \land q \lor r)\) isn’t a wff but both \((p \land (q \lor r))\) and \(((p \land q) \lor r)\) are wffs. You could write code to implement an algorithm to validate a string as a wff.

It can be shown that every compound proposition can be represented by at least one wff. However, a wff may be difficult to read quickly if it contains many parentheses. As an example, it is not easy to read \(( (p \rightarrow q) \lor ( (\neg r) \land (s \leftrightarrow t) ) )\). For this reason, we can introduce operator precedence rules that allow us to eliminate some of the parentheses.

To evaluate a compound proposition, we start by evaluating

This allows us to drop some parentheses from a wff that represents a compound proposition.

For example, the compound proposition \(\neg p \lor q \land r \rightarrow s\) represents the same proposition as the wff \((((\neg p) \lor (q \land r)) \rightarrow s)\). At least some of the parentheses must be used if you want to represent a different proposition such as \((\neg p \lor q) \land (r \rightarrow s)\).

To compute the truth values of a longer compound proposition or wff by hand, it can be useful to break up the proposition or wff into the smaller propositions or wffs that it was built from.

When creating your own truth table it is crucial to be systematic about ensuring you have all possible truth values for each of the simple propositions. Each simple proposition has two possible truth values, so the number of rows in the table should be \(2^n\) where \(n\) is the number of propositions (Do you recall why the number of rows must be \(2^n\)?) You should also consider breaking complex propositions into smaller pieces.

A proposition is a tautology if its truth value is always True. That is, a tautology is True for every possible interpretation of its propositional variables.

A proposition is called satisfiable if there is at least one interpretation for which the proposition is True.

A proposition is unsatisfiable if there is no interpretation for which the proposition is True.

A proposition is a contradiction if its truth value is always False. That is, a contradiction is False for every possible interpretation of its propositional variables. This is just another way of saying that it is unsatisfiable.

A proposition that is neither a tautology nor a contradiction is said to be a contingency since its truth value can be either True or False, contingent on the truth value assigned to its propositional variables.

The two compound propositions in the previous example are so important that they have their own names,

Two important logical equivalences are De Morgan’s Law. These describe how to "distribute" the \(\neg\) operator across the \(\land\) and \(\lor\) operators.

De Morgan’s Laws can be verified by creating truth tables for \(\neg (p \land q) \leftrightarrow \neg p \lor \neg q\) and \(\neg (p \lor q) \leftrightarrow \neg p \land \neg q\) to show that these propositions are True for every interpretation of \(p\) and \(q\).

Here is a collection of additional equivalencies of compound propositions. Each of these can be verified by constructing a truth table to show that the biconditional of the left-hand side and the right-hand side of the logical equivalence is true for all interpretations of the propositional variables.

Double Negation: \[ p \equiv \neg (\neg p) \]

Commutative laws: \[ p \lor q \equiv q \lor p \] \[ p \land q \equiv q \land p \]

Associative laws: \[ p \lor (q \lor r) \equiv (p \lor q) \lor r \] \[ p \land (q \land r) \equiv (p \land q) \land r \]

Distributive 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) \]

It is traditional to focus on negation \(\neg\), conjunction \(\land\), and disjunction \(\lor\) as the three primary logical operations. This is because any compound proposition can be rewritten in terms of these three operations and the propositional variables present in the original compound proposition.

One way to justify this is by using an expression in disjunctive normal form (DNF), which is a disjunction of one or more conjunctions, where only one of the conjunctions can be true for any interpretation of the propositional variables. This description should become clearer after reading the following example.

In some applications of propositional logic, it is more useful to find a logically equivalent expression for a given proposition that is written as a conjunction of several disjunctions. This conjunctive normal form (CNF) can be constructed as shown in the following example.

Here is a website that allows you to build the DNF and CNF for a given propositional function.

A set \(S\) of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only operators that are members of \(S.\)

The importance of the NAND and NOR in electronic circuits arises from the following theorem.

A predicate is a statement that includes one or more variables such that when values are assigned to the variables the predicate becomes a proposition.

Predicates are denoted as \(P(x)\) or \(Q(x,y)\) where \(P\) and \(Q\) represent the statements and \(x\) and \(y\) are variables. After a value is assigned to each variable, the predicate becomes a proposition which has a truth value. That is, we "evaluate" a predicate by substituting inputs into the variables and get a proposition as the output.

Consider the statements

Each of these statements considers a proposition over an entire population or set, called the domain, and describes whether at least one element, or all of the elements in the domain satisfy the proposition. There are two commonly-used quantifiers, the universal quantifier and the existential quantifier .
The domain is also called the domain of discourse or the universe of discourse.

The Universal Quantifier, \(\forall,\) represents the statement "for all", "for every", "for each". When it comes before a statement, it means that statement is true for all values in the domain.

The Existential Quantifier, \(\exists,\) represents the statement "there exists", "for some", "at least one". When it comes before a statement, it means the statement is true for at least one value in the domain.

Recall the previous example statements:

Let \(P(x)\) be the predicate "\(x^2 \geq 0\)". Then we write the statement as \(\forall x P(x)\), where the domain is the set of all integers. This quantified statement will be true since anytime you square a nonzero integer it is positive and \(0^2=0\).

Let \(Q(s)\) be the predicate "student \(s\) has a birthday in July". Then we write the statement as \(\exists s Q(s)\), where the domain is the set of all students in the class. This statement will be true as long as at least one student in the class has a birthday in July. It will be false, otherwise.

It is important to consider the negation of a quantified expression.

This is a universally quantified statement and can be expressed as \(\forall x P(x)\) where \(P(x)\) is the statement "\(x\) has taken Programming Fundamentals" and the domain consists of all the students in this class. The negation of the statement would be "It is not true that every student in this has taken Programming Fundamentals." Equivalently,

This is an existentially quantified statement expressed as \(\exists x \neg P(x)\).

This demonstrates that the negation of a universally quantified statement is an existential statement. In symbols, we have \(\neg \forall x P(x)\equiv \exists x \neg P(x)\).

Similarly, the negation of an existential statement is a universal statement. \(\neg \exists x P(x) \equiv \forall x \neg P(x)\).

The predicate of a quantified statement could be a compound statement. For instance,

This is written as \(\exists x (B(x) \land F(x))\) where \(B(x)\) is the proposition "\(x\) is big." and \(F(x)\) is the proposition "\(x\) is fluffy." and the domain is dogs. Negating this statement would give

\(\neg \exists x (B(x) \land F(x)) \equiv \forall x \neg (B(x) \land F(x)) \equiv \forall x (\neg B(x) \lor \neg F(x))\)

In words,

There are times it will take more than one quantifier to express a statement.

This statement contains both a universal and an existential quantifier. \(\forall x \exists y S(x,y)\) where \(x\) and \(y\) are integers and \(S(x,y)\) is the proposition \(x+y=0\). This statement means, if you have any integer \(x\) (for instance \(x=5\)) then you can find an integer \(y\) (for instance \(y=-5\)) such that \(x+y=0\).

The order of the quantifiers matters. \(\exists x \forall y S(x,y)\) would be

Note that in this statement you find an integer \(x\) so that when you add any integer \(y\) to it you always get 0.

The first statement, for all integers \(x\), there exists an integer \(y\) such that \(x+y=0\), is true. For any integer \(x\) you could choose \(y=-x\) and \(x+y=x+(-x)=0\). While the second statement, there exists an integer \(x\), such that for all integers \(y\), \(x+y=0\), is false.

To negate nested quantifiers, repeatedly apply De Morgan’s Laws of negating a quantifier and a predicate.

Namely, \(\neg \forall x P(x) \equiv \exists x \neg P(x)\) and \(\neg \exists x P(x) \equiv \forall x \neg P(x)\).

A bitwise operation is a Boolean operation that operates on the individual bits (\(0s\), or \(1s\)) of the operand(s) and are summarized

We summarize the truth tables for the bitwise boolean operators.

Logic circuits are important in designing the arithmetic and logic units of a computer processor.

Consider the problem of adding two \(8\)-bit numbers in binary. In binary, \((0)_2 + (0)_2 = (0)_2\) and \((0)_2 + (1)_2 = (1)_2 + (0)_2 = (1)_2\), but as in decimal addition, \((1)_2 + (1)_2 = (10)_2\) requires a carry, that is, the "sum bit" is \(0\) with a "carry bit" of \(1\) to the next significant column on the left.
Note: The bits are enclosed in parentheses which are followed by the subscript \(_2\) to emphasize that binary notation, not decimal notation, is being used. This notation is covered in much more detail in the Number Bases chapter.

Thinking then of adding a specific column of two binary digits, say \(A\) and \(B\), involves as input the bits \(A, B\) and the carry in from the previous column say \(C_{in}\). The output will be the sum \(S\) and the carry out to the next column, say \(C_{out}\). These are the basic components of what is called a binary adder.

The logic table for binary addition based on the digital inputs \(A, B, C_{in}\), and digital outputs \(S\) and \(C_{out}\) is summarized in the table.

It can be shown that the logic for the outputs \(S\), and \(C_{out}\) is given by the following propositions \[ C_{out}=(A\land B)\lor \left(B\land C_{in}\right)\lor \left(A\land C_{in}\right)\] \[S=\left(\sim A\land \sim B\land C_{in}\right)\lor \left(\sim A\land B\land \sim C_{in}\right)\lor \left(A\land \sim B\land \sim C_{in}\right)\lor \left(A\land B\land C_{in}\right) \]

Implementing these logical outputs based on the inputs \((A,B, C_{in})\), is through the use of electronic circuits called logic gates.

The basic logic gates, are the Inverter or Not gate, the And gate, the Or gate and the Xor gate. The graphical representation for each is shown below.

We end this section by first analyzing logic circuits to give their outputs in terms of their input variables, and then, constructing logic circuits based on logical statements.

In the next two examples, we design logic circuits based on logical propositions. The idea is to work backward using order of operations from the right to the left.