Introducció a la lògica 2020 (Codi oficial: 360906; Grup A1)

Organització

Professor: Joost J. Joosten, Coordinació: José Martínez Fernández

El curs és de 6 crédits el qual correspon amb 50 hores de contacte.

Les clases es fan en català (o alguna cosa semblant) al aula 403 a Montalegre 6.

Dimarts: 10:00 -- 11:00;

Dimecres: 10:00 -- 11:00;

Dijous: 10:00 -- 11:00;

En aquesta pàgina anirem anotant el progres i potser posarem alguns apunts.

El professor de les sessions de problemes és en Quim Casals Buñuel en l'horari de 11:00 a 12:00 i sempre l'aula 403.

En Quim també impartirá la mayoría de les classes teóriques dels dimecres. Com sabeu vosaltres millor que jo, tenim dos grups `bombolla'. Una setmana un grup, l'altre setmana un altre. Farem servir el streaming i aquesta pàgina. En la avaluació continuada farem un midterm exam i un examen final per a cada grup `bombolla'.

Fem servir el llibre Elementos de lógica formal en la segona edició dels autors Calixto Badesa, Ignasi Jané, i en Ramon Jansana. L'editora és Ariel. Filosifia.

Dates primer parcial: dimecres 11 de novembre de 13:00 -- 14:00.;
Els alumnes amb NIUB senar han d'anar al 403.
Els alumnes amb NIUB parell han d'anar al 404.

Data segon parcial: Dimarts 22 de desembre 15:00-16:00;
Els alumnes amb NIUB senar han d'anar al 403
Els alumnes amb NIUB parell han d'anar al 404

Data examen avaluació única: divendres 15 de gener del 2021 de 9:00-11:00 a l'aula 403 (l'aula de sempre)

Data examen reevaluació: dijous 4 de febrer del 2020 de 9:00-11:00 a l'aula 403 (l'aula de sempre)

Aqui teniu un link


Setmana 1	Setmana 2
Setmana 3	Setmana 4
Setmana 5	Setmana 6
Setmana 7	Setmana 8
Setmana 9	Setmana 10
Setmana 11	Setmana 12
Setmana 13	Setmana 14
Setmana 15	Setmana 16

Setmana 1

La primera setmana. (Octubre 5 -- 9)

vam començar amb una introducció: Per a nosaltres, lógica és l'art del raonament valid (aquí ). A més, vam delimitar molt quin tipos de raonament estudiarem. De moment només lògica proposicional clàssica. Vam tractar amb la sintaxi que correspon amb el principi del Capítol 6 del llibre.

Setmana 2

(Octubre 12 -- 16)

Hem fet el capitol 7 del llibre. Taules de veritat, tautologies, contingències, contradiccions. Us animo fer molts exercisis.

Setmana 3

19 --23 Octubre

Esta semana las clases han sido impartidas por Eduardo Hermo Reyes

En estas clases hemos repasado las nociones de tautología, contradicción y fórmula contingente, y además hemos explicado la noción de equivalencia lógica. También hemos visto cómo podemos usar las tablas de verdad para averiguar si una determinada fórmula es una tautología, contradicción o fórmula contingente, y también cómo podemos aplicar este mismo método para examinar si dos fórmulas son equivalentes o no (Aqui hay algunas notas que usó Eduardo en su clase. ).

Setmana 4

26 -- 30 d'octubre.

Hem fet equivalències, la definició i com comprabar o desmentir que dues formulos siguin lògicament equivalents. Després hem parlat de la eliminabilitat de les conectives i hem fet molts exercisis al respecte. Heu de practicar molt el cap de setmana.

Setmana 5

2--6 novembre

En Joost tenia una presentació a Wuhan (en linea) i la Mireia González Bedmar ha fet la classe. En resum, la Mireia ha fet satisfacibilidad i un par d'exemples. En particular ha fet 1) Indicar si és satisfacible el conjunt: p -> q, ¬p -> ¬q 2) Indicar si és satisfacible el conjunt: q \/ ¬p, q -> ¬r, p /\ r.

Setmana 6

9 -- 13 novembre: primer midterm

