[Discrete Mathematics] lecture 1 - Basics of Logic

* 원본 포스팅은 여기를 참조해주세요

What is logic?

A formal system for describing knowledge and implementing reasoning on knowledge.

Logic is just like a language. But as it is used for reasoning, it eleminates ambiguity.

Just like a language, it consistof syntax and semantics. Syntax is the rules for constructing sentences, and semantics is the meaning of the sentences. But in logic, there is a set of rules for deducing the entailments of a set of sentences.

Propositional Logic

Propositional logic treats simple sentences aa atomic entities. By making use of boolean connectives, we can construct complex sentences from simple ones.

Definition 1.

A proposition is an assertion, a declarative sentence with a definite meaning, having a truth value that is either true or false.

1. A propositional variable such as $P, Q, R, \ldots$ represents an arbitrary proposition with an unspecified truth value.

e.g. Seoul is the capital of Korea. is a proposition.

Operator combines one or more operand expressions into larger expression.
Propositional or Boolean operators operate on propositions or truth values instead of numbers.
The following is a table of boolean operators.

Formal Name	Nickname	Arity	Symbol
Negation	NOT	Unary	$\neg$
Conjunction	AND	Binary	$\wedge$
Disjunction	OR	Binary	$\vee$
Exclusive or	XOR	Binary	$\oplus$
Implication	IMPLIES	Binary	$\rightarrow$
Biconditional	IFF	Binary	$\leftrightarrow$

Negation Operator

The negation of a proposition $P$ is denoted by $\neg P$ (NOT), and is true when $P$ is false, and false when $P$ is true.

$P$	$\neg P$
T	F
F	T

Conjunction Operator

The conjunction of propositions $P$ and $Q$ is denoted by $P \wedge Q$ (AND), and is true when both $P$ and $Q$ are true, and false otherwise.

$P$	$Q$	$P \wedge Q$
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction Operator

The disjunction of propositions $P$ and $Q$ is denoted by $P \vee Q$ (OR), and is true when either $P$ or $Q$ is true, and false when both are false.

$P$	$Q$	$P \vee Q$
T	T	T
T	F	T
F	T	T
F	F	F

This operation is also called inclusive or in that it includes the case where both are true.

Nested operators

Use parentheses to indicate the order of operations.

By convention $\neg$ has higher precedence than $\wedge$ and $\vee$.

Exclusive Or Operator

The exclusive or of propositions $P$ and $Q$ is denoted by $P \oplus Q$ (XOR), and is true when either $P$ or $Q$ is true, but not both.

$P$	$Q$	$P \oplus Q$
T	T	F
T	F	T
F	T	T
F	F	F

Implication Operator

The implication of propositions $P$ and $Q$ is denoted by $P \rightarrow Q$ (IMPLIES), and is false when $P$ is true and $Q$ is false, and true otherwise.

• $P \rightarrow Q$ asserts that $Q$ is true on the condition that $P$ holds.
• $P$ is called the antecedent and $Q$ is called the consequent.
• If antecedent is true, you can simply drop the antecedent as the the result will be determined only by the consequent.

$P$	$Q$	$P \rightarrow Q$
T	T	T
T	F	F
F	T	T
F	F	T

Ways of expressing $P \rightarrow Q$:

• If $P$, then $Q$.
• $P$ implies $Q$.
• $P$ only if $Q$.
• If $P, Q$
• $P$ is sufficient for $Q$.
• $Q$ if $P$.
• $Q$ whenever $P$.
• $Q$ is necessary for $P$.
• $Q$ follows from $P$.

Terminoology for $P \rightarrow Q$:

• Converse: $Q \rightarrow P$
• Inverse: $\neg P \rightarrow \neg Q$
• Contrapositive: $\neg Q \rightarrow \neg P$

Note: The contrapositive is logically equivalent to the original implication. (proof by truth table)

Biconditional Operator

The biconditional of propositions $P$ and $Q$ is denoted by $P \leftrightarrow Q$ (IFF), and is true when both $P$ and $Q$ are true, or both are false.

