# CSS 220 Module 5 In-Class Problems

CSS 220 Module 5 In-Class Problems

Just \$7 Welcome

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

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)