Discrete Mathematical Structures

---

DiscreteMathematicalStructures

---

---

---

1、What's logic?

---

1.1 Definition of Logic

Logic is the discipline that deals with the methods of reasoning. It is now an integral part of disciplines such as mathematics, computer science, and linguistics.

---

2、Propositions and Logical Operations

---

2.1、Definition of Propositions

A statement or proposition is a declarative sentence that is either true of false, but not both.

Proposition	Not a Statement
The national flag of China is red	x + 5 ＞ 3

---

2.2、Logic Operators

In mathmematics, the letters $x,y,z...$ ofen denote variables that can be replaced by real numbers,and these variables can be combined with the familiar operations$+,-,\times,\div$. In
logic, the letters $p,q,r...$ denote propositions variables; that is, variables that can be replaced by statements.

Statements or propositional variables can be combined by logical connectives to obtain compound statements.

Use logical operators:

Operator	Symbol
Negation (not)	$\sim p$
Conjunction (and)	$p\bigwedge q$
Disjunction (or)	$p \bigvee q$
Exclusive or	$p \bigoplus q$
Implication	$p \implies q$
Biconditional	$p \iff q$

---

2.2.1、Negation $\sim$

常用语：不，没有，无，否定，取反

p	$\sim p$
$T$	$F$
$F$	$T$

---

2.2.2、Conjunction $\bigwedge$

For propositions p and q, the output will be true if and only if (notation: IFF) both p and q are true.

常用语：并且，以及，和，与，既…又，不但…而且，尽管…依然，虽然…但是

p	q	$p\bigwedge q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

---

2.2.3、Disjunction $\bigvee$

For propositions p and q, the output will be true if either or both p and q are true.

常用语：或者

p	q	$p\bigvee q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

---

2.2.4、Exclusive or $\bigoplus$

It is also called exclusive disjunction and the results in a value of true if exactly one of the operands has a value of true."one or the other but not neither nor both."

p	q	$p\bigoplus q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

---

2.2.5、Implication $\implies$

p is the premise and q is the conclusion.

常用语：如果…那么，若…则，只要…就

eg.

• p implies q
• whenever p is true q must be true
• if p then q
• q if p
• p is sufficient for q
• p only if q

In the case where p is true and q is false, the outcome is false.A false hypothesis implies ANYTHING

p	q	$p\implies q$
$T$	$T$	$F$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

If $p \implies q$ is an implication, then the converse of $p \implies q$ is the implication $q \implies p$, and the contrapositive of $p \implies q$ is the implication $\sim q \implies \sim p$.

---

2.2.6、Biconditional $\iff$

True if p and q have the same truth value.

常用语：当且仅当，等价于，…和…一样

p	q	$p\iff q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

---

2.3、Classification of Propositions

---

A statement that is true for all possible values of its propositional variables is called tautology. A statement that is always false is called a contradiction or an absurdity, and a statement that can be either true or false, depending on the truth values of its propositional variables, is called a contingency.

If a proposition is tautology then it is contingency, the reverse is not true.

---

2.4、Theorem

---

Commutative properties

• $p\bigvee q \equiv q\bigvee p$
• $p\bigwedge q \equiv q\bigwedge p$

Associative Properties

• $(p \bigvee q)\bigvee r\equiv p \bigvee (q\bigvee r)$
• $(p \bigwedge q)\bigwedge r\equiv p\bigwedge (q \bigwedge r)$

Distributive Properties

• $p \bigvee (q \bigwedge r)\equiv (p \bigvee q)\bigwedge(p \bigvee r)$
• $p \bigwedge (q \bigvee r)\equiv (p \bigwedge q)\bigvee (p \bigwedge r)$

Idempotent Properties

• $p \bigvee p\equiv p$
• $p \bigwedge p \equiv p$

Absorption Properties

• $p \bigvee (p \bigwedge q)\equiv p$
• $p \bigwedge (p \bigvee q)\equiv p$

Properties of Negation

• $\sim (\sim p)\equiv p$
• $\sim (p \bigvee q)\equiv \sim p \bigwedge \sim q$
• $\sim (p \bigwedge q)\equiv \sim p \bigvee \sim q$

Other Properties

• $p \bigvee \sim p\equiv T$
• $p \bigwedge \sim p \equiv F$
• $p \bigvee F\equiv p$
• $p \bigvee T \equiv T$
• $p \bigwedge T\equiv p$
• $p \bigwedge F \equiv F$
• $p \iff q \equiv (p \implies q)\bigwedge (q \implies p)$
• $p \iff q\equiv (\sim p \bigvee q)\bigwedge (\sim q \bigvee p)$
• $p\iff q \equiv (p \bigwedge q)\bigvee (\sim q \bigwedge \sim p)$

