logic notes Flashcards Preview

logic > logic notes > Flashcards

Flashcards in logic notes Deck (199):
1

¬

not, negation

2

not

¬

3

And, conjunction

4

and

5

conjunction

6

negation

¬

7

or, disjunction

8

or

9

disjunction

10

if ... then, implication

11

if ... then

12

implication

13

if and only if, iff, equivalence

14

if and only if

15

equivalence

16

not premise p

_
p

17

_
p

not premise p

18

He has an Ace if he does not have a Knight or a Spade

¬(k ∨ s) → a
or
(¬k ∨ s) → a

19

exclusive disjunction

20

exclusive disjunction

21

define the Language of propositional logic

Let P be a set of proposition letters and let p ∈ P
ϕ ::= p | ¬ϕ | (ϕ ∧ ϕ) | (ϕ ∨ ϕ) | (ϕ → ϕ) | (ϕ ↔ ϕ)

22

syllogism

a logical argument where a quantified statement of a specific form (the conclusion) is inferred from two other quantified statements (the premises).

23

4 corners of Square of Opposition


All A are B
........No A are B

Some A are B
........Not all A are B

24

syllogistic Q N V

Q: quantifier
N: noun
V: verb

25

well known tautologies

Double Negation
De Morgan laws
Distribution laws

26

Double Negation

¬¬ϕ ↔ ϕ

27

De Morgan laws

¬(ϕ ∨ ψ) ↔ (¬ϕ ∧ ¬ψ)

¬(ϕ ∧ ψ) ↔ (¬ϕ ∨ ¬ψ)

28

Distribution laws

(ϕ ∧ (ψ ∨ χ)) ↔ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ))

(ϕ ∨ (ψ ∧ χ)) ↔ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ))

29

aristotals inference pattern as human language

Q=Quantifier
NP = noun phrase
CN = Common Noun
VP = verb phrase (Q + CN)

Q1 CN1 VP1
Q2 CN2 VP2
__________
Q3 CN3 VP3

30

syllogistic form

2 predicates and a conclusion

31

middle term

the missing class that is in the predicates but not the conclusion

For all A then B
For all B then C
____________
for all A then C

the middle term is B

32

"is an element of" operation
member of operation

33

a is an element of a set A

a ∈ A

34

a ∈ A

a is an element of a set A

35

a is not an element of a set A

a ∉ A

36

a ∉ A

a is not an element of a set A

37

the set of those x that have the property described by ϕ.

{x | ϕ(x)}

38

the set of all those x in U for which ϕ holds

{x ∈ U | ϕ(x)}

39

a set of elements sharing multiple properties ϕ1, . . . , ϕn

{x | ϕ1(x), . . . , ϕn(x)}

40

(Bill Clinton, Hillary Clinton) ∈ A
, (Hillary Clinton,Bill Clinton) ∉ A

A = {(x, y) | x is in the list of presidents of the US , y is married to x}

41

A ∩ B

intersection
{x | x ∈ A and x ∈ B}

42

{x | x ∈ A and x ∈ B}

A ∩ B
intersection

43

intersection

A ∩ B
{x | x ∈ A and x ∈ B}

44

A ∪ B

union
{x | x ∈ A or x ∈ B}

45

{x | x ∈ A or x ∈ B}

union
A ∪ B

46

union

A ∪ B
{x | x ∈ A or x ∈ B}

47

A \ B (set)

difference
{x | x ∈ A and x ∉ B}

48

{x | x ∈ A and x ∉ B}

difference
A \ B

49

difference (set)

A \ B
{x | x ∈ A and x ∉ B}

50

complement (set)

_
A

{x ∈ U | x ∉ A}

51

{x ∈ U | x ∉ A}

complement
_
A

52

_
A

complement
{x ∈ U | x ∉ A}

53

_
A ∩ B

A \ B

54

_
_
A

A

55

de morgans law (in set operations)

____     _     _
A ∪ B = A ∩ B
____     _     _
A ∩ B = A ∪ B

56

