Logic

Why Study Logic?


	A basis for computer hardware
	A basis for computer programming
	A basis for program optimization

	A basis for specification
	A basis for verification and testing

Computing is Logic


	In a certain sense

Is all Logic Computing?


	No, but
	a lot of it can be reduced to computing.

Flavors of Logic


	Proposition Logic
	Predicate Logic
	Temporal Logic
	Modal Logics
	Programming Logics
	Fuzzy Logic

Proposition Logic


Also known as Switching Logic
Basic elements are
	0 (false)
	1 (true)
	proposition variables (take values 0 or 1)
	either
		functions (functional view)
		connectives (expression view)

Mostly we use


	the function view
	and occasionally
		the expression view

Proposition Logic Domain


	{false, true} (for purists) or {0, 1} (more readable) or {^, T } (more symmetric)

Proposition Logic Functions


	and
	or
	not
	implies
	iff (if, and only if)
	others

and


	form 1 table: x y and(x, y) 0 0 0 0 1 0 1 0 0 1 1 1

and


	form 2 table: and(x, y) 0 1 0 0 0 1 0 1

and


	rex ÒtableÓ:
		and(0, 0) => 0;
		and(0, 1) => 0;
		and(1, 0) => 0;
		and(1, 1) => 1;

and


	shorter rex rules (using sequential convention):
		and(1, 1) => 1;
		and(x, y) => 0;


	form 1 table: x y or(x, y) 0 0 0 0 1 1 1 0 1 1 1 1


	form 2 table: or(x, y) 0 1 0 0 1 1 1 1


	rex ÒtableÓ
		or(0, 0) => 0;
		or(0, 1) => 1;
		or(1, 0) => 1;
		or(1, 1) => 1;


	shorter rex rules:
		or(0, 0) => 0;
		or(x, y) => 1;

not


	form 1 table = form 2 table: x not(x) 0 1 1 0

not


	rex rules:
		not(0) => 1;
		not(1) => 0;

implies


	form 1 table: x y implies(x, y) 0 0 1 0 1 1 1 0 0 1 1 1

implies


	form 2 table: implies(x, y) 0 1 0 1 1 1 0 1

implies


	rex rules:
		implies(0, 0) => 1;
		implies(0, 1) => 1;
		implies(1, 0) => 0;
		implies(1, 1) => 1;

implies


	shorter rex rules (sequential):
		implies(1, 0) => 0;
		implies(x, y) => 1;

Concise Summary
(sequential convention applies)


		and(1, 1) => 1;
		and(x, y) => 0;
		or(0, 0) => 0;
		or(x, y) => 1;
		not(0) => 1;
		not(1) => 0;
		implies(1, 0) => 0;
		implies(x, y) => 1;

Expression Forms


	Use for greater readability of certain equalities
	Similar to ordinary discourse

Expression Forms


	Function symbols
		and: ú ^. && juxtaposition Example: x y means x ú y
		or: û + \|\|
		not: ù ! Õ superscript (overbar)
	Example: These mean the same thing:
		(a ú b) û (c ú ù d)
		ab + cdÕ
	Binding order, tightest to weakest: not, and, or

Expression Forms


	Function symbols:
		implies: ¨ Þ ƒ
		iff: ¼ = == Ç ó

What WeÕll Use


	To start, weÕll use ú û ù ¨ ¼

	When we discuss circuits, weÕll use ^. + Õ =

Logical Equivalences


	aú b = bú a Commutative
	aû b = bû a
	(a ú b) ú c = a ú (b ú c) Associative
	(a û b) û c = a û (b û c)
	(a û b) ú c = (a ú c) û (b ú c) Distributive
	(a ú b) û c = (a û c) ú (b û c)

More Logical Equivalences


	(a ú 1) = a Identity
	(a û 0) = a

	(a ú 0) = 0 Absorption
	(a û 1) = 1

More Logical Equivalences


	ù (aú b) = (ù b û ù a)
	ù (a û b) = (ù b ú ù a)
	(a û ùa b) = a û b
	(a ú (ù a û b)) = a ú b

Logical Equivalences for Implies


	(a ¨ b) = (ùa û b)
	(a ¨ b) = ù(a ú ùb)
	(0 ¨ b) = 1
	(1 ¨ b) = b
	(a ¨ 0) = ùa
	(a ¨ 1) = 1

More Logical Equivalences for Implies


	(a ¨ bc) = (a ¨ b) ú (a ¨ c)
	((a û b) ¨ c) = (a ¨ c) ú (b ¨ c)
	((a ¨ b) ú (b ¨ c)) ¨ (a ¨ c)
	(a ¨ b) = (ùb ¨ ù a)
	ù(a ¨ b) = (a úùb)

Checking Relations using
Full Enumeration or ÒTruth TableÓ method


	Make a table with each variable as a column header and a column for the expression to be checked.
	Enumerate all combinations of 0Õs and 1Õs for the variable values.
	Evaluate the expression for each combination.
	Check whether each value is 1 (you can stop early if one isnÕt.)

Example: Checking Relations using
Full Enumeration or ÒTruth TableÓ method

Checking Relations using the
Boole-Shannon Principle


	Relations hold iff they hold for any substitution of 0 and 1 for the variables (uniformly throughout the expression)
	Therefore, a relation holds if, choosing any variable V, it holds for V = 0 and for V = 1.
	But substituting 0 or 1 for a variable often yields simplifications that make the relation obvious.

Example


Verify (a ¨ b) = (ùb ¨ ùa)
Choose a as the variable.
	Substituting 0 for a:
		(0 ¨ b) = (ùb ¨ ù0)
	which simplifies to:
		1 = (ùb ¨ 1), a known equivalence
	Substituting 1 for a:
		(1 ¨ b) = (ùb ¨ ù1)
	which simplifies to:
		b = (ùb ¨ 0)

Boole and Shannon


	Boole
		Invented ÒBoolean algebraÓ (switching theory)
		(In modern mathematics, ÒBoolean algebraÓ is a more general, abstract, system)
	Shannon
		Wrote thesis on switching theory
		Invented ÒInformation theoryÓ
		Maze-solving mouse
		Wrote first chess-playing program
		Wrote paper on the mathematics of juggling

Boole and Shannon

Tautologies


	An expression that always evaluates to 1 (true) regardless of what value each variable is assigned is called a tautology.
	The property of being a tautology can be checked using:
		Truth-table construction
		Boole-Shannon Principle, recursively
	Example of a tautology checker (applet): http://www.cs.hmc.edu/~keller/javaExamples/taut/taut.html

How to Check Equivalences
http://www.cs.hmc.edu/~keller/javaExamples/taut/

How to Check Equivalences