Boolean Logic

Aidan Delaney

aidan@ontologyengineering.org | @aidandelaney

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?

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

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