本文由Hobee原创，并仅在本站发表，仅供各位小伙伴学习交流使用。
为避免不必要的纠纷，本文禁止以任何形式转载，谢谢配合。
如有问题请通过评论区或邮件联系作者。
本文封面源于网络，侵删。
系列文章传送门：
写在前面
众所周之，hobee在数学的学习方面就宛如一只菜鸡，只好通过不断复习和整理的途径来巩固自己辣鸡的数学成绩。主要是我真的什么也不会了啊（哭哭脸…那就从这里开始吧！
因为考核是候题目是英文的，所以我的整理也就用英文来叭（我也不想啊…
中英术语对照表
为了防止之后我自己都看不明白，在梳理知识点之前我先写一份中英术语对照表好了。
Key Terms
| English | Chinese | English | Chinese | English | Chinese |
|---|---|---|---|---|---|
| Proposition | 命题 | Propositional variable | 命题变量 | Truth value | 真值 |
| Negation | 否定 | Logical operators | 逻辑运算符 | Compound proposition | 复合命题 |
| Truth table | 真值表 | Disjunction | 析取 | Conjunction | 合取 |
| Exclusive or | 异或 | Implication | 蕴含 | Converse | 逆 |
| Contrapositive | 逆否 | Inverse | 反 | Biconditional | 双蕴含 |
| Tautology | 永真式 | Contingency | 可能 | Logically equivalent | 逻辑等价 |
| Predicate | 谓词 | Propositional function | 命题函数 | Domain of discourse | 论域 |
| Existential quantifier | 存在量词 | Universal quantifier | 全称量词 | Free variable | 自由变元 |
| Bound variable | 约束变量 | Scope of a quantifier | 量词的作用域 | Argument | 参数 |
| Argument form | 参数形式 | Premise | 条件 | Conclusion | 结论 |
| Valid argument form | 合法参数形式 | Rule of inference | 推理规则 | Fallacy | 谬误 |
| even | 偶数 | odd | 奇数 |
Results
Proposition and Logic
Propositional Logic
Propositions
A proposition is a declarative sentence that is either true or false.
The proposition that is always true is denoted by $T$ and the proposition that is always false is denoted by $F$ .
Propositional Variables: $p,q,r,s\dots$
Connectives
Compound Propositions is constructed from logical connectives and other propositions.
Negation
The negation of a proposition $p$ is denoted by $\neg p$ and the truth table is as follow:
| $p$ | $\neg p$ |
|---|---|
| $T$ | $F$ |
| $F$ | $T$ |
Conjunction
The conjunction of propositions $p$ and $q$ is denoted by $p \wedge q$ and the truth table is as follow:
| $p$ | $q$ | $p \wedge q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |
Disjunction
Inclusive Or
The disjunction of propositions $p$ and $q$ is denoted by $p \vee q$ and the truth table is as follow:
| $p$ | $q$ | $p \vee q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
Exclusive Or (Xor)
The exclusive Or of propositions $p$ and $q$ is denoted by $p \oplus q$ and the truth table is as follow:
| $p$ | $q$ | $p \vee q$ |
|---|---|---|
| $T$ | $T$ | $F$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
Implication
The implication of propositions $p$ and $q$ is denoted by $p \rightarrow q$ which is read as “if $p$ , then $q$ “and the truth table is as follow:
| $p$ | $q$ | $p \rightarrow q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |
More ways to express $p \rightarrow q$:
- if $p$ , then $q$ or if $p$ , $q$
- $q$ unless $\neg p$
- $q$ if $p$ or $p$ only if $q$
- $p$ implies $q$
- $q$ follows from $p$
- $q$ whenever $p$ or $q$ when $p$
- $q$ is necessary for $p$ or $p$ is sufficient for $q$
Contrapositive
$\neg q \rightarrow \neg p$ is the contrapositive of $p \rightarrow q$
Inverse
$\neg p \rightarrow\neg q$ is the inverse of $p \rightarrow q$
converse
$q \rightarrow p$ is the converse of $p \rightarrow q$
Biconditional
The biconditional of propositions $p$ and $q$ is denoted by $p \leftrightarrow q$ which is read as “$p$ if and only if $q$ “and the truth table is as follow:
| $p$ | $q$ | $p \leftrightarrow q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $T$ |
More ways to express $p \leftrightarrow q$:
- $p$ is necessary and sufficient for $q$
- if $p$ then $q$ , and conversely
- $p$ iff $q$
**The precedence of logical connectives: **
$\neg >\wedge > \vee > \rightarrow > \leftrightarrow$
Propositional Equivalences
Tautologies,Contradictions, and Contingencies
Tautologies
A tautology is a proposition which is always true.
For example: $p \vee \neg p$
Contradictions
A contradiction is a proposition which is always false.
For example:$p \wedge \neg p$
Contingencies
A contingency is a proposition which is neither a tautology nor a contradiction.
For example: $p$
Logical Equivalences
We say two compound propositions $p$ and $q$ are logically equivalent if $p\leftrightarrow q$ is a tautology or they have the same truth table.
We write this as $p \Leftrightarrow q$ or as $p\equiv q$ where $p$ and $q$ are compound propositions
Important Logical Equivalences
De Morgan’s Law
First Law: $\neg(p\wedge q)\equiv \neg p \vee \neg q$
Second Law: $\neg(p\vee q)\equiv \neg p \wedge\neg q$
Identity Laws
$p\wedge T\equiv p$ , $p\vee F\equiv p$
Domination Laws
$p\vee T\equiv T$ , $p\wedge F\equiv F$
Idempotent Laws
$p\wedge p\equiv p$ , $p\vee p\equiv p$
Double Negation Laws
$\neg(\neg p)\equiv p$
Negation Laws
$p\wedge \neg p \equiv F$ , $p\vee \neg p\equiv T$
Commutative Laws
$p\vee q\equiv q\vee p$ , $p\wedge q\equiv q\wedge p$
Associative Laws
$(p\wedge q)\wedge r\equiv q\wedge (p \wedge r)$ , $$(p\vee q)\vee r\equiv q\vee (p \vee r)$$
Distributive Laws
$(p\vee(q\wedge r))\equiv(p\vee q)\wedge(p\vee r)$ , $(p\wedge(q\vee r))\equiv(p\wedge q)\vee(p\wedge r)$
Absorption Laws
$p\vee(p\wedge q)\equiv p$ , $p\wedge(p\vee q)\equiv p$
More Logical Equivalences
$p\rightarrow q\equiv\neg p \vee q$
$p\leftrightarrow q \equiv (p\wedge q)\vee(\neg p\wedge\neg q)$
Normal Forms (Not So Important)
Disjunctive Normal Form
A compound proposition is Disjunctive Normal Form (DNF) if it is a disjunction of conjunctions.
Conjunctive Normal Form
A compound proposition is Conjunctive Normal Form (CNF) if it is a conjunction of disjunctions.
Propositional Satisfiability
A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. When no such assignments exist, the compound proposition is unsatisfiable. That mean a compound proposition is unsatisfiable iff it is a contingency.
Applications of Propositional Logic
Translating English Sentences
A list of propositions is consistent if there is an assignment of truth values to its variables that make all of them true. When no such assignments exist, the list of propositions is inconsistent.
Boolean Search
Logic Puzzles
Use Propositional Satisfiability to get the solution.
Logic Circuits
0 for False
1for True
Predicate Logic
Introducing Predicate Logic
Predicates : $P(x),M(x)$
Variables : $x,y,z$
Quantifiers : $\forall \quad \exists$
Propositional functions
Propositional functions are a generalization of propositions.
Variables can be replaced by elements from their domain.
Propositional functions become propositions when their variables are each replaced by a value from the domain.
The domain is often denoted by $U$.
Quantifiers
Universal Quantifier
for all , $\forall$
$\forall x P(x)$ asserts $P(x)$ is true for every $x$ in the domain.
means conjunction.
Existential Quantifier
for some , $\exist$
$\exist x P(x)$ asserts $P(x)$ is true for some $x$ in the domain.
means disjunction.
Uniqueness Quantifier
for one and only one , $\exist !$
$\exist !x P(x)$ asserts $P(x)$ is true for one and only one $x$ in the domain.
The uniqueness quantifier can be expressed as: $\exist x (P(x) \wedge \forall y (P(y)\rightarrow y = x))$
Quantifiers with Restricted Domains
The restriction of a universal quantification is the same as the universal quantification of a conditional statement.
e.g. $\forall x < 0 (x^2>0)$ is the same as $\forall x (x<0\rightarrow x^2 >0)$
The restriction of an existential quantification is the same as the universal quantification of a conjunction.
e.g. $\exist z>0(z^3=2)$ is the same as $\exist z(z>0\wedge z^2 = 2)$
Precedence of Quantifiers
The quantifiers $\forall$ and $ \exist$ have higher precedence than all the logical operators.
Equivalences in Predicate Logic
Statements involving predicates and quantifiers are logically equivalent iff they have the same truth value.
De Morgan’s Laws for quantifiers
$\neg\forall x P(x) \equiv \exist x\neg P(x)$
$\neg\exist x P(x) \equiv \forall x\neg P(x)$
Translating English to Logic
Notice the domain !
Nested Quantifiers
Nested quantifiers are quantifiers where one quantifier is within the scope of another.
The order of the quantifiers is important , unless all the quantifiers are the same.
Rules of Inference
Valid Arguments
All but the final proposition are called premises. The last statement is the conclusion.
We can express the premises and the conclusion in predicate logic as an argument.
The argument is valid if the premises imply the conclusion.
if the premises are $p_1 , p_2 ,\dots,p_n$ and the conclusion is $q$ ,then $(p_1 \wedge p_2 \wedge\dots\wedge p_n)\rightarrow q$ is a tautology.
Rules of Inference for Propositional Logic
Modus Ponens
$$
\begin{align}
&p \rightarrow q \
&p \
\hline
&\therefore q \
\end{align}
$$
Corresponding Tautology : $(p\wedge(p\rightarrow q))\rightarrow q$
Modus Tollens
$$
\begin{align}
&p \rightarrow q \
&\neg q \
\hline
&\therefore\neg p \
\end{align}
$$
Corresponding Tautology : $(\neg q\wedge(p\rightarrow q))\rightarrow \neg p$
Hypothetical Syllogism
$$
\begin{align}
&p \rightarrow q \
&q \rightarrow r \
\hline
&\therefore p \rightarrow r \
\end{align}
$$
Corresponding Tautology : $((p \rightarrow q)\wedge(q \rightarrow r))\rightarrow (p \rightarrow r)$
Disjunctive Syllogism
$$
\begin{align}
&p \vee q \
&\neg p \
\hline
&\therefore q \
\end{align}
$$
Corresponding Tautology : $(\neg p \wedge(p \vee q))\rightarrow q$
Addition
$$
\begin{align}
&p \
\hline
&\therefore p \vee q \
\end{align}
$$
Corresponding Tautology : $(p\rightarrow (p \vee q)$
Simplification
$$
\begin{align}
&p \wedge q \
\hline
&\therefore p \
\end{align}
$$
Corresponding Tautology : $(p \wedge q)\rightarrow p $
Conjunction
$$
\begin{align}
&p \
&q \
\hline
&\therefore p \wedge q \
\end{align}
$$
Corresponding Tautology : $((p)\wedge(q))\rightarrow (p \wedge q)$
Resolution
$$
\begin{align}
&\neg p \vee r\
&p\vee q \
\hline
&\therefore q \vee r \
\end{align}
$$
Corresponding Tautology : $((\neg p \vee r)\wedge(p\vee q))\rightarrow (q \vee r)$
Rules of Inference for Quantified Statements
Universal Instantiation
$$
\begin{align}
&\forall xP(x) \
\hline
&\therefore P(c) \
\end{align}
$$
Universal Generalization
$$
\begin{align}
&P(c) \text{ for an arbitrary } c \
\hline
&\therefore \forall xP(x) \
\end{align}
$$
Universal Modus Ponens
$$
\begin{align}
&\forall x(P(x)\rightarrow Q(x)) \
&P(a) \text{ where $a$ is a particular element in the domain } \
\hline
&\therefore Q(a) \
\end{align}
$$
Existential Instantiation
$$
\begin{align}
&\exist xP(x) \
\hline
&\therefore P(c) \text{ for some element } c \
\end{align}
$$
Existential Generalization
$$
\begin{align}
&P(c) \text{ for some element } c \
\hline
&\therefore \exist xP(x) \
\end{align}
$$
Common fallacies
Fallacy of affirmative conclusion
$((p\rightarrow q)\wedge q)\rightarrow p$
Fallacy of negative hypothesis
$((p\rightarrow q)\wedge \neg p)\rightarrow \neg q$