distributive equations (in set operations)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

57

definition of a union of 2 sets (using negatives)

              _     _    ____
              _     _    _     _
A ∪ B = A ∪ B = A ∩ B

58

number of predicate forms in a sylogism

3

59

venn diagram inference steps

1) draw skeleton
2) Universal step - cross out All and No
3) Existential step - ◦ in Some and Not all (where not removed by Universal step)
4) Check conclustion, if existential and universal are where they are meant to be then valid, otherwise a counter argument can exist

60

A syllogism with only universal premises and an existential conclusion is
always invalid, because ..

the situation with all classes empty is a counterexample

61

predicate logic is the most important system in logic because ...

it is a universal language for talking about structure

62

a,b,c (predicate) are ..

constant / proper names

63

x,y,z (predicate) are ...

variable / indefinite names

64

A,B,C (predicate) are ...

predicate letters

65

1-place predicate

a predicate with 1 argument , e.g. intransitive verbs (walk) common nouns (boy)

66

2-place predicate

a predicate with 2 arguments - transitive verbs (see)

67

3-place predicate

a predicate with 3 arguments - distributive verbs (give(

68

unary predicates

1-place predicates

69

binary predicates

2-place predicates

70

ternary predicates

3-place predicates

71

sentence combination operators (predicate)

¬, ∧, ∨, →, ↔,∀x,∃x

72

∃x

Existential operator - "there exists an x"

73

"there exists an x"

∃x

74

Existential operator

∃x

75

∀x

universal operator - "for all x"

76

universal operator

∀x

77

"for all x"

∀x

78

natural language:John walks

W j

79

natural language:John is a boy

B j

80

natural language:He walks

W x

81

natural language:John sees Mary

S jm

82

natural language:John gives Mary the book

G jmb

83

an atomic statements ...

express basic properties of one or more objects together

84

natural language: John sees her

Sjx

85

natural language: He sees her

Syx

86

natural language: This is less than that

x < y

87

natural language: He sees himself

Sxx

88

natural language: John does not see Mary

¬Sjm

89

natural language: Three is not less than two

¬3 < 2, or abbreviated: 3 ≮ 2.

90

natural language: John sees Mary or Paula

Sjm ∨ Sjp

91

natural language: Three is less than three or three is less than four

3 < 3 ∨ 3 < 4

92

natural language: x is odd (i.e., two does not divide x)

¬(2|x)

93

natural language: If John sees Mary, he is happy

Sjm → Hj

94

natural language: Someone walks

∃xW x

95

natural language: Some boy walks

∃x(Bx ∧ W x)

96

natural language: A boy walks

∃x(Bx ∧ W x)

97

natural language: John sees a girl

∃x(Gx ∧ Sjx)

98

natural language: A girl sees John

∃x(Gx ∧ Sxj)

99

natural language: A girl sees herself

∃x(Gx ∧ Sxx)

100

natural language: Everyone walks

∀xW x

101

natural language: Every boy walks

∀x(Bx → W x)

102

natural language: Every girl sees Mary

∀x(Gx → Sxm)

103

natural language: Everyone sees someone

∀x∃ySxy

104

natural language: Someone sees everyone

∃x∀ySxy

105

natural language: Everyone is seen by someone

∀x∃ySyx

106

natural language: Someone is seen by everyone

∃x∀ySyx

107

domain of discourse

quantifiers range over all objects in some given set of relevant objects

108

All A are B

∀x(Ax → Bx)

109

No A are B

¬∃x(Ax ∧ Bx)

110

Some A are B

∃x(Ax ∧ Bx)

111

Not all A are B

¬∀x(Ax → Bx)

112

translate in steps:
Every boy loves a girl.

1) All B are . . .:
∀x (Bx → ϕ(x))

2) “Some C are D”, where C represents the class of girls and D the class of those objects which are loved by x:
∃y (Gy ∧ Lxy)

3) substitute ϕ(x):
∀x (Bx → ∃y (Gy ∧ Lxy))

113

