In Class:
Implication, Inverse, Converse, and Contrapositive

Math Foundations of Computing, F23

Inverse, Converse, Contrapositive

If I hydrate then I’ll learn better

• Translate to a logical expression (define any propositions you need).
• Using logical symbols, form the:
  1. Inverse
  2. Converse
  3. Contrapositive
• Translate each of these three back into English.

Logical Equivalence

Consider the following two statements:

• \(\lnot (P \rightarrow Q)\)
• \(P \land \lnot Q\).

Are these two statements logically equivalent? What are two strategies we could use to find out?

DMOI 3.1.6

Boolean Circuits

A Boolean circuit is an abstract description of the fundamental operation building block of computation: performing an operation on one or more bits.

flowchart LR
  
  M(0) --> N[NOT]
  N --> Q{1}

flowchart LR
  

  A(1) --> C[OR]
  B(0) --> C
  C --> F{1}

  E(1) --> G[AND]
  H(0) --> G
  G --> I{0}

We can string Boolean circuits together to make more complicated ones:

flowchart LR
  A(0) --> C[NOT]
  B(1) --> D[OR]
  C --> D
  D --> E[NOT]
  E --> F{?}

Boolean Circuits

Can you draw a simpler Boolean circuit that has the same output in all cases?

flowchart LR
  A(p) --> C[NOT]
  B(q) --> D[OR]
  C --> D
  D --> E[NOT]
  E --> F{OUTPUT}

Fancy Vocab Time: Isomorphism

Informally, two sets of things are isomorphic if you can translate back and forth between them without losing “structure.”

In our case:

• For every logical expression there is a unique corresponding Boolean circuit.
• For every Boolean circuit there is a unique logical expression.
• I can simplify Boolean circuits using a three-step process:
  1. Translate to logical expression.
  2. Simplify logical expression using logical equivalences.
  3. Translate back to Boolean expression.

We’ll formally define isomorphisms once we’ve studied sets a bit more.