Discrete Math

The negation is a statement that has the opposite truth value. The negation of a proposition \(p\), denoted by \(\neg p\), is the proposition "It is not the case , that \(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."

"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\), is True when both \(p\) and \(q\) are True, False otherwise.

"She studied hard or she is extremely bright."

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

"Take either 2 Advil or 2 Tylenol."

Let \(p\) and \(q\) be propositions. The exclusive disjunction of \(p\) and \(q\) (also known as xor ), denoted in mathematics by \(p \oplus q\), is True when exactly one of \(p\) and \(q\) are True, False otherwise.

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

Let \(p\) and \(q\) be propositions. The implication of \(p\) and \(q\), denoted in mathematics by \(p \implies q\), is short hand for the statement "if p then q". As such, implication requires \(q\) to be True whenever \(p\) is True. If \(p\) is not True, then \(q\) can be any value. In other words, implication fails (is False) when \(p\) is True and \(q\) is False. Note, this is different from "p if and only if q".

We can form new compound propositions from the implication, \(p \implies q\). They are

The truth tables for these new propositions are shown in the table.

In the section proposition equivalences we will explain why the truth table shows that the conditional \(p \implies q\) and contrapositive \( \neg q \implies \neg p\) are logically equivalent, and why the converse \(q \implies p\) and inverse \( \neg p \implies \neg q\) are logically equivalent.

We illustrate these ideas with an example.

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

Let \(p\) and \(q\) be propositions. The bi-implication of \(p\) and \(q\), denoted in mathematics by \(p \iff q\), is short hand for the statement "p if and only if q". As such, bi-implication requires \(q\) to be True only when \(p\) is True. In other words, bi-implication fails (is False) when \(p\) is True and \(q\) is False or when \(p\) is False and \(q\) is True.

It is important to contrast implication with bi-implication. Consider the implication 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.

As a bi-implication it 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 where you can earn an A in the class by getting a 100 on the final, but if you do not get a 100 on the final you will not earn an A.

To find truth values of compound propositions, it is useful to break them up into smaller parts.

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. You should also consider breaking complex propositions into smaller pieces.

Logical Translations

A long time ago philosophers discovered we could put our thoughts into symbols and more easily follow lines of reasoning. This was an important step in the eventual development of our modern technological society and our use of digital computers. Before computers can work, we have to put our thoughts into them.

BUT, the English language is difficult and we use many different phrases to represent the same logical statements. Translating statements from English sentences to symbols and back is a skill that needs lots of practice.

Two important logical equivalences are De Morgan’s Law. These describe how we "distribute" the negation across the and and or operators.

A proposition is a tautology if its truth value is always True.

A proposition is a contradiction if its truth value is always False.

A proposition that is neither a tautology nor a contradiction is said to be a contingency .

A predicate is a statement involving a variable.

Predicates are denoted as \(P(x)\) or \(Q(x,y)\) where \(P\) and \(Q\) represent the statements and \(x\) and \(y\) represent the possible values. After a value is assigned to each variable, the predicate becomes a proposition which has a truth value.

Consider the statements

Each of these statements considers a proposition over an entire population or set, called the domain, and quantifies how many elements (or people) in the set satisfy the proposition. To represent this idea, we use two main quantifiers, the universal quantifier and the existential quantifier .

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+0=0\), and \(1+0=0+1=1\), but, as in decimal addition, in binary \(1+1=2\), which in binary will be a sum of \(0\) and a carry of \(1\) to the next significant column on the left. Thinking then of adding a specific column of two binary digits, say \(A\) and \(B\), involves as input the digits \(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.