Sudoku Puzzle https://www.websudoku.com/?level=1

Solve using set theory

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

- 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

- What is the difference between the truth value and the truth table (Semantics).
- 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

- p in logic corresponds with
*_*in set - 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

- Tautology vs Contradiction Examples:
- 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

- Populate this truth table for ¬p ∨ ¬q

p

q

¬p

¬q

¬p ∨ ¬q

- If you have n propositions, how many lines will you have in your truth table?
- Create a truth table for (p q) r

p

q

r

(p q)

(p q)

(p q) r

- 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

- 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

- Prove that:

p ⇒ q ≡ ¬p ∨ q

p

q

p ⇒ q

¬ p

¬p ∨ q

- Distributive Law p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (q ∧ r)

p

q

- De Morgan’s Law: ¬(p ∨ q) ≡ ¬p ¬q

p

q

- Simplify: (p ∧ q) ∨ ( ¬q ∧ p)