Note:

• 只要够分数线，就能上大学(充要条件)

  • p:(某人)够分数线
  • q:(某人)能上大学
  • $p \implies q$

• 只有够分数线，才能上大学(充分条件)

  • p:(某人)够分数线
  • q:(某人)能上大学
  • $q \implies p$

---

3、Propositional Logic

---

3.1、Equivalence Calculus

The process of deriving a new equivalent form from a known equivalent form.

Basic equivalence	Symbol
Double negative law	$\sim (\sim p)\equiv p$
Idempotent law	$p \bigvee p\equiv p \quad p \bigwedge p \equiv p$
Commutative law	$p\bigvee q \equiv q\bigvee p\quad p\bigwedge q \equiv q\bigwedge p$
Associative law	$(p \bigvee q)\bigvee r\equiv p \bigvee (q\bigvee r) \quad(p \bigwedge q)\bigwedge r\equiv p\bigwedge (q \bigwedge r)$
Distributive law	$p \bigvee (q \bigwedge r)\equiv (p \bigvee q)\bigwedge(p \bigvee r)\quad p \bigwedge (q \bigvee r)\equiv (p \bigwedge q)\bigvee (p \bigwedge r)$
De morgan law	$\sim (p \bigvee q)\equiv \sim p \bigwedge \sim q \quad \sim (p \bigwedge q)\equiv \sim p \bigvee \sim q$
Absorption law	$p \bigvee (p \bigwedge q)\equiv p \quad p \bigwedge (p \bigvee q)\equiv p$
Zero or one law	$p \bigvee T \equiv T \quad p \bigwedge F \equiv F$
Law of Identity	$p \bigvee F\equiv p \quad p \bigwedge T\equiv p$
Law of excluded middle	$p \bigvee \sim p \equiv T$
Law of contradiction	$p \bigwedge \sim p \equiv F$
Implicit equivalence	$p \implies q \equiv \sim p\bigvee q$
Equivalent equation	$p \iff q \equiv (p \implies q)\bigwedge (q \implies p)$
False translocation	$p \implies q \equiv \sim q \implies \sim p$
Equivalent negation equivalent formula	$p \iff q \equiv \sim p \iff \sim q$
Return to fallacy	$(p \implies q)\bigwedge (p \implies \sim q)\equiv \sim p$

---

3.2、Rules About Logical Equivalences

---

3.2.1 Substitution

Where $\Phi$ and $\phi$ represent formulas of propositional logic, $\Phi$ is a substitution instance of $\phi$ if and only if $\Phi$ may be obtained from $\phi$ by substituting formulas for symbols in $\phi$, always replacing an occurrence of the same symbol by an occurrence of the same formula. If $\phi$ is a tautology, so is $\Phi$.

3.2.2 Replacement

Suppose $\Phi(A)$ represents a formula of propositional logic contain formula A as a clause, and $\Phi(B)$ represents a formula which replace an occurrence of A with a logically equivalent formula B; then $\Phi(A) \equiv \Phi(B)$.

Note: Unlike substitution its permissible for the replacement to occur only in one place (i.e. for one formula).

3.2.3 Contrast between Substitution and Replacement

Aspect	Substitution	Replaceemnt
Use object	Any tautology	Any propositional formula
Substitution object	Any propositional variable	Any sub-formula
Substitute	Any propositional formula	Any Propositional Formula Equivalent to Substitution Object
Substitution method	Substituting all occurrences of the same proposition variable	Some Appearances of Substitution Formula
Substitution result	It is still tautological	Equivalent to the original formula

eg.

化简语句:"情况并非如此:如果他不来，那么我也不去"。

• p:他来
• q:我去

$\quad\sim (\sim p \implies \sim q)$
$\equiv \sim (\sim \sim p\bigvee \sim q)$
$\equiv (p \bigvee \sim q)$
$\equiv \sim p \bigvee q$

我去了，而他没来

---

3.3 Normal Form

$$\begin{cases} DNF&\text{Disjunctive normal form is a disjunction of one or more fundamental conjunctions} \\[2ex] CNF, & \text{Conjunctive normal form is a conjunction of one or more fundamental disjunctions} \end{cases}$$

Note:

• A disjunctive normal form is a contradiction if and only if each fundamental conjunction of it is a contradiction.
• A conjunctive normal form is a tautology if and only if each fundamental disjunction of it is a tautology.

Every propositional formula can be converted into an equivalent formula that is in CNF and DNF.

---

3.4 Steps to Seek Normal Form

To convert a propositional formula to equivalent CNF or DNF:

