Logic and Proofing

Question 1

The negation of p → q

Answer 1

p ⋀ ~q

Question 2

p → q ≡ ?

(Material Implication)

Answer 2

p → q ≡ ~ p ⋁ q

(Material Implication)

Question 3

~ (p → q) ≡ ?

Answer 3

~ (p → q) ≡ p ⋀ ~q

Question 4

p ↔ q ≡ ?

Answer 4

p ↔ q ≡ (p → q) ⋀ (q → p)

Question 5

p → q

What is:
Contrapositive, Converse, Inverse

Answer 5

Conditional 𝑝 → 𝑞
Contrapositive ∼ 𝑞 →∼ 𝑝
Converse 𝑞 → 𝑝
Inverse ∼ 𝑝 →∼ 𝑞

Question 6

Order of operations for logical statements?

Answer 6

First: ~
Equal second: ⋀ and ⋁, use parentheses to specify. If no parentheses given, work from left to right.
Equal third: → ← ↔ Use parentheses to specify. If no parentheses given, work from left to right.

Question 7

What does same parity imply?

Answer 7

if x & y have the same parity, they are both even or both odd.

Question 8

3 Methods for checking validity?

Answer 8

1. Truth Table
2. Rules of inference & Laws of Logical Equivalence
3. Assuming the argument is invalid

Note: Rules of Inference only work for VALID arguments.

Question 9

Process for checking validity via ‘Assuming the argument is invalid’

Answer 9

Assume all premises are true and the conclusion is false.
If there are truth values that allow for this, then the argument is invalid.
However, if this leads to a contradiction, then the argument is valid.

Remember, we set the supposed conclusion to false first.

Question 10

Negate:
∀m ∈ D, Q(m)

Answer 10

∃ m ∈ D | ~Q(m)

Question 11

Negate:
∃ m ∈ D | ~Q(m)

Answer 11

∀m ∈ D, Q(m)

Question 12

Negate:
∃ m ∈ D | ∀n ∈ E, ~Q(m,n)

Answer 12

∀m ∈ D, ∃n ∈ E | Q(m,n)

Question 13

Negate:
∀m ∈ D, ∃n ∈ E | Q(m,n)

Answer 13

∃ m ∈ D | ∀n ∈ E, ~Q(m,n)

Question 14

Method: Proof by Contradiction?

Answer 14

1. Assume that the statement is false
2. Show that this leads logically to a contradiction.
3. Conclude the statement is true.

Question 15

Contrapositive:
∀m ∈ D, P(m) → Q(m)

Answer 15

∀m ∈ D, ~Q(m) → ~P(m)