translate in steps:
No girl who loves a boy is not loved by some boy

1) “No A are B”:
¬∃x (ϕ(x) ∧ ψ(x))
- ϕ(x) who are girls who love some boy
- ψ(x) class of those x who are loved by no boy

2) x is a girl and x loves a boy:
(Gx ∧ ϕ1(x))

3) substitute with ϕ(x)
¬∃x ((Gx ∧ ϕ1(x)) ∧ ψ(x))

4) “x loves a boy:
∃y (By ∧ Lxy)

5) substitute
¬∃x ((Gx ∧ ∃y (By ∧ Lxy)) ∧ ψ(x))

6) No boy loves x:
¬∃z (Bz ∧ Lzx)

7) substitute:
¬∃x ((Gx ∧ ∃y (By ∧ Lxy)) ∧ ¬∃z (Bz ∧ Lzx))

114

translate: “Someone can fool some people some of the time”

∃x(P x ∧ ∃y(P y ∧ ∃z(T z ∧ F xyz)))

115

translate: ”Someone cannot fool all people all of the time”

¬∃x(P x ∧ ∀y(P y → ∀z(T z → F xyz)))

116

monadic predicate logic

“unary properties”, with atomic statements involving one object only.

e.g: ∀x(Ax → Bx), ∀x(Bx → Cx) imply ∀x(Cx → Ax)

117

Not all A are B =

Some A are not B

118

All A are not B =

there are no A that are also B

119

There are no A that are also B =

All A are not B

120

Some A are not B =

Not all A are B

121

¬∀x(Ax → Bx) is equivalent to

∃x¬(Ax → Bx)
and
∃x(Ax ∧ ¬Bx)

122

∃x¬(Ax → Bx) is equivalent to

¬∀x(Ax → Bx)
and
∃x(Ax ∧ ¬Bx)

123

∃x(Ax ∧ ¬Bx) is equivalent to

¬∀x(Ax → Bx)
and
∃x¬(Ax → Bx)

124

∀x(Ax → ¬Bx) is equivalent to

¬∃x¬(Ax → ¬Bx)
and
¬∃x(Ax ∧ Bx)

125

¬∃x¬(Ax → ¬Bx) is equivalent to

∀x(Ax → ¬Bx)
and
¬∃x(Ax ∧ Bx)

126

¬∃x(Ax ∧ Bx) is equivalent to

¬∃x¬(Ax → ¬Bx)
and
∀x(Ax → ¬Bx)

127

¬∀xϕ is equivalent to

∃x¬ϕ,

128

¬∃xϕ is equivalent to

∀x¬ϕ

129

∀xϕ is equivalent to

¬∃x¬ϕ

130

∃xϕ is equivalent to

¬∀x¬ϕ

131

what is epistemic logic

logic of knowledge as based on information, including changes in knowledge which result from observations of facts, or communication between agents knowing different things

132

main sources of information

observation
inference
communication

133

functions V valuations

V (ϕ) = 1, means ϕ is true in V, V ⊨ ϕ
V (ϕ) = 0 means ϕ is false in V, V ⊭ϕ

134

Truth table: Logical True

p
T T
F T

135

Truth table: Logical False

p
T F
F F

136

Truth table: logical Identity

p
T T
F F

137

Truth table: negation

p ¬p
T F
F T

138

Truth table: Logical Conjunction

p q p ∧ q
T T T
T F F
F T F
F F F

139

Truth table: Logical Disjunction

p q p ∨ q
T T T
T F T
F T T
F F F

140

Truth table: Logical implication

p q p → q
T T T
T F F
F T T
F F T

141

Truth table: Logical Equality

p q p ↔ q
T T T
T F F
F T F
F F T

142

Truth table: Exclusive Disjunction

p q p ⊕ q
T T F
T F T
F T T
F F F

(p ∧ ¬q) ∨ (¬p ∧ q)

143

Truth table: Logical NAND

p q p ↑ q
T T F
T F T
F T T
F F T