• STEP1. Eliminate implications and equivalences such that the formula contains only connectives of $\sim \bigwedge \bigvee$;
• STEP2. Move all negations inside to create literals.
• STEP3. Apply the distributive law and associative law to obtain a DNF or a CNF.

eg.

Find a DNF of $\sim (p \bigvee q)\iff (p \bigwedge q)$

$\quad \sim (p \bigvee q)\iff (p \bigwedge q)$
$\equiv (\sim (p \bigvee q)\bigwedge (p \bigwedge q))\bigvee (\sim \sim (p \bigvee q)\bigwedge \sim (p \bigwedge q))$
$\equiv (\sim p \bigwedge \sim q \bigwedge p \bigwedge q)\bigvee ((p \bigvee q)\bigwedge (\sim p \bigvee \sim q))$
$\equiv (\sim p \bigwedge \sim q \bigwedge p \bigwedge q)\bigvee (p \bigwedge \sim p)\bigvee (p \bigwedge \sim q)\bigvee (q \bigwedge \sim p)\bigvee (q \bigwedge \sim q)$
$\equiv (p \bigwedge \sim q)\bigvee (q \bigwedge \sim p)$

Find a CNF of $\sim (p \bigvee q)\iff (p \bigwedge q)$

$\quad \sim (p \bigvee q)\iff (p \bigwedge q)$
$\equiv(\sim \sim (p \bigvee q)\bigvee (p \bigwedge q))\bigwedge (\sim (p \bigwedge q)\bigvee \sim (p \bigvee q))$
$\equiv ((p \bigvee q)\bigvee (p \bigwedge q))\bigwedge ((\sim p \bigvee \sim q)\bigvee(\sim p \bigwedge \sim q))$
$\equiv (p \bigvee q)\bigwedge (\sim p \bigvee \sim q)$

---

3.5 FDNF and FCNF

---

3.5.1 Minterm and Maxterm

• A fundamental conjunction is called as a minterm (极小项) if each of its variables appears exactly once in it.

A conjunction of n propositional variables$P_1,P_2,...P_n$:

$$Q_1\bigwedge Q_2\bigwedge...\bigwedge Q_n$$
where $Q_i=P_i$ or $\sim P_i$.That is, each propositional variable does not appear at the same time as its negation, but one of the two must appear only once, and the i-th propositional variable or its negation appears at the i-th position from the left, then the conjunctive formula ,$Q_1\bigwedge Q_2\bigwedge...\bigwedge Q_n$,is called the minimal item and is expressed by $m_i$.

There are $2^n$ minterms of n propositional variables. We denote them as $m_0, m_1, ..., m_{2n-1}$.

Suppose there are three propositional variable p, q and r.

minterm	represent1	represent2	symbol
$\sim p \bigwedge\sim q \bigwedge \sim r$	000	0	$m_0$
$\sim p \bigwedge\sim q \bigwedge r$	001	1	$m_1$
$\sim p \bigwedge q \bigwedge \sim r$	010	2	$m_2$
$\sim p \bigwedge q \bigwedge r$	011	3	$m_3$
$p \bigwedge\sim q \bigwedge \sim r$	100	4	$m_4$
$p \bigwedge\sim q \bigwedge r$	101	5	$m_5$
$p \bigwedge q \bigwedge \sim r$	110	6	$m_6$
$p \bigwedge q \bigwedge r$	111	7	$m_7$

Nature:
(1)、For any formula with n propositional variables, the number of all possible minimum terms is the same as the number of interpretations of the formula, and is $2^n$.
(2)、Each minterm is true under only one explanation.
(3)、Minterm are not equivalent, and $m_i \bigwedge m_j\equiv F(i \neq j)$
(4)、Any formula containing n propositional variables can be represented by the disjunction of k $(k \leq 2^n)$ minterms.
(5)、The formula formed by the disjunction of $2^n$ minterms must be tautology.

• A fundamental disjunction is called as a maxterm (极大项) if each of its variables appears exactly once in it.

Disjunctive formula consisting of n propositional variables$P_1,P_2,...P_n$:

$$Q_1\bigvee Q_2\bigvee...\bigvee Q_n$$
where $Q_i=P_i$ or $\sim P_i$. That is, each propositional variable does not appear at the same time as its negation, but one of the two must appear only once, and the I-th propositional variable or its negation appears at the I-th position from the left, then the conjunctive formula ,$Q_1\bigvee Q_2\bigvee...\bigvee Q_n$,is called the maxterm item and is expressed by $M_i$.

There are 2n maxterms of n propositional variables.We denote them as $M_0, M_1, ..., M_{2n-1}$.

