CSS 220 Module 5 In-Class Problems
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 Morgan’s Law: ¬(p ∨ q) ≡ ¬p ¬q
| p | q | |||
16. Simplify: (p ∧ q) ∨ ( ¬q ∧ p)