Hem fet i acabat el capítol 11.
El dimecres 11 de novembre: el primer parcial de 13:00-14:00 en les aulas 403/404.
Els alumnes amb NIUB senar han d'anar al 403.
Els alumnes amb NIUB parell han d'anar al 404.
Després de l'examen no es pot quedar pels passadissos i hem de sortir tot seguit al carrer per protocol Covid 19.
El dijous hem fet sintaxi de la lògica de primer ordre. Per tant, hem començat el capítol 12.

Setmana 7

16 -- 20 novembr

Més sobre llenguatge de primer ordre: formalització i arbres genealogics. Ja tenim els resultats del primer parcial. Varem definir first order language. So we have done much of Chapter 12.

Setmana 8

23 -- 27 novembre.

This week we have started informally semantics (mons possibles, models) of first order logic. As such, we have started part of Chapter 13. The problem session will be done by Quim, the Wednesday and Thursday class by Eduardo Hermo Reyes. He will speak on sets (he has done some exercises (Pág. 38: 1, 2 y 3)) and if time allows on relations.

Setmana 10

30 novembre -- 4 desembre

El dimarts hem acabat el capítol 1 del llibre. En particular hem presentat la paradoxa de Russell. Sisplau, llegueu-vos lo amb atenció en la secció 1.3 del llibre. Dimecres i dijous fet per n'Eduardo: Esta semana hemos visto operaciones entre conjuntos (unión, intersección y diferencia) y también hemos comenzado a estudiar las relaciones desde el punto de vista de la teoría de conjuntos. Para ello hemos explicado la noción de par ordenado y la relación como conjunto de pares ordenados. Brevemente y sin entrar en detalle, hemos visto también qué es el producto cartesiano y cómo se define el par ordenado con el lenguaje conjuntista. (Aqui hay algunas notas que usó Eduardo en su clase. ).

Setmana 11

7 -- 11 desembre

Segueix l'Eduado Hermo Reyes. Moltes gràcies! Hi ha més notes de n'Eduado!

Setmana 12

14 -- 18 desembre

Dimarts vindrà el nostre amic, maestro i professor Eduardo Hermo Reyes. Hem acabat tot el contingut del curs. Pel Campus Virtual s'ha enviat un examen (segon parcial) de prova. L'examen de debo serà del mateix format. També hi ha uns exercicis de n'Eduado

Semana 13

21 --23 desembre final exam

Data segon parcial: Dimarts 22 de desembre 15:00-16:00;
Els alumnes amb NIUB senar han d'anar al 403
Els alumnes amb NIUB parell han d'anar al 404

Doncs amb el segon parcial el dimart s'acaba el curs.

Reavaluació

Preguntes i respostes

Pregunta

Soc un alumne teu de 1r curs de l'assignatura Introducció a la Lògica (Grup A1) i volia fer-te unes preguntes sobre el llibre aquell que ens vas recomanar a classe anomenat Elementos de Lógica Formal.

1) És un llibre teòric o de lectura?

2) És obligatori o simplement consideres que és molt recomanable tenir-lo?

3) Un cop que el tinguem, el podrem aprofitar a 3r de grau quan fem l'assignatura de Lògica? És que em sona que vas dir que ens podria ser molt útil, també.

4) Em podries dir el nom dels autors, editorial, etc. (o directament el número ISBN, que conté ja tota la informació) per, si ho recomanes, poder-me'l comprar?

5) Aquesta cinquena pregunta no està relacionada amb aquest llibre sobre el qual t'he preguntat, però volia preguntar-te, a més a més, si de la teva assignatura hi ha algun llibre purament de lectura la lectura de la qual sigui obligatòria o no.

Resposta

1) Teòric però amb molts exercisis.

2) Molt, però molt recomanable.

3) Si, serveix a tercer també (pot dependre una mica del professor...)

4)A dalt d'aquesta pàgina.

5)From last year's website I copy-paste:
Here are some suggestions:

"Gödel, Escher, Bach", from Douglas Hofstadter. Dissemination text for the general interested audience. Relatively little logic though. It is somehow related to "The emperor's new mind" from Penrose.

The book by Torkel Franzen "Gödel's Theorem: An Incomplete Guide to Its Use and Abuse" is much more on logic. Although accessible, it requires much more dedication from the reader but it is very well written and a good read in general.

There is "Logic, Logic and Logic" by Boolos but I guess that is too hard for the moment.

