Logic and Set Notation

Set theory is a branch of mathematical logic. Therefore, it is natural that logical language and symbols are used to describe sets. In this section, we will look at the basic logical symbols and ways of defining sets.

Propositional Logic

A proposition is a declarative statement which is either true or false. If a proposition is true, then we say it has a truth value of true. Respectively, if a proposition is false, its truth value is false. So, for example, the following statements have a truth value of true:

• The Earth revolves around the Sun;
• \(10 + 3 = 13;\)
• If \(x\) is an even integer, then \({x^2}\) is also even.

Examples of false propositions:

• An electron is heavier than a proton;
• \(1 + 2 \gt 3;\)
• \(6\) is a prime number.

Not all sentences are propositions:

• \(x \gt 5\) (This may be true or false depending on \(x\))
• Is it raining? (This is a question, not a declarative sentence)
• Mondrian paintings are too abstract. (What is abstract and too abstract?)

To represent propositions, we denote them by letters. The most common letters are \(p,\) \(q,\) \(r,\) \(s,\) \(t.\)

Using logical operators or connectives, we can build compound propositions.

Logical Operators and Truth Tables

Let \(p\) and \(q\) be two propositions. Each of these statements can take two values - true (\(T\)) and false (\(F\)). So there are \(4\) pairs of input values: \(TT,\) \(TF,\) \(FT,\) and \(FF.\)

Suppose that a new proposition \(r\) is composed of \(p\) and \(q.\) The truth values of the proposition \(r\) can take different values (\(T\) or \(F\)) for each pair of input values.

There are total \(2^4 = 16\) possible output combinations (truth functions) for \(2\) binary input variables. Each of these combinations is represented by a certain logical operator.

Further we'll look at the most important operators.

Negation

Negation is a unary logical operator. If \(p\) is a proposition, then the negation of \(p\) is called not \(p\) and is denoted by \(\lnot p.\)

To represent the meaning of a logical expression, it is convenient to use a truth table. Each row of the table contains one possible configuration of the input variables and truth values of the output proposition(s).

In case of the negation operator, the truth table is very simple:

As you can see, the logical negation operator reverses the truth value of the input proposition.

Example 1:

Example 2:

Сonsider now some binary operators.

Conjunction

If \(p\) and \(q\) are two propositions, then their conjunction means \(p\) and \(q\) and is denoted by \(p \land q.\)

The conjunction \(p \land q\) is true only when both \(p\) and \(q\) are true. Otherwise, it is false. Thus, the truth table for conjunction looks as follows:

Example 1:

Example 2:

Disjunction

If \(p\) and \(q\) are two propositions, then their disjunction means \(p\) or \(q\) and is denoted by \(p \lor q.\)

The disjunction \(p \lor q\) is true when either \(p\) is true, \(q\) is true, or both are true. It is false, if both \(p\) and \(q\) are false.

Truth table for disjunction:

Example 1:

Example 2:

Material Conditional

The material conditional of \(p\) and \(q\) means the statement if \(p\) then \(q\) and is denoted by \(p \to q.\) This logical operator is also called just a conditional statement.

If \(p\) is true, then the conditional \(p \to q\) takes the truth value of \(q.\) If \(p\) is false, then the conditional \(p \to q\) is assumed to be true by default.

Here is the truth table for conditional statement:

The conditional \(p \to q\) can be expressed by different sentences, some of them are listed below:

• \(p\) implies \(q\)
• \(p\) is a sufficient condition for \(q\)
• \(q\) is a necessary condition for \(p\)
• \(q\) follows from \(p\)
• \(p\) only if \(q\)

Example:

Special Conditional Propositions

• The converse of \(p \to q\) is the proposition \(q \to p\)
• The contrapositive of \(p \to q\) is the proposition \(\neg q \to \neg p\)
• The inverse of \(p \to q\) is the proposition \(\neg p \to \neg q\)

If the statement \(p \to q\) is true, then the contrapositive is also true. If the converse is true, then the inverse is also true.

The special conditional operators are defined by the following truth table:

Example:

Material Biconditional

The material biconditional or logical biconditional of \(p\) and \(q\) means the statement \(p\) if and only if \(q\) and is denoted by \(p \leftrightarrow q.\)

The biconditional statement has the same truth value as the compound logical operator \(\left( {p \to q} \right) \land \left( {q \to p} \right),\) which means \(p\) implies \(q\) and \(q\) implies \(p.\)

The truth table for biconditional statement has the form

Example 1:

Example 2:

Logical Equivalence

Propositions \(p\) and \(q\) are said to be logically equivalent if they have the same truth tables. The logical equivalence of \(p\) and \(q\) is denoted as \(p \equiv q,\) or sometimes by \(\Leftrightarrow\) depending on the notation being used.

Predicates and Quantifiers

So far, we considered propositions which are defined as statements that can be either true or false.

To extend the simple propositional logic, we introduce the concept of predicate.

A predicate is a logical statement that contains one or more variables or parameters. The predicates are denoted by a capital letter and the variables listed as arguments, like \(P\left( x \right)\) or \(Q\left( {x,y} \right).\) The truth value of a predicate depends on the values of its variables.

Example 1:

Example 2:

Similarly to propositions, predicate take two values - true or false. Therefore, all operations of logic algebra are applicable to them. Using the operators \(\neg, \land, \lor, \rightarrow,\) and \(\leftrightarrow,\) we can form more complex predicates.

There is also an additional operation defined on predicates and called quantification. Quantification allows us to specify the extent of validity of a predicate, that is, the range of values of variables for which the predicate should hold.

There are two types of quantifiers in predicate logic − universal quantifier and existential quantifier.

Universal Quantifier

The universal quantifier is used to express sentences with words like all or every. It is denoted by the symbol \(\forall.\) The notation \(\forall x P\left({x}\right)\) means "for every value of \(x\) in a particular domain, the predicate \(P\left({x}\right)\) is true". The domain is called the universe of discourse or domain of discourse.

Existential Quantifier

The existential quantifier is used to express sentences with words like some or there is a. It is denoted by the symbol \(\exists.\) The notation \(\exists x P\left({x}\right)\) means "there is some value of \(x\) such that \(P\left({x}\right)\) is true".

Predicates, logical operators, and quantifiers are a powerful set of tools for describing mathematical objects and for modeling the real world.

Set Builder Notation

The set builder notation is used to specify a set of objects by means of a predicate. The common notation includes \(3\) parts: a variable \(x,\) a colon or vertical bar separator, and a logical predicate \(P\left({x}\right):\)

where \(S\) denotes the set of objects.

The single variable \(x\) can be replaced with a term that may include one or more variables, combined with functions acting on them. The predicate \({P\left( x \right)}\) may be represented by a complex logical formula.

Some Other Definitions and Notations