$P$	$Q$	$P \leftrightarrow Q$
T	T	T
T	F	F
F	T	F
F	F	T

It can be understood as combining $P \rightarrow Q$ and $Q \rightarrow P$.

$P \leftrightarrow Q$ is equivalent to $\neq (P \oplus Q)$.

Well-formed Formula

Definition 2.

1. Any proposition variable is a wff.
2. For any wff $P$, $\neg P$ is a wff.
3. For any wffs $P$ and $Q$, $P \wedge Q$, $P \vee Q$, $P \oplus Q$, $P \rightarrow Q$, and $P \leftrightarrow Q$ are wffs.
4. A finite string of symbols is a wff only when it is constructed by steps 1-3.

Tautology

Definition 3.

A well-formed formula (wff) is a tautology if, for every truth value assignment made to the variables appearing in the formula, the formula has the value of true.

e.g. $P \vee \neg P$ is a tautology.

Contradiction

Definition 4.

A wff is a contradiction if, for every truth value assignment to the variables in the formula, the formula has the value of false

e.g. $P \wedge \neg P$ is a contradiction.

Contingency

Definition 5.

A wff is a contingency if it is neither a tautology nor a contradiction.

Logical Equivalence

Definition 6.

Two wffs A and B are logically equivalent (denoted by $A \iff B$) if and only if A and B have the same truth values for every truth value assignment to all variables contained in A and B.

Proving Techniques

Truth Table

e.g. Prove that $P \vee Q \iff \neg (\neg P \wedge \neg Q)$

$P$	$Q$	$P \vee Q$	$\neg P$	$\neg Q$	$\neg P \wedge \neg Q$	$\neg (\neg P \wedge \neg Q)$
T	T	T	F	F	F	T
T	F	T	F	T	F	T
F	T	T	T	F	F	T
F	F	F	T	T	T	F

Equivalence Theorems

Name	Theorem
Identity	$P \vee F \iff P$ $P \wedge T \iff P$
Domination	$P \vee T \iff T$ $P \wedge F \iff F$
Idempotent	$P \vee P \iff P$ $P \wedge P \iff P$
Double Negation	$\neg (\neg P) \iff P$
Commutative	$P \vee Q \iff Q \vee P$ $P \wedge Q \iff Q \wedge P$
Associative	$P \vee (Q \vee R) \iff (P \vee Q) \vee R$ $P \wedge (Q \wedge R) \iff (P \wedge Q) \wedge R$
Distributive	$P \vee (Q \wedge R) \iff (P \vee Q) \wedge (P \vee R)$ $P \wedge (Q \vee R) \iff (P \wedge Q) \vee (P \wedge R)$
De Morgan's	$\neg (P \vee Q) \iff \neg P \wedge \neg Q$ $\neg (P \wedge Q) \iff \neg P \vee \neg Q$
Trivial tautology / contradiction	$P \vee \neg P \iff T$ $P \wedge \neg P \iff F$

Defining Operators via Equivalence

Operator	Definition
Exclusive or	$P \oplus Q \iff (P \vee Q) \wedge \neg (P \wedge Q)$
Conditional	$P \rightarrow Q \iff \neg P \vee Q$
Biconditional	$P \leftrightarrow Q \iff (P \rightarrow Q) \wedge (Q \rightarrow P)$

Predicate Logic

In propositional logic, we can only make assertions about propositions.

e.g. Socrates is a man.

On the other hand, in predicate logic, we can make assertions about objects and their properties, which makes it more useful for describing relationships between objects. Predicate logic consists of subjects and predicates, as well as quantifiers, functions, and boolean connectives.

e.g. $p(x) = \text{x is socrates}$

e.g. $\exist x ; p(x) = \text{There exists x such that x is Socrates.}$

Like above, the core of the predicate logic is the predicate.
There is something that is not determined or unknown. For instance, $x$ in above example.

In first-order logic, predicates can have variables as arguments.

In higher-order logic, predicates can have predicates or functions as arguments.

We will be only dealing with first-order logic.

