Study Stanford: CS103: Mathematical Foundations of Computing

[yaobinwen]

Description

• [ ] CS103: Mathematical Foundations of Computing
  • [x] The lecture slides can be found here. The class is still going on as of 2023-07-20.
  • [x] Introduction, Set Theory
  • [x] #198
  • [x] #199
  • [x] Propositional Logic
  • [x] #204
  • [x] First-Order Logic, Part II
  • [ ] Functions, Part I
  • [ ] Functions, Part II
  • [ ] Graphs, Part I
  • [ ] Graphs, Part II
  • [ ] Mathematical Induction, Part I
  • [ ] Mathematical Induction, Part II
  • [x] #223
  • [x] #226
  • [x] #227
  • [x] #228
  • [x] #229
  • [x] #230
  • [x] #231
  • [x] #232
  • [x] #233

[yaobinwen]

Update (2023-07-20)

I wanted to study propositional logic because I want to evaluate the following proof (see the reply by Jan Hidders):

To show this we need to show that for any x the following two statements are equivalent:

    x∈A∖(B∩C)

x∈(A∖B)∪(A∖C)

We can show this by using the definitions of the set operations and propositional reasoning rules:

(i) x∈A∖(B∩C)

By definition of ∖

this is equivalent to:

(ii) x∈A∧x∉(B∩C)

By definition of ∩

this is equivalent to:

(iii) x∈A∧¬(x∈B∧x∈C))

By De Morgan (i.e. ¬(P∧Q)
is equivalent to ¬P∨¬Q

) this is equivalent to:

(iv) x∈A∧(x∉B∨x∉C)

By distribution of ∧
over ∨

this is equivalent to:

(v) (x∈A∧x∉B)∨(x∈A∧x∉C)

By definition of ∖

this is equivalent to:

(vi) x∈A∖B∨x∈A∖C

By definition of ∪

this is equivalent to:

(vii) x∈(A∖B)∪(A∖C)

QED