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 ⊨ ψ

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