Syntax and Semantics

• Constants: $A, B, C, ...$
• Variables: $x, y, z, ...$
• Predicate symbols: $ROUNDS, BROTHER, ...$, where a predicate symbol refers to a particular relation.
• Function symbols: $father, color, ...$, where a function symbol maps objects to objects.

Definition 7.

A term is a logical expression that refers to an object, which is defined as follows:

1. Constant symbols and variables are terms.

If $x$ is a term and $h$ is a function symbol, $h(x)$ is a term.

1. A finite string is a term only when it is constructed by steps 1-2.

e.g. $x$, $C$, $father(A)$, $mother(father(x))$

Functions and Predicates

Argument of functions and predicates are given by terms.
But predicate itself is not a term as it is not an object.

Note: The statement $p(x)$ is said to be the value of the propositional function $p$ at the argument $x$. e.i. once the argument is given, the statement $p(x)$ becomes a proposition with truth value.

Quantifiers

• u.d. (universe of discourse): the set of objects that we are considering. (e.g. $x \in \mathbb{R}$)
• $\forall x ; p(x)$ : FOR ALL x in u.d., P(x) is true.
• $\exist x ; p(x)$ : THERE EXISTS x in u.d., P(x) is true.

Definition 8.

Free variables: Variables that are not bound by a quantifier.
> Bound variables: Variables that are bound by a quantifier.

For a statement to be a proposition, all variables must be bound.

wwf in Predicate Logic

Definition 9.

1. Every predicate formula is a wwf.
2. If $P$ is a wwf, then $\neg P$ is a wwf.
3. Two wffs is joined by $\wedge$, $\vee$, $\rightarrow$, or $\leftrightarrow$ from a wwf.

If $P$ is a wwf and $x$ is a variable, then $\forall x ; P$ and $\exist x ; P$ are wffs.

1. A finite string is a wwf only when it is constructed by steps 1-4.

cf. More about binding.

• $\forall x \exist x ; P(x)$ : $x$ is not free in $\exist x ; P(x)$. Thus, $\forall x$ binding is not used. (wwf)
• $(\forall x ; P(x)) \vee Q(x)$ : $x$ is bound in $P(x)$ but not in $Q(x)$. Note that $x$ in $Q(x)$ is not same $x$ in $P(x)$. (not wwf)
• $(\forall x ; P(x) )\vee (\exist x ;Q(x))$ : Note that there are two $x$ instances. (wwf)

By convention, if u.u. is empty

• $\forall x ; P(x)$ is true for all $P(x)$
• $\exist x ; P(x)$ is false for all $P(x)$

Equivalence Laws in quantifiers

If u.d. is ${a,b,c}$,

• $\forall x ; P(x) \iff P(a) \wedge P(b) \wedge P(c)$
• $\exist x ; P(x) \iff P(a) \vee P(b) \vee P(c)$

From above, we can derive the following:

• $ \forall x ; P(x) \iff \neg (\exist x ; \neg P(x))$
• $ \exist x ; P(x) \iff \neg (\forall x ; \neg P(x))$

... and more

• $\forall x \forall y P(x,y) \iff \forall y \forall x P(x,y)$
• $\exist x \exist y P(x,y) \iff \exist y \exist x P(x,y)$
  ⠀
• $\forall x ; (P(x) \wedge Q(x)) \iff (\forall x ; P(x)) \wedge (\forall x ; Q(x))$
• $\exist x ; (P(x) \vee Q(x)) \iff (\exist x ; P(x)) \vee (\exist x ; Q(x))$

Proofs and Inference Rules

Terminology

Term	Definition
Theorem	A statement that can be shown to be true.
Axiom, Postulate, Hypothesis, Premise	Asumptions that defines the structure about which we reason.
Lemma	A minor theorem that is used to prove a major theorem.
Corollary	A theorem that follows directly from another theorem.
Theory	A set of theorems that can be derived from a set of axioms.
Rules of inference	Patterns of deriving conclusions from hypotheses.

Monotonicity

