Boolean Logic, and a bit more besides

Aidan Delaney

aidan@ontologyengineering.org | @aidandelaney

About Me

  • Academic for over a decade (PhD in Logic(ish) i.e. CS involving logic).
  • Researcher in Visual Languages and Visual Reasoning.
  • Shipped code in Haskell, C, Java, Perl, Python, C++, JavaScript & others.
  • Outgoing CAS Regional Co-ordinator for East Sussex & Kent.
  • Director of an Eastbourne not-for-profit TechResort

Introduction

Formalisation

Reasons for

Rhetoric

Everyone who is sane can do Logic. No lunatics are fit to serve on a jury. None of your sons can do Logic. Therefore, none of your sons are fit to serve on a jury. -- Charles L. Dodgson, Symbolic Logic, 1896

\[ (\forall x\; Sane(x) \rightarrow Logical(x)) \wedge\\ (\forall x\; \neg Sane(x) \rightarrow \neg Juror(x)) \wedge\\ (\forall x\; Sons(x) \rightarrow Logical(x)) \rightarrow\\ (\forall x\; \neg Sons(x) \wedge Logical(x)) \]

Note we're not modelling the relationship between you and your sons here.

Limits of Formalisation

Any sufficiently expressive self-referential system is either inconsistent or incomplete -- Paraphrasing Kurt Gödel

Boolean Logic

Examples

Boolean logic (a.k.a. Propositional logic) is restrictive in what it can express.

It is useful because

if(a < b || (a >= b && c == d)) ...

can be simplified to

if(a < b || c == d)

Syntax of Boolean Logic

\(\top\) and \(\bot\) Denote true and false
\(P\) and \(Q\) Denote propositions
\(P\wedge Q\) Denoting conjunction
\(P\vee Q\) Denoting disjunction
\(\neg P\) Denoting negation

Other people define different syntax

Alternative Syntax

\(1\) and \(0\) Denote true and false
\(P\) and \(Q\) Denote propositions
\(P.Q\) Denoting conjunction
\(P + Q\) Denoting disjunction
\(\overline{P}\) Denoting negation

let's call these terms.

Forming Sentences

All terms are sentences.

If \(\alpha\) and \(\beta\) are sentences then \((\alpha \wedge \beta)\) is a sentence.

Similarly \((\alpha \vee \beta)\) is a sentence.

Semantics of Boolean Logic

A sentence in Boolean logic evaluates to either true or false.

'And' diagrammatically

'Or' diagrammatically

'Not' diagrammatically?

Your turn.

Misunderstandings

Mostly stem from applying linguistic interpretation of a sentence rather than an logical interpretation.

'and'

Aidan bought a motorbike and went to work.

The English sentence has issues

  • temporal implicature
  • causality

Which is why we formalise in the first place.

'or'

Eat your carrots or your peas.
  • Exclusive or versus inclusive or.

Logical or is inclusive. Exclusive or more precisely translates as

Either eat your carrots or your peas.

implication

Some people add implication to their set of Boolean connectives.

\(P\rightarrow Q\) read as "if P then Q"

This shorthand for \((\neg P \vee Q)\), it causes significant confusion.

As a diagram

Game Time

If a card has a vowel on one side, then it has an even number on the other side.

Reasoning Rules

In light of this game modus tollens and modus ponens make more sense.

modus ponens modus tollens
\(\frac{\matrix{P\rightarrow Q, P}}{Q}\) \(\frac{\matrix{P\rightarrow Q, \neg Q}}{\neg P}\)

First Order Logic

Syllogism

All Ducks are Mortal

Aristotle is a Duck

Therefore, Aristotle is Mortal

Another Game

1 2 3 4 5
All
No
Some
Some Not

Quantifier \(P\) are \(Q\).

Self-test

Misunderstandings

'Some'

After the pub, some of us went to the club.

Issues

  • linguistic implicature that at least 2 but not all.

'All'

Scene: 14 blue circles, 2 blue squares, 3 red squares.

Q: Are all the circles blue?

A: No, there are two blue squares.

-- Inhelder and Piaget (1959)

'All'

Scene: 5 apples and 3 pigs eating 1 apple each.

Q: Every pig is eating an apple . . . Does this picture go with the story?

A: No. Those two apples have no pig.

-- Philip and Takahashi (1991)

'All'

Scene: 5 cars and 4 garages, each occupied by 1 of the cars.

Q: All the cars are in the garages.

A: Yes.

-- Donaldson and Lloyd (1974)

'All'

Scene: 3 cats holding a balloon, and 1 mouse holding an umbrella.

Q: Is every cat holding a balloon?

A: No.

-- Philip and Verrips (1994)

Conclusion

  • Boolean Logic is a useful system for demonstrating computational thinking.
  • A visual approach to Boolean Logic is useful.
  • The visual approach extends to First-order logic (and Second-order).
  • Learners make consistent types of mistakes -- knowing these allow us to target interventions.

Thank you