Sets
if all elements s = T ,
S C- T , S is subsets of T .
if some elements 5 are elements of T SFT
SCT ,
s is proper subsets of T
Power set : 2h Cartesian product
-
P =
{
,
1) 21 A✗ B
F B. ✗ A
p( s) = { { 11 ,
{ 2} , { 1 , I } '
⑨ } a :{ v25
B =
{ c, ☐ 3
Set of difference
D- ✗ B =
{ ( 1 C)
, , (2) C) , 21 D)
> ,
A- B = A1 B- ( 2 / D) }
Logic
① Proposition logic
③ Predicate logic
③ Proof
Proposition :
statement that either is
True -0k False . Cannot both .
( AND ) ( n)
|
-
Conjunction
-
disjunction ( OR ) ( v)
operate r
-
negation I -
)
① Conditional ④ Bi conditional
proposition proposition
c
p→q
/ thenarconsequence p q
→
if p
antecedent
P if and only if or
iff
.EE?:...........-T:::::::
p q
÷÷÷
T
f-
→
→
F
T
(F)
IT ) Converse
inverse -
q →
p → -9
p →
every output
Contradiction
is TRUE
is False
→
every output
→ neither tautologies
nor contradiction
Logical Equivalence p→q= >
pvq
-
2 propositions are the same truth value p→q =/ q→p
pc-sqn-rgum-e.int
→
-
validation depends on
pattern ( Rule of inference )
( Every statements that is true]
{
" " " " ""
"
µ
Modus Ponens : P → 9 Disjunction : P i.
Affirming the
P Introduction :-P V9 consequence
i.
q p →
q
{ Ipv4
Disjunction :P V9 a
Modus Tokens :
P → 9 syllogism
7
or :-p
sq :p ; q
:-p 2. Denying antecedent
:P
Hypothetical →
9 p→q
Conjunction : PA 9 Syllogism 9. → r -
p
elimination :p :p → r q
-
.
:
q
i.
,.mn . . p ,
p →r
q → s
: . rvs
Predicates? ( Quantification at
Logie >
Predicate → property taat some object has -
"
"
Dogs are blue .
blue
dog
some has the of being
object property a
dog .
That object also has the
property of being blue
Formal
syntax :
'
Predicates : A / B. C. 2-
not gonna
Terms : -
Constants : a. b. c. d ,
. .
- t ←
change
variables : m
,y , z
,
-
-
w ← generic
connective : n , v , n ,
→
, →
Quantifiers :
y , F
all exist
dogs are blue
at
Universal Quantifier : Y
Tx ( DX Bx )
"
"
All
dogs are blue →
for all if dog
DX : ✗ is a
dog
✗ . ✗ is a i
/True )
BX : ✗ is blue then ✗ is blue
"
"
All man like cake and pie
Mx : ✗ is a man Fx / Mx → ( Lxcnlxp ) )
Lxy : ✗ likes y
c : cake for all ✗ , if ✗ is a man ,
then ✗
p :
pie like cake and pie
Lxy ⇐> ✗ likes y
Existential Quantifier There is other dogs
:
g- is red etc
p
"
"
some dogs is blue Fx ( DX A BX )
There is exist an ✗ , such that
Dx : ✗ is a
dog ✗ is a
dog and ✗ is a blue
Bx : ✗ is blue
"
some Fx ( Mxn ( LXCALXP ) )
"
man like cake and pie
There is an ✗ / such that ✗ is
Mx : ✗ is a man
a man , and this ✗ likes cake
Lxy : ✗ likes y and ✗ Likes pie
c : cake
p :
pie
Specific connective depending on the quantifier
" "
All men are happy
mark
happy
-
I 0
f- txlmx Hx ) F tx ( Mx → Hx ) ✓
John →
sad
Steve Fx ( Mxn Hx ) F
I 0
is T
everyone here man
" "
All men are happy
mark
happy
-
0 I
#
Jane txlmx → Hx ) T
Steve
sad
u
4- ✗ ( Mxn
o
Hx
1
) F
Not all ✗ are men -0
t
all I
g) Are man
happy
-
All man are
happy -
I
is
every element that F is
-
O
we
looking are a man
↳ No not airmen
?⃝
"
"
some is
men happy
mark
happy
-
Jane
Steve
# sad
Fxlmx
Fxlnfxnltx )
→ Hx )
T
FxlMx^H× )
some person is a man -
l
T
and some person that is a
man that is happy -
I
5--1 There is some person
* is a man and happy
"
Mary
"
some is
happy men happy
✗
,
Jane F×lM%→H× )
(
-1
sad 0
Stacy Fxlmxnltx )
the problem can be seen here [ > There is a
There is
man -0
an ✗ that is happy -
I
T
there is a man -0 F
There is an ✗ that is happy
-
I
predicate Logic and quantifiers :
do not have truth value
Elm )
,
• =
✗ is even : not a statement
%%"¥° Gay ] =
n is greater than y
✓
6712,11 greater than True !
aged {
• = 2 is 1
"
gornik • Gt3 6) , = 3 is greater than 6 False !
Quantifiers :
" "
tx Pen) :
For all n ,
✗ is P
"
Fx Plm )
"
:
for some n ,
✗ is P
For real number there is real number such that
every
2 =
n
n , a m
Hn t 112 ,
Fm t IR : MEN
/ Pimm ) : m2=n
Given two rationals M and y ,
tny will also be rational .
V-x.us c- ☒ ,
JMJE Q1
Negating Quantifiers :
•
Define tx , Fx for a universe with elements { 112 ,
.
. -
in }
Fx Pcx ) Pcl ) ^ P(2) 1 . .
NP ( n )
-
Fx Pcx ) ⇐ Pas v Pez , V - - -
vpcn )
Show that > txfpcn ) ] ⇐ FXÉTPCX ) ]
-
f- ✗ Pcx ]
= 7 / Pcl ) ^ P (2) 1 . . .
n Pln ) )
= → Pll ] V 7 P (2) V - . . v
-
Pcn )
=
Fx [ 7Pa 5)
\ Pcl ) P( 2) Pcn )
Fx PCX ) = ✓ v. . .
v .
ltxpcx ) ⇐s -
7×[-17×1]
1- ✗ Pix ) <=) 7th [ -
Pix ) ]
n
th Pix ) 1- ✗ [ Pix ) ]
'
-
Fx Pix ) # ltx f- Pix ) ]
Negate the
following :
b- [ Fy [ Pcxiy ) Qly ) ) ) )
-
✗ ^
= Fx -
[ Fy / pin , y) ^ Q ly ) ) )
= 3- ✗
try
-
[ Pin , g) ^
Qly ) )
Q ly ) )
7- thy [ PA y) V
- -
= ✗ ,
Rule of inference :
Universal Instantiations :
Tx PCX ] → Pcc )
Universal Generalisation :
P (c) → V- ✗ Pcxi
Existential Instantiations :
1- ✗ PCX )
→ Pcc )
Existential Generalisation :
Pcc ) → Fx PCX )
Proof argument
:
An that establish the truth of a
theorem
① Direct proofs :-p → q prove if P true then , q is true
.
disprove by counterexample .
④ Proof by contradiction : if P → Q is true , P → Q
-
is false
-
:
prove P → -
Q is false .
③ Proof by contrapositive : if P →
Q true ,
-
a → -
P is true
-
i -
prove
-
Q → -
P is true
④ Proof by cases :
exhaustive proof ( prove one by one )
Proof equivalence P←sQ true
⑤ by : if is
,
Q true
proof both
}
P → is ,
are true
Q→ P is true .
apply methods
above
-
Function .
fcx ) =
y
°
"et°man9→nid
non
number of function :
{ 9" basic from hignsc.no , , f-CX ) 1411×1
( has inverse )
number
① injective ( invertible function ) :
y
of bijective ✗
-
one to one function .
① Surjective ( all the codomain matched ) Range 1×1=141
-
if ,
The number
✓
③ Bijective injective " """
:
✓
"
surjective function is
""
non injective non injective injective
injective
-
-
} non surjective 4 surjective 4
} surjective
-
non -
surjective
( bijective )
?⃝
?⃝
?⃝