Monotonic logic is a logic in which the truth of a conclusion is preserved when additional premises are added.

Non-monotonic logic is a logic in which the truth of a conclusion is not preserved when additional premises are added.

Rules of Inference

• Argument: A sequence of statements ending with a conclusion.
• Validity: An argument is valid if and only if it is impossible for all premises to be true and the conclusion to be false.
  • $ p \rightarrow q $
  • $ p $
  • $ \therefore q $
• Example of a valid argument:
• Rules of Inference: Basic tools for establishing the truth of statements.
  • Each rule corresponds to an implication that is a tautology.
  Example of a rule of inference:
  • $ ((p \rightarrow q) \land p) \rightarrow q $

---

Implication Tauologies

1. $P \land Q \Rightarrow P$ (I.1)
2. $P \land Q \Rightarrow Q$ (I.2)
3. $P \Rightarrow P \lor Q$ (I.3)
4. $Q \Rightarrow P \lor Q$ (I.4)
5. $\neg P \Rightarrow P \to Q$ (I.5)
6. $Q \Rightarrow P \to Q$ (I.6)
7. $\neg (P \to Q) \Rightarrow P$ (I.7)
8. $\neg (P \to Q) \Rightarrow \neg Q$ (I.8)
9. $P, Q \Rightarrow P \land Q$ (I.9)
10. $\neg P, P \lor Q \Rightarrow Q$ (I.10)
11. $P, P \to Q \Rightarrow Q$ (I.11)
12. $\neg Q, P \to Q \Rightarrow \neg P$ (I.12)
13. $P \to Q, Q \to R \Rightarrow P \to R$ (I.13)
14. $P \lor Q, P \to R, Q \to R \Rightarrow R$ (I.14)
15. $(\forall x) P(x) \lor (\forall x) Q(x) \Rightarrow (\forall x)(P(x) \lor Q(x))$ (I.15)
16. $(\exists x)(P(x) \land Q(x)) \Rightarrow (\exists x) P(x) \land (\exists x) Q(x)$ (I.16)

---

Biconditional Tautologies

1. $\neg \neg P \Leftrightarrow P$ (E.1)
2. $P \land Q \Leftrightarrow Q \land P$ (E.2)
3. $P \lor Q \Leftrightarrow Q \lor P$ (E.3)
4. $(P \land Q) \land R \Leftrightarrow P \land (Q \land R)$ (E.4)
5. $(P \lor Q) \lor R \Leftrightarrow P \lor (Q \lor R)$ (E.5)
6. $P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)$ (E.6)
7. $P \lor (Q \land R) \Leftrightarrow (P \lor Q) \land (P \lor R)$ (E.7)
8. $\neg (P \land Q) \Leftrightarrow \neg P \lor \neg Q$ (E.8)
9. $\neg (P \lor Q) \Leftrightarrow \neg P \land \neg Q$ (E.9)
10. $P \lor P \Leftrightarrow P$ (E.10)
11. $P \land P \Leftrightarrow P$ (E.11)
12. $R \lor (P \land \neg P) \Leftrightarrow R$ (E.12)
13. $R \land (P \lor \neg P) \Leftrightarrow R$ (E.13)
14. $R \lor (P \lor \neg P) \Leftrightarrow T$ (E.14)
15. $R \land (P \land \neg P) \Leftrightarrow F$ (E.15)
16. $P \to Q \Leftrightarrow \neg P \lor Q$ (E.16)
17. $\neg (P \to Q) \Leftrightarrow P \land \neg Q$ (E.17)
18. $P \to Q \Leftrightarrow \neg Q \to \neg P$ (E.18)
19. $P \to (Q \to R) \Leftrightarrow (P \land Q) \to R$ (E.19)
20. $\neg (P \leftrightarrow Q) \Leftrightarrow (P \leftrightarrow \neg Q)$ (E.20)
21. $(P \leftrightarrow Q) \Leftrightarrow (P \to Q) \land (Q \to P)$ (E.21)
22. $(P \leftrightarrow Q) \Leftrightarrow (P \land Q) \lor (\neg P \land \neg Q)$ (E.22)
23. $(\exists x)(A(x) \lor B(x)) \Leftrightarrow (\exists x)A(x) \lor (\exists x)B(x)$ (E.23)
24. $(\forall x)(A(x) \land B(x)) \Leftrightarrow (\forall x)A(x) \land (\forall x)B(x)$ (E.24)
25. $\neg (\exists x)A(x) \Leftrightarrow (\forall x)\neg A(x)$ (E.25)
26. $\neg (\forall x)A(x) \Leftrightarrow (\exists x)\neg A(x)$ (E.26)
27. $(\forall x)(A \lor B(x)) \Leftrightarrow A \lor (\forall x)B(x)$ (E.27)
28. $(\exists x)(A \land B(x)) \Leftrightarrow A \land (\exists x)B(x)$ (E.28)
29. $(\forall x)A(x) \to B \Leftrightarrow (\exists x)(A(x) \to B)$ (E.29)
30. $(\exists x)A(x) \to B \Leftrightarrow (\forall x)(A(x) \to B)$ (E.30)
31. $A \to (\forall x)B(x) \Leftrightarrow (\forall x)(A \to B(x))$ (E.31)
32. $A \to (\exists x)B(x) \Leftrightarrow (\exists x)(A \to B(x))$ (E.32)
33. $(\exists x)(A(x) \to B(x)) \Leftrightarrow (\forall x)A(x) \to (\exists x)B(x)$ (E.33)

