Difference between revisions of "Truth table proofs"
(→Assignment 2) |
(→Assignment 2) |
||
| Line 69: | Line 69: | ||
# 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). | # 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). | ||
# 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. | # 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. | ||
| − | # 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. | + | # 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. |
'''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. | '''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. | ||
Revision as of 00:40, 26 September 2022
Truth tables are used to show all possible values that a given logical expression might take.
Contents
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
The following are additional problems related to truth tables and logic. Some are from Building Blocks for Theoretical Computer Science (which we abbreviate MCS).
- 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).
- 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).
- 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.
- 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.
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.
