Courses/Computer Science/CPSC 203/CPSC 203 Template/Lecture Template/Lecture 15

Introduction

Today we introduce the notion of Truth Tables, which are part of Booleon Logic. George Boole was interested in "mathematicizing" the rules of correct reasoning, or Aristotelian Logic. The result was Boolean Logic. Where "Propositions" are given values of True(1) or False(0). Since computers only understand the values, 1 and 0, an introduction to Boolean Logic also begins to give one an understanding of the workings of computers at a low level.

In this lecture we will:

• Revisit Venn Diagrams
• Introduce Truth Tables for Boolean Logic
• Work our way through a more complex Truth Table.

Glossary

• Proposition -- A Statement about the World.
• Boolean Logic -- A logical sytem where every proposition is assigned a truth value of 1 (True) or 0 (False), and Propositions can be combined via a small set of Boolean Logic Operators.
• Truth Table -- A "functional" view of Boolean logic, where for a given set of inputs, and a specific operator, there is a specific output.
• Boolean Logic Operators
  • AND
  • OR
  • NOT
  • XOR
  • Logical Implication; If X, Then Y; X-->Y
    • Logical Implication has some philosopical 'difficulties' associated with it (though we use the idea in comp sci all the time). see : http://en.wikipedia.org/wiki/Logical_implication

Concepts

• From Venn Diagrams to Boolean Logic

From Venn Diagrams to Boolean Logic

1. Venn Diagrams Revisited
2. The Idea of a Truth Table (as a logical function).
3. The Basic Truth Tables and Functions (on which everything else is built)

The terms of Boolean Logic were illustrated by their respective Truth Tables. See also Wikipedia: http://en.wikipedia.org/wiki/Truth_table (note that in class we used 1 where they use "T", and we used 0 where they use "F").

For more on Boolean Logic please see: http://en.wikipedia.org/wiki/Boolean_Logic

A Computer Science oriented summary of Boolean logic is at: http://en.wikipedia.org/wiki/Boolean_logic

Truth Tables

The basic Truth Tables covered in this lecture are in the document below.

Media:TruthTableExamples.doc

Summary

(to be added)

Resources

The primary resource for this lecture was:

• Ones & Zeros -- Understanding Boolean Algebra, Digital Circuits and the Logic of Sets. 1998. By John R. Gregg

Supplementary References are:

• Logic. A Very Short Introduction. 2000. By Graham Priest.
• Logic Made Easy. How to Know When Language Decieves You. 2004. By Deborah J. Bennett.
• Feynman Lectures on Computation. 1996. By Richard P. Feynman.

Homework

Good luck on the Midterm next class!

Questions

• /Lecture 15 Questions