01 Logic

What is a proposition?

A logical statement that is either true or false.

Example: x + 1 = 1 is not a proposition; it is a predicate.

What is negation (¬ / NOT), and how does its truth table work?

Negation flips the truth value.A truth table shows all possible inputs and their corresponding outputs.

A	¬A
T	F
F	T

Every teacher owns a car. What is ¬P?

One teacher does not own a car.

P: 8 ≤ 12. What is ¬P?

8 > 12.

It is snowing. What is ¬P?

It is not snowing.

7 is an odd number. What is ¬Q?

7 is not an odd number.

What is a conjunction (∧ / AND), and when is it true?

A conjunction combines 2 logical statements. It is true only if both statements are true; all other cases are false.

A	B	A ∧ B
T	T	T
T	F	F
F	T	F
F	F	F

P: 4 + 4 = 8. Q: 7 is a prime number. Is P ∧ Q true or false?

True, because P is true and Q is true.

What is an inclusive OR / disjunction (∨), and when is it true?

For two logical statements A and B, A ∨ B is false only if both are false. All other cases are true.

A	B	A ∨ B
T	T	T
T	F	T
F	T	T
F	F	F

A = False. What is ¬A ∨ A?

True.
¬A ∨ A is a tautology → it is always true.

Complete the truth table for ¬(A ∨ B) and ¬A ∧ ¬B. What do you notice?

A	B	A ∨ B	¬A	¬B	¬(A ∨ B)	¬A ∧ ¬B
T	T	T	F	F	F	F
T	F	T	F	T	F	F
F	T	T	T	F	F	F
F	F	F	T	T	T	T

¬(A ∨ B) ⇔ ¬A ∧ ¬B ✅

The last two columns are identical, so the statements are equivalent.

A job requires experience with C++ OR Java.
P: experience with C++
Q: experience with Java

What logical expression represents the requirement?

P ∨ Q — P or Q or both.

What is an exclusive disjunction / XOR (⊕), and when is it true?

P ⊕ Q is true when exactly one is true, but not both.

Example: When you buy a car, you get either €2,500 cashback OR €2,500 worth of accessories, but not both.

P	Q	P ⊕ Q
T	T	F
T	F	T
F	T	T
F	F	F

What do integer, prime, and binary mean?

• Integer: a whole number; no decimals/fractions.

• Prime: a whole number > 1 divisible only by 1 and itself. Examples: 2, 3, 5, 7, 11, 13, ...

• Binary: a number system that uses only 0 and 1.

How do you write decimal numbers 0–10 in binary?

What is an implication (P → Q), and when is it false?

P → Q means “If P, then Q” — like a promise. t is false only when P is true and Q is false → the promise was broken.

P	Q	P → Q
T	T	T
T	F	F
F	T	T
F	F	T

Example:
P: If you study → hypothesis (promise)
Q: You’ll get candy → conclusion (consequence)

What is the converse of P → Q, and when is it false?

• The converse switches P and Q:

• P → Q becomes Q → P

• Q → P is false only when Q is true and P is false.

Example:
Original: If you study (P), you’ll get candy (Q).
Converse: If you get candy (Q), then you studied (P).

P	Q	Q → P
T	T	T
T	F	T
F	T	F
F	F	T

Let P: a = b

and Q: a² = b².

For a = 3 and b = −3,

determine the truth values of P → Q and its converse Q → P.

Implication P → Q:
If a = b, then a² = b².
3 = −3 → F
9 = 9 → T
F → T = True

Converse Q → P:
If a² = b², then a = b.
9 = 9 → T
3 = −3 → F
T → F = False

P: If you tidy your room, Q: you get ice cream. Is the promise broken if you do NOT tidy your room but still get ice cream? What if you do NOT tidy and do NOT get ice cream?

Case 1: P = F, Q = T → F → T = True → promise not broken.

Case 2: P = F, Q = F → F → F = True → promise not broken.

Nothing was promised if you didn’t tidy your room, so the promise cannot be broken.

For the implication P → Q, what are the inverse and contrapositive?

Inverse: ¬P → ¬Q
Contrapositive: ¬Q → ¬P

P: You receive an “A”.

Q: You are awarded a scholarship.

Original: If P, then Q. State the converse, inverse, and contrapositive.

Converse (Q → P):
If you are awarded a scholarship, then you received an “A”.

Inverse (¬P → ¬Q):
If you don’t receive an “A”, then you won’t be awarded a scholarship.

Contrapositive (¬Q → ¬P):
If you aren’t awarded a scholarship, then you didn’t receive an “A”.