Suppose there are three propositional variable p, q and r.

maxterm	represent1	represent2	symbol
$p \bigvee q \bigvee r$	000	0	$M_0$
$p \bigvee q \bigvee \sim r$	001	1	$M_1$
$p \bigvee \sim q \bigvee r$	010	2	$M_2$
$p \bigvee \sim q \bigvee\sim r$	011	3	$M_3$
$\sim p \bigvee q \bigvee r$	100	4	$M_4$
$\sim p \bigvee q \bigvee \sim r$	101	5	$M_5$
$\sim p \bigvee \sim q \bigvee r$	110	6	$M_6$
$\sim p \bigvee \sim q \bigvee \sim r$	111	7	$M_7$

Nature:
(1)、For any formula with n propositional variables, the number of all possible maxterms is the same as the number of interpretations of the formula, and is $2^n$.
(2)、Each maxterm is false under only one explanation.
(3)、Minterm are not equivalent, and $M_i \bigvee M_j\equiv T(i \neq j)$
(4)、Any formula containing n propositional variables can be represented by the conjunction of k $(k \leq 2^n)$ maxterms.
(5)、The formula formed by the conjunction of $2^n$ maxterms must be tautology.

Therefore,we can know the relationship of the minterm and the maxterm:

$$m_i\equiv \sim M_i$$

---

3.5.2 FDNF and FCNF

$$\begin{cases} FDNF, &\text{Full disjunctive normal form is a disjunction of one or more minterms} \\[2ex] FCNF, & \text{Full conjunctive normal form is a conjunction of one or more maxterms} \end{cases}$$

To convert a propositional formula to equivalent formula that is in FDNF:

• STEP1. Convert it to an equivalent DNF.
• STEP2. If one of its fundamental conjunction B does not contain the variable $p_i$ and $\sim p_i$, then add them to B as $B \equiv B\bigwedge (p_i \bigvee \sim p_i) \equiv (B\bigwedge p_i)\bigvee(B\bigwedge \sim p_i)$.
• STEP3. Eliminate the repeated occurrence of literals in a fundamental conjunction, the fundamental conjunction containing complement literals, and the repeated minterms.
• STEP4. Express it using $\sum$.

Note:Suppose the formula A has n propositional variables and $A \equiv \sum(i_l, i_2,…, i_k)$.Then $\sim A \equiv \sum(j_l, j_2, …, j_{2^n-k})$, where $(j_l, j_2, …, j_{2^n-k})= {0, 1, …, 2^n-1}-{i_l, i_2,…, i_k}$.

To convert a propositional formula to equivalent formula that is in FCNF:

• STEP1. Convert it to an equivalent CNF.
• STEP2. If one of its fundamental disjunction B does not contain the variable $p_i$ and $\sim p_i$, then add them to B as $B \equiv B\bigvee (p_i \bigwedge \sim p_i) \equiv (B\bigvee p_i)\bigwedge(B\bigvee \sim p_i)$.
• STEP3. Eliminate the repeated occurrence of literals in a fundamental disjunction, the fundamental disjunction containing complement literals, and the repeated maxterms.
• STEP4. Express it using $\prod$.

Note:
Every propositional formula can be converted into an unique equivalent formula that is in full disjunctive normal form.
Every propositional formula can be converted into an unique equivalent formula that is in full conjunctive normal form.

eg.

求$(p \bigvee(q\bigwedge r))\implies (p \bigvee q \bigvee r)$的主析取范式和主合取范式。

原公式的析取范式是，
$\quad (p \bigvee(q\bigwedge r))\implies (p \bigvee q \bigvee r)$
$\equiv\sim (p \bigvee (q \bigwedge r))\bigvee (p \bigvee q \bigvee r)$
$\equiv\sim p \bigwedge \sim(q \bigwedge r)\bigvee (p \bigvee q \bigvee r)$
$\equiv\sim p \bigwedge (\sim q \bigvee \sim r)\bigvee (p \bigvee q \bigvee r)$
$\equiv(\sim p \bigwedge \sim q )\bigvee (\sim p \bigwedge \sim r )\bigvee p \bigvee q \bigvee r$
$\equiv q\bigvee (\sim p \bigwedge \sim q )\bigvee r \bigvee (\sim p \bigwedge \sim r ) \bigvee p$
$\equiv(q \bigvee \sim p)\bigwedge (q \bigvee \sim q)\bigvee (r \bigvee \sim p)\bigwedge (r\bigvee \sim r)\bigvee p$
$\equiv(q \bigvee \sim p)\bigwedge T \bigvee (r \bigvee \sim p)\bigwedge T \bigvee p$
$\equiv \sim p \bigvee q \bigvee \sim p \bigvee r \bigvee p$
$\equiv T$

