Week 3

Question 1

What is a tautology?

Answer 1

A compound proposition which is true under all possible assignments of truth values to its prime propositions. Also called a valid proposition. Contain only T in the last column of their truth tables.

Question 2

What is a contradiction?

Answer 2

A compound proposition which is false under all possible assignments of truth values to its prime propositions. Also called an inconsistent proposition. Contain only F in the last column of their truth tables.

Question 3

What is a contingent proposition?

Answer 3

A compound proposition which is neither a tautology nor a contradiction. Has T and F in the last column of their truth tables.

Question 4

What is the difference between gates and propositional connectives?

Answer 4

Gates distinguish between input signals and the output signal, whereas formulae in propositional logic have no such notion. Inputs are known and the output is an unknown dependent.

Question 5

What is logical equivalence?

Answer 5

If and only if their equivalence is a tautology. Always true.

Question 6

What is logical implication?

Answer 6

A formula p is said to logically imply a formula q if and only if their implication is a tautology.

Question 7

What are the commutative laws?

Answer 7

p and q is logically equivalent to q and p
p or q is logically equivalent to q or p

Question 8

What are the associative laws?

Answer 8

p and (q and r) is logically equivalent to (p and q) and r
p or (q or r) is logically equivalent to (p or q) or r

Question 9

What are the distributive laws?

Answer 9

p or (q and r) is logically equivalent to (p or q) and (p or r)
p and (q or r) is logically equivalent to (p and q) or (p and r)

Question 10

What are De Morgan’s Laws?

Answer 10

¬(p ^ q) is logically equivalent to ¬p v ¬q
¬(p v q) is logically equivalent to ¬p ^ ¬q

Question 11

What is the law of negation? (involution law)

Answer 11

Two negations cancel each other out.
¬(¬p) = p

Question 12

What is the law of excluded middle and the law of contradiction known as collectively?

Answer 12

Complement laws.

Question 13

What is the law of implication?
What is the contrapositive law?
What is the law of equivalence?

Answer 13

p implies q is logically equivalent to ¬p v q;
p implies q is logically equivalent to ¬q implies ¬p;
(p equivalent to q) is logically equivalent to (p implies q) ^ (q implies p)

Question 14

What are the laws of idempotence?

Answer 14

p v p is logically equivalent to p
p ^ p is logically equivalent to p

Question 15

What are the laws of simplification?

Answer 15

p ^ true is logically equivalent to p
p v true is logically equivalent to true
p ^ false is logically equivalent to false
p v false is logically equivalent to p
p v (p ^ q) is logically equivalent to p
p ^ (p v q) is logically equivalent to p

Question 16

What is the rule of substitution?

Answer 16

We can always substitute a logically equivalent formula for a subformula embedded in a much larger formula without changing it’s meaning.

Question 17

What is the rule of transistivity?

Answer 17

If p is logically equivalent to q and q is logically equivalent to r. Then p is logically equivalent to r.

Question 18

What is the law of excluded middle?

Answer 18

(¬p or p) is logically equivalent to True

Question 19

What is the law of contradiction?

Answer 19

p ^ ¬p is logically equivalent to False

Question 20

Checks for valid argument.

Answer 20

if when all parameters are true the conclusion is also true at all times, valid argument.
If the conjunction of the parameters implies the conclusion is a tautology, valid argument.

Question 20

What are the inference rules?

Answer 20

A series of simpler valid arguments that are known to be valid. Enable the elimination or the introduction of a logical connective. They consist of premises above the line and a conclusion below the line. The line signifies logical implication as in an inference rule the conjunction of the premises will logically imply the conclusion with a tautology.

Question 21

Conjunction Introduction? (conjunction)

Answer 21

if p
and q
then p ^ q

Question 22

Conjunction Elimination? (simplification)

Answer 22

if p ^ q
then p

Question 23

Disjunction Introduction? (addition)

Answer 23

if p
then p v q

Question 24

Disjunction Elimination? (disjunctive syllogism)

Answer 24

If p v q
and ¬p
then q

Question 25

Modus ponens?

Answer 25

If p ⇒ q
And p
then q

Question 26

Modus tollens?

Answer 26

If p ⇒ q
and ¬q
then ¬p

Question 27

Double negation?

Answer 27

If ¬¬p
Then p

Question 28

Transisitivity of equivalence?

Answer 28

If p ⇔ q
and q ⇔ r
then p ⇔ r

Question 29

Laws of equivalence?

Answer 29

If p ⇔ q
then p ⇒ q
then q ⇒ p

Question 30

Deduction theorem?

Answer 30

If p, … , r, s |– t
Then p, …, r|– s ⇒ t

Question 31

Reductio ad absurdum?

Answer 31

p, …, q, r |– s
p, …, q, r |– ¬s
p, …, q |– ¬r

Question 32

Hypothetical Syllogism

Answer 32

(p ⇒ q) ∧ (q ⇒ r) ≡ p ⇒ r