The Foundations: Logic and Proofs

在本章中，我们将阐释构成正确数学论证的要素，并介绍构建这些论证的工具。我们将建立一系列不同的证明方法，这些方法将使我们能够验证多种类型的数学结论。在介绍多种证明方法后，我们将探讨构建数学证明的若干策略。此外，我们将提出猜想的概念，并阐述通过研究猜想推动数学发展的完整过程。

In this chapter, we will explain what makes up a correct mathematical argument and introduce tools to construct these arguments. We will develop an arsenal of different proof methods that will enable us to prove many different types of results. After introducing many different methods of proof, we will introduce several strategies for constructing proofs. We will introduce the notion of a conjecture and explain the process of developing mathematics by studying conjectures.

Propositional Logic 命题逻辑

Propositions 命题

• proposition : a declarative sentence (either true or false).
  • propositional variables (or sentential variables) : use letters to present propositions ( \(p\) , \(q\) , \(r\) , \(s\) ...). \(T\) denote true. \(F\) denote false.
  • atomic propositions : Propositions that cannot be expressed in terms of simpler propositions.

Connectives 逻辑连接词

Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators (also called connectives).

• negation : \(\lnot p\) , is the statement It is not the case that p.

Note

It also denoted by \(\bar{p}\), \(\sim p\) , \(p'\) , \(Np\) , \(!p\) .

Example

negation example 1negation example 2

Find the negation of the proposition Michael's PC runs Linux.

Solution

It is not the case that Michael's PC tuns Linux.

Michael's PC does not run Linux.

Find the negation of the proposition Vandana's smartphone has at least 32 GB of memory.

Solution

It is not the case that Vandana's smartphone has at least 32 GB of memory.

Vandana's smartphone does not have at least 32 GB of memory.

Vandana's smartphone has less than 32 GB of memory.

• conjunction : \(p \land q\) , the proposition p and q.

Example

Find the conjunction of the propositions Rebecca's PC has more than 16 GB free hard disk space. and The processor in Rebecca's PC runs faster than 1GHz.

Solution

Rebecca's PC has more than 16 GB free hard disk space, and the processor in Rebecca's PC runs faster than 1GHz.

Rebecca's PC has more than 16 GB free hard disk space, and its processor runs faster than 1GHz.

• disjunction : \(p \lor q\) , the proposition p or q (inclusive or).

Example

disjunction example 1disjunction example 2

Translate the statement Students who have taken calculus or introductory computer science can take this class in a statement in propositional logic using \(p\) : A student who has taken calculus can take this class and \(q\) : A student who has taken introductory computer science can take this class.

Solution

\(p \lor q\) or disjunction of p and q

What's the disjunction of the propositions in conjunction's example?

Solution

Rebecca's PC has more than 16 GB free hard disk space, or the processor in Rebecca's PC runs faster than 1GHz.

• exclusive or : \(p \oplus q\)

Note

It also denoted by \(p\) \(XOR\) \(q\).

Example

exclusive or example 1exclusive or example 2

What is the exclusive or of A student can have a salad with dinner. and A student can have soup with dinner.?

Solution

A student can have soup or salad, but not both, with dinner.

Warning

Note that this is often stated as A student can have soup or salad with dinner without explicitly stating that taking both is not permitted.

Express the statement I will use all my savings to travel to Europe or tu buy an electric car. in propositional logic using the statement \(p\) : I will use all my savings to travel to Europe. and the statement \(q\) : I will use all my savings to buy an electric car.

Solution

Student cannot both go to Europe and buy an electric car. Hence this can be expressed as

\[p \oplus q\]

Applications of Propositional Logic 命题逻辑的应用

Translating English Sentences into logical expressions

System Specifications

Systems specifications should be consistent, that is if it is possible to assign truth values to the proposition variables so that each proposition is true.

Example

Are there specifications consistent? The diagnostic message is stored in the buffer or it is retransmitted The diagnostic message is not stored in the buffer If the diagnostic message is stored in the buffer, then it is retransmitted

Solution

Let \(p\) denote The diagnostic message is stored in the buffer. and \(q\) denote The diagnostic message is retransmitted. The specifications can be written as

\[p \lor q, \lnot p, p \to q\]

they are all true if and only if \(p\) is false and \(q\) is true.

What if The diagnostic message is not retransmitted is added?

Solution

new specification is

\[\lnot q\]

which is false when \(q\) is true. Consequently, they are inconsistent.

boolean searched

Example

• Web Page Serching : For instance, using Boolean searching to find Web pages about universities in New Mexico, we can look for pages matching NEW AND MEXICO AND UNIVERSITIES.

logic puzzles

Example

logic puzzles example 1logic puzzles example 2

There is an island that has two kinds of inhabitants, knights, who always tell the truth, and their opposites, knaves, who always lie.

\(A\) say B is a knight.

\(B\) say we are opposite types.

What are \(A\) and \(B\) ?

Solution

Let \(p\) and \(q\) be the statements that A is a knight and B is a knight

• if \(p\) is true, then \(q\) is true, then \((p \land q) \lor (\lnot p \land q)\) is true, which is not.
• if \(p\) is false, then \(q\) is false, then \((p \land q) \lor (\lnot p \land q)\) is false.

So we can conclude that both \(A\) and \(B\) are knaves.

www.why3.org/doc/whyml.html#problem-o-einsteins-problem

Inreoduction to Proofs

• direct proof : use rule of inference axioms and logical equivalences to show that \(q\) must also true.
• proof by contraposition 反证法 : \(p \to q \equiv \lnot q \to \lnot p\)
• proof by contradiction 归谬证明法 : \(\text{T} \to p \equiv \lnot p \to \text{F}\)
• \(p \leftrightarrow q \equiv p \to q \land q \to p\)

Proof Methods and Strategy

• proof by cases : \((\bigvee_{i=1}^n p_i) \to q \equiv \bigwedge_{i=1}^n p_i \to q\)
• similarly : 同理可得
• without loss of generality（WLOG）: 不失一般性
• existence proofs
• constructive
• no constructive : no \(c\) exists which makes \(P(c)\) true and derive a contradiction.
• counter examples
• Uniqueness proofs : existence + uniqueness
• backward reasoning
• universally quantified assertion

评论