故
$\quad (p \bigvee(q\bigwedge r))\implies (p \bigvee q \bigvee r)$
$\equiv\sum(0,1,2,3,4,5,6,7)$

因此，主合取范式为空公式

---

3.6、Inference

Inference is the act or process of deriving logical conclusions from premises known or assumed to be true.

Rules of Inference

rule	symbol
Addition	$A \implies (A \bigvee B)$
Simplification	$(A \bigwedge B)\implies A$
Modus ponens	$(A \implies B)\bigwedge A \implies B$
Modus tollens	$(A \implies B)\bigwedge \sim B\implies \sim A$
Disjunctive syllogism	$(A\bigvee B)\bigwedge \sim B \implies A$
Hypothetical syllogism	$(A \implies B)\bigwedge (B \implies C)\implies (A \implies C)$
Equivalent syllogism	$(A \iff B)\bigwedge (B \iff C)\implies (A \iff C)$

---

3.6.1、Proof by Introducing Additional Premise

用附加前提法证明推理：

• 前提:$(p \bigvee q)\implies (r\bigwedge s),(r\bigvee h)\implies g$
• 结论:$p\implies g$

• $(1)\quad p \qquad\qquad\qquad 附加前提引入$
• $(2)\quad (p \bigvee q) \qquad\qquad\quad \quad附加律$
• $(3)\quad (p \bigvee q)\implies (r\bigwedge s)\quad 前提$
• $(4)\quad r \bigwedge s \qquad \qquad(2)(3)假言推理$
• $(5)\quad r \qquad\qquad\qquad\qquad\quad 化简律$
• $(6)\quad (r\bigvee h) \qquad\qquad\quad \quad附加律$
• $(7)\quad (r \bigvee h)\implies g \qquad\qquad 前提$
• $(8)\quad g \qquad \qquad \qquad(6)(7)假言推理$

推理正确，$p \implies g$是有效结论

---

3.6.2、Proof by Contradiction

用归谬法证明推理：

• 前提:$p \implies \sim q,q \bigvee \sim r,r \bigwedge \sim s$
• 结论:$\sim p$

• $(1)\quad r \bigwedge \sim s \qquad\quad 前提$
• $(2)\quad r \qquad \qquad \quad 化简律$
• $(3)\quad q \bigvee \sim r \qquad \quad前提$
• $(4)\quad q \qquad (2)(3)假言推理$
• $(5)\quad \sim (\sim p) \qquad 否定结论$
• $(6)\quad p \qquad \qquad \quad (5)置换$
• $(7)\quad p \implies \sim q\qquad 前提$
• $(8)\quad \sim q\quad (6)(7)假言推理$
• $(9)\quad q \bigwedge \sim q \quad (4)(8)合取$

由(9)得出矛盾，说明推理正确

---

4、Predicate and Quantifiers

---

4.1、Quantifiers

• Let x be a variable and D be a set; P(x) is a sentence.

Then P(x) is called a predicate or propositional function with respect to the set D if for each value of x in D, P(x) is a statement; i.e., P(x) is true or false.Moreover, D is called the domain of the discourse and x is called the free variable.

• Let x, y be variables and D be a set; P(x, y) is a sentence.

Then P(x, y) is a predicate with respect to the set D if for each value pair of x and y in D, P(x, y) is a statement.Such as Greater(x, y),Equal(x, y).

Predicate P(x) means that x has the property P,while P(x, y) means that x and y have the relation P.

• Let P(x) be a predicate and let D be the domain of the discourse.

The universal quantification of P(x) is the statement: “for all x, P(x)” or “for every x, P(x)” or “for any x, P(x)” The symbol $\forall$ is read as “for all and every”.

• Let P(x) be a predicate and let D be the domain of the discourse.

The existential quantification of P(x) is the statement:“there exists an x, P(x)” or “there is an x, P(x) ” or “there is some x, P(x) ” The symbol $\exists$ is read as “there exists”.

Note:The variable appearing in: $\forall$x P(x) or $\exists$x P(x) is called a bound variable, and P(x) is called the scope of the quantifier.

eg.

All the primes are odd.

• $\forall x (Prime(x)\implies Odd(x))$

Not

• $\forall x (Prime(x)\bigwedge Odd(x))$

“all…are…”: use $\implies$ , not $\bigwedge$

eg.

There is an even prime.

• $\exists x (Even(x)\bigwedge Prime(x))$

Not

• $\exists x (Even(x) \implies Prime(x))$

use $\exists$, not $\implies$.

eg.

