Propositional Logic 3 Flashcards

Covers how tautologies & contradictions can be used to and the algebraic laws of propositional logic

1
Q

metavariables

A

expressions in meta-languages that represent arbitrary formulae

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

when can a formula be neither a tautology or contradiction

A

when there is a combination of T and F in the output column

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

in the WFF p ⇒ q, p is the p____?

A

premise

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

in the WFF p ==> q, q is the c_______?

A

conclusion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

the implication symbol is ______ associative

A

right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

is the equivalence symbol associative?

A

yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

is the conjunction symbol associative?

A

yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

is the implication symbol associative?

A

NO

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

describe the law of replication

A

p ⇒ q therefore i’m either not p or i’m q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

describe the contrapositive in words

A

the negation of the conclusion implies the negation of the premises

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

each of the algebraic laws are in themselves a …?

A

tautology

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what is short-circuiting

A

skipping the evaluation of the second part of a boolean expression in a conditional statement if the first part is enough to determine the result

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

benefit of short-circuiting

A

optimises and can speed up the execution of code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

disadvantage of short-circuiting

A

can cause unexpected problem if the right hand side of the short-circuited expression has a side effect that is important (but not executed)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

name of this algebraic law:

p ∨ q ⇔ q ∨ p

A

commutativity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

name of this algebraic law:

p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)

A

distributivity

17
Q

name of this algebraic law:

⌐(p ∧ q) ⇔ ⌐p ∨ ⌐q

A

de Morgan’s Law

18
Q

name of this algebraic law:

⌐(⌐p) ⇔ p

A

double negation

19
Q

name of this algebraic law:

p ∧ true ⇔ p

20
Q

name of this algebraic law:

p ∨ true ⇔ true

21
Q

name of this algebraic law:

p ∨ false ⇔ p

A

contradiction

22
Q

name of this algebraic law:

p ∧ false ⇔ false

A

contradiction

23
Q

name of this algebraic law:

p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r

A

associativity

24
Q

name of this algebraic law:

p ∨ p ⇔ p

A

idempotence

25
idempotence law with conjunction
p ∧ p ⇔ p
26
idempotence law with disjunction
p ∨ p ⇔ p
27
name of this algebraic law: p ∨ ⌐p ⇔ true
law of the excluded middle
28
name of this algebraic law: p ∧ ⌐p ⇔ false
law of the excluded middle
29
name of this algebraic law: p ∧ (p ∨ q) ⇔ p
absorption law
30
example of the absorption law
p ∨ (p ∧ q) ⇔ p
31
name of this algebraic law: (p ⇒ q) ⇔ (⌐p ∨ q)
implication law
32
name of this algebraic law: (p ⇒ q) ⇔ (⌐q ⇒ ⌐p)
contrapositive law
33
name of this algebraic law: (p ⇔ q) ⇔ (p ⇒ q) ∧ (q ⇒ p)
equivalence law
34
imagine there are 4 shapes: a white circle, a white square, a black circle and a black square. let B be the proposition that the shape is black and C be the proposition that the shape is a circle. for which shape(s) is B ⇒ C false?
the black square
35
why use inference rules rather than truth tables to prove the validity of a conclusion with premises containing many variables?
the size of truth tables grows exponentially
36
if p ⇔ q is true under all interpretations, the propositions p and q are said to be...?
logically equivalent
37
contradictions are said to be...?
unsatisfiable
38