Truth table proofs

Truth tables are used to show all possible values that a given logical expression might take.

Examples

Definition of AND

The following gives the definition of the logical AND operation.

A	B	A ∧ B
false	false	false
false	true	false
true	false	false
true	true	true

Proof of one of De Morgan's laws

A truth table can also be used to prove a logical identity. The following proves De Morgan's law that ¬ (A ∧ B) is equivalent to (¬ A) ∨ (¬ B). Notice that the truth values for these (the last two columns in the table) are always the same.

A	B	A ∧ B	¬ (A ∧ B)	(¬ A) ∨ (¬ B)
false	false	false	true	true
false	true	false	true	true
true	false	false	true	true
true	true	true	false	false

Disproof of a logical fallacy

Truth tables can also be used to disprove a logical fallacy. For example, one fallacy is to assume the converse of an implication holds. If you know that (A → B) is true, and you know that B is true, the fallacy would be to then conclude that A must also be true. Note that the statement - "if an animal is a mammal then it is also a vertebrate" - is true. If we have an animal that is a vertebrate (for example, a dog), it would be a fallacy to now conclude that the animal must also be a mammal.

We will show that this is a logical fallacy - regardless of the statements A and B, just because we know A → B is true, we should not in general assume the converse is also true. First we remind you that (A → B) is equivalent to ¬ A ∨ B. What we want to look at is the claim: ((A → B) ∧ B) → A. If this expression is always true, then we could rely on the converse to always be used. Let us first simplify the expression. It is equivalent to ((¬ A ∨ B) ∧ B) → A. This is equivalent to ¬ ((¬ A ∨ B) ∧ B) ∨ A. We can keep this formula in mind as we evaluate it's truth value for each possible value of A and B.

Consider this truth table.

A	B	A → B	((A → B) ∧ B) → A
false	false	true	true
false	true	true	false
true	false	false	true
true	true	true	true

In the second row, we see that the last column is false. This is where we should expect to see a problem - the place where B is true, but we should not be able to conclude that A must also be true. We have shown that we cannot always apply the converse.

Assignment 1

You will be assigned a logical identity to prove and a logical fallacy to disprove. For each, you are permitted and encouraged to simplify the expressions to make it easier to evaluate the expressions. You then write a truth table for each part - proving the logical identity, and disproving the logical fallacy. Include a similar amount of explanation as above.

Unless otherwise indicated by your instructor, you can submit your solutions in whatever format you like - word document, pictures of it worked out on paper, physical paper, OneNote notebook link. If you send a link to an electronic document, make sure it is set so it is shared with your instructor.

Pass rating check Each part must be correct to earn a 1/1 on that part. The total for the problems would be 2 points. You need to both hand in your work, and also check in with the help lab to demonstrate your proofs. You can use your work that you hand in, and should talk the GA through the proof. The GA will make note if you are not able to do this, or if it seems you do not fully understand the process. Your written work should follow the rules of writing good proofs - Proofs

Note - the shared spreadsheet that GAs use for submitting information to Jeff Kinne's courses is this link, which should work only for the current term's GAs.

Assignment 2

Problem 3.5 at the end of Chapter 3 from Building Blocks for Theoretical Computer Science. If you have a program that produces truth tables, you may use it for this problem for part (a).

Problem 3.8.

Problem 3.11.

Show how you can use a NOR gate to construct AND, OR, NOT, XOR gates.