There exists an unique even prime.

• $\exists x(P(x)\bigwedge \forall y(P(y)\implies Equal(x,y)))$

---

4.2、Predicate Formulas and Classification

The well-formed formula in predicate logic are inductively defined as follows:
(1) Any variable, constant symbol and a simple predicate is a wff.
(2) If A is a wff, then $(\sim A)$ is also a wff.
(3) If A and B are wffs, then $(A\bigwedge B), (A\bigvee B), (A\implies B),and (A\iff B)$ are also wffs.
(4) If A is a wff and x is a variable which does not bounded occur in A(x), then $\forall x A(x), \exists x A(x)$ are also wffs.

A formula A is logically valid if it is true for every interpretation.
A formula A is unsatisfiable if it is false for every interpretation.
A formula A is satisfiable if it is true for some interpretation.

---

4.3、Equivalent Calculus in Predicate Logic

---

4.3.1、Rules about logical equivalences

Replacement:

Suppose $\Phi(A)$ represents a formula contain formula A as a subformula, and $\Phi(B)$ represents a formula which replace an occurrence of A with a logically equivalent formula B; then $\Phi(A)\equiv \Phi(B)$.

Substitution

Suppose $\Phi$ and $\phi$ are all predicate formulas and $\Phi$ is obtained from $\phi$ by substituting all the occurrence of a free variable by an new variable not appear in $\phi$; then $\Phi =\phi$ .

Renaming

Suppose $\Phi$ and $\phi$ are all predicate formulas and $\Phi$ is obtained from $\phi$ by substituting one bound variable x of $\phi$ by an new variable not appear in its scope; then $\Phi \equiv \phi$ .

---

4.3.2、Basic Laws

Tautologies in predicate logic:

A sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing propositional variables by first-order formulas (one formula per propositional variable).

Elimination of quantifiers

$D=\{a_1,a_2,...,a_m\}$
$\forall x P(x)\equiv P(a_1)\bigwedge P(a_2)\bigwedge ... \bigwedge P(a_m)$
$\exists x P(x)\equiv P(a_1)\bigvee P(a_2)\bigvee ... \bigvee P(a_m)$

Shrink and expansion of scope

The equivalences are valid when x does not appear as a free variable of B.

