10.14 Propositions and Quantifiers

Propositions

Definition

It's a sentence that must be true or false

Denotation

\(P,Q,R\) as propositions

SYMBOL	IT READS	NAME	TRUE IF	FALSE IF
\(\sim P\)​	not \(P\)​	the negation of \(P\)​	If \(P\) is F	\(P\) is True
\(P\wedge Q\)​	\(P\) and \(Q\)​	conjunction	If both \(P\) and \(Q\) are true	otherwise
\(P\vee Q\)​	\(P\) or \(Q\)​	disjunction	otherwise	\(P\) and \(Q\) are both false
\(P\Rightarrow Q\)​	If \(P\) then \(Q\)​	conditional	otherwise	\(P\) is true and \(Q\) is false
\(P\Leftrightarrow Q\)​	\(P\) iff Q (if and only if)	biconditional	\(P\) and \(Q\) are true or \(P\) and \(Q\) are false	otherwise

Terminology (术语) for conditional

\(P\Rightarrow Q\) (\(P\) is antecedent and \(Q\) is consequent) \(\begin{cases}Q\Rightarrow P\text { the converse}\\\sim Q\Rightarrow \sim P\text{ the contrapositive}\end{cases}\)​

The contrapositive is equivalent to the original proposition

Propositional forms

They are sentences like \(P\vee Q,P\wedge Q\vee R,...\) which don't have true or false

They will become propositions (have true or false) when we replace the denotation like above with real propositions

Note

but, while, and although are usually translated into conjunction since they have the same meaning as and.

Truth table

\(P\)​	\(\sim P\)​
T	F
F	T

\(P\)	\(Q\)	\(P\wedge Q\)	\(P \vee Q\)	\(P\Rightarrow Q\)	\(P\Leftrightarrow Q\)
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

Tautology

It is a propositional form whose truth table has only true

Example

\(P\)​	\(\sim P\)​	\(P~~\vee \sim P\)​
T	F	T
F	T	T

Contradiction

It is a propositional form that is always false

Example

\(P\)​	\(\sim P\)​	\(P~~\wedge\sim P\)​
T	F	F
F	T	F

Equivalence of propositions

Two propositions are equivalent if they have the same truth table

We denote it as \(\equiv\) (equivalent)

Theorem

1

1. \(\sim(\sim P)\equiv P\)

2. \(P\wedge Q\equiv Q\wedge P\)​

3. \(P\vee Q\equiv Q\vee P\)​

4. \(P\vee(Q\vee R)\equiv\left(P\vee Q\right)\vee R\)

5. \(P\wedge(Q\wedge R)\equiv\left(P\wedge Q\right)\wedge R\)​​

6. \(P\wedge(Q\vee R)\equiv\left(P\wedge Q\right)\vee\left(P\wedge R\right)\)

7. \(P\vee(Q\wedge R)\equiv\left(P\vee Q\right)\wedge\left(P\vee R\right)\)​​

8. \(\sim(P\vee Q)\equiv\left(\sim P\right)\wedge\left(\sim Q\right)\)

9. \(\sim(P\wedge Q)\equiv\left(\sim P\right)\vee\left(\sim Q\right)\)​

6 and 7 are distributive laws

8 and 9 are De Morgan's laws

All can be proved by truth table easily

Application

It is useful to write negations

Either '\(2^{16}+1\) is prime' or 'it is divisible by \(7\)' but 'it is not divisible by \(49\)'

The form is \(P\vee(Q~~\wedge \sim R)\)

‍

Then, write a negation

\(\sim\left(P\vee(Q~~\wedge\sim R\right))\equiv\sim P\wedge\sim\left(Q\wedge\sim R\right)\equiv\sim P\wedge\left(\sim Q\vee\sim\left(\sim R\right)_{}\right)\\\equiv\sim P\wedge\left(\sim Q\vee R\right)\equiv\left(\sim P\right)\wedge\left(\sim Q\right)\vee\left(\sim P\right)\wedge R\)

Into natural sentence: '\(2^{16}+1\) is not prime' and 'it is not divisible by \(7\)' or '\(2^{16}+1\) is not prime' and 'it is not divisible by \(49\)'

2

From Denotation we can conclude that: \(P\Rightarrow Q\equiv \sim P\vee Q\)

"If \(P\) then \(Q\)" can be seen as saying either "\(P\) is false" or "\(Q\) is true" (i.e., \(\sim P\) or \(Q\)).

1. \(P\Rightarrow Q\equiv\sim Q\Rightarrow\sim P\equiv\sim P\vee Q\)​