For an implication P → Q, which condition is sufficient and which is necessary? What do “enough,” “required,” “both,” and “neither” mean?

For P → Q:

• P is sufficient for Q → P is enough for Q.

• Q is necessary for P → P can’t happen without Q.

Terms:

• Enough = sufficient

• Required = necessary

• Both = necessary and sufficient

• Neither = neither necessary nor sufficient

Example: A = “I become rich”; B = “I’ll be happy.”
A → B → A is sufficient for B; B is necessary for A.

What is a biconditional statement (P ↔ Q), and when is it true?

P ↔ Q means “P if and only if Q”:

• P → Q and Q → P

• It is true when P and Q have the same truth value.

Example: An integer x is divisible by 6 if and only if it is divisible by 2 and 3 → True.

What does logical equivalence mean? Give an example.

Two statements are logically equivalent when they always have the same truth value.

Example:
P → Q ≡ ¬Q → ¬P

An implication is logically equivalent to its contrapositive.

What is a propositional formula?

An expression constructed from:

• propositional variables such as P, Q, ...

• logical operators such as ¬, ∧, ∨, →, ↔

How can you prove that two propositional formulas A and B are logically equivalent using a biconditional? What are a tautology and a contradiction?

• If every row is true → tautology → A and B are logically equivalent.

• If every row is false → contradiction.

Example: P → Q ≡ ¬Q → ¬P, so
(P → Q) ↔ (¬Q → ¬P) is a tautology.

What are the 10 important logical equivalence laws? (Slide 22)

1. Commutative:
   P ∨ Q ≡ Q ∨ P
   P ∧ Q ≡ Q ∧ P

2. Associative:
   (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
   (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)

3. Distributive:
   P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
   P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

4. Idempotent:
   P ∨ P ≡ P
   P ∧ P ≡ P

5. Involution:
   ¬¬P ≡ P

6. De Morgan’s laws:
   ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
   ¬(P ∧ Q) ≡ ¬P ∨ ¬Q

7. Implication / contrapositive:
   P → Q ≡ ¬Q → ¬P

8. Implication as disjunction:
   P → Q ≡ ¬P ∨ Q

9. Negation of implication:
   ¬(P → Q) ≡ P ∧ ¬Q

10. Biconditional:
    P ↔ Q ≡ (P → Q) ∧ (Q → P)

What is a predicate P(x), and when does it become a proposition?

A predicate P(x) is a statement whose truth depends on the value of a variable.

Once x is given a specific value, the statement becomes true or false → a proposition.

Example: P(x): x > 10

What is a truth set? For P(x): x > 10, what is its truth set?

The truth set contains every value of x that makes P(x) true.

For P(x): x > 10:
Tₚ = {11, 12, 13, ...}

P(x): “x is even.” What is its truth set over the integers ℤ?

Tₚ = {0, ±2, ±4, ...} ⊂ ℤ

What do quantifiers tell us? What do ∀, ∃, ∃!, and ∄ mean?

Quantifiers tell us how many allowed x-values make P(x) true.

• ∀ = “for every” → universal quantifier

• ∃ = “there exists / at least one” → existential quantifier

• ∃! = “there exists exactly ONE”

• ∄ = “there exists NO x” → truth set is empty

P(x): “x is even,” with domain X = {1, 2, 3, 4, 5, 6}. Which values satisfy P(x)?

{2, 4, 6}

Is this statement true or false? ∃! M ∈ ℝ ∀ p ∈ P: p < M

There exists exactly ONE real number \(M\) such that every prime number \(p\) is smaller than \(M\).

False. There is no real number bigger than every prime number.

P = Prime number

How do you negate a quantified statement?

Two things change:

1. Switch the quantifier:
   ∀ → ∃
   ∃ → ∀

2. Negate the predicate:
   P(x) → ¬P(x)

So:
¬∀x P(x) ≡ ∃x ¬P(x)
“NOT every” = “at least one NOT”

Negate: ∀x ∈ X ∃y ∈ Y : P(x,y)

∃x ∈ X ∀y ∈ Y : ¬P(x,y)

Switch each quantifier and negate the predicate.

Negate: “Every student has passed at least one exam.”

There is at least one student who has not passed any exams.

Original:
∀s ∈ S ∃e ∈ E : P(s,e)

Negation:
∃s ∈ S ∀e ∈ E : ¬P(s,e)

When can you switch the order of quantifiers?

When the quantifiers are identical, you can switch their order:

∀x ∀y = ∀y ∀x

∃x ∃y = ∃y ∃x

So every–every and exists–exists can be switched.