$\forall$	$\exists$
$\forall x(A(x)\bigvee B)\equiv \forall xA(x)\bigvee B$	$\exists x(A(x)\bigvee \equiv \exists xA(x)\bigvee B$
$\forall x(A(x)\bigwedge B)\equiv \forall xA(x)\bigwedge B$	$\exists x(A(x)\bigwedge B\equiv \exists xA(x)\bigwedge B$
$\forall x(A(x)\implies B)\equiv \exists xA(x)\implies B$	$\exists x(A(x)\implies B\equiv \forall xA(x)\implies B$
$\forall x(B\implies A(x))\equiv B\implies \forall xA(x)$	$\exists x(B\implies A(x))\equiv B \implies \exists x A(x)$

De Morgan’s laws

If x appear as a free variable of A(x), then
$\sim \forall A(x)\equiv \exists x \sim A(x)$
$\sim \exists A(x)\equiv \forall x \sim A(x)$

Distribution of quantifiers

$\forall x(A(x)\bigwedge B(x))\equiv \forall xA(x)\bigwedge \forall xB(x)$
$\exists x(A(x)\bigvee B(x))\equiv \exists xA(x)\bigvee \exists xB(x)$
$\exists x(A(x)\implies B(x))\equiv \forall xA(x)\implies \exists xB(x)$

Note:$\forall$ vs. $\bigvee$,$\exists$ vs.$\bigwedge$

Variable renamed equivalent

$\forall x\forall y(A(x)\bigvee B(y))\equiv \forall xA(x)\bigvee \forall xB(x)$
$\exists x \exists y(A(x)\bigwedge B(y))\equiv \exists xA(x)\bigwedge \exists x B(x)$
$\forall x\exists y(A(x)\bigvee B(y))\equiv \forall xA(x)\bigvee \exists xB(x)$
$\forall x \exists y(A(x)\bigwedge B(y))\equiv \forall xA(x)\bigwedge \exists x B(x)$
$\exists x\forall y(A(x)\bigvee B(y))\equiv \exists xA(x)\bigvee \forall xB(x)$
$\exists x \forall y(A(x)\bigwedge B(y))\equiv \exists xA(x)\bigwedge \forall x B(x)$

Equivalence for Quantizing Predicate Arguments Many Times

$\forall x\forall yP(x,y)\equiv \forall y\forall xP(x,y)$
$\exists x\exists yP(x,y)\equiv \exists y \exists xP(x,y)$

eg.

证明:$\sim(\forall x)((\exists y)L(x,y)\implies (\forall y)H(x,y))\equiv (\exists x)(\exists y)(\exists z)(L(x,y)\bigwedge \sim H(x,z))$

$Prove:$

• (1) 消去联结词 $\implies$得

$\sim(\forall x)((\exists y)L(x,y)\implies (\forall y)H(x,y))$
$\equiv \sim (\forall x)(\sim (\exists y)L(x,y)\bigvee (\forall y)H(x,y))$

• (2) $\sim$内移(使用德摩根律),得

$\sim (\forall x)(\sim (\exists y)L(x,y)\bigvee (\forall y)H(x,y))$
$\equiv (\exists x)\sim(\sim(\exists y)L(x,y)\bigvee (\forall y)H(x,y))$
$\equiv (\exists x)((\exists y)L(x,y)\bigwedge \sim (\forall y)H(x,y))$
$\equiv (\exists x)((\exists y)L(x,y)\bigwedge (\exists y)\sim H(x,y))$

• (3) 变元易名,得

$(\exists x)((\exists y)L(x,y)\bigwedge (\exists y)\sim H(x,y))$
$\equiv (\exists x)((\exists y)L(x,y)\bigwedge (\exists z)\sim H(x,z))$
$\equiv (\exists x)(\exists y)(\exists z)(L(x,y)\bigwedge \sim H(x,z))$

eg.

证明:$\sim(\forall x)((\exists y)L(x,y)\implies (\forall y)H(x,y))\equiv (\exists x)(\exists y)(\exists z)(L(x,y)\bigwedge \sim H(x,z))$

$Prove:$

• (1) 消去联结词 $\implies$得

$\sim(\forall x)((\exists y)L(x,y)\implies (\forall y)H(x,y))$
$\equiv \sim (\forall x)(\sim (\exists y)L(x,y)\bigvee (\forall y)H(x,y))$

• (2) $\sim$内移(使用德摩根律),得

$\sim (\forall x)(\sim (\exists y)L(x,y)\bigvee (\forall y)H(x,y))$
$\equiv (\exists x)\sim(\sim(\exists y)L(x,y)\bigvee (\forall y)H(x,y))$
$\equiv (\exists x)((\exists y)L(x,y)\bigwedge \sim (\forall y)H(x,y))$
$\equiv (\exists x)((\exists y)L(x,y)\bigwedge (\exists y)\sim H(x,y))$

• (3) 变元易名,得

$(\exists x)((\exists y)L(x,y)\bigwedge (\exists y)\sim H(x,y))$
$\equiv (\exists x)((\exists y)L(x,y)\bigwedge (\exists z)\sim H(r,z))$
$\equiv (\exists x)(\exists y)(\exists z)(L(x,y)\bigwedge \sim H(r,z))$

---

4.4、Prenex Normal Form

A formula of the predicate calculus is in prenex normal form if it is written as a string of quantifiers (referred to as the prefix) followed by a quantifierfree part (referred to as the matrix)

$Q_1 x_1 Q_2 x_2 ... Q_n x_n M(x_1, x_2, ..., x_n)$
where $Q_i(1...i...n)$ is $\forall$ or $\exists$.Every formula in predicate logic is equivalent to a formula in prenex normal form. However, the equivalent prenex normal form is not unique.

The Basic Steps to seek Prenex Normal Form:

• STEP1. Eliminate implications and equivalences.
• STEP2. Right shift all negations inside the scope of each quantifiers.
• STEP3. Move the quantifiers to the leftmost.
• STEP4. Rename the variables if necessary.

eg.

求 $\exists xF(x,y)\implies (G(x)\implies \sim \exists yH(x,y))$的前束范式

• (1) 消去联结词 $\implies$得

$\exists xF(x,y)\implies (G(x)\implies \sim \exists yH(x,y))$
$\equiv \sim \exists xF(x,y)\bigvee (\sim G(x)\bigvee \sim \exists yH(x,y))$

• (2) $\sim$内移(使用德摩根律),得

$\sim \exists xF(x,y)\bigvee (\sim G(x)\bigvee \sim \exists yH(x,y))$
$\equiv \forall x\sim F(x,y)\bigvee (\sim G(x)\bigvee \forall y \sim H(x,y))$

• (3) 变元易名,得

$\forall x\sim F(x,y)\bigvee (\sim G(x)\bigvee \forall y \sim H(x,y))$
$\equiv \forall x\sim F(x,y)\bigvee (\sim G(x)\bigvee \forall z \sim H(t,z))$
$\equiv (\forall x )\sim F(x,y)\bigvee((\forall z) \sim G(x)\bigvee\sim H(t,z))$
$\equiv (\forall x )(\forall z)(\sim F(x,y)\bigvee \sim G(x)\bigvee\sim H(t,z))$
$\equiv (\forall x )(\forall z)S(t,x,y,z)$

---

4.5、Inference in Predicate Calculus

Universal Instantiation (or Universal Elimination, or Universal Specification)

$\forall x P(x) \implies P(y), or \forall x P(x) \implies P(a)$

Restriction

• No bounded occurrence of y in P(x).
• a is a constant.

Universal Generalization (or Universal Introduction)

$P(y) \implies \forall x P(x)$

Restriction

• y is not mentioned in any hypothesis or undischarged assumptions.
• x is a variable which does not occur in P.

Existential Instantiation (or Existential Elimination or Existential Specification)

$\exists x P(x) \implies P(a)$

Restriction

• a is a variable which does not occur in P(x).
• There is no free occurrence of other variables in P(x).
• a must be a new term that has not occurred earlier in the proof.

Existential Generalization (or Existential Introduction)

$P(a) \implies \exists x P(x)$

Restriction

• No occurrence x in P(a).

构造下列推理的证明:

• 如果一个人怕困难，他就不会获得成功。所有的人或者获得成功，或者失败。有些人没有失败。所以，有些人不怕困难。

引入谓词将这三句话形式化，可得如下推理形式:

设定:
$A(x):x怕困难,$
$B(x):x成功,$
$C(x):x失败;$

• 前提:$(\forall x)(A(x)\implies \sim B(x)),(\forall x )(B(x)\bigvee C(x)),(\exists x)(\sim C(x))$
• 结论:$(\exists x)(\sim (A(x)))$

(1) $(\forall x)(A(x)\implies \sim B(x))$
(2) $A(c)\implies \sim B(c)$
(3) $A(c)$
(4) $(\forall x )(B(x)\bigvee C(x))$
(5) $B(c)\bigvee C(c)$
(6) $(\exists x)(\sim C(x))$
(7) $\sim C(c)$
(8) $B(c)$
(9) $\sim A(c)$
(10) $(\exists x)(\sim (A(x)))$

---

5、Set

---

5.1、What's set?

A set is an well-defined collection of objects.Individual items in a set are called elements or members.

NOTE: there is no relationship between different elements of a general set.

---

5.2、Sets and Subsets

We write $x\in A$ to say that element x belongs to the set A.The set with NO elements is called the empty set and denoted by $\Phi$.

We designate by card(A) or |A| the cardinality of a set A, which is the number of distinct element in A.

---

5.2.1、Superset and Subset

Given two sets A and B ,if every element in A is an element of B ,we say that A is a subset of B or that A is contained in B,and B is a superset of A,and we write $A \subseteq B$

---

5.2.2、Power Set

Let A be a set. Then set of all subsets in A is called the power set of A and is denoted as P (A).For finite A, | P (A) | =$2^n$.

---

6、Something I Want to Share

---

6.1、About class

Discrete mathematics is one of the major courses for software engineering majors. In the past four weeks of study, we have learned about set and logic. In the previous knowledge combing, since the collected knowledge was repeatedly studied in high schools and universities, only a few basic and important concepts were combed, and the knowledge of logic part was thoroughly combed. In the process of learning and combing logic knowledge, I have been thinking about the importance and necessity of logic for software development and project management. At first, I didn't think of the importance of logic for software engineering. With the constant clarification of knowledge, I gradually realized that logical thinking is helpful to the algorithm design and overall design mode of software project development, and it is also helpful to transform complex requirements into abstract logical thinking. As we have said in class, simple and abstract algorithms are as important to software as universally valid formulas.

As for the teacher's teaching mode, I am very happy that the teacher can share with us cutting-edge knowledge and hot technologies. Although we may not be able to understand or make great efforts to study some technologies, such teaching mode also helps us to understand knowledge.

However, it is hoped that teachers can appropriately increase the amount and difficulty of homework in the subsequent teaching so as to understand and apply knowledge more effectively.

---

6.2、About me

Since entering the university, I have met many teachers who are responsible for friendship and students who are active and enterprising. Such an environment also makes me continuously improve. Of course, under such circumstances, there will inevitably be some pressure. As the teacher said, our present age is not suitable for labeling ourselves. We should enrich ourselves by learning more. Whether it is to improve their professional level, enrich their knowledge, or enjoy the scenery of the four seasons, universities should do something meaningful. The flower has a re-opening day, and there are no more teenagers. I think we should all live in this way, and when we wake up in the morning, we can all expect something.