2. \(\sim\left(P\Rightarrow Q\right)\equiv P\wedge\sim Q\)​

3. \(P\Leftrightarrow Q\equiv\left(P\Rightarrow Q\right)\wedge\left(Q\Rightarrow P\right)\)​

4. \(P\Rightarrow\left(Q\Rightarrow R\right)\equiv\left(P\wedge Q\right)\Rightarrow R\)​

5. \(P\Rightarrow\left(Q\wedge R\right)\equiv\left(P\Rightarrow Q\right)\wedge\left(P\Rightarrow R\right)\)​

6. \(P\Rightarrow\left(Q\vee R\right)\equiv\left(P\Rightarrow Q\right)\vee\left(P\Rightarrow R\right)\)​

Quantifiers

Definition

Open propositions

Sentences like "\(x^2>3\)", "\(x^2+y^2=1\)"

Universe of diverse of an open proposition

\(P(x)\). It is a set \(A\) such that \(P(a)\) is a proposition whenever \(a\in A\)

The set \(\left\lbrace a\in A:P\left(a\right)\text{ is true}\right\rbrace\) is called the true set

Example

\(P(x):"x^2>3"\)

Universe \(\N\) and true set is \(\left\lbrace2,3,4,\ldots\right\rbrace\)

Universe \(\R\) and true set is \((\sqrt3,\infty)\)

Equivalence of open propositions

If two open propositions have the same true set (in that universe), they are equivalent in a given universe.

or

If two open propositions are equivalent, they are equivalent in any universe.

Example

Consider \("x^2<1"\) and \("x=0"\)

	True set of \("x^2<1"\)​	True set of \("x=0"\)​	Equivalent over ...
over \(\Z\)​	\(\left\lbrace0\right\rbrace\)​	\(\left\lbrace0\right\rbrace\)​	\(\checkmark\)​
over \(\R\)​	\((-1,1)\)​	\(\left\lbrace0\right\rbrace\)​	\(×\)​

\("x^2<1"\) and \("x=0"\) are not equivalent

Quantified propositions

Given an open \(P(x)\) and a universe \(U\), we define

PROPOSITION	HOW IT READS	WHEN IT IS TRUE
\((\exists x)P(x)\)	There exists \(x\in U\) such that \(P(x)\)	True set \(\neq \emptyset\)
\((\forall x)P(x)\)	For all \(x\in U\), \(P(x)\) or For any \(x\in U\), \(P(x)\)	True set \(= U\)
\((\exists!x)P(x)\)	There is a unique \(x\) in \(U\), such that \(P(x)\)	True set has only one element

\((\exists!x)A(x)\text{ is equivalent to }(\exists x)A(x)\wedge(\forall y)(\forall z)(A(y)\wedge A(z)\Rightarrow y=z)\)

Some names

\(\exists\) existential quantifier

\(\forall\) universal quantifier

\(\exists !\) unique existential quantifier

Example

1. \(\left(\exists x\right)x^2=1\begin{cases}\text{True if universe is }\mathbb{N}\\ \text{False if universe is \textbraceleft2,3,4\textbraceright}\end{cases}\)​

2. \(\left(\exists!x\right)x^2=1\begin{cases}\text{True if universe is }\mathbb{N}\\ \text{False if universe is }\Z\end{cases}\)

Equivalence of quantified sentence

If two quantified sentences have the same true value (in that universe), they are equivalent in a given universe.

or

If two quantified sentences are equivalent in all universe, they are equivalent.

Example

\(\left(\forall x\right)x>1\) and \(\left(\forall x\right)x\geq2\begin{cases}\text{in }\R \text{ they are equivalent since they are both false }\\\text{in }(1,\infty) \text{ they are not equivalent}\end{cases}\)

Theorem

1. \(\sim (\forall x)P(x)\equiv (\exists x)\sim P(x)\)​

2. \(\sim(\exists x)P(x)\equiv(\forall x)\sim P(x)\)

Example

Write a denial for "All primes are odd"

\(\left(\forall x\in Z\right)\left(x~prime\Rightarrow x~is~odd\right)\)​

\(\left(\forall x\right)\left(P\left(x\right)\Rightarrow Q\left(x\right)\right)\)

\(\sim(\forall x)(P\left(x)\right.\Rightarrow Q(x))\equiv(\exists x)(\sim(P(x)\Rightarrow Q(x)))\equiv(\exists x)(P(x)\land\sim Q(x))\)​

Into English: There exists an integer \(x\) that is prime but it is not odd.