Logica fuzzy

Questa è una pagina di introduzione al corso: contiene i turni, le modalità d'insegnamento, alcune informazioni generali ed eventuali giudizi sul corso in questione. Se sei giunto qui passando da un link, puoi tornare indietro e correggerlo in modo che punti direttamente alla voce appropriata.

Indice

1 A.A. passati
2 Informations
3 Lessons' notes
- 3.1 Classical Propositional Logic
- 3.2 Godel logic

A.A. passati

(Marra, Aguzzoli), A.A. 2007-2008

Informations

Course's website
Times and classrooms:
Monday 15:30 - 17:30 - Room 5 (Ground floor - via comelico 39)
Friday 10:30 - 12:30 - Room 5

Lessons' notes

This notes are written in english to help foreign students to follow this course.

Classical Propositional Logic

We are going to describe the classical propositional logic (CPL) language.

Syntax

The syntax of a language is the set of rules that specify how the elements of the language are formed regardless their meaning.

Let ${\mathbb {N}}=\{1,2,...\}$ be the set of the natural numbers and ${\mathbb {A}}=\{(,),X,|,\$,\rightarrow ,\land ,\lor ,\neg ,\top ,\bot \}$ an alphabet of symbols.
The symbols $\bot ,\top$ are called respectively "falsum", "verum".
${\mathbb {A}}^{\star }$ is the set of strings on this alphabet. For example $''(\top \land \bot )'',''(\neg \land '',''X((''\in {\mathbb {A}}^{\star }$ .
We have now to define the set of the "well formed formula" $FORM$ , that is the set of the elements of the L.P.C.
Definition (well formed formulas). $FORM\subset {\mathbb {A}}^{\star }$ is defined with some conditions:

$\top ,\bot \in FORM$
$\forall n\in {\mathbb {N}}$
$\qquad X||...|\$\in FORM$ , where | is taken n times. For example: $X|\$,X||\$,X|||\$,....\in FORM$
if $\alpha ,\beta \in FORM$ , then $(\neg \alpha )\in FORM$ .
if $\alpha ,\beta \in FORM$ , then $(\alpha \land \beta )\in FORM$ .
if $\alpha ,\beta \in FORM$ , then $(\alpha \lor \beta )\in FORM$ .
if $\alpha ,\beta \in FORM$ , then $(\alpha \rightarrow \beta )\in FORM$ .

Well formed formulas is often abbreviated with f.b.f. The strings in condition (2) are called "propositional variables" or "atomic formulas" or "propositional letters" or simply "variables". They are abbreviated with this notation: $X_{1},X_{2},X_{3},...,X_{n}$ (In other books p, q, r, .., are used to refer to variables).
The set of variables is $VAR$ .
$VAR\subset FORM$
Example of well formed formulas:
$(((X_{1}\land X_{2})\lor \top )\rightarrow (X_{1}\lor \bot ))\in FORM$
Instead
$(X_{1}\land \land )\notin FORM$
In this notes we omit (, ) where it is clear the precedence of the connectives. (Connectives are $\neg ,\land ,\lor ,\rightarrow ,\bot ,\top$ )
Why don't we use directly $X_{1},X_{2},...$ or $p,q,r,s,...$ ?
Because it is important that the alphabet is a finited set. Although, in this notes, we use $X_{1},X_{2},...,$ notation. It is essential, even, that the L.P.C. language is decidable, that is it must exist an algorithm that tell us if a string is $\in FORM$ or not. For this reason it is crucial the
Unique readability of well formed formulas. For all $\alpha \in FORM$ one (and only one) of the following sentences must be true:

$\alpha =\bot$ or $\alpha =\top$ but not both.
Exists an unique $n\in {\mathbb {N}}$ such that $\alpha =X_{n}$ .
Exists an unique $\beta \in FORM$ such that $\alpha =(\neg \beta )$ .
Exist unique $\beta ,\gamma \in FORM$ such that $\alpha =(\beta \land \gamma )$ .
Exist unique $\beta ,\gamma \in FORM$ such that $\alpha =(\beta \lor \gamma )$ .
Exist unique $\beta ,\gamma \in FORM$ such that $\alpha =(\beta \rightarrow \gamma )$ .

Let's, infact, consider the parser of the algorithm we talked above: When it finds, for example, $\neg (\alpha \land \beta )$ , to decide if the string belongs to FORM, it have to decide (for the unique readability of well formed formulas) if $\alpha \land \beta \in FORM$ . But how can it do this? Deciding if $\alpha \in FORM$ and $\beta \in FORM$ . This is what the above theorem tell us. Try to draw the parser tree. It is unique thanks to, again, that theorem.

Formally, a string $\alpha$ is a finite sequence of elements: $\alpha =s_{1}s_{2}...s_{n},s_{i}\in {\mathbb {A}},i\in \{1,..,n\}$
A substring of $\alpha$ is a string in the form $s_{i}s_{{i+1}}...s_{{i+j}}$ , where $j\in \{0,1,..,n\}$ and $i+j\leq n$ .
A subformula is a substring $\in FORM$ .
For example: $\alpha =(X_{1}\land X_{2})\rightarrow \top$
$\beta =(X_{1}\land \qquad \gamma =(X_{1}\land X_{2})$
$\beta ,\gamma$ are both substring of $\alpha$ but only $\gamma$ is a subformula. With $Var(\alpha )$ we indicate the set of variables that are subformulas of $\alpha$ . With $\alpha (X_{1},X_{2},..,X_{n})$ we denote a formula whose variables are a subset of $\{X_{1},X_{2},..,X_{n}\}$ .

Semantic

The semantic of a language is the relation between the elements of that language and their meaning.
The set {0,1} is called truth values set. 0 means false and 1 means true. Definition(Assignment). An atomic assignment is any function
$\mu _{0}:Var\rightarrow \{0,1\}$ .
An assignment (or interpretation) is a function
$\mu :FORM\rightarrow \{0,1\}$
that extends $\mu _{0}$ and respects the following rules for every $\alpha ,\beta \in FORM$ .

$\mu (\bot )=0$ and $\mu (\top )=1$
$\mu ((\neg \alpha ))={\begin{cases}1&if\quad \mu (\alpha )=0\\0&if\quad \mu (\alpha )=1\end{cases}}$
$\mu ((\alpha \land \beta ))={\begin{cases}1&if\quad \mu (\alpha )=1\quad and\quad \mu (\beta )=1\\0&else\end{cases}}$
$\mu ((\alpha \lor \beta ))={\begin{cases}1&if\quad \mu (\alpha )=1\quad or\quad \mu (\beta )=1\quad or\quad both\\0&else\end{cases}}$
$\mu ((\alpha \rightarrow \beta ))={\begin{cases}0&if\quad \mu (\alpha )=0\quad and\quad \mu (\beta )=1\\1&else\end{cases}}$

Informally we can say that the variables represent propositions with one verb and one or more complement. For example:
$X_{1}=$ "It rains";
$X_{2}=$ "I go to school".
$\neg X_{2}=$ "I don't go to school"
$X_{1}\land X_{2}=$ "It rains and I go to school"
$X_{1}\lor X_{2}=$ "it rains or I go to school"
$X_{1}\rightarrow X_{2}=$ "If it rains then I will go to school"
I can choose $\mu _{0}$ such as $\mu _{0}(X_{1})=1$ and $\mu _{0}(X_{2})=0$
Consequently we have
$\mu (\neg X_{2})=1\quad \mu (X_{1}\land X_{2})=0\quad \mu (X_{1}\lor X_{2})=1\quad \mu (X_{1}\rightarrow X_{2})=0$

Proposition (Unique extendibility of atomic assignment): Every atomic assignment $\mu _{0}:Var\rightarrow \{0,1\}$ admits exactly one extension to an assignment $\mu :FORM\rightarrow \{0,1\}$

More informally, as you can see in the example above, when we choose the values of the variables we determinate the values of the formulas within those variables.

Definition (truth and falsehood). Let $\alpha \in FORM$ . When we have $\mu (\alpha )=1$ we say that $\alpha$ is true in the interpretation of $\mu$ , or $\mu$ is a model of $\alpha$ . Instead, when we have $\mu (\alpha )=0$ we say that $\alpha$ is false in the interpretation of $\mu$ , or $\mu$ is an anti-model of $\alpha$ .
In symbols:
$\mu \models \alpha$ when $\mu (\alpha )=1$
$\mu \not \models \alpha$ when $\mu (\alpha )=0$ .
When $\alpha$ is true for every $\mu$ we say that $\alpha$ is a tautology. Instead when we have $\alpha$ false for every assignment $\mu$ we say that $\alpha$ is a contradiction. When exists a $\mu$ such as $\mu (\alpha )=1$ we say that $\alpha$ is satisfiable; instead when exists a $\mu$ such as $\mu (\alpha )=0$ we say that $\alpha$ is refutable.
In symbols:
$\models \alpha$ tautology
$\not \models \alpha$ refutable

In these notes we abbreviate
$((\alpha \to \beta )\land (\beta \to \alpha ))$
with
$(\alpha \leftrightarrow \beta )$
and it can be read as "if and only if".

Exercise. Prove that the following formulas are tautologies for all $\alpha ,\beta \in FORM$
Hint: use the truth table

$\alpha \lor \neg \alpha$ (Excluded middle)
$\neg (\alpha \land \neg \alpha )$ (Not contradiction)
$\neg \neg \alpha \leftrightarrow \alpha$ (Law of double negation)
$\neg (\alpha \land \beta )\leftrightarrow \neg \alpha \lor \neg \beta$ (De Morgan rule I)
$\neg (\alpha \lor \beta )\leftrightarrow \neg \alpha \land \neg \beta$ (De Morgan rule II)
$\alpha \land \neg \alpha \to \beta$ (Ex falso quodlibet)
$(\alpha \to \beta )\lor (\beta \to \alpha )$ (Prelinearity)

Exercise. Prove that exist $\alpha ,\beta \in FORM$ for those the following formulas aren't tautologies. Which of these are contradiction?
Hint: to prove that a formula isn't a tautology is sufficient an counter-example but to prove that it is a contradiction it isn't sufficient. You can use the truth table again.

$X_{1}$
$\alpha \to \neg \alpha$
$(\alpha \to \beta )\to (\neg \alpha \to \beta )$
$\neg ((\alpha \to \beta )\to (\neg \beta \to \neg \alpha ))$

Relationship between syntax and semantic

Definition (Axioms of CPL (Classical propositional logic)). For all $\alpha ,\beta ,\gamma \in FORM$ , let's consider the following formulas.

$\alpha \to (\beta \to \alpha )$
$(\alpha \to \beta )\to ((\alpha \to (\beta \to \gamma ))\to (\alpha \to \gamma ))$
$\alpha \to (\beta \to (\alpha \land \beta ))$
$(\alpha \land \beta )\to \alpha$
$(\alpha \land \beta )\to \beta$
$(\alpha \to (\alpha \land \beta ))$
$(\alpha \to (\alpha \land \beta ))$
$(\alpha \to \gamma )\to ((\beta \to \gamma )\to ((\alpha \lor \beta )\to \gamma ))$
$(\alpha \to \beta )\to ((\alpha \to \neg \beta )\to \neg \alpha )$
$\alpha \to (\neg \alpha \to \beta )$
$\neg \neg \alpha \to \alpha$
$\alpha \to \neg \neg \alpha$

The formulas between 1 and 12 $\in AXIOM\subset FORM$ .
$AXIOM$ is called set of the axioms of the classical propositional logic.
Why these formulas are axioms and not others? Because they are needed to prove the theorem of completeness that is very important for logic. We will talk about this theorem later.. The cardinality of $AXIOM$ is $\infty$ because $\alpha ,\beta ,\gamma$ can be other formulas. For example:
Let $\alpha :=\beta \land \gamma$ and substitute in the first axiom; it becomes
$(\beta \land \gamma )\to (\beta \to (\beta \land \gamma ))\in AXIOM$
It is important to understand that the axioms are defined only through syntax, because we don't speak about values of formulas. Axioms, for definition, are demostrable without demonstration. Think about syntax and semantic as two different worlds. In "syntax world" there are $AXIOM\subset FORM$ but even $THM$ , the set of theorems. So we have
$AXIOM\subset THM\subset FORM$
The elements of $THM$ are the demonstrable formulas.
Definition. We say that a formula $\alpha$ is demonstrable (or syntactic consequence), $\vdash \alpha$ if exist a finite sequence of formulas $\alpha _{1},\alpha _{2},...,\alpha _{n}\quad n\in {\mathbb {N}}$ such that $\alpha _{n}=\alpha ,\forall i\in \{1,..,n\}$ one of the following conditions is true.

$\alpha _{i}\in AXIOM$
Exist indexes $j,k\in {1,..,n}\quad j,k\leq i$ such that $\alpha _{i}$ is deducible from $\alpha _{j}$ and $\alpha _{k}$ through modus ponens.

A sequence of formulas like that is a formal demonstration of $\alpha$ .
Definition (modus ponens). Let $\alpha ,\beta \in FORM$ . We say that $\gamma \in FORM$ is deducible, through modus ponens, if $\alpha =(\beta \to \gamma )$ . For example:
$\alpha :=$ "If it rains then I will stay home" $\beta :=$ "It rains" $\gamma :=$ "I will stay home". We know that $\alpha ,\beta$ are true, hence we can say that $\gamma$ is true.

The elements of $THM$ are found in this way through modus ponens starting from elements of $AXIOM$ . Modus ponens is one of the inference rules. Example of demonstration: We want to prove that $\gamma \to ((\gamma \land \delta )\to \gamma )\in THM$ . We start from axioms 1, 4.

1A $\alpha \to (\beta \to \alpha )$

4A $(\alpha \land \beta )\to \alpha$

$\alpha \longmapsto (\gamma \land \delta )\to \gamma \qquad \beta \longmapsto \gamma$ (substitution of $\alpha ,\beta$ in A1 (first axiom)
$\alpha _{1}:=((\gamma \land \delta )\to \gamma )\to (\gamma \to (\gamma \land \delta )\to \gamma ))\in AXIOM$ $\alpha \longmapsto \gamma \qquad \beta \longmapsto \delta$ (substitution in A4)
$\alpha _{2}:=(\gamma \land \delta )\to \gamma \in AXIOM$
Now we have $\alpha _{1}=(\alpha _{2}\to \alpha _{3})$ hence we can conclude that
$\alpha _{3}=\gamma \to ((\gamma \land \delta )\to \gamma )\in THM$

It is really hard to find theorems in this way: in this course we don't have to learn this, just have to know how a formal syntactic demonstration are made. Thanks to completeness and validity theorem we can prove theorem through an easier way; infact it says that $THM\equiv TAUT$ the set of theorems and the set of tautologies coincide. Hence, proving that a formula is a tautology is equals to prove that a formula is a theorem. This is the bridge between Syntax and Semantic.

Theorem of validity and completeness. For all $\alpha \in FORM$ we have
$\vdash \alpha \leftrightarrow \models \alpha$

The demonstrable formulas coincide with tautologies.

Example: If I prove that $\neg (\alpha \land \neg \alpha )\in TAUT$ (using truth table or by reduction to absurd or any other way that use the values of the formulas (semantic)) then, it must exist a syntactical demonstration (starting from axioms and going on through modus ponens) to prove that formula.

We can divide the theorem in two part:

Theorem of validity:
$\vdash \alpha \to \models \alpha$
Theorem of completeness:
$\vdash \alpha \leftarrow \models \alpha$

It is very difficult to prove the theorem of completeness (in this course it isn't requested), but it is simple to prove the theorem of validity.

Theorem of validity proof: Before prove this theorem we have to prove that modus ponens (MP) preserves tautology:

$\forall \alpha ,\beta \in FORM$ if $\alpha ,(\alpha \to \beta )$ are tautologies then $\beta$ is a tautology.
Proof by absurdity: Let's suppose $\mu (\alpha )=1,\mu (\alpha \to \beta )=1,\mu (\beta )=0$
We have a contraddiction because $\mu (\alpha \to \beta )=0$
So MP preserves tautologicity.
Now we can face theorem of validity proof: $\forall \alpha \in FORM\vdash \alpha \to \models \alpha$ infact the hypothesis $\vdash \alpha$ means:

$\exists \alpha _{1},\alpha _{2},..,\alpha _{n}\in FORM$ such that $\alpha _{n}=\alpha$
1. or $\alpha _{i}\in AXIOM$ (then is a tautology for definition)
2. or $\alpha _{i}$ is proved by modus ponens.

So, thanks to preservation of tautologicy of MP, we have that $\alpha \in TAUT$

Decidability

When a logic is decidable? When exists a program that:
Input: $\alpha \in FORM$
Output: YES, if $\alpha \in THM$ , else NO.
The classical propositional logic is decidable because, for the theorem of completeness (and validity), we have $THM=TAUT$ , so the program can make the truth table of the formula and then check if all the evaluation are 1. Infact, if a formula's truth table have all the entry 1, we can say that $\alpha \in TAUT$ and so $\alpha \in THM$ .