Y82WN

Discrete Mathematics Lecture 2 — Logic

University course in discrete mathematics for computer science and engineering.

Sep 2, 2021
Downloads ‐ HTML, Markdown, PDF
All Files ‐ Post Files

Propositional Logic

Def: A statement is a (in some language syntactically correct) formulation which is either true or false.

Some examples are given below.

  1. \(2 + 2 = 5\) - self evidently false
  2. There exists an infinite amount of prime numbers - true but not obvious
  3. The moon is a golfball
  4. Smoking causes lung-cancer - scientific statement
  5. This statement is false - nonsense, logical trap

All of the above are grammatically correct formulations. But, whether or not they are statements can be discussed.

Examples 1 and 2 are pure mathematical statements. All mathematical statements stem from a set of well-defined statements which everyone just assumes to be true and does not question. These have a special word, they are called axiomes. The cases 1 and 2 are based on the Peano axiomes which define a way on how to do basic arithmetic. They go through super basic rules such as there exists a number \(1\), and if you add \(1\) to \(1\) you get 2. And that you can continue doing this indefinately and so on. If these are to be followed, cases 1 and 2 are statements. We can also conclude that case 1 is self evidently false. Case 2 is not as self evident, it is a bit more complicated but there is a mathematical proof which makes case 2 true.

Case 3 and 4 are different from 1 and 2, they are not pure mathematical statements, they are called scientific statements. What this entails is that, they are not true statements. This is because you cannot with 100% certainty say that either are true or false. All you can do with these is collect evidence for or against case 3 for example. Although, in normal life, you would call these two statements, but if you were as precise as possible whens speaking, they are not true statements. That is because there may always come evidence in the future proving otherwise. Case 4 is slightly different because you can interpret it differently. If you were to interpret it as all people that ever smoke would get lung cancer. Then it would be false because there are people who have smoked their entire life and never gotten lung cancer. The more common interpretation is that you are statistically more likely to get lung cancer if you smoke. Which can be statistically researched and therefore get either a true or false for the statement.

Case 5 cannot be a statement because it is constructed in a way that makes it nonsense. If it were to be true it says that itself is false which would not make it true. It is simply nonsense.

Note: If we were to say that “The moon is a golfball” : Hypothesis 1. We can now collect evidence for this evidence. Somebody could say that golfballs have craters : Hypothesis 2 (evidence). Therefore somebody could say that a golfball has craters and the moon does as well therefore the moon is a golfball. The argument itself is logically valid. Regardless of the hypothesises.

Combinations of Propositions

Def: A Boolean variable is variable which can only have the value of either true or false, respectively 1 and 0.

Def: A statement is denoted as \(P\) and is also a Boolean value with value either 1 or 0.

Foundational Logical Operations

\(p\) \(q\) \(p \lor q\) \(p \land q\) \(\neg p\)
Logical OR Logical AND Logical NOT
0 0 0 0 1
1 0 1 0 0
0 1 1 0 1
1 1 1 1 0

Non-foundational Operations

\(p\) \(q\) \(p \Rightarrow q\) \(p \oplus q\) \(p \Leftrightarrow q\) \(p \barwedge q\)
Implication XOR (Exclusive OR) Equivalence NAND (NOT AND, \(\neg (p \land q)\))
0 0 1 0 1 1
1 0 0 1 0 1
0 1 1 1 0 1
1 1 1 0 1 0

Note: All combinations of Boolean variables, both foundational and non-foundational, can be built from NAND operations. This may come in handy when dealing with logical gates in computer science. Because in essence you only need NAND logical gates.

Non-foundational from foundational

All the non-foundational operations can also be built from from the foundational operations.

Ex: Logical implication can be derived from the foundational operations.

\[ (p \Rightarrow q) \Leftrightarrow (\neg p \lor q) \Leftrightarrow \neg(p \land \neg q) \]

This also illustrates a general law which is that.

