逻辑和推理

命题逻辑

Operators

  • , material implication (conditional statement)
  • , bi-conditional statement

逻辑等价式

Distributive laws

De Morgan's laws

Absorption laws

Conditional distributive laws

Like De Morgan's laws, ha?

Normal forms

Disjunction normal Form

Conjunction Normal Form

Minimal Operators to Express Statements

One could use and only use

  1. AND, NOT
  2. OR, NOT
  3. IMPLICATION

谓词和量词

Unique Quantifier

The uniqueness quantifier is denoted as , the statement states "There exists a unique such that is true."

Quantifiers with Restricted Domains

and

Tip

Note that for existential quantification, here is but not

推理规则

TautologyName
Modus ponens
Modus tollens
Hypothetical syllogism
Disjunctive syllogism
Addition
Simplification
Conjunction
Resolution
潘天麟 概率论与数理统计 2024年10月26日(周六)下午14:00-16:00 17 阶一6
潘天麟 离散数学 2024年10月26日(周六)上午09:00-10:30 18 阶一6
潘天麟 信号与系统 2024年10月27日(周日)下午14:00-15:40 21 阶二3

证明方法

Proof by Contraposition

Proofs by contraposition make use of the fact that the conditional statement is equivalent to tis contrapositive, . This means that the conditional statement can be proved by showing that its contrapositive, , is true. In a proof by contraposition of , we take as a premise, and using axioms, definitions, and previously proven theorems, together with rules of inference, we show that must follow.

Proof by Contradiction

Suppose we want to prove that a statement is true. Furthermore, suppose that we can find a contradiction such that is true. Because is false, but is true, we can conclude that is false, which means that is true.

To find a contradiction , we consider the statement , which is a contradiction whenever is a proposition. We can prove that is true if we can show that is true for some proposition .

集合

幂集(Power Sets)

Given a set , the power set of is the set of all subsets of the set . The power set of is denoted as

For example

If , than we have

Cartesian积

Relation

A subset of the Cartesian Product is called a relation from set to the set . A relation from to itself is called a relation on

重集(Multisets)

The multiset denoted by is the multiset that contains the element thrice and twice. There is another notation denotes the multiset with occurs times.

The numbers are called the multiplicities of the elements . (Elements not in a multiset are assigned as their multiplicities in this set)

势(基数, Cardinality)

The sets and have the same cardinality if and only if there is one-to-one correspondence from to . When and have the same cardinality, we write

If there is a one-to-one function from to , the cardinality of is less than or the same as the cardinality of and we write .

If and are sets with and , then

Countable Sets

A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set is countable, we denote the cardinality of by . We write and say that has cardinality "aleph null"

If and are countable sets, then is also countable.

The Continuum Hypothesis

Cantor states that the cardinality of a set is always less than the cardinality of its power set. Hence, . We can rewrite this as . We denote

We have

The continuum hypothesis is that there is no cardinal number between these numbers:

where

矩阵

01矩阵

A 0-1 Matrix is a matrix whose elements are either 0 or 1.

Let be 0-1 matrices, we define

and

which is called the Boolean Product of and

Tip

We can see Boolean Product as a normal matrix multiplication with replaced by and replaced by

Based on this, we can also define the -th Boolean power of as

算法

性质

  • 输入
  • 输出
  • 确定性: Well-defined, without a second interpretation
  • 正确性: Generate correct output for every possible input
  • 有限性: Finishing in finite steps
  • 有效性: Each step finishing in finite time
  • 通用性: Can be generalized

Note

The following example demonstrate correctness for specific cases but lack generality

def sort_five_numbers(a, b, c, d, e): 
	return sorted([a, b, c, d, e])

时间复杂度

Ranking

记号

Big

For function , if and only if s.t.

Big symbol indicates both the upper and lower bound of a time function

Big

We say if and only if s.t.

This gives us the upper bound of a time function.

Big

We say if and only if , s.t.

This gives us the lower bound of a time function.

数论

模算数

is a commutative ring:

  1. Definition
  1. If and , then

中的乘法逆元

The modular inverse of  in the ring of integers modulo  is an integer  such that

Euler定理

i if is a positive integer, and let be an integer that is relatively prime to . Then

where is Euler's totient function, which counts the number of positive integers less than that is also relative prime to

Fermat小定理(Euler定理的一个特例)

If is a prime, then , then Euler's Theorem becomes Fermat's Little Theorem

伪素数

Let be a positive integer. If is a composite positive integer, and , then is called a pseudo-prime to be base

Among the positive integer not exceeding , where is a positive real number, compared to primes there are relatively few pseudo-primes to the base . So determining whether is a useful test that provides some evidence concerning whether is prime.

However, there are some composite that satisfies the congruence for all positive integers with is called a Carmichael number. For example, the integer is a Carmichael number.

Exgcd

For example, calculate

010810
1086801
68401-1
4028-12
28122-3
124-58
40
this gives

中国剩余定理

Let be integers greater than , and . If the are pair-wise co-prime, and if are any integers, then the system

has a solution, and any two solutions, say and , satisfy

To construct a solution, let be the product of all moduli but one. As the are pair-wise co-prime, and are co-prime. Thus Bezout's identity applies, and there exist integers and such that

A solution of the system of congruences is

In fact, as is a multiple of for , we have

原根和离散对数

A primitive root module a prime is an integer in such that every non-zero element of is a power of .

We can say here can generate the space of

An important fact is that there is a primitive root module for every prime . Suppose this primitive root is , and is an integer between and inclusive. If and , we say that is the discrete logarithm of module to the base and we write

例题

T1

Prove that and have the same cardinality

Using Hilbert's Hotel. Let , then define so that

and

Tip

We can also construct a bijection from to by letting and

T2

Let where . Prove that there exist such that

Let's divide into threes sections

First we prove that we can select elements at most from such that there are no in this selection satisfying . To conclude this, we further divide into pairs

We can select no more than element in each pair, so we can select no more than elements in .

Similarly, we can select no more than elements in . Therefore, we can select no more than elements in

T3