CS 182 Week 1

What is a Proposition

a declarative sentence that is either true or false

Which of these is not a proposition

x+4=2x

Negation

¬

Conjunction

$$\land$$

Disjunction

$$\lor$$

Implication

$$\rightarrow$$

Biconditional

↔

What is the truth value of the negation ¬p when p is True?

False

When is the conjunction p ∧ q true?

Only when both p and q are true

When is the disjunction p ∨ q false?

Only when both p and q are false

What's the difference between inclusive or (∨) and exclusive or (⊕)?

Inclusive or is true if either or both are true

Exclusive or is true only if exactly one is true

In the implication p → q, when is the statement false?

Only when p is true and q is false

In p → q, what are p and q called?

p is the hypothesis (premise), q is the conclusion (consequence)

What is the contrapositive of p → q?

¬q → ¬p

Is the converse (q → p) always equivalent to the original implication (p → q)?

No — they can have different truth values

What is the inverse of p → q?

¬p → ¬q

When is the biconditional p ↔ q true?

When p and q have the same truth value

What is the correct order of operator precedence from highest to lowest?

¬, ∧, ∨, →, ↔

In a logic circuit, what does a two-input AND gate produce?

The conjunction (p ∧ q) of its inputs

In a logic circuit, what does an inverter (NOT gate) do?

Produces the negation of its input

Tautology

a compound proposition which is always true

Contridiction

a compound proposition which is always false

Which one is a tautology

P ∨¬P

Which one is a contradiction

P ∧¬P

Two compound propositions p and q are logically equivalent if p ↔ q is a _____

Tautology

Identity Laws

p^T