Odifreddi has some dissemination writings that I have not read but may be worth while looking at.

For the real daring and dedicated student, there is even Pudlak's "Logical Foundations of Mathematics and Computational Complexity" which you can also have a look at.

My colleague Joan Bagaria suggested: A good source for introductory material is SEP:

https://plato.stanford.edu/index.html

Pregunta

Estamos haciendo ejercicios de equivalencias y eso. Nos preguntamos si para ti, en la disyunción, ¿Que método aplicas? El inclusivo o exclusivo, es decir si P y Q son verdaderas, la conjunción de P y Q (P v Q) ¿Sería verdadera o falsa?

Resposta

La pregunta no està del tot ben formulada. Però suposo que la vostra pregunta és: per la semántica de la disjunció, quina fem servir, la inclusiva o la exclusiva? Com vaig dir a classe, aqui tenim llibertat. Nosaltres (pots (I hauràs de) consultar el llibre) fem servir la inclusiva. Vol dir que en l’assignació on tant p com q són vertadars, doncs la formula p\/q agafa el valor de veritat.

Pregunta

Al final que passa amb el primer parcial?

Resposta

Son temps estranys i les normatives canvien casi de dia en dia. Abans no deixaven fer cap activitat presencial però per al parcial sí és possible. La proposta és fer el primer parcial en els dos grups bombolla el dimecres 11 de novembre de 13:00 -- 14:00. Ara (escric això el dimarts 3 de novembre) el cap d'estudis ens ha de confirmar si és possible. Sisplau reserveu aquest horari!

Pregunta

Qué entra al primer parcial?

Resposta

Del llibre:
Cap. 6 par. 1 i 2.
Cap. 7 par. 1 i 2.
Cap. 8 sencer
Cap. 9 sencer
Cap. 11 sencer

Pregunta

Quina és la forma millor de preparar l'examen?

Resposta

Fent exercisis!!!! Compartir solucions i treballar junts. Però sobre tot: FENT MOLTS EXERCISIS!!!!

Pregunta

In order to consider alpha a semantic consequence of gamma (Γ ⊨ α), is it necessary that gamma is a satisfiable set? And, if it were not, wouldn't any alpha be a semantic consequence of an unsatisfiable set?

Resposta

In order to consider alpha a semantic consequence of gamma (Γ ⊨ α), is it necessary that gamma is a satisfiable set? No, not at all. As a matter of fact, this answers your second question: wouldn't any alpha be a semantic consequence of an unsatisfiable set? Indeed! Very good, my congratulations. Indeed, any formula is a logical consequence of an unsatisfiable set. In Latin they call that ex falsum sequitur quodlibet. Well done.

Pregunta

Suposo que no ens hem de saber això, oi?
l . (ley de identidad).
2. (ley del tercio excluso).
3. (principio de no contradicción).
4. (ley de Clavius).
5. (ley de Duns Scoto).
6. (ley de Peirce).
7. (Modus ponens).
8. (Modus tollens).
Apareix en el capítol 7 del llibre. Moltes gràcies :)

Resposta

Strictament parlat, no cal saber-t'ho. Això si, si et saps aquestes lleis et serà molt més fàcil operar amb equivalències. A més et donarà més seguretat abarcant altres exercisis. Per altra banda, crec que per la teva educació en general pot aportar. També és bonic adonar-te que la lògica porta un llarg camí amb molts autors fins arribar a on estem ara.

Pregunta

I've been doing some exercises about satisfactibility and logical consequences. I finally understood the differences (or at least I think I did. Just in case, could you tell me if the following definition is correct? The basic difference between satisfactibility and logical consequence is that in satisfactibility we just look for at least one assignation that has all the value of truth in all the formulas that participate. While in logical consequence we search for the values of truth in the left formula to continue being true in the right formula).

Resposta

Great!!! That's exactly right! Very good. keep up the good work.

Pregunta

Anyway I would like to send you two exercises that I've done so you could tell me if they are correct, whenever you can.

Resposta

