Differenze tra le versioni di "Logica fuzzy"

Da WikiDsy.
(Syntax)
(Decidability)
 
(44 versioni intermedie di 2 utenti non mostrate)
Riga 3: Riga 3:
 
==A.A. passati ==
 
==A.A. passati ==
 
{{Annipassati|2007-2008|(Marra, Aguzzoli)|}}
 
{{Annipassati|2007-2008|(Marra, Aguzzoli)|}}
==Information ==
+
==Informations ==
 
[http://logicafuzzy.di.unimi.it/ Course's website]<br>
 
[http://logicafuzzy.di.unimi.it/ Course's website]<br>
 
Times and classrooms:<br>
 
Times and classrooms:<br>
Riga 12: Riga 12:
 
''This notes are written in english to help foreign students to follow this course.''
 
''This notes are written in english to help foreign students to follow this course.''
 
===Classical Propositional Logic===
 
===Classical Propositional Logic===
We are going to describe the classical propositional logic (L.P.C) language.
+
We are going to describe the classical propositional logic (CPL) language.
 
====Syntax====
 
====Syntax====
 
''The syntax of a language is the set of rules that specify '''how''' the elements of the language are formed regardless their meaning''.
 
''The syntax of a language is the set of rules that specify '''how''' the elements of the language are formed regardless their meaning''.
  
 
Let <math>\mathbb{N} = \{1, 2, ... \} </math> be the set of the natural numbers and <math>\mathbb{A} = \{ (, ), X, |, $, \rightarrow, \and, \or, \neg, \top, \bot \}</math> an alphabet of symbols.<br>
 
Let <math>\mathbb{N} = \{1, 2, ... \} </math> be the set of the natural numbers and <math>\mathbb{A} = \{ (, ), X, |, $, \rightarrow, \and, \or, \neg, \top, \bot \}</math> an alphabet of symbols.<br>
 +
The symbols <math>\bot, \top</math> are called respectively "falsum", "verum".<br>
 
<math>\mathbb{A}^\star</math> is the set of strings on this alphabet. For example <math>''(\top \and \bot)'' ,  ''(\neg \and'' , ''X(('' \in \mathbb{A}^\star</math>.<br>
 
<math>\mathbb{A}^\star</math> is the set of strings on this alphabet. For example <math>''(\top \and \bot)'' ,  ''(\neg \and'' , ''X(('' \in \mathbb{A}^\star</math>.<br>
 
We have now to define the set of the "well formed formula" <math>FORM</math>, that is the set of the elements of the L.P.C.<br>
 
We have now to define the set of the "well formed formula" <math>FORM</math>, that is the set of the elements of the L.P.C.<br>
Riga 46: Riga 47:
 
#Exist unique <math>\beta, \gamma \in FORM</math> such that <math>\alpha = (\beta \rightarrow \gamma)</math>.
 
#Exist unique <math>\beta, \gamma \in FORM</math> such that <math>\alpha = (\beta \rightarrow \gamma)</math>.
 
Let's, infact, consider the parser of the algorithm we talked above:
 
Let's, infact, consider the parser of the algorithm we talked above:
When it find, for example, <math>\neg(\alpha \and \beta)</math>, to decide if the string belongs to FORM, it have to decide (for the unique readability of well formed formulas) if <math>\alpha \and \beta \in FORM</math>. But how can it do this? Deciding if <math>\alpha \in FORM</math> and <math>\beta \in FORM</math>.
+
When it finds, for example, <math>\neg(\alpha \and \beta)</math>, to decide if the string belongs to FORM, it have to decide (for the unique readability of well formed formulas) if <math>\alpha \and \beta \in FORM</math>. But how can it do this? Deciding if <math>\alpha \in FORM</math> and <math>\beta \in FORM</math>.
 
This is what the above theorem tell us. Try to draw the parser tree. It is unique thanks to, again, that theorem.
 
This is what the above theorem tell us. Try to draw the parser tree. It is unique thanks to, again, that theorem.
  
Riga 105: Riga 106:
 
Exercise. Prove that the following formulas are tautologies for all <math>\alpha, \beta \in  FORM</math><br>
 
Exercise. Prove that the following formulas are tautologies for all <math>\alpha, \beta \in  FORM</math><br>
 
''Hint: use the truth table''<br>
 
''Hint: use the truth table''<br>
#<math>\alpha \or \neg\alpha</math>
+
#<math>\alpha \or \neg\alpha</math>     (Excluded middle)
#<math>\neg(\alpha \and \neg\alpha)</math>
+
#<math>\neg(\alpha \and \neg\alpha)</math>     (Not contradiction)
#<math>\neg\neg\alpha \leftrightarrow \alpha</math>
+
#<math>\neg\neg\alpha \leftrightarrow \alpha</math>       (Law of double negation)
 
#<math>\neg(\alpha \and \beta) \leftrightarrow \neg\alpha \or \neg\beta</math>          (De Morgan rule I)
 
#<math>\neg(\alpha \and \beta) \leftrightarrow \neg\alpha \or \neg\beta</math>          (De Morgan rule I)
 
#<math>\neg(\alpha \or \beta) \leftrightarrow \neg\alpha \and \neg\beta</math>          (De Morgan rule II)
 
#<math>\neg(\alpha \or \beta) \leftrightarrow \neg\alpha \and \neg\beta</math>          (De Morgan rule II)
#<math>\alpha \and \neg \alpha \to \beta</math>
+
#<math>\alpha \and \neg \alpha \to \beta</math>   (Ex falso quodlibet)
#<math>(\alpha \to \beta) \or (\beta \to \alpha)</math><br>
+
#<math>(\alpha \to \beta) \or (\beta \to \alpha)</math>   (Prelinearity)<br>
  
 
Exercise. Prove that exist <math>\alpha, \beta \in FORM</math> for those the following formulas aren't tautologies. Which of these are contradiction?<br>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.
 
Exercise. Prove that exist <math>\alpha, \beta \in FORM</math> for those the following formulas aren't tautologies. Which of these are contradiction?<br>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.
Riga 121: Riga 122:
 
====Relationship between syntax and semantic====
 
====Relationship between syntax and semantic====
  
Definition (Axioms of LPC (Classical propositional logic)). For all <math>\alpha, \beta, \gamma \in FORM</math>, let's consider the following formulas.
+
Definition (Axioms of CPL (Classical propositional logic)). For all <math>\alpha, \beta, \gamma \in FORM</math>, let's consider the following formulas.
 
#<math>\alpha \to (\beta \to \alpha)</math>
 
#<math>\alpha \to (\beta \to \alpha)</math>
 
#<math>(\alpha \to \beta) \to ((\alpha \to (\beta \to \gamma)) \to (\alpha \to \gamma))</math>
 
#<math>(\alpha \to \beta) \to ((\alpha \to (\beta \to \gamma)) \to (\alpha \to \gamma))</math>
Riga 133: Riga 134:
 
#<math>\alpha \to (\neg \alpha \to \beta)</math>
 
#<math>\alpha \to (\neg \alpha \to \beta)</math>
 
#<math>\neg\neg\alpha \to \alpha</math>
 
#<math>\neg\neg\alpha \to \alpha</math>
 +
#<math>\alpha \to \neg\neg \alpha</math>
  
The formulas between 1 and 11 <math>\in AXIOM \subset FORM</math>.<br><math>AXIOM</math> is called '''set of the axioms of the classical propositional logic'''.<br>
+
The formulas between 1 and 12 <math>\in AXIOM \subset FORM</math>.<br><math>AXIOM</math> is called '''set of the axioms of the classical propositional logic'''.<br>
 +
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 <math>AXIOM</math> is <math>\infty</math> because <math>\alpha, \beta, \gamma</math> can be other formulas. For example:<br>
 
The cardinality of <math>AXIOM</math> is <math>\infty</math> because <math>\alpha, \beta, \gamma</math> can be other formulas. For example:<br>
 
Let <math>\alpha := \beta \and \gamma</math> and substitute in the first axiom; it becomes<br>
 
Let <math>\alpha := \beta \and \gamma</math> and substitute in the first axiom; it becomes<br>
Riga 146: Riga 149:
 
A sequence of formulas like that is a formal demonstration of <math>\alpha</math>.<br>
 
A sequence of formulas like that is a formal demonstration of <math>\alpha</math>.<br>
 
'''Definition''' (modus ponens). Let <math>\alpha, \beta \in FORM</math>. We say that <math>\gamma \in FORM</math> is deducible, through modus ponens, if <math>\alpha = (\beta \to \gamma)</math>.
 
'''Definition''' (modus ponens). Let <math>\alpha, \beta \in FORM</math>. We say that <math>\gamma \in FORM</math> is deducible, through modus ponens, if <math>\alpha = (\beta \to \gamma)</math>.
For example:<br><math>\alpha := </math>"If it rains then I will stay home" <math>\beta := </math>"It rains" <math>\gamma := </math>"I go to school".
+
For example:<br><math>\alpha := </math>"If it rains then I will stay home" <math>\beta := </math>"It rains" <math>\gamma := </math>"I will stay home".
 
We know that <math>\alpha, \beta</math> are true, hence we can say that <math>\gamma</math> is true.
 
We know that <math>\alpha, \beta</math> are true, hence we can say that <math>\gamma</math> is true.
 
<br><br>The elements of <math>THM</math> are found in this way through modus ponens starting from elements of <math>AXIOM</math>.  
 
<br><br>The elements of <math>THM</math> are found in this way through modus ponens starting from elements of <math>AXIOM</math>.  
Riga 198: Riga 201:
 
##or <math>\alpha_i</math> is proved by modus ponens.
 
##or <math>\alpha_i</math> is proved by modus ponens.
 
So, thanks to preservation of tautologicy of MP, we have that <math>\alpha \in TAUT</math>
 
So, thanks to preservation of tautologicy of MP, we have that <math>\alpha \in TAUT</math>
 +
 +
====Decidability====
  
 
When a logic is decidable?
 
When a logic is decidable?
Riga 215: Riga 220:
 
#<math>\mu(\alpha) = 0 </math> we say that <math>\alpha</math> is false, or absolutely false;
 
#<math>\mu(\alpha) = 0 </math> we say that <math>\alpha</math> is false, or absolutely false;
 
#<math>\mu(\alpha) = 1 </math> we say that <math>\alpha</math> is true, or absolutely true;
 
#<math>\mu(\alpha) = 1 </math> we say that <math>\alpha</math> is true, or absolutely true;
#<math>\mu(\alpha) \in (0,1) </math> we cannot say that <math>\alpha</math> is true neither false.
+
#<math>\mu(\alpha) \in (0,1) </math> we cannot say that <math>\alpha</math> is true neither false. Although these values represent difference degrees of truth.
 +
For example:<br>
 +
<math>\mu(\alpha)=0.7\qquad \mu(\beta)=0.3</math> we can say that <math>\alpha</math> '''is truer''' then <math>\beta</math>. <br>
 +
Infact let <math>\alpha=</math>"Matt is young" and <math>\beta=</math>"Matt is old". <br>
 +
I'm 23 so I can say that I'm not absolutely young and not absolutely old so we can assign a value 0.7 to <math>\alpha</math> and 0.3 <math>\beta</math> because I'm more young than old.
  
 
Definition(Assignment). An atomic assignment is any function <br>
 
Definition(Assignment). An atomic assignment is any function <br>
<math>\mu_0: Var \rightarrow (0, 1)</math>.<br>
+
<math>\mu_0: Var \rightarrow [0, 1]</math>.<br>
 
An assignment (or interpretation) is a function<br>
 
An assignment (or interpretation) is a function<br>
<math>\mu: FORM \rightarrow (0, 1)</math><br>
+
<math>\mu: FORM \rightarrow [0, 1]</math><br>
 
that extends <math>\mu_0</math> and respects the following rules for every <math>\alpha, \beta \in FORM</math>.<br>
 
that extends <math>\mu_0</math> and respects the following rules for every <math>\alpha, \beta \in FORM</math>.<br>
 
#<math>\mu(\bot)= 0</math> and <math>\mu(\top) = 1</math>
 
#<math>\mu(\bot)= 0</math> and <math>\mu(\top) = 1</math>
Riga 227: Riga 236:
 
#<math>\mu((\alpha \or \beta)) = max(\mu(\alpha), \mu(\beta))</math>
 
#<math>\mu((\alpha \or \beta)) = max(\mu(\alpha), \mu(\beta))</math>
 
#<math>\mu((\alpha \rightarrow \beta)) = \begin{cases}1 & if \quad \mu(\alpha) \le \mu(\beta)\\\mu(\beta) & else \end{cases}</math>
 
#<math>\mu((\alpha \rightarrow \beta)) = \begin{cases}1 & if \quad \mu(\alpha) \le \mu(\beta)\\\mu(\beta) & else \end{cases}</math>
 +
 +
This is the sematic of Goedel logic but it is not the only fuzzy logic. There are many fuzzy logic with different semantic. So the question is "why those functions and not others?"
 +
The answer is because the semantic of every fuzzy logic must behave, for assignment in <math>{0,1}</math> as classical propositional logic.<br>
 +
 +
Even Godel logic satisfy the '''principle of truth-functionality''' so the value of <math>\mu(\alpha(X_1, ... , X_n))</math> depends only from the values assigned to <math>X_1, ..., X_n</math>.
 +
 +
'''Exercise'''. Let <math>\mu: FORM \to \{0,1\}</math>. Prove that the semantic of Goedel logic coincide with semantic of classical propositional logic for the formulas <math>\bot, \top, \neg \alpha, \alpha \and \beta, \alpha \or \beta, \alpha \to \beta</math>.
 +
 +
'''Exercise'''. let <math>\alpha, \beta \in FORM</math>. Prove that
 +
#<math>\mu(\neg\alpha)) = \mu(\alpha \to \bot)  \forall \mu: FORM \to [0, 1]</math> <br>The negation is semantically definable from implication and "falsum" (<math>\bot</math>).
 +
#<math>\mu(\alpha \leftrightarrow \beta) = 1</math> if and only if <math>\mu(\alpha) = \mu(\beta)</math><br>
 +
'''Exercise'''. Make a plot of every function of Goedel logic. (Some are in 3D).<br>
 +
Here's the graph of <math>\mu(\alpha \and \beta)</math> [http://www.livephysics.com/tools/mathematical-tools/online-3-d-function-grapher/?xmin=0&xmax=1&ymin=0&ymax=1&zmin=0&zmax=1&f=min%28x%2Cy%29 graph]
 +
 +
It is important to said that evary fuzzy logic assign <math>\mu(\alpha \to \beta) = 1</math> when <math>\mu(\alpha) \le \mu(\beta)</math> infact, without this, MP wouldn't preserve tautology in fuzzy logic and it would be impossible to prove the theorem of completeness in that fuzzy logic.
 +
 +
'''Definition''' (truth, not truth, falsehood). Let <math>\alpha \in FORM</math> and <math>\mu : FORM \to [0,1]</math>. When we have <math>\mu(\alpha) = 1 </math> we say that <math>\alpha</math> is true in the interpretation of <math>\mu</math>, or <math>\mu</math> is a model of <math>\alpha</math>. Instead, when we have <math>\mu(\alpha) < 1</math> we say that <math>\alpha</math> is not true in the interpretation of <math>\mu</math>.<br>In particular we say that <math>\alpha</math> is false in the interpretation of <math>\mu</math> when we have <math>\mu(\alpha) = 0</math>.
 +
In symbols:<br>
 +
<math>\mu \models_g \alpha</math> when <math>\mu(\alpha)=1</math><br>
 +
<math>\mu \not\models_g \alpha</math> when <math>\mu(\alpha)<1</math>.<br>
 +
When <math>\alpha</math> is true for every <math>\mu</math> we say that <math>\alpha</math> is a tautology. Instead when we have <math>\alpha</math> false for every assignment <math>\mu</math> we say that <math>\alpha</math> is a contradiction.
 +
When exists a <math>\mu</math> such as <math>\mu(\alpha) = 1</math> we say that <math>\alpha</math> is satisfiable; instead when exists a <math>\mu</math> such as <math>\mu(\alpha) < 1</math> we say that <math>\alpha</math> is refutable.<br>
 +
In symbols:<br>
 +
<math>\models_g \alpha</math> tautology<br>
 +
<math>\not\models_g \alpha</math> refutable<br><br>
 +
Exercise. Establish which of the following formulas are tautology in Godel Logic and which not. Hint: use truth table for <math>\mu(\alpha) = \{0, 0.5, 1\}</math><br>
 +
#<math>\alpha \or \neg\alpha</math>    (Excluded middle)
 +
#<math>\neg(\alpha \and \neg\alpha)</math>    (Not contradiction)
 +
#<math>\neg\neg\alpha \leftrightarrow \alpha</math>        (Law of double negation)
 +
#<math>\neg(\alpha \and \beta) \leftrightarrow \neg\alpha \or \neg\beta</math>          (De Morgan rule I)
 +
#<math>\neg(\alpha \or \beta) \leftrightarrow \neg\alpha \and \neg\beta</math>          (De Morgan rule II)
 +
#<math>\alpha \and \neg \alpha \to \beta</math>    (Ex falso quodlibet)
 +
#<math>(\alpha \to \beta) \or (\beta \to \alpha)</math>    (Prelinearity)<br> 
 +
 +
For example: The law of Excluded middle is not a tautology in Godel Logic, infact for <math>\mu(\alpha)=0.5</math> we have that <math>\mu(\alpha \or \neg\alpha)=0.5</math>.
 +
 +
It is clear that the semantic of Godel logic is equal to classical logic only for boolean values of the variables. The exercise above shows that some tautology in classical logic aren't tautology in Godel logic. Summing up:<br>
 +
 +
'''Proposition'''. If <math>\alpha</math> is a tautology is Godel logic then is a tautology <math>\alpha</math> is a tautology in classical logic, but the reverse isn't true.<br>
 +
<math>\models_g \alpha \to \models \alpha</math><br>
 +
<math>TAUT_g \subset TAUT</math><br>
 +
Exercise. Prove the above proposition.
 +
Here's my proof:<br>
 +
<math>\alpha \in TAUT_g \leftrightarrow \forall \mu_g  \quad \mu(\alpha) = 1 </math> where <math>\mu_g : FORM \to [0,1]</math><br>
 +
<math>\alpha \in TAUT \leftrightarrow \forall \mu  \quad \mu(\alpha) = 1 </math> where <math>\mu : FORM \to \{0,1\}</math><br>
 +
Well, as we said above, Godel logic, under classical assignment <math>\{0, 1\}</math>, behaves the same way of the classical one; so, when we say that <math>\alpha</math> is a tautology in Godel Logic, we mean that <math>\forall \mu_g \quad \mu_g(\alpha)=1</math> but in these there are the classical ones! Therefore <math>\alpha \in TAUT</math> also.<br>
 +
 +
====Relationship between syntax and semantic====
 +
 +
Definition (Axioms of GL (Godel logic)). For all <math>\alpha, \beta, \gamma \in FORM</math>, let's consider the following formulas.
 +
#<math>\alpha \to (\beta \to \alpha)</math>
 +
#<math>(\alpha \to \beta) \to ((\alpha \to (\beta \to \gamma)) \to (\alpha \to \gamma))</math>
 +
#<math>\alpha \to (\beta \to (\alpha \and \beta))</math>
 +
#<math>(\alpha \and \beta) \to \alpha</math>
 +
#<math>(\alpha \and \beta) \to \beta</math>
 +
#<math>(\alpha \to (\alpha \and \beta))</math>
 +
#<math>(\alpha \to (\alpha \and \beta))</math>
 +
#<math>(\alpha \to \gamma) \to ((\beta \to \gamma) \to ((\alpha \or \beta) \to \gamma))</math>
 +
#<math>(\alpha \to \beta) \to ((\alpha \to \neg \beta) \to \neg \alpha)</math>
 +
#<math>\alpha \to (\neg \alpha \to \beta)</math>
 +
#
 +
#<math>\alpha \to \neg\neg \alpha</math>
 +
 +
The formulas between 1 and 10, 12 <math>\in AXIOM_g \subset FORM</math>.<br><math>AXIOM_g</math> is called '''set of the axioms of Godel logic'''.<br>
 +
<math>AXIOM_g \subset AXIOM</math>.
 +
 +
Exercise. Choose some formulas <math>\in AXIOM_g</math> and prove that they are tautology. Note: to prove that a formula isn't a tautology we used a counter-example but now we have to prove that a formula is a tautology. The cardinality of <math>[0,1]</math> is <math>\infty</math> so we can't try every assignment...The solution is to choose <math>\mu</math> that represents a class of <math>\mu</math>. For example, we want to prove that <math>\alpha \to \neg\neg \alpha</math> is a tautology. So we have three cases:
 +
#<math>\mu(\alpha) = 0</math>
 +
#<math>\mu(\alpha) = 1</math>
 +
#<math>\mu(\alpha) = 0.5</math> that represents all the <math>0 < \mu(\alpha) < 1</math>
 +
We have to evaluate the whole formula in these three cases. The evaluation is always true.
 +
Hint: the number of cases depends on the number of variables; infact, to prove A1, we have to consider 3 x 3 assignment.
 +
This will be clearer when we will face Decidibility of Godel Logic.
 +
 +
'''Theorem of validity and completeness'''. For all <math>\alpha \in FORM</math> we have <br>
 +
<math>\vdash_g \alpha \leftrightarrow \models_g \alpha</math>
 +
 +
The demonstrable formulas coincide with tautologies also in Godel Logic.
 +
We can split the theorem in two part:
 +
*Theorem of validity: <math>\vdash_g \alpha \rightarrow \models_g \alpha</math>
 +
*Theorem of completeness: <math>\vdash_g \alpha \leftarrow \models_g \alpha</math>
 +
Even here we prove only the former because the latter is too much harder.
 +
 +
'''Theorem of validity proof (in GD)'''
 +
We had to prove two propositions in order to prove the theorem:
 +
#<math>AXIOM_G \subseteq TAUT_G</math><br> It was the exercise above.
 +
#MP (Modus ponens) preserves tautology in GD also. <br>To prove this proposition we have to prove that if <math>\mu(\alpha) = 1 \quad \mu(\alpha \rightarrow \beta) = 1</math> then <math>\mu(\beta) = 1</math>. Thanks to the semantic definition of implication in GD, it is clear that <math>\mu(\beta)</math> can be only <math>= 1</math> with that conditions.
 +
 +
'''Proposition'''. Every formula proved in GL is proved also in CPL.
 +
 +
====Decidability====
 +
 +
Godel logic is decidable if exists a program such that:
 +
Input: <math>\alpha \in FORM</math>
 +
Output: Yes if <math>\alpha \in THM_g</math>, No else.
 +
 +
In the Classical Logic this program exists, as we said above; infact we just have to write the truth table of the formula and check if every entry result is 1. More formally, for every possible assignment <math>\mu(X_1, X_2, .. , X_n) \to \{0,1\}</math> we check if <math>\mu(\alpha) = 1</math>; if at least one <math>\mu(\alpha) \not= 1</math> we can conclude that <math>\alpha \not\in THM</math>.
 +
This method doesn't work for Godel Logic because of the number of <math>\mu_g(X_1, X_2, .. , X_n) \to [0,1]</math> that is infinity. In other words, the truth table of every formula cannot be computed.
 +
 +
Nevertheless Godel Logic is decidable. The reason is because it is possible to reduce, as we will see later, the infinity number of assignment <math>\mu_g \to [0,1]</math> to a finite number of cases.
 +
 +
Take a look at all the possible plots of <math>\mu(\alpha(X_1)), \alpha \in FORM_1</math> [[file:Plot.pdf]].
 +
 +
Note that, everytime we have <math>\mu(X_1)=a</math> where <math>0 < a < 1</math> and <math>\mu(\alpha) = 1</math> we have also <math>\mu(\alpha)=1</math> for every assignment <math>0 < \mu(X_1) < 1</math>. This consideration is defined in the two following theorems.
 +
 +
'''Definition'''(Equivalent assignments). Let <math>\mu, \nu : FORM \to [0,1]</math> be two assignments. We can say the <math>\mu, \nu</math> are equivalent (on the first n variables) if exists a permutation <math>\sigma : \{1, ... , n\} \to \{1, ... , n\}</math> and a function <math> s : {0,1, ... , n} \to \{<,=\}</math> such that <br><br>
 +
<math>0s(0)\mu(X_{\sigma(1)})s(1)\mu(X_{\sigma(1)})...s(n-1)\mu(X_{\sigma(n)})s(n)1</math><br><br>
 +
<math>0s(0)\nu(X_{\sigma(1)})s(1)\nu(X_{\sigma(1)})...s(n-1)\nu(X_{\sigma(n)})s(n)1</math><br><br>
 +
In this case we can write like this:<br>
 +
<math>\mu \equiv_n \nu</math><br>
 +
To understand the definition above, here's an example.<br>
 +
Example. We fix the number of variables <math>n = 1</math>. Let's consider the assignment <math>\mu(X_1) = \frac{1}{2}\ \nu(X_1) = \frac{2}{3}</math>
 +
Then <math> \mu \equiv_1 \nu </math><br>
 +
Infact, seen that <math>n = 1</math>, there is no choice for the permutation <math>\sigma : {1} \to {1}</math>. The only one is the identity function <math>\sigma(1) ) = 1</math>. For the function <math>s : {0,1} \to {<,=}</math> we choose <math>s(0) = < \ s(1) = <</math>. <br>
 +
Then <math> 0 < \frac{1}{2} < 1</math> and <math> 0 < \frac{2}{3} < 1</math> as the definition request.
 +
Instead, if we had <math>\nu(X_1) = 0 </math> we would have <math>\mu \not\equiv_1 \nu</math><br>
 +
because <math>0 < \frac{1}{2} < 1</math> but <math> 0 < 0 < 1 </math> isn't true.
 +
We can conclude that two assignment <math>\mu, \nu</math> are equivalent on the first variable if one of the following sentences is true:
 +
#<math>\mu(X_1) = \nu(X_1) = 0</math>
 +
#<math>\mu(X_1) = \nu(X_1) = 1</math>
 +
#<math>\mu(X_1), \nu(X_1) \in (0,1)</math>
 +
 +
'''Proposition'''. The relation <math>\equiv_n</math> on the set of all possible assignments is an equivalent relation, infact it is reflexive, symmetric, transitive.
 +
 +
Because of it is a equivalent relation, it partitions the set of all assignments, so we can define the equivalent classes like this:
 +
 +
<math>[a]_R = \{b \in A | aRb\}</math> where <math>A</math> is the set of all possible assignments.
 +
 +
We can write
 +
 +
<math>\mathcal{F}_n = \{[\mu]_{\equiv n} | \mu: FORM \to [0,1]\}</math>
 +
 +
to refer to the quotient set of the relation <math>\equiv_n</math> on the set of all possible assignment.
 +
We can call it also ''family of all equivalence classes''.
 +
 +
'''Proposition'''. <math>\mathcal{F}_n</math> is a finite set.
 +
 +
Example: for <math>n = 1\ |\mathcal{F}_n| = 3</math> infact we have
 +
#<math>[\mu]_{\equiv 1} = \{\eta : FORM \to [0,1]\  |\  \eta(X_1) = 0 \}</math>
 +
#<math>[\nu]_{\equiv 1} = \{\eta : FORM \to [0,1]\  |\  \eta(X_1) = 1 \}</math>
 +
#<math>[\theta]_{\equiv 1} = \{\eta : FORM \to [0,1]\  |\  0 < \eta(X_1) < 1 \}</math>
 +
 +
 +
'''Lemma''' (possible worlds reduction). Let be <math>\mu, \nu : FORM \to [0,1]</math> two assignments. If
 +
 +
<math>\mu\equiv_n\nu</math>
 +
 +
then for every formula <math>\alpha(X_1,...,X_n) \in FORM</math>
 +
 +
<math>\mu \models_g \alpha(X_1, ... , X_n)</math> if and only if <math>\nu \models_g \alpha(X_1, ... , X_n)</math>.
 +
 +
on the other hand, if <math>\mu \not\equiv_n \nu</math> then
 +
 +
exists a formula <math>\alpha(X_1, ... , X_n) \in FORM</math> such that it true that either
 +
 +
<math>\mu \models_g \alpha(X_1, ... , X_n)</math> but <math>\nu \not\models_g \alpha(X_1, ... , X_n)</math>
 +
 +
or
 +
 +
<math>\mu \not\models_g \alpha(X_1, ... , X_n)</math> but <math>\nu \models_g \alpha(X_1, ... , X_n)</math>
 +
 +
 +
It was a very strong theorem because, to prove that <math>\alpha \in TAUT</math> where <math> \alpha \in FORM</math> is now possible:
 +
infact we cannot compute <math>\mu(\alpha)</math> for every possible <math>\mu</math>, because the set <math>A = \{\mu : FORM \to [0,1]\}</math> it is an infinitive set '''but we can''' compute <math>\mu(\alpha), \mu \in \mathcal{F}_n</math> because it is a finite set and, thanks the lemma above, we know that it is the same thing.
 +
 +
Now we can write the algorithm we talked at the beginning of the paragraph:
 +
 +
Input: <math>\alpha \in FORM_n</math>
 +
 +
#Enumerate of the possible permutations <math>\sigma : \{1, ... , n\} \to \{1, ... , n\}</math>
 +
#Enumerate of the possible <math>s : \{0, ... , n\} \to \{=, <\}</math>
 +
#For every couple <math>(\sigma, s)</math> find, if exists, an assignment <math>\mu : FORM \to [0,1]</math> such that it is true <br><math>0s(0)\mu(X_{\sigma(1)})s(1)\mu(X_{\sigma(1)})...s(n-1)\mu(X_{\sigma(n)})s(n)1</math><br>
 +
#Compute <math>\mu(\alpha)</math>
 +
#if <math>\mu(\alpha) < 1</math> exit with output NO else go on cycling
 +
#Exit with output YES
 +
 +
Note that:
 +
#finding <math>\mu</math> such that it is true that <math>0s(0)\mu(X_{\sigma(1)})s(1)\mu(X_{\sigma(1)})...s(n-1)\mu(X_{\sigma(n)})s(n)1</math> is equals to finding an representative <math>\mu</math> for its own equivalence class.
 +
#We can arrive to step 6 if only, for every representative <math>\mu</math>, we have <math>\mu(\alpha) = 1</math>
 +
#<math>|\sigma| = n!, |s| = 2^{n+1}</math>
 +
 +
<math>|\mathcal{F}_n| \le n!2^{n+1}</math> because there are repetitions or untrue sentences. For example:
 +
 +
it cannot exist a <math>\mu</math> such that <math>0=\mu(X_1)=1</math>.
 +
 +
====Last concepts (Devo ancora decidire che titolo dargli)====
 +
 +
The last concepts' notes (of the first part of the course) are written directly in latex because are full of plots and Hasse diagrams.
 +
[[file:Posets Hesse.pdf]]

Versione attuale delle 15:47, 4 gen 2013

Disambigua compass.PNG
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.

A.A. passati

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:

  1. \top ,\bot \in FORM
  2. \forall n\in {\mathbb  {N}}
    \qquad X||...|\$\in FORM, where | is taken n times. For example: X|\$,X||\$,X|||\$,....\in FORM
  3. if \alpha ,\beta \in FORM, then (\neg \alpha )\in FORM.
  4. if \alpha ,\beta \in FORM, then (\alpha \land \beta )\in FORM.
  5. if \alpha ,\beta \in FORM, then (\alpha \lor \beta )\in FORM.
  6. 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 FORMone (and only one) of the following sentences must be true:

  1. \alpha =\bot or \alpha =\top but not both.
  2. Exists an unique n\in {\mathbb  {N}} such that \alpha =X_{n}.
  3. Exists an unique \beta \in FORM such that \alpha =(\neg \beta ).
  4. Exist unique \beta ,\gamma \in FORM such that \alpha =(\beta \land \gamma ).
  5. Exist unique \beta ,\gamma \in FORM such that \alpha =(\beta \lor \gamma ).
  6. 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.

  1. \mu (\bot )=0 and \mu (\top )=1
  2. \mu ((\neg \alpha ))={\begin{cases}1&if\quad \mu (\alpha )=0\\0&if\quad \mu (\alpha )=1\end{cases}}
  3. \mu ((\alpha \land \beta ))={\begin{cases}1&if\quad \mu (\alpha )=1\quad and\quad \mu (\beta )=1\\0&else\end{cases}}
  4. \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}}
  5. \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

  1. \alpha \lor \neg \alpha (Excluded middle)
  2. \neg (\alpha \land \neg \alpha ) (Not contradiction)
  3. \neg \neg \alpha \leftrightarrow \alpha (Law of double negation)
  4. \neg (\alpha \land \beta )\leftrightarrow \neg \alpha \lor \neg \beta (De Morgan rule I)
  5. \neg (\alpha \lor \beta )\leftrightarrow \neg \alpha \land \neg \beta (De Morgan rule II)
  6. \alpha \land \neg \alpha \to \beta (Ex falso quodlibet)
  7. (\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.

  1. X_{1}
  2. \alpha \to \neg \alpha
  3. (\alpha \to \beta )\to (\neg \alpha \to \beta )
  4. \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.

  1. \alpha \to (\beta \to \alpha )
  2. (\alpha \to \beta )\to ((\alpha \to (\beta \to \gamma ))\to (\alpha \to \gamma ))
  3. \alpha \to (\beta \to (\alpha \land \beta ))
  4. (\alpha \land \beta )\to \alpha
  5. (\alpha \land \beta )\to \beta
  6. (\alpha \to (\alpha \land \beta ))
  7. (\alpha \to (\alpha \land \beta ))
  8. (\alpha \to \gamma )\to ((\beta \to \gamma )\to ((\alpha \lor \beta )\to \gamma ))
  9. (\alpha \to \beta )\to ((\alpha \to \neg \beta )\to \neg \alpha )
  10. \alpha \to (\neg \alpha \to \beta )
  11. \neg \neg \alpha \to \alpha
  12. \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:

  1. Theorem of validity:
    \vdash \alpha \to \models \alpha
  2. 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:

  1. \exists \alpha _{1},\alpha _{2},..,\alpha _{n}\in FORM such that\alpha _{n}=\alpha
  2. \forall i=1,..,n
    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.

Godel logic

Syntax

The syntax of Godel logic is the same of the syntax of the classical propositional logic, so we have that FORM_{G}=FORM_{{LC}}.
So we can write FORM.

Semantic

The semantic in the Godel logic is polyvalent infact \alpha \in FORM assumes values in [0,1].
When:

  1. \mu (\alpha )=0 we say that \alpha is false, or absolutely false;
  2. \mu (\alpha )=1 we say that \alpha is true, or absolutely true;
  3. \mu (\alpha )\in (0,1) we cannot say that \alpha is true neither false. Although these values represent difference degrees of truth.

For example:
\mu (\alpha )=0.7\qquad \mu (\beta )=0.3 we can say that \alpha is truer then \beta .
Infact let \alpha ="Matt is young" and \beta ="Matt is old".
I'm 23 so I can say that I'm not absolutely young and not absolutely old so we can assign a value 0.7 to \alpha and 0.3 \beta because I'm more young than old.

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.

  1. \mu (\bot )=0 and \mu (\top )=1
  2. \mu ((\neg \alpha ))={\begin{cases}1&if\quad \mu (\alpha )=0\\0&if\quad \mu (\alpha )>0\end{cases}}
  3. \mu ((\alpha \land \beta ))=min(\mu (\alpha ),\mu (\beta ))
  4. \mu ((\alpha \lor \beta ))=max(\mu (\alpha ),\mu (\beta ))
  5. \mu ((\alpha \rightarrow \beta ))={\begin{cases}1&if\quad \mu (\alpha )\leq \mu (\beta )\\\mu (\beta )&else\end{cases}}

This is the sematic of Goedel logic but it is not the only fuzzy logic. There are many fuzzy logic with different semantic. So the question is "why those functions and not others?" The answer is because the semantic of every fuzzy logic must behave, for assignment in {0,1} as classical propositional logic.

Even Godel logic satisfy the principle of truth-functionality so the value of \mu (\alpha (X_{1},...,X_{n})) depends only from the values assigned to X_{1},...,X_{n}.

Exercise. Let \mu :FORM\to \{0,1\}. Prove that the semantic of Goedel logic coincide with semantic of classical propositional logic for the formulas \bot ,\top ,\neg \alpha ,\alpha \land \beta ,\alpha \lor \beta ,\alpha \to \beta .

Exercise. let \alpha ,\beta \in FORM. Prove that

  1. \mu (\neg \alpha ))=\mu (\alpha \to \bot )\forall \mu :FORM\to [0,1]
    The negation is semantically definable from implication and "falsum" (\bot ).
  2. \mu (\alpha \leftrightarrow \beta )=1 if and only if \mu (\alpha )=\mu (\beta )

Exercise. Make a plot of every function of Goedel logic. (Some are in 3D).
Here's the graph of \mu (\alpha \land \beta ) graph

It is important to said that evary fuzzy logic assign \mu (\alpha \to \beta )=1 when \mu (\alpha )\leq \mu (\beta ) infact, without this, MP wouldn't preserve tautology in fuzzy logic and it would be impossible to prove the theorem of completeness in that fuzzy logic.

Definition (truth, not truth, falsehood). Let \alpha \in FORM and \mu :FORM\to [0,1]. 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 )<1 we say that \alpha is not true in the interpretation of \mu .
In particular we say that \alpha is false in the interpretation of \mu when we have \mu (\alpha )=0. In symbols:
\mu \models _{g}\alpha when \mu (\alpha )=1
\mu \not \models _{g}\alpha when \mu (\alpha )<1.
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 )<1 we say that \alpha is refutable.
In symbols:
\models _{g}\alpha tautology
\not \models _{g}\alpha refutable

Exercise. Establish which of the following formulas are tautology in Godel Logic and which not. Hint: use truth table for \mu (\alpha )=\{0,0.5,1\}

  1. \alpha \lor \neg \alpha (Excluded middle)
  2. \neg (\alpha \land \neg \alpha ) (Not contradiction)
  3. \neg \neg \alpha \leftrightarrow \alpha (Law of double negation)
  4. \neg (\alpha \land \beta )\leftrightarrow \neg \alpha \lor \neg \beta (De Morgan rule I)
  5. \neg (\alpha \lor \beta )\leftrightarrow \neg \alpha \land \neg \beta (De Morgan rule II)
  6. \alpha \land \neg \alpha \to \beta (Ex falso quodlibet)
  7. (\alpha \to \beta )\lor (\beta \to \alpha ) (Prelinearity)

For example: The law of Excluded middle is not a tautology in Godel Logic, infact for \mu (\alpha )=0.5 we have that \mu (\alpha \lor \neg \alpha )=0.5.

It is clear that the semantic of Godel logic is equal to classical logic only for boolean values of the variables. The exercise above shows that some tautology in classical logic aren't tautology in Godel logic. Summing up:

Proposition. If \alpha is a tautology is Godel logic then is a tautology \alpha is a tautology in classical logic, but the reverse isn't true.
\models _{g}\alpha \to \models \alpha
TAUT_{g}\subset TAUT
Exercise. Prove the above proposition. Here's my proof:
\alpha \in TAUT_{g}\leftrightarrow \forall \mu _{g}\quad \mu (\alpha )=1 where \mu _{g}:FORM\to [0,1]
\alpha \in TAUT\leftrightarrow \forall \mu \quad \mu (\alpha )=1 where \mu :FORM\to \{0,1\}
Well, as we said above, Godel logic, under classical assignment \{0,1\}, behaves the same way of the classical one; so, when we say that \alpha is a tautology in Godel Logic, we mean that \forall \mu _{g}\quad \mu _{g}(\alpha )=1 but in these there are the classical ones! Therefore \alpha \in TAUT also.

Relationship between syntax and semantic

Definition (Axioms of GL (Godel logic)). For all \alpha ,\beta ,\gamma \in FORM, let's consider the following formulas.

  1. \alpha \to (\beta \to \alpha )
  2. (\alpha \to \beta )\to ((\alpha \to (\beta \to \gamma ))\to (\alpha \to \gamma ))
  3. \alpha \to (\beta \to (\alpha \land \beta ))
  4. (\alpha \land \beta )\to \alpha
  5. (\alpha \land \beta )\to \beta
  6. (\alpha \to (\alpha \land \beta ))
  7. (\alpha \to (\alpha \land \beta ))
  8. (\alpha \to \gamma )\to ((\beta \to \gamma )\to ((\alpha \lor \beta )\to \gamma ))
  9. (\alpha \to \beta )\to ((\alpha \to \neg \beta )\to \neg \alpha )
  10. \alpha \to (\neg \alpha \to \beta )
  11. \alpha \to \neg \neg \alpha

The formulas between 1 and 10, 12 \in AXIOM_{g}\subset FORM.
AXIOM_{g} is called set of the axioms of Godel logic.
AXIOM_{g}\subset AXIOM.

Exercise. Choose some formulas \in AXIOM_{g} and prove that they are tautology. Note: to prove that a formula isn't a tautology we used a counter-example but now we have to prove that a formula is a tautology. The cardinality of [0,1] is \infty so we can't try every assignment...The solution is to choose \mu that represents a class of \mu . For example, we want to prove that \alpha \to \neg \neg \alpha is a tautology. So we have three cases:

  1. \mu (\alpha )=0
  2. \mu (\alpha )=1
  3. \mu (\alpha )=0.5 that represents all the 0<\mu (\alpha )<1

We have to evaluate the whole formula in these three cases. The evaluation is always true. Hint: the number of cases depends on the number of variables; infact, to prove A1, we have to consider 3 x 3 assignment. This will be clearer when we will face Decidibility of Godel Logic.

Theorem of validity and completeness. For all \alpha \in FORM we have
\vdash _{g}\alpha \leftrightarrow \models _{g}\alpha

The demonstrable formulas coincide with tautologies also in Godel Logic. We can split the theorem in two part:

  • Theorem of validity: \vdash _{g}\alpha \rightarrow \models _{g}\alpha
  • Theorem of completeness: \vdash _{g}\alpha \leftarrow \models _{g}\alpha

Even here we prove only the former because the latter is too much harder.

Theorem of validity proof (in GD) We had to prove two propositions in order to prove the theorem:

  1. AXIOM_{G}\subseteq TAUT_{G}
    It was the exercise above.
  2. MP (Modus ponens) preserves tautology in GD also.
    To prove this proposition we have to prove that if \mu (\alpha )=1\quad \mu (\alpha \rightarrow \beta )=1 then \mu (\beta )=1. Thanks to the semantic definition of implication in GD, it is clear that \mu (\beta ) can be only =1 with that conditions.

Proposition. Every formula proved in GL is proved also in CPL.

Decidability

Godel logic is decidable if exists a program such that: Input: \alpha \in FORM Output: Yes if \alpha \in THM_{g}, No else.

In the Classical Logic this program exists, as we said above; infact we just have to write the truth table of the formula and check if every entry result is 1. More formally, for every possible assignment \mu (X_{1},X_{2},..,X_{n})\to \{0,1\} we check if \mu (\alpha )=1; if at least one \mu (\alpha )\not =1 we can conclude that \alpha \not \in THM. This method doesn't work for Godel Logic because of the number of \mu _{g}(X_{1},X_{2},..,X_{n})\to [0,1] that is infinity. In other words, the truth table of every formula cannot be computed.

Nevertheless Godel Logic is decidable. The reason is because it is possible to reduce, as we will see later, the infinity number of assignment \mu _{g}\to [0,1] to a finite number of cases.

Take a look at all the possible plots of \mu (\alpha (X_{1})),\alpha \in FORM_{1} File:Plot.pdf.

Note that, everytime we have \mu (X_{1})=a where 0<a<1 and \mu (\alpha )=1 we have also \mu (\alpha )=1 for every assignment 0<\mu (X_{1})<1. This consideration is defined in the two following theorems.

Definition(Equivalent assignments). Let \mu ,\nu :FORM\to [0,1] be two assignments. We can say the \mu ,\nu are equivalent (on the first n variables) if exists a permutation \sigma :\{1,...,n\}\to \{1,...,n\} and a function s:{0,1,...,n}\to \{<,=\} such that

0s(0)\mu (X_{{\sigma (1)}})s(1)\mu (X_{{\sigma (1)}})...s(n-1)\mu (X_{{\sigma (n)}})s(n)1

0s(0)\nu (X_{{\sigma (1)}})s(1)\nu (X_{{\sigma (1)}})...s(n-1)\nu (X_{{\sigma (n)}})s(n)1

In this case we can write like this:
\mu \equiv _{n}\nu
To understand the definition above, here's an example.
Example. We fix the number of variables n=1. Let's consider the assignment \mu (X_{1})={\frac  {1}{2}}\ \nu (X_{1})={\frac  {2}{3}} Then \mu \equiv _{1}\nu
Infact, seen that n=1, there is no choice for the permutation \sigma :{1}\to {1}. The only one is the identity function \sigma (1))=1. For the function s:{0,1}\to {<,=} we choose s(0)=<\ s(1)=<.
Then 0<{\frac  {1}{2}}<1 and 0<{\frac  {2}{3}}<1 as the definition request. Instead, if we had \nu (X_{1})=0 we would have \mu \not \equiv _{1}\nu
because 0<{\frac  {1}{2}}<1 but 0<0<1 isn't true. We can conclude that two assignment \mu ,\nu are equivalent on the first variable if one of the following sentences is true:

  1. \mu (X_{1})=\nu (X_{1})=0
  2. \mu (X_{1})=\nu (X_{1})=1
  3. \mu (X_{1}),\nu (X_{1})\in (0,1)

Proposition. The relation \equiv _{n} on the set of all possible assignments is an equivalent relation, infact it is reflexive, symmetric, transitive.

Because of it is a equivalent relation, it partitions the set of all assignments, so we can define the equivalent classes like this:

[a]_{R}=\{b\in A|aRb\} where A is the set of all possible assignments.

We can write

{\mathcal  {F}}_{n}=\{[\mu ]_{{\equiv n}}|\mu :FORM\to [0,1]\}

to refer to the quotient set of the relation \equiv _{n} on the set of all possible assignment. We can call it also family of all equivalence classes.

Proposition. {\mathcal  {F}}_{n} is a finite set.

Example: for n=1\ |{\mathcal  {F}}_{n}|=3 infact we have

  1. [\mu ]_{{\equiv 1}}=\{\eta :FORM\to [0,1]\ |\ \eta (X_{1})=0\}
  2. [\nu ]_{{\equiv 1}}=\{\eta :FORM\to [0,1]\ |\ \eta (X_{1})=1\}
  3. [\theta ]_{{\equiv 1}}=\{\eta :FORM\to [0,1]\ |\ 0<\eta (X_{1})<1\}


Lemma (possible worlds reduction). Let be \mu ,\nu :FORM\to [0,1] two assignments. If

\mu \equiv _{n}\nu

then for every formula \alpha (X_{1},...,X_{n})\in FORM

\mu \models _{g}\alpha (X_{1},...,X_{n}) if and only if \nu \models _{g}\alpha (X_{1},...,X_{n}).

on the other hand, if \mu \not \equiv _{n}\nu then

exists a formula \alpha (X_{1},...,X_{n})\in FORM such that it true that either

\mu \models _{g}\alpha (X_{1},...,X_{n}) but \nu \not \models _{g}\alpha (X_{1},...,X_{n})

or

\mu \not \models _{g}\alpha (X_{1},...,X_{n}) but \nu \models _{g}\alpha (X_{1},...,X_{n})


It was a very strong theorem because, to prove that \alpha \in TAUT where \alpha \in FORM is now possible: infact we cannot compute \mu (\alpha ) for every possible \mu , because the set A=\{\mu :FORM\to [0,1]\} it is an infinitive set but we can compute \mu (\alpha ),\mu \in {\mathcal  {F}}_{n} because it is a finite set and, thanks the lemma above, we know that it is the same thing.

Now we can write the algorithm we talked at the beginning of the paragraph:

Input: \alpha \in FORM_{n}

  1. Enumerate of the possible permutations \sigma :\{1,...,n\}\to \{1,...,n\}
  2. Enumerate of the possible s:\{0,...,n\}\to \{=,<\}
  3. For every couple (\sigma ,s) find, if exists, an assignment \mu :FORM\to [0,1] such that it is true
    0s(0)\mu (X_{{\sigma (1)}})s(1)\mu (X_{{\sigma (1)}})...s(n-1)\mu (X_{{\sigma (n)}})s(n)1
  4. Compute \mu (\alpha )
  5. if \mu (\alpha )<1 exit with output NO else go on cycling
  6. Exit with output YES

Note that:

  1. finding \mu such that it is true that 0s(0)\mu (X_{{\sigma (1)}})s(1)\mu (X_{{\sigma (1)}})...s(n-1)\mu (X_{{\sigma (n)}})s(n)1 is equals to finding an representative \mu for its own equivalence class.
  2. We can arrive to step 6 if only, for every representative \mu , we have \mu (\alpha )=1
  3. |\sigma |=n!,|s|=2^{{n+1}}

|{\mathcal  {F}}_{n}|\leq n!2^{{n+1}} because there are repetitions or untrue sentences. For example:

it cannot exist a \mu such that 0=\mu (X_{1})=1.

Last concepts (Devo ancora decidire che titolo dargli)

The last concepts' notes (of the first part of the course) are written directly in latex because are full of plots and Hasse diagrams. File:Posets Hesse.pdf