CSS 220 Module 5 In-Class Problems
PROPOSITIONAL LOGIC: Computer Circuits
p,q,r input nodes
s,c output nodes
– XOR gate (the output of an XOR gate is on if and only if its inputs disagree with each other.) ¬ (p ? q)
– AND gate (the output of an AND gate is on if and only if both of its inputs are on)
p q
– OR gates (the value of an OR node is on if and only if at least one of its inputs is on)
p ? q
1. Identify which of the following are propositions: (circle one)
a. p: Today is Friday PROPOSITION NOT A PROPOSITION
b. p: 3 + 5 = 8 PROPOSITION NOT A PROPOSITION
c. p: Take the quiz PROPOSITION NOT A PROPOSITION
d. p: 7 < 11 PROPOSITION NOT A PROPOSITION e. p: Put your hat on PROPOSITION NOT A PROPOSITION f. p: a triangle has 4 sides PROPOSITION NOT A PROPOSITION 2. What is the difference between the truth value and the truth table (Semantics). 3. NEGATION (NOT): The negation of a proposition can be formed by inserting the word _______ as appropriate. The notation for the negation of p is p. Example: State the negation of the following propositions: a. p: Today is Saturday. p: _______________________________ b. p: All mammals respire p: _______________________________ c. p: The glass is full p: _______________________________ The truth table for a negation is: q ¬q 4. p in logic corresponds with _________ in set 5. CONJUNCTION (AND): A conjunction is formed when two propositions are connected by the word _________. Example: Let p: London is the capital of England. q: Houston is the capital of the United States. State p q: ___________________________________________________ The truth table for a conjunction is: p q p q 6. Tautology vs Contradiction Examples: 7. DISJUNCTION (OR): A disjunction is formed when propositions are joined by the word or. Example: Let p: London is the capital of England. q: Houston is the capital of the United States. State p q: ________________________________________________ The truth table for a conjunction is: p q p V q 8. Populate this truth table for ¬p ? ¬q p q ¬p ¬q ¬p ? ¬q 9. If you have n propositions, how many lines will you have in your truth table? 10. Create a truth table for (p q) r p q r (p q) (p q) (p q) r 11. IMPLICATION (If-Then): When a proposition p being true implies that another proposition q must also be true then we say that p implies q. p ? q Example: a. If you score 90% or above in this class, then you will get an A. b. My thumb will hurt if I hit it with a hammer. c. x = 2 implies x + 1 = 3. d. If Jimmy loses a tooth, then Jimmy finds a dollar. p (antecedent) q (consequence) p implies q T T T T F F F T T F F T 12. EQUIVALENCE (If-And-Only-If): Two propositions p and q are called equivalent statements if each implies the other (p if and only if q): p ? q, p?q p: we will go to the amusement park, q: we will go to the zoo p q p ? q T T T F F T F F 13. Prove that: p ? q ? ¬p ? q p q p ? q ¬ p ¬p ? q 14. Distributive Law p ? (q ? r) ? (p ? q) ? (q ? r) p q 15. De Morgans Law: ¬(p ? q) ? ¬p ¬q p q 16. Simplify: (p ? q) ? ( ¬q ? p)
Recent Comments