I correct your answer set under the condition that you share it with your fellow students. First, let me comment on your exercesise to the extent that q |= (p --> p) --> q. Indeed, this is a logical consequence. Your methodology to show it was correct: make the truth-table of (p --> p) --> q and then check that each assignation that validates (p --> p) --> q also validates q. You made one small mistake in the table though: when both p and q are false, then (p --> p) --> q is false (since (p --> p) is true and q is false and true --> false yields false). You were lucky here since your error did not affect the conclusion that (p --> p) --> q is a logical consequence of q. As it turns out however, q is actually also a logical consequence of (p --> p) --> q. Please check this. Here, your error would have been fatal :-) Please share your wrong solution and a corrected version with your fellow students in the drive.

Pregunta

I'm writing because I've been wondering which kind of exercicis you will put in the exam. Could you give me some examples so I can practice similar things? If not, could you give some examples in class on Tuesday?

Resposta

The exercises from the exam will be similar (if not exactly the same) as the exercises from the book.

Pregunta

Hola Joost, com suposo que ja saps, i no sóc l'únic, ens dificulta molt a l'hora d'estudiar el fet de no tenir exercicis amb les solucions corresponents, i et demanaria com a favor si podries passar-me algun document on hi hagi exercicis amb les solucions pertinents. Gràcies i anem parlant.

Resposta

I am working hard to correct all answer-sets that you and your fellow students send me. By now, you should have at least already ten or more worked out and corrected examples. I have seen that not everybody shares them in the drive folder. Please ask your fellow students over whatsapp to do so!!!! Also, there is Eduardo's answer set, etc. If you browse my webpage for previous years of the same course or related, you can also find corrected answer sets. Also, if you send me your answer set, then I'll correct and comment it over mail and you can then share it in the drive with your fellow students. I hope that helps!

Pregunta

How do I prove that if A |= B and B |= C, then A |=C?

Resposta

A structured answer would be something like the following.

We assume that

(1) A |= B

and

(2) B |= C.

We are to prove that

(3) A |= C.

