: Logic<a class="btn btn-sm" href="/UUID/EDB/1YS/?lang=eng"><span class="ttfamily"><small class="scriptsize">[1YS]</small></span></a>

3.1 Logic[1YS]

[23H]In the next sections we will give some definitions; these are simplified, but sufficient to cope with the exercises. Readers interested in an in-depth study can consult a book on Logic such as [ 12 ] .

Propositions

Definition 3

[1VW](Solved on 2020-10-22) A logical proposition $φ$ is an assertion that takes on the value of truth or falsehood.

Example 4

[1VX]Examples:

”the snow is white”,
”the Earth has a diameter of about 12000km”,
”a kg of bread costs 3$”.

[23J](One could argue philosophically about what is meant by ”truth”: in many areas the truth of a proposition is subjective, it can depend on the context, the interpretation, who does and who answers the question, on when the question is asked, etc etc; in mathematics the situation is simpler).

A proposition may depend on some variables. Examples:

”the person x by trade is a baker”,
”the number x is greater than 9”.

We write

\[ P(x)≐\text{``the number x is larger than 9'} \]

to say that $P(x)$ is the symbol that summarizes the proposition written on the right.

Remark 5

[23K]For the proposition to make sense, we will have to narrow down the scope of the variable to an appropriate set; in the first case, the set of human beings; in the second case, a numerical set (e.g. integers).

At this level of discussion, the concept of ”set” is intuitive; we will see later that there is an axiomatic theory of sets, almost universally used in Mathematics; however, even the intuitive concept of set is widely used (See remark 34).

Propositional logic

Definition 6

[00D]A propositional logic is a language, with associated an alphabet of variables (which for convenience in the following we will identify with the Italian alphabet) and a family of connectives ¹

\begin{align*} \text{negation, NOT} & & ¬ \\ \text{conjunction, AND} & & { ∧ } \\ \text{disjunction, OR} & & { ∨ } \\ \text{implication} & & ⇒ \\ \text{biconditional, iff} & & ⇔ \end{align*}

to these symbols we add parentheses, which are used to group parts of the formula (when there is a risk of ambiguity); the parentheses are omitted when the precedence of the operators allows; the operators are listed in the previous list in descending order of precedence. ²

[UNACCESSIBLE UUID ’00F’]

Definition 7

[00G] (Solved on 2022-10-11) Well-formed formulas are

atomic formulas, i.e. composed of a single variable, or
a formula of the type $ ¬ (𝛼)$ where $𝛼$ is a well-formed formula, or
- a formula of the type $ (𝛼) ⇒ (𝛽) $ , or
- a formula of the type $ (𝛼) ⇔ (𝛽) $ , or
- a formula of the type $ (𝛼) ∨ (𝛽) $ , or
- a formula of the type $ (𝛼) ∧ (𝛽) $ ,
where $𝛼,𝛽$ are two well-formed formulas.

[1YK] You can determine if a formula is well formed by making a finite number of checks using the previous rules: in fact the rules establish that any well-formed formula must be decomposable in terms of well-formed formulas that are shorter than it. So the statement ”this formula is well formed” is ”decidable”. ³

Remark 8

[228]In the definition 7 we speak of atomic formulas, i.e. composed of a single variable; we want to reflect on this. In programming languages we may use names composed of several letters to identify objects (variables, functions, etc.): such as

 foo = 3 ;
 bar = 7;
 foo = foo + bar;

In mathematics this is unusual, since in a formula such as

\[ xyz + abc \]

it would be difficult to understand if xyz is a variable, or the product of three variables $x,y,z$. For this reason, usually, in mathematics the identifiers are composed of a single letter; some notable functions are an exception, such as $\sin ,\cos ,\exp ,\log $…etc. However, this creates some problems when you want to express a formula where there are many variables; for this reason, letters from the Greek alphabet are also used, and even Hebrew, in particular ”aleph” $\aleph $ and ”beth” $\beth $; and the letters are also accompanied by indexes, subscript as $x_ 1,x_ 2,x_ 3$ or superscript $x^ 1,x^ 2,x^ 3$ (being careful not to be confused with the exponentiation); then there are variants expressed with the signs $\hat x,\overline x,\tilde x,x'$ (being careful not to get confused with derivatives); and there are choices of fonts, such as ”calligraphic” $\mathcal A,\mathcal B,\mathcal C,\mathcal D,\ldots $, the ”fraktur” $\mathfrak a,\mathfrak b,\mathfrak c,\mathfrak d\ldots \mathfrak A,\mathfrak B,\mathfrak C,\mathfrak D$ or the blackboard bold $\mathbb a,\mathbb b,\mathbb c,\mathbb d\ldots \mathbb A,\mathbb B,\mathbb C,\mathbb D$.

[UNACCESSIBLE UUID ’00H’]

Definition 9

[00J] An evaluation assigns to each variable a value of ”true” or ”false”. Knowing the value of the variables, and using the known truth tables for connectives ⁴ , we can calculate the value of each well-formed formula.

So a well-formed formula is a ”logical proposition” as it takes on the value of truth or falsehood, depending on the value given to its free variables. We can broaden the definition by adding that the propositions seen in the previous section they are ”atomic formulas”; For example,

”$x$ is a number less than 3” $∧$ ”$y$ is an even number”

it will also be a ”well-formed formula”.

For convenience, in this Section, we also add to the language the constants $V$ and $F$ which are respectively always true and always false, in every evaluation. ⁵ In the construction of well-formed formulas they are treated as variables. Note that we have not introduced the equality connective ”$=$”. When all variables can only take true/false values, the equality $a=b$ can be interpreted as $a\iff b$. In more general contexts (as in the case of set theory) instead, ”equality” needs a precise definition.

E9

[1VY] Complete the following truth table

P	Q	¬ P	$P ∧ Q$	$P ∨ Q$	$P ⇒ Q$	$P⇐ Q$	$P ⇔ Q$
V	V
V	F
F	V
F	F

Hidden solution: [UNACCESSIBLE UUID ’1VZ’]

E9

[00K] Tell which formulas are well formed, and add parentheses to highlight the order of precedence.

\begin{eqnarray*} a \land \neg b \land c \land d\\ \neg a \lor b \land c \Rightarrow d\\ a \Rightarrow \neg b \land c \lor d \\ a \land b \lor c \Leftrightarrow \neg c \Rightarrow d\\ a \lor b \neg c \lor d \end{eqnarray*}

Hidden solution: [UNACCESSIBLE UUID ’00M’]

E9

[00N] A well-formed formula in propositional logic is a tautology if for each evaluation the formula is always true. Suppose $A, B, C $ are well-formed formulas. Show that the following properties of connectives are tautologies. ⁶

\begin{eqnarray} {A⇒ A} & & \text{identity law} \nonumber \\ { ¬ (¬ A)⇔ A} & & \text{law of double negation} \nonumber \\ {A∨ A⇔ A}~ ~ ,~ ~ {A∧ A⇔ A} & & \text{laws of idempotence} \nonumber \\ {(A⇒ B) ⇔ (¬ B⇒ ¬ A)} & & \text{law of opposition,} \nonumber \\ & & \text{or of the contrapositive \footnotemark } \label{eqn:legge_ contrapposizione} \\ {(A⇒ B) ⇔ (¬ A∨ B)} ⇔ (¬ (A∧ ¬ B)) & & \text{equivalence of implication,} \nonumber \\ & & \text{conjunction and disjunction} \label{eq_ and_ or_ not_ 3r23n} \\ {A∧ B⇔ ¬ (¬ A∨ ¬ B)} & & \text{first law of De Morgan} \label{deMorgan_ 1} \\ {A∨ B⇔ ¬ (¬ A∧ ¬ B)} & & \text{second law of De Morgan} \label{deMorgan_ 2} \\ {A∧ (B∨ C) ⇔ (A∧ B) ∨ (A∧ C)} & & \text{distributive property of the conjunction } \nonumber \\ & & \text{with respect to the disjunction} \label{distrib_ and_ or} \\ {A∨ (B∧ C) ⇔ (A∨ B) ∧ (A∨ C)} & & \text{distributive property of the disjunction } \nonumber \\ & & \text{with respect to the conjunction} \label{distrib_ or_ and} \\ {A∧ B⇔ B∧ A} & & \text{commutative property of } {∧} \nonumber \\ { A∨ B⇔ B∨ A} & & \text{commutative property of } {∨} \nonumber \\ { A∧ (B∧ C)⇔ (A∧ B)∧ C} & & \text{associative property of } {∧} \nonumber \\ { A∨ (B∨ C)⇔ (A∨ B)∨ C} & & \text{associative property of} {∨} \label{assoc_ or} \end{eqnarray}

These last two properties allow to omit parentheses in sequences of conjunctions or disjunctions.

The property ??,??,?? they say that we could base all logic on connectives alone $¬ $ and $∧ $, (or on $¬, ∨ $).

Other important tautologies, often used in logical reasoning.

\begin{eqnarray} {A∨ ¬ A} & & \text{{excluded middle}} \nonumber \\ {¬ (A∧ ¬ A)} & & \text{law of non-contradiction} \nonumber \\ {(A∧ (A⇒ B)) ⇒ B} & & \text{modus ponens} \label{modus_ ponens} \\ {(¬ B∧ (A⇒ B)) ⇒ ¬ A} & & \text{modus tollens} \label{modus_ tollens} \\ {¬ A ⇒ (A⇒ B)} & & \text{negation of the antecedent} \nonumber \\ {B ⇒ (A⇒ B)} & & \text{affirmation of the consequent} \nonumber \\ {(A ⇒ (B⇒ C)) ⇒ ((A∧ B) ⇒ C)} & & \text{exporting} \nonumber \\ {((A⇒ B) ∧ (A⇒ C)) ⇒ (A⇒ (B∧ C))} & & \text{proof by parts} \nonumber \\ {((A⇒ C) ∧ (B⇒ C)) ⇒ ((A∨ B) ⇒ C)} & & \text{proof by cases} \nonumber \\ {((A⇒ B) ∧ (B⇒ C)) ⇒ (A⇒ C)} & & \parbox{\RightWidth }{hypothetical syllogism, or transitivity of implication } \nonumber \\ {(A∨ (A∧ B)) ⇔} { A∧ (A∨ B) ⇔ } & & \nonumber \\ {(A∨ F)⇔ (A∧ V) ⇔ A} & & \text{absorption laws} \nonumber \\ {{F ⇒ B}} & & \parbox{\RightWidth }{first law of Pseudo Scotus, or \em ex falso sequitur quodlibet } \nonumber \\ {A⇒ (¬ A⇒ B)} & & \text{second law of Pseudo Scoto} \nonumber \\ {(¬ A⇒ F) ⇔ A} & & \text{proof by contradiction} \nonumber \\ {((A∧ ¬ B) ⇒ F) ⇔ (A⇒ B)} & & \parbox{\RightWidth }{proof by contradiction, with hypothesis and thesis} \nonumber \\ {(¬ A⇒ A)⇒ A} & & \text{consequentia mirabilis} \end{eqnarray}

[UNACCESSIBLE UUID ’00P’]

[22C]Show the validity of the following tautology

\[ ((\neg A\land B ) \Rightarrow C ) \iff ((\neg C\land B ) \Rightarrow A ) \]

Then use the 6 exercise to turn it into a Venn diagram with three sets. Hidden solution: [UNACCESSIBLE UUID ’22D’] [2G8]Show that the implication connective $\Rightarrow $ is neither commutative nor associative. ⁸ Hidden solution: [UNACCESSIBLE UUID ’2G9’]

First-order logic

In the first order logic we add the connectives $∀$, which reads ”for each” and $∃$, which reads ”exists”. We must therefore enlarge the family of well-formed formulas.

Definition 20

[00Q] A formula is well formed if it meets all the rules in the list in 7 and this additional rule: ”given a well-formed formula $𝜙$ where the variable $x$ is free, a formula of the form ”$∀ x, 𝜙$”, or ”$∃ x, 𝜙$” is a well-formed formula.”

We will say that a variable $x$ is free in a well-formed formula if

the formula is atomic and the variable $x$ appears in it; or if
the formula is of the form $¬ 𝛼$ and the variable $x$ is free in $𝛼$; or even if
the formula is of the form $𝛼∧𝛽, 𝛼∨𝛽,𝛼⇒ 𝛽, 𝛼\iff 𝛽$ (or other logical connective introduced later) and the variable $x$ is free in $𝛼$ or $𝛽$.

So in the formulas $(∀ x, 𝜙)$ or $(∃ x, 𝜙)$, the variable $x$ is no longer free; we will say that ”the variable is quantified”.

In every part of a formula where a variable is quantified this variable can be replaced with every other variable.

Remark 21

[1X1](Solved on 2022-10-11) The variable $x$ , which is quantified in a part of a formula, is again free if it is reused in another piece of the formula; this is syntactically permissible but makes the formula less readable, as in this example that uses the language of set theory

\[ A⊆ {\mathbb {N}}∧ x∈ {\mathbb {N}}∧ x≥ 4 ∧ (∀ x∈ A,x≤ 10) \]

which should be written as

\[ A⊆ {\mathbb {N}}∧ x∈ {\mathbb {N}}∧ x≥ 4 ∧ (∀ y∈ A,y≤ 10) \]

renaming the variable inside the part where it is quantified.

Remark 22

[2DC]It is assumed as an axiom that

\begin{equation} \label{eq:forall_ exists} ¬ (∀ x, 𝜙 ) ⇔ (∃ x, ¬ 𝜙 ) ~ ~ . \end{equation}

(In Sec. 2.1 in [ 12 ] indeed $(∀ x, 𝜙)$ is presented as short form for $¬(∃ x, ¬𝜙)$).

Note that, in many examples, quantified variables are assumed to be elements of a ”set”.

Definition 24

[1X2] Given two variables $x,y$ we will write $x∈ y$ to say that “$x$ is an element of the set $y$”. Equivalent expressions are “$x$ is a member of $y$”, “$x$ belongs to $y$” or just simply “$x$ is in $y$”.

The formula $(x∈ y)$ is equivalent to $(y∋ x)$; the negations are $(x∉ y )≐ ¬ (x∈ y) $ and $(y ∌ x)≐ ¬ (y∋ x)$.

The formula $(x∈ y)$ (as all other variants) takes value of truth/falsehood and therefore can be used as atom in the construction of a well-formed formula.

Definition 25

[00R] We usually write

”$∀ x∈ A, P(x)$”	to say	”for every $x$ in $A$ $P(x)$ holds”,
or
”$∃ x∈ A, P(x)$”	to say	”there is a $x$ in $A$ for which $P(x)$” holds;

(where $A$ is a set); to link these writings to the previous definitions, we decide that the previous writings are abbreviations for

\begin{align*} ∀ x∈ A, P(x) \doteq & ∀ x, x∈ A⇒ P(x)\quad , \\ {} ∃ x∈ A, P(x) \doteq & ∃ x, x ∈ A ∧ P(x)\quad . \end{align*}

Note that these RHS are ”well-formed formulas”. See also the exercise 4.

We use the term ”together” informally here, see footnote 34.

Remark 26

[00S](Solved on 2022-10-11) Note that ”$∀ x∈ A, 𝜑$” is true if $A$ is the empty set; this is consistent with what was discussed in the exercise 4. This has though a striking consequence: the implication

\[ (∀ x∈ A, 𝜑 ) \Rightarrow (\exists x∈ A, 𝜑) \]

is always valid when $A$ is a non-empty set, but is instead false when $A=\emptyset $.

Since an element of a set may not have a truth/falsehood value, we enrich the language by adding the ”logical propositions”.

Definition 27

[00T](Solved on 2021-10-18) A logical proposition $𝜙$ is an assertion that assumes value of truth or falsehood depending on the value given to the its free variables, and only from that.

An example of a logical proposition would be: ”$n$ is an even number”. We can use logical propositions as atoms in the construction of well-formed formulas.

E27

[00V]Let $X,Y$ sets. Let $𝜙,𝜓$ logical propositions be; $x,a$ are free variables in $𝜙$, and $y,b$ are free in $𝜓$. We also assume that $a,b$ can only be true or false, while $x∈ X, y∈ Y$. Consider the following formulae. Which ones are well formed? What variables are free in them?

\begin{eqnarray*} b ∧ (∀ x,𝜙) \\ (∃ y, 𝜓) ∨ (∀ x,𝜙)\\ ∀ x,∀ b, \bigl(𝜙∧ (𝜓∨ b)\bigr) \\ a ∨ (∀ x,∀ a, 𝜙) \\ (∃ x, 𝜓) ∧ (∀ x,𝜙) \end{eqnarray*}

Hidden solution: [UNACCESSIBLE UUID ’00W’]

E27

[00X]Consider a proposition $P(u,ℓ)$ dependent on two free variables $u$ (which takes values in the set of people), and $ℓ$ (in the set all the jobs), and which is worded as follows: ’Person $u$ knows how to do the job $ℓ$’.

Express the following formulas in English

\begin{align*} ∃ u∃ ℓ P(u,ℓ)~ ~ , ∀ u ∃ ℓ P(u,ℓ)~ ~ , ∃ ℓ ∀ u P(u,ℓ)~ ~ , \\ ∀ ℓ ∃ u P(u,ℓ)~ ~ , ∃ u ∀ ℓ P(u,ℓ)~ ~ , ∀ u ∀ ℓ P(u,ℓ)~ ~ . \end{align*}

Hidden solution: [UNACCESSIBLE UUID ’00Y’]

E27

[00Z](Proposed on 2021-10-21) What implications are there among the previous formulas?

Hidden solution: [UNACCESSIBLE UUID ’010’]

E27

[011]You may prove that

\[ \Big((∀ x,\, 𝜑(x))∧ (∀ y,\, 𝜓(y))\Big) \iff \Big(∀ x\, (𝜑(x) ∧ 𝜓(x)) \Big) \]

[UNACCESSIBLE UUID ’012’]

[016]As already commented in 25, given $A$ a set, and $P(x)$ a logical proposition dependent from a free variable $x$, we usally write

\[ ∀ x∈ A, P(x)\quad ,\quad ∃ x∈ A, P(x) \]

however

\[ ∀ x∈ A, P(x)~ ~ \text{summarizes} ~ ~ ∀ x, (x ∈ A) ⇒ P(x)~ ~ , \]

\[ ∃ x∈ A, P(x)~ ~ \text{summarizes} ~ ~ ∃ x, (x ∈ A) ∧ P(x)~ ~ ; \]

where the ”extended” versions are well-formed formulas.

Using this extended version you can prove that the two propositions

\[ ¬(∀ x∈ A, P(x))~ ~ ,~ ~ ∃ x∈ A, (¬ P(x))~ ~ . \]

are equivalent, in the sense that from one it is possible to prove the other (and vice versa). In the proof use only tautologies (listed in 3) and in particular the equivalence of the formula ”$P⇒ Q$” with ”$(¬ P)∨ Q$” ⁹ , and finally the equivalence between ”$¬ ∃ x, Q$” and ”$∀ x, ¬ Q$” ¹⁰ .

Replacing $P(x)$ with $¬ P(x)$ and using the tautology of double negation finally results in

\[ ∀ x∈ A, (¬ P(x))~ ~ ,~ ~ ¬(∃ x∈ A, P(x))~ \]

are equivalent.

Hidden solution: [UNACCESSIBLE UUID ’017’] [013] Given $A$ a set, and $P(x)$ a proposition dependent on a free variable $x$, we usually write

\[ ∃! x∈ A, P(x) \]

when there is one and only one element $x$ of $A$ for which $P(x)$ is true. Define this notation with a well-formed formula. (Note that you will need to use the equality connective, because you must be able to express the idea of ”unique”, which needs of a method to be able to tell when two objects are distinguishable and when they are not).

Hidden solution: [UNACCESSIBLE UUID ’015’]

P	Q	¬ P	\(P ∧ Q\)	\(P ∨ Q\)	\(P ⇒ Q\)	\(P⇐ Q\)	\(P ⇔ Q\)
V	V
V	F
F	V
F	F

”\(∀ x∈ A, P(x)\)”	to say	”for every \(x\) in \(A\) \(P(x)\) holds”,
or
”\(∃ x∈ A, P(x)\)”	to say	”there is a \(x\) in \(A\) for which \(P(x)\)” holds;