class: big, middle

# Engineering 1020: Introduction to Programming

.title[
  .lecture[Lecture 3:]
  .title[Logic]
  
  
]

.footer[[/lecture/3/](/lecture/3/)]

---

# Previously:

## Expressions

##### **Values** and **operations** that **evaluate** to a **value**

.floatleft[
### Values

* literals ✅
* variables ✅
]

.floatleft[
### Operators

* arithmetic ✅
* function calls ✅
]

.floatleft[
### Today

## Logic
]

---

# Today:

### Propositional logic
--
 (a.k.a., propositional calculus)

???

Don't let the word "calculus" scare you!
There are many kinds of "calculus", and this one involves no differentiating or integrals.

* propositions
* operators
* expressions

### ... as [discrete math](https://www.mun.ca/university-calendar/st-johns-campus/faculty-of-science/13/9/#d.en.304337) / [philosophy](https://www.mun.ca/university-calendar/st-johns-campus/faculty-of-humanities-and-social-sciences/16/25/#d.en.307021)

???

If you go on to take a course in discrete mathematics
(e.g., 
[ECE 4110](https://www.mun.ca/university-calendar/st-johns-campus/faculty-of-engineering-and-applied-science/11/3/#d.en.303656)
or
[MATH 23020](https://www.mun.ca/university-calendar/st-johns-campus/faculty-of-science/13/9/#d.en.304337)),
you'll get into more advanced stuff like predicate logic with quantifiers.
For our purposes, though, we will stick to nice, simple propositional logic.

---

# Propositions

##### a.k.a., logical _statements_

$ P : $ it is sunny outside

$ Q : $ everyone in this room is taller than 6'

$ R : $ you passed the exam portion of Engineering 1020

##### Could be true or false!
--
  
Cannot be both true _and_ false (Law of Non-Contradiction)
--
  
Must be either true _or_ false (Law of Excluded Middle)

---

# Operators

### Apply to one or more propositions

### Given propositions, can evaluate

---

# Negation operator

## $\neg$
--
 (`not`)

$ P : $ it is sunny outside

$ \neg P : $ it is not sunny outside

### _Unary_ operator

???

A _unary_ operator operates on **one** value...
like a **unicycle** has **one** wheel!

$ Q : $ there are more than 100 students here

$ \neg Q : $
--
 there are less than **or equal to** 100 students here

???

Remember: the opposite of $ > $ isn't $ < $, it's $ \leq $!

---

# Conjunction operator

## $ \wedge $
--
 (`and`)

### _Binary_ operator

???

A binary operator has **two operands** in the same way that a
**bicycle** has **two** wheels

$ P : $ it's over 20 degrees outside

$ Q : $ it's dry outside

#### Can you go out without a coat?

$$ R = P \wedge Q $$

---

# Conjunction operator

.floatright[
##### Truth table

| $P$ | $Q$ | $P \wedge Q$ |
|:---:|:---:|:------------:|
|  T  |  T  | T
|  T  |  F  | F
|  F  |  T  | F
|  F  |  F  | F

]

## $ \wedge $ (`and`)

### _Binary_ operator

$ P : $ it's over 20 degrees outside

$ Q : $ it's dry outside

#### Can you go out without a coat?

$$ R = P \wedge Q $$

???

A binary operator has **two operands** in the same way that a
**bicycle** has **two** wheels

---

# Disjunction operator

.floatright[
##### Truth table

| $P$ | $Q$ | $P \vee Q$ |
|:---:|:---:|:------------:|
|  T  |  T  | T
|  T  |  F  | T
|  F  |  T  | T
|  F  |  F  | F

]

## $ \vee $
--
 (`or`)

???

Logical _disjunction_ is the _dual_ of conjunction:
whereas both operands to a conjunction (`and`) operator have to be true to
make the conjunction true, both operands to a disjunction (`or`) have to be
**false** to make the disjunction **false**.

$ P : $ transfer credit for MATH 1001

$ Q : $ passed 1001 with a grade $\geq$ 55

#### Have you satisfied the Eng One requirement for MATH 1001?

$$ R = P \vee Q $$

---

# Expressions

### _Statements_ and _operations_ that can be _evaluated_...

???

Logical expressions have values and operators... they are expressions!

#### Given this logical expression:

$$ P \vee \left( Q \wedge \neg R \right) $$

Evaluate with different values of $P$, $Q$ and $R$ (in Top Hat)

---

# Exclusive disjunction

.floatright[
##### Truth table

| $P$ | $Q$ | $P \vee Q$ |
|:---:|:---:|:------------:|
|  T  |  T  | F
|  T  |  F  | T
|  F  |  T  | T
|  F  |  F  | F

]

## $ \oplus $ (exclusive or)

### _Either_ this or that

$ P : $ switch at this end of the hall

$ Q : $ switch at the other end of the hall

#### Is the light on?

$$ R = P \oplus Q $$

???

The _exclusive or_ operation turns out to be very important in computing.
There are lots of things that can be either this or that, but **not both**.

---

# Truth table

### Fill out as homework:

.centered[
| $P$ | $Q$ | $\neg P$ | $P \wedge Q$ | $P \vee Q$ | $P \oplus Q$ |
|:---:|:---:|:---------:|:--------:|:-------:|
|  F  |  F  | | | | |
|  F  |  T  | | | | |
|  T  |  F  | | | | |
|  T  |  T  | | | | &nbsp;
]

---

# Operator properties

### $ \wedge $ is like multiplication

### $ \vee $ and $ \oplus $ are like addition

???

The `and` and `or` operations behave like multiplication and addition in that
the multiplicative operation (`and`) comes before the additive ones (`or`),
and also in that these operations share some common mathematical properties
with their arithmetic cousins.

#### Associative:
--
 $ (P \wedge Q) \wedge R \Leftrightarrow P \wedge (Q \wedge R) $

#### Commutative:
--
 $ P \oplus Q \Leftrightarrow Q \oplus P $

#### Distributive:
--
 $ P \wedge (Q \vee R) \Leftrightarrow P \wedge Q \vee P \wedge R $

---

# Useful expressions

???

In order for a logical expression to be useful to us, it needs to be something
that _could_ evaluate to **either true or false**.

### Contradictions and tautologies tell us nothing:

$$
R = P \wedge Q \wedge \neg P
$$

$$
R = (P \vee Q) \vee \neg (P \vee Q)
$$

???

Imagine that I said I would give you a "pass" grade if your final exam mark was
either **above 50** or else **not above 50**.
In that case, no matter how hard you work — or not! — it makes no difference
to the outcome.
That's not very motivational!

### _Contingencies_ could be true or false, depending:

$$
R = \neg P \wedge Q
$$

---

# Normal form

### What's wrong with this?

$$
x + 9 + 3x^2
$$

In one sense, nothing, but...

---

# Normal form

### What's wrong with this?

$$
x + 9 + 3x^2
$$

In one sense, nothing, but...

### Similarly:

* $ (P \vee \dots) \wedge (Q \vee \dots) \wedge \dots $ (_conjunctive normal form_)
 * $ P \wedge \dots \vee Q \wedge \dots \vee \dots $ (_disjunctive normal form_)

???

The _conjunctive normal form_ should include only ANDs of terms that
include only ORs.
The _disjunctive normal form_ should include only ORs of terms that
include only ANDs.
In both cases, negation should only be applied to specific propositions
(e.g., $ \neg P $), not expressions (e.g., $ \neg (P \vee Q) $).

---

# De Morgan's Laws

### Expression negation

???

It's often the case that we have a complex logical expression and we need to find
its opposite.

$$
\neg \left( P \wedge Q \right) = \neg P \vee \neg Q
$$

???

Say that it's safe to land an aircraft if the landing lights are on,
the gear is down and ATC has given permission to land.
What's the opposite of that logical expression?
If **any** of those conditions are not met, **it is not safe to land**.

$$
\neg \left( P \vee Q \right) = \neg P \wedge \neg Q
$$

#### More complex example:

$ \neg \left( P \wedge \neg Q \vee R \right) $
--
 $= \neg \left( (P \wedge \neg Q) \vee R \right) $
--
 $= \neg (P \wedge \neg Q) \wedge \neg R $
--
 $= (\neg P \vee \neg \neg Q) \wedge \neg R $
--
 $= (\neg P \vee Q) \wedge \neg R $

---

# Summary

### Propositions

### Operators: $ \wedge $, $ \vee $ and $ \oplus $

### Expressions

* precedence
 * normal forms
 * De Morgan's Laws

---
class: big, middle

---
class: big, middle

(here endeth the lesson)