Let us see what it means to prove A |= C. By definition we need to see that for any assignation s, if s(A) = 1, then necessary S(C) =1. Therefore, let s_0 be any arbitrary assignation. So, we assume no particular property of s_0 so that our argument will work for ANY assignation s. (This type of reasoning is known as `generalisation’.) Let us further assume that for this, for now fixed, assignation s_0 we have that s_0(A) = 1. We now use the fact (1) that A |= B. That means that for any assignation t, if t(A) = 1, then t(B) = 1. I particular, for our s_0 will we know that s_0(B) =1 since we assumed that s_0(A) = 1. Now we know (still under the assumption that s_0(A) = 1) that s_0(B) = 1. Now, we will use assumption (2) that B |= C. That means that for any assignation u, if u(B) = 1, then u(C) = 1. I particular, for our s_0 will we know that s_0(C) =1 since we concluded just before that s_0(B) = 1. Thus we have concluded that s_0(C) = 1 under the original assumption that s_0(A) =1. In other words we have shown that “If s_0(A) = 1, then s_0(C) = 1”. Since we assumed no particular property of s_0 the implications will hold for any assignation s. In other words, we have now shown “For every assignation s we have that if s(A) = 1, then 0(C) = 1”. This is exactly what it means for C to be a logical consequence of A and we have finished our proof of (3).

OK, so, that’s a complete answer. However, in the exam, you will NOT be required to repeat such reasoning.

Pregunta

I'm really lost with exercice 15, page 197. I assume the first part of the formula it's hypothetical and we have to take as true. And then we must see if the consequences are correct according to the info in the first proposition. The probem is not that I don't know wether if it's correct or not it's that i don't know how to justify it without the table of truth. I took the A as an example.

Resposta

All exercises that come with a star (like Exercise 15 on Page 197 (when an item has a number it gets capitalised in English)) come with some worked out examples in the back of the book. In particular the example a you mentioned is worked out in quite some details.

Pregunta

Sobre una cosa del ejercicio 1b del tema 11.

Pone en el enunciado "es un triángulo sólo si es roja". Cómo se escribiría, " triángulo--->rojo" o "rojo--->triángulo"?

Resposta

The last one is correct indeed.

Pregunta

No entenc a nivell teoric la classe d'avui (1-12-2020). Per què 1 no és element de 1? Así mateix, per que x no es element de x?

Resposta

Today was a difficult class indeed. However, each and every philosopher has to really understand the Russell paradox I think. I advice you to read and reread the book on it. Please play close attention to Chapter 1.3 where the Russell paradox is dealt with in great detail. To get back to your notion of elements: “one" is not a set so in particular it has no elements. So, one is not an element of 1. However, we can consider the set {1} and then we have that 1 is an element of this set {1}. There are many exercises in Chapter 1 and I recommend you make plenty of them. This should clarify your doubts on the status of sets, elements and subsets.

Pregunta

I'm studying the types of formulas and how they interact between them. Now i'm checking the "closed formulas" or sentences as the book says. The examples so far are understandable, but i'm having trouble trying to comprehend this one in particular: Ax(Ey(Px ^Rxy)=>¬Rxc) (sorry about the quantificators, i couldn't figure out how to put them) Isn't that "c" in "Rxc" free on the formula? It doesn't have any quantificator or anything that interacts with it.

Resposta

No probs, I can make the substitutions in my head replacing A by a universal quantifier and E by an existential quantifier. The thing is, c is not a variable. It is a proper name or synonimously, a constant. It is a linguistic artifact referring to one particular object in the domain of discourse. Thus, the sentence should be read as "for any object x, if there is an arrow leaving x going to some element y that has property P, then there is no arrow from x to c".

Pregunta

Pel que fa a l'examen de prova: Per començar, a l'exercici 5 he arribat a la conclusió que els dos primers enunciats són vertaders però l'últim és fals. El que passa és que no sé massa com rahonar-ho.

Resposta

El primer és una universal (per tot) sobre una implicació. El consequent d'aquesta implicació diu que existeix un y tal que Q(y). Això és cert. Per exemple, per y = 2 o per y =y. Per tant existeix un y tal que Q(y) és cert, per tant l'implicació es vertadera i també ho és el universal d'aquesta implicació. Aquesta és la forma de raonar. De totes maneres, a l'examen només heu de dir "vertader" o "fals". Et deixo el raonament dels altres tres perquè ho intentis.

Pregunta

Pel que fa a l'examen de prova: Després, a l'exercici 6, el primer apartat m'ha donat {} i al segon Sa però no sé si entenc el que demanes.

Resposta

El primer, correcte. El segon: es tracta del producte relacional. Ho trobes al llibre. M'acaba de dir l'Eduardo que NO ho ha fet a classe. Per tant NO hi haura cap exercisi a l'examen final respecte al producte relacional. Discupla'm.

Pregunta

Pel que fa a l'examen de prova: Tampoc acabo d'entendre l'exercici 7 que has fet a la pissarra. Ja que si 2 fos x, llavors aquest s'hauria de relacionar amb ell mateix per tal que amb el que es relacionés tingués la propietat p, no? Segurament no però és que no ho entenc 🙁.

Resposta

Ah, potser que tinguis raó! Ara no em recordo del tot el model final a classe que varem decidir doncs no sé si puc respondre del tot bé. Però efectivament, quan hi ha una fórmula amb x i y i la has de evaluar per possibles valors de x i y al teu model, també hauràs de contemplar la posibilitat de que x sigui igual a y.

Pregunta

Pel que fa a l'examen de prova: A l'exercici 8 he pensat que si A={1,2,3}, PA = {1,2} i QA ={} llavors es compleix i ∀xP(x) → ∃yQ però no es ∀x (P(x) → ∃yQ(y) ). Què en penses?

Resposta

Molt re-bé!!! Has trobat una solució. Una altra una mica més minimalista seria: A={1,2}, PA = {1} i QA ={}. Però la teva és correcte també. Enhorabona. Vas molt bé!

Pregunta

Pel que fa a l'examen de prova:
Ex 9.
. (a) Hi ha un filòsof que estima a tot poeta:
∃x(F(x)∧∀y(P(x) --> E(x,y)))

(b) Hi ha un poeta que s’estima a si mateix i a tots poetes que s’estimen a si mateixos
∃x((P(x)∧E(x,x)) ∧∀y(P(y)E(y,y) --> E(x,y))).

Resposta

Correcte la a, molt bé!
M'HE EQUIVOCAT o més aviat despistat: hi havia un petit error en la a. La resposta correcte és:
∃x(F(x)∧∀y(P(y) --> E(x,y)))

La b, casi correcte. Només t'havies oblidat de posar-hi una conjuncció:
∃x((P(x)∧E(x,x)) ∧∀y(P(y)∧E(y,y) --> E(x,y))).

Pregunta

Pel que fa a l'examen de prova: he fet l'exercici 2 i crec que l'única que està malament és la última frase, que diu: ∀c ( P(c) → ∃dQ(d) ) perquè un nom propi no pot ser quantificat. No obstant, encara que tot el que hi ha a la 1a em quadra, no li trobo massa sentit a la construcció de la fòrmula.

Resposta

Tens tota la raó. No es pot quantificar un constant. Els altres tres son correcte. La 1a és grammaticalament correcte però com ben dius, semanticament no té molt de sentit.

Pregunta

Pel que fa a l'examen de prova: A l'exercici 5 he arribat a la conclusió que els dos primers enunciats són vertaders però l'últim és fals. És correcte?

Resposta

És correcte.

Pregunta

En l'exercici 3 tots tres donen el mateix?
A∩B= {{Ø}, Ø }
B∩C= {{Ø}, Ø }
A∩C= {{Ø}, Ø }

Resposta

A∩B= {{Ø}, Ø }: no és correcte
A∩B= {{Ø}} és la resposta correcte
B∩C= {{Ø}}
A∩C= {{Ø}, Ø }: és correcte.

Pregunta

En l'exercici 4 són així les solucions?
(F) A∈B
(V) A∈C
(V) A⊆B
(F) A⊆C

Resposta

En l'exercici 4 són així les solucions?
(F) A∈B : correcte, és fals
(V) A∈C correcte, effectivament, el conjunt A és un element de C
(V) A⊆B : fals, A no és pas subconjunt de B, per tant la resposta correcte és F
(F) A⊆C cada element de A és tb element de C per tant A és efectivament un subconjunt de C.

Pregunta

Pel que fa a l'examen de prova: En l'exercici 5 no se ben bé per què la tercera afirmació és falsa.

Resposta

La tercera afirmació diu que per tots elements tenim alguna cosa (una implicació). Però és fals perquè podem trobar un element (x) tal que l'antecendt és vertader i el consequent fals. Per exemple podem agafar x = 3. O també podem agafar x = 0.

Pregunta

Per fer els exercicis en què hem de trobar models on es compleixin les premisses donades, les premisses que són implicacions, les podem convertir en una disjunció amb negació de l'antecedent?

Resposta

Efectivament. Perque A--> B és vertader en un model si i només si (o B és vertader o no A és vertader).

Pregunta

També tinc un altre dubte. Les implicacions en lògica de 1r ordre funcionen com a lògica proposicional i si es compleix el conseqüent és certa la fórmula?

Resposta

Correcte. Molt bona observació!

Pregunta

About the exam, is it correct that for 6, the answer on both questions is {Ø}?

Resposta

Your answers are incorrect. The intersection is empty Ø since there are no two points between which there is both an R and an S arrow at the same time. Note that the empty set is different from the set containing only the empty set…, that is, Ø is not equal to {Ø}.

Also your second answer is not correct: the product of S with R consists of those pairs so that you can travel from the first using some intermediate point to the second using first an S arrow and then an R arrow. Since we can go from 3 to 3 with an S arrow and then from 3 to 2 with an R arrow, the product consists of just one pair (3,2). Anyway, since this was not dealt with in class I shall not ask it in the exam.

Pregunta

Siguiendo el lenguaje del ejercicio 9 del simulacro de examen, he ideado ésta abstracción
para saber si había entendido de verdad cómo funciona la formalización:

«Hay algún poeta que quiere a todos los filósofos que quieren a algún poeta»

Mi resultado:
∃x(P(x)∧∀y(F(y)∧∃xP(x)→E(y,x))→E(x,y))
¿Es ésto correcto?

Resposta

It is almost correct. Here's how I would do it:
∃x( P(x) ∧∀y(F(y)∧ ∃z (P(z)∧ E(y,z))→E(x,y)) )

Renaming your x to z is actually not needed so equally correct would have been:
∃x( P(x) ∧∀y(F(y)∧ ∃x (P(x)∧ E(y,x))→E(x,y)) )
However, replacing the implication by a conjunction was essential.