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	(¬ A)	B	(¬ B)	A ∧ B	¬ (A ∧ B)	(¬ A) ∨ (¬ B)
false	true	false	true	false	true	true
false	true	true	false	false	true	true
true	false	false	true	false	true	true
true	false	true	false	true	false	false

Disproof of a logical fallacy

Truth tables can also be used to disprove a logical fallacy. For example, one fallacy (affirming the consequent) 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 → B) ∧ B) → A
false	false	true	false	true
false	true	true	true	false
true	false	false	false	true
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.

Assignment 2

The following are additional problems related to truth tables and logic. Some are from Mathematics for Computer Science (which we abbreviate MCS).

1. MCS Problem 3.5. This gives you more practice examining proofs for mistakes. If you have a program that produces truth tables, you may use it for this problem for part (a).
2. MCS Problem 3.8. This gives you some practice working with logical formulae and reasoning about them rather than just using truth tables for proofs (since the truth table for this problem would be unwieldy).
3. MCS Problem 3.11. This gives you practice examining logical formulae to look for examples / counter-examples of truth assignments. Note that a logical expression is valid if it is always true. For each response for this question, you should give a reason why the answer you give is correct; you don't need it to be a formal proof.
4. Ungraded - Show how you can use a NOR gate to construct AND, OR, NOT, XOR gates. For each you need to give the expression using just NOR gates, and you need to give a justification for why this works. Your justification could be a truth table or just reasoning about the expressions. It does not need to be a formal proof, but does need to convince the reader that your claims are true. Note - you may use the values true and false in your constructions. If you do a construction for NOT, you can use that in the later parts, without fully expanding it.

Pass rating check You should be able to get 90% of the individual parts completely correct, and should correctly identify any parts that you are not sure your answer is correct.

Grading notes Notes on things people have missed on these problems...

• MCS Problem 3.5
  • For part a, you need to give the truth tables asked for (* and ** from the problem) and indicate where they are different.
  • For part b, you need to identify where specifically Sam's argument is wrong. It is not enough to argue that his conclusion is wrong.
• MCS Problem 3.8
  • You need to explain why the variables are forced to their values, in both of your cases. Many people gave a reasonable argument only for one of the cases.
  • Many people did not explain why the variables are forced in either case. Just giving the 2 truth assignments is not enough.
• MCS Problem 3.11
  • You need to give some reason for why you give the answer you give. Some did not explain why the valid one(s) is(are) valid.
• NOR gate constructions
  • If you found the solution online (e.g., on wikipedia) then you should put a comment in canvas to give a link to what you used. If you did use something and don't cite it, that is plagiarism, that will waste all of our time, and your grade will be impacted (maybe worse).