\[ \neg (a \land b) \Leftrightarrow \neg a \lor \neg b \]

This is intuitive because because for not \(a\) and \(b\) then both have to be false.

Tautology

Def: A Boolean formula is said to be a tautologi regardless of the truth values of the inputted Boolean values.

You have a formula which you build up from a set of Boolean variables, which again will always be true completely independent of what you input.

The most dumb example of this is.

\[ p \lor \neg p \]

A more interesting example of this are logically valid arguments.

Def: A logically valid argument is a tautology of the following form.

You have a set of hypothesis which are all true regardless of what you input to them.

\[ H_1 \land H_2 \land \text{...} \land H_n \Rightarrow S \]

Which means that you cannot create the following scenario.

\[ 1 \Rightarrow 0 \]

If the logical argument is valid.

Mathematics in general consist of these logical arguments, which again are impossible to disprove, if and only if they are logically valid as defined above.

Logical Arguments

Ex: Which of the following are valid arguments?

Argument one.

\[ \begin{align*} & b \Rightarrow a \\ & c \Rightarrow \neg b \lor \neg a \\ & d \Rightarrow b \\ & d \\ \hline \neg & c \end{align*} \]

Argument two.

\[ \begin{align*} & a \Rightarrow b \\ & c \Rightarrow \neg b \lor \neg a \\ & d \Rightarrow b \\ & d \\ \hline \neg & c \end{align*} \]

What you would try to do here is try to prove that the argument is valid or you find out that it is not valid. The common way to do this is a so called proof through contradiction.

Standard Strategy: To try to get a contradiction proof for the argument.

The question is now what does a proof of contradiction entail. What you have is a set of hypothesis that imply a conclusion.

\[ H \Rightarrow S \]

What you do now is assume that the conclusion is false \(\neg S\). Then you try that one of the hypothesis are false \(\neg H\). This works the same way as if the hypothesis is true then the conclusion also becomes true, just the other way around. Which makes it easier to prove that the statement / argument is either true or false. You can also express this relationship with.

\[ (H \Rightarrow S) \Leftrightarrow (\neg S \Rightarrow \neg H) \]

The part to the right of the logical equivalence is the contra positive formulation of the implication.

Proof through Contradiction

Example 1

We can now try to use this method in evaluating the first argument as seen again below, but now with a hypothesis number to the right, and lastly \(\neg c\) being the conclusion.

\(b \Rightarrow a\) H1
\(c \Rightarrow \neg b \lor \neg a\) H2
\(d \Rightarrow b\) H3
\(d\) H4
\(\neg c\) S

The first step is to assume that the conclusion is false, that is to say \(\neg c = 0\). Which is logically equivalent to \(c = 1\).

\[ \neg c = 0 \Leftrightarrow c = 1 \]

The second step is to check whether or not any of the hypothesis H1, H2, H3 and H4 become false. If they do then we have proved that the argument is valid, otherwise not.

For H2 to be true, then \(\neg b \lor \neg a\) be true. Therefore either \(\neg b = 1 \Leftrightarrow b = 0\) or \(\neg a = 1 \Leftrightarrow a = 0\). At least one of \(a\) and \(b\) must be 0 that is.

For H4 to be true, then \(d=1\).

But now according to H3 \(b=1\).

And now according to H1 \(a=1\).

We now have come to the conclusion that \(a=1\), \(b=1\) and \(d=1\). Which would go against H2 because it requires at least one of \(a\) and \(b\) to be \(0\).

This is our contradiction, now that we have found it we know that assuming that the conclusion was false \(\neg c = 0\) is not true. Therefore \(\neg c = 1\) in other words the conclusion is true and the argument is valid.

This is the proof through contradiction method.

Example 2

\(a \Rightarrow b\) H1
\(c \Rightarrow \neg b \lor \neg a\) H2
\(d \Rightarrow b\) H3
\(d\) H4
\(\neg c\) S

We can now do the same thing with the other argument.