¬(p ∧ q)

144

Truth table: Logical NOR

p q p ↓ q
T T F
T F F
F T F
F F T

¬(p ∨ q)

145

Build Truth table: for (¬ (p ∨ q) → r)


(¬ (p ∨ q) → r)
· 0 0 0 · 0
· 0 0 0 · 1
· 0 1 1 · 0
· 0 1 1 · 1
· 1 1 0 · 0
· 1 1 0 · 1
· 1 1 1 · 0
· 1 1 1 · 1

(¬ (p ∨ q) → r)
1 0 0 0 · 0
1 0 0 0 · 1
0 0 1 1 · 0
0 0 1 1 · 1
0 1 1 0 · 0
0 1 1 0 · 1
0 1 1 1 · 0
0 1 1 1 · 1

(¬ (p ∨ q) → r)
1 0 0 0 0 0
1 0 0 0 1 1
0 0 1 1 1 0
0 0 1 1 1 1
0 1 1 0 1 0
0 1 1 0 1 1
0 1 1 1 1 0
0 1 1 1 1 1

146

If p then q

p → q

147

p if q

q → p

148

p only if q

p → q

149

p if and only if q

p ↔ q

150

The inference from a finite set of premises ϕ1, . . . , ϕk to to a conclusion ψ is a valid consequence

ϕ1, . . . , ϕk ⊨ ψ

151

ϕ1, . . . , ϕk ⊨ ψ

The inference from a finite set of premises ϕ1, . . . , ϕk to to a conclusion ψ is a valid consequence

152

if ϕ ⊨ ψ and ψ ⊨ ϕ

ϕ and ψ are logically equivalent.

153

ϕ and ψ are logically equivalent.

if ϕ ⊨ ψ and ψ ⊨ ϕ

154

Modus Tollens

(The simplest case of refutation)
(the way that denies by denying)
(denying the consequent)
If P, then Q.
Not Q.
Therefore, not P.
ϕ → ψ, ¬ψ ⊨ ¬ϕ

155

Truth table: Modus Tollens

ϕ ψ ϕ → ψ ¬ψ ¬ϕ
1 1 1 0 0
1 0 0 1 0
0 1 1 0 1
0 0 1 1 1

156

Satisfiable

X (say, ϕ1, . . . , ϕk) is satisfiable if there is a valuation that makes all formulas in X true

157

Consistent

A set of formulas that does not lead to a contradiction is called a consistent formula set
ϕ |= ψ if and only if {ϕ, ¬ψ} is not consistent

158

inconsistent

there is no valuation where all formulas in the set are true simultaneously

159

Tautology

A formula ψ that gets the value 1 in every valuation
⊨ ψ
ϕ1, . . . , ϕk |= ψ if and only if (ϕ1 ∧ . . . ∧ ϕk) → ψ is a tautology

160

Logical Equivalences: Commutative

p ∧ q ⇐⇒ q ∧ p
p ∨ q ⇐⇒ q ∨ p

161

Logical Equivalences: Associative

(p ∧ q) ∧ r ⇐⇒ p ∧ (q ∧ r)
(p ∨ q) ∨ r ⇐⇒ p ∨ (q ∨ r)

162

Logical Equivalences: Distributive

p ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r)

163

Logical Equivalences: Identity

p ∧ T ⇐⇒ p
p ∨ F ⇐⇒ p

164

Logical Equivalences: Negation

p ∨ ¬p ⇐⇒ T
p ∧ ¬p ⇐⇒ F

165

Logical Equivalences: Double Negative

¬(¬p) ⇐⇒ p

166

Logical Equivalences: Idempotent

p ∧ p ⇐⇒ p
p ∨ p ⇐⇒ p

167

Logical Equivalences: Universal Bound

p ∨ True ⇐⇒ True
p ∧ False ⇐⇒ False

168

Logical Equivalences: De Morgan’s

¬(p ∧ q) ⇐⇒ (¬p) ∨ (¬q)
¬(p ∨ q) ⇐⇒ (¬p) ∧ (¬q)