Formal Proof

A formal proof is a sequence of statements that starts with the premises and ends with the conclusion. Each statement is either a premise, an axiom, or derived from previous statements using rules of inference.

Note that proofs gaurantee the truth of the conclusion only if the premises are true.

Inference Rules for Quantifiers

1. $\forall x , P(x)$
   
   ∴ $P(c)$
   
   Universal Instantiation
2. $P(c)$ for any element $c$
   
   ∴ $\forall x , P(x)$
   
   Universal Generalization
3. $\exists x , P(x)$
   
   ∴ $P(c)$ for some element $c$
   
   Existential Instantiation
4. $P(c)$ for some element $c$
   
   ∴ $\exists x , P(x)$
   
   Existential Generalization

Note: In UG, the element $c$ must not be free in any premise or assumption.

$$
\begin{align}
&(\forall x)(\exists y)P(x, y) \
&\Rightarrow (\exists y)P(x_0, y) \quad \text{by UI} \
& \Rightarrow P(x_0, y_0) \quad \text{by EI} \
& \Rightarrow (\forall x)P(x, y_0) \quad \text{by UG (not allowed!)} \
& \Rightarrow (\exists y)(\forall x)P(x, y) \quad \text{by EG (contradiction!)}
\end{align}
$$

Proving Methods

For proving $P \rightarrow Q$:

• Direct Proof: Assume $P$ and derive $Q$.
• Indirect Proof: Assume $\neg Q$ and derive $\neg P$.
• Vacuous Proof: Prove $\neg P$.
• Trivial Proof: Prove $Q$.
• Proof by Contradiction: Prove $\neg(P \rightarrow Q) \rightarrow F$.
• Proof by Cases: Show $P \rightarrow (A \vee B)$ and $A \rightarrow Q$ and $B \rightarrow Q$.

More about proof by contradiction:

Proving $P$

Assume $\neg P$.

Show that $\neg P$ leads to both $R$ and $\neg R$

Thus, $\neg P \rightarrow F$.

Therefore, $P$.

Proving $P \rightarrow Q$

Assume $P \wedge \neg Q$. ($P \wedge \neg Q$ is equal to $\neg(P \rightarrow Q)$)

Show that $P \wedge \neg Q$ is false

Therefore, $P \rightarrow Q$.

Types of proof:

• Existence Proof: Prove that there exists an element with a certain property.
• Uniqueness Proof: Prove that there is only one element with a certain property.

---

This is for the lecture 1 of Discrete Mathematics. Further examples and exercises will be added in separate blog if needed.