logic notes Flashcards
(199 cards)
1
Q
¬
A
not, negation
2
Q
not
A
¬
3
Q
∧
A
And, conjunction
4
Q
and
A
∧
5
Q
conjunction
A
∧
6
Q
negation
A
¬
7
Q
∨
A
or, disjunction
8
Q
or
A
∨
9
Q
disjunction
A
∨
10
Q
→
A
if … then, implication
11
Q
if … then
A
→
12
Q
implication
A
→
13
Q
↔
A
if and only if, iff, equivalence
14
Q
if and only if
A
↔
15
Q
equivalence
A
↔
16
Q
not premise p
A
_
p
17
Q
_
p
A
not premise p
18
Q
He has an Ace if he does not have a Knight or a Spade
A
¬(k ∨ s) → a
or
(¬k ∨ s) → a
19
Q
exclusive disjunction
A
⊕
20
Q
⊕
A
exclusive disjunction
21
Q
define the Language of propositional logic
A
Let P be a set of proposition letters and let p ∈ P
ϕ ::= p | ¬ϕ | (ϕ ∧ ϕ) | (ϕ ∨ ϕ) | (ϕ → ϕ) | (ϕ ↔ ϕ)
22
Q
syllogism
A
a logical argument where a quantified statement of a specific form (the conclusion) is inferred from two other quantified statements (the premises).
23
Q
4 corners of Square of Opposition
A
All A are B
……..No A are B
Some A are B
……..Not all A are B
24
Q
syllogistic Q N V
A
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}.