169

Logical Equivalences: Absorption

p ∨ (p ∧ q) ⇐⇒ p
p ∧ (p ∨ q) ⇐⇒ p

170

Logical Equivalences: Conditional

(p =⇒ q) ⇐⇒ (¬p ∨ q)
¬(p =⇒ q) ⇐⇒ (p ∧ ¬q)

171

Rules of Inference: Modus Ponens

p =⇒ q
If P, then Q.
P.
Therefore, Q.

172

Rules of Inference: Modus Tollens

p =⇒ q
If P, then Q.
Not Q.
Therefore, not P.

173

Rules of Inference: Elimination

p ∨ q
P or Q
Not Q
therefore P

174

Rules of Inference: Transitivity

p =⇒ q
q =⇒ r
if P then Q
if Q then R
therefore If P then R

175

Rules of Inference: Generalization

p =⇒ p ∨ q
q =⇒ p ∨ q
If P then P or Q
therefore
If Q then P or Q

176

Rules of Inference: Specialization

p ∧ q =⇒ p
p ∧ q =⇒ q
If P and Q then P
therefore
If P and Q then Q

177

Rules of Inference: Conjunction

P
Q
therefore P or Q

178

Rules of Inference: Contradiction Rule

¬p =⇒ False
If Not P then False
therefore P

179

A proof

A proof is a finite sequence of formulas, where each
formula is either an axiom, or follows from previous formulas in the proof by a deduction
rule.

180

theorem

A formula that occurs in a proof, typically as the last formula in the sequence

181

axiomatization

A set of axioms and rules defines an axiomatization for a given logic

182

axiomatization for propositional logic

(1) (ϕ → (ψ → ϕ))
(2) ((ϕ → (ψ → χ)) → ((ϕ → ψ) → (ϕ → χ)))
(3) ((¬ϕ → ¬ψ) → (ψ → ϕ))
and modus ponens
if ϕ and (ϕ → ψ) are theorems, then ψ is also a theorem

183

sound

If all theorems of an axiomatic system
are valid, the system is sound

184

complete

if all valid formulas are provable theorems,the logic is called complete

185

MOD(ϕ)

The information content of a formula ϕ is the set MOD(ϕ) of its models,
that is, the valuations that assign the formula ϕ the truth-value 1.

186

The Sheffer stroke

nand (equivalent to the negation of the conjunction operation)

187

conjunctive normal form

Every propositional logical formula is equivalent to a conjunction of disjunctions of propositions or their negations

188

boolean tautalogies (in binary arithmatic for or)

x + (y + z) = (x + y) + z
x + y = y + x
x + x = x
x + x = x
x + 0 = 0
x + 1 = 1
x + −x = 1

189

boolean tautalogies (in binary arithmatic for and)

x · (y · z) = (x · y) · z
x · y = y · x
x · x = x
x · 0 = 0
x · 1 = x
x · −x = 0

190

boolean tautalogies (in binary arithmatic mixed and/or/not)

x + (y · z) = (x + y) · (x + z)
x + (x · y) = x
−(x + y) = −x · −y
x · (y + z) = (x · y) + (x · z)
x · (x + y) = x
−(x · y) = −x + −y
− − x = x

191

All A's are B's

(x)(Ax ⊃ Bx)

192

No A's are B's

(x)(Ax ⊃ ¬Bx)

193

Some A's are B's

(∃x)(Ax ⋀ Bx)

194

Some A's are not B's

(∃x)(Ax ⋀ ¬Bx)

195

All and only A's are B's

(∃x)(Ax ↔ Bx)

196

Only A's are B's

(x)(Bx ⊃ Ax)

197

Not all A's are B's

(∃x)(Ax ⋀ ¬Bx)

198

All A's are not B's

(x)(Ax ⊃ ¬Bx)

199

what is Rˇ

Rˇ is the relational converse of Rˇ
Rˇ = {(y, x) ∈ S^2 | (x, y) ∈ R}.