Assume \(\neg c = 0 \Rightarrow c = 1\).

H2 forces \((b = 0) \lor (a = 0)\).

H4 forces \(d=1\).

H3 forces \(b=1\).

H1 will be true if \(a = 0\) because \(0 \Rightarrow 1\).

Therefore with the appointments.

\[ a = 0, b = 1, c = 1, d = 1 \]

All the hypothesis become true but the conclusion becomes false. We cannot get a contradiction. Assuming the conclusion is false all hypothesis can become true. Therefore the argument is invalid.

Boolean Satisfiability

Def: A boolean formula \(F\) is said to be satisfiable if \(\neg F\) is not a tautology.

What this means is that if \(\neg F\) were a tautology it would always be false. To be satisfiable means that you can input at least one way to input variables into the formula in which case it becomes true.

A tautology again means that you always get a \(1\) regardless of what you input, to be satisfiable means that there is at least one arrangement of inputs where it becomes true. That it works to make it true.

Connecting Logic and Set Theory

You can connect logic and set theory through predicates. A predicate is a Boolean statement in which its formulation depends on one or more inputs / variables.

If you are going to write down a predicate, then you need to spesify a universe first.

Ex.1: Lets spesify our universe \(u = \mathbb{Q}\). Now we can make our predicate \(P(x) : x^2 < 7\).

We cannot say that our predicate is either true or false, what we need to do first is define what \(x\) is.

\[ \begin{align*} P(3) & \text{ is false} \\ P\left(\frac{3}{2}\right) & \text{ is true} \end{align*} \]

These are predicates, not functions, do not confuse them.

Ex.2: \(u=\mathbb{Q}\), \(P(x,y) : x > y\).

\[ \begin{align*} P(3, 2) & \text{ is true} \\ P(2, 3) & \text{ is false} \end{align*} \]

The Connection

\[ u = \text{universe} \]

We have sets in \(u\) and we can make predicates about \(u\).

We can have a set \(A\) and a predicate \(P(x)\). A can be defined in the following way to connect both logic and sets.

\[ A = \{x \in u \mid P(x) \text{ is true} \} \]

If we now introduce another \(B\) with a predicate \(Q(x)\).

\[ B = \{x \in u \mid Q(x) \text{ is true} \} \]

Then we can actually find a paralell beween set operations such as union, intersection and complement and logical operations.

\[ A \cup B \]

has a logical equivalence of.

\[ P(x) \lor Q(x) \]

and

\[ A \cap B \]

has a logical equivalence of.

\[ P(x) \land Q(x) \]

and

\[ A^c \]

has a logical equivalence of.

\[ \neg P(x) \]

We can continue on this, as seen in the table below.

Operation Set Theory Logic
Union \(A \cup B\) \(P(x) \lor Q(x)\)
Intersection \(A \cap B\) \(P(x) \land Q(x)\)
Complement \(A^c\) \(\neg P(x)\)
Subset \(A \subseteq B\) \(P(x) \Rightarrow Q(x)\)
Symmetric Difference \(A \Delta B\) \(P(x) \oplus Q(x)\)
Similarity \(A = B\) \(P(x) \Leftrightarrow Q(x)\)
\((A \cap B)^c\) \(P(x) \text{ NAND } Q(x)\)

Quantifiers

Quantifier Reads Like
\(\forall\) “for all”
\(\exists\) “there exists”

The purpose of these is to be able to create new types of predicates without needing to type them out.

Ex.1: \(u=\mathbb{Q}\), \(P(x) : x^2 < 7\).

We can now do.

\(\forall x P(x)\)

This reads like “for all \(x\) (from the universe) the predicate \(P(x)\) is true”. This statement is false but nevertheless it illustrates how to use \(\forall\) to form statements.

\(\exists x P(x)\)

And this reads like “there exists at least one \(x\) for which \(P(x)\) is true”. Which is true because there exists values from \(\mathbb{q}\) which squared is less than 7.

References