2018 | OriginalPaper | Chapter

# 1. Fundamentals of Mathematical Logic

Published in:
The Discrete Math Workbook

## Abstract

The chapter gives an idea of mathematical logic, a science that studies mathematical proofs. Subjects of mathematical logic are mathematical proofs, methods and means for their construction.

The simplest division of mathematical logic is the propositional logic. Proposition is a statement that has a value of truth; i.e., it can be true or false. The respective values of truth will be denoted by T or F.

Compound proposition can be built out of atomic propositions using logical operations and brackets. The most common logical operations are: and (conjunction or logical multiplication), or (disjunction or logical addition), if ... then (logical consequence or implication, this operation is also denoted as “\(\Rightarrow \)”), not (negation).

Statements about properties of variable x are called predicates and denoted: P(x), Q(x), ... Truth domain of a predicate is a collection of all x, for which the given predicate becomes a true proposition. The predicate properties are studied by predicate logic.

For construction of compound logical expressions we use quantifiers: \(\forall \) (for all)—universal quantifier—and \(\exists \) (exists)—existential quantifier. Quantifier is a logical operation that by predicate P(x) constructs a proposition that characterizes the truth domain P(x).

In this chapter, the main proof methods are described:

1.

forward reasoning;

2.

backward reasoning;

3.

method “by contradiction”.

Examples are considered to illustrate a powerful method for proving the truth of statements with respect to all natural numbers, the method of mathematical induction.