Logica-aula-01imprimir.pdf

L´ogica Matem´atica Prof. Miguel Zamora [email protected] Instituto do Noroeste Fluminense de Educa¸c˜ ao Superior - INFES Universidade Federal Fluminense

04 de Maio de 2017

Aula 01 L´ ogica Proposicional

Prof. Miguel Zamora

L´ ogica Matem´ atica

L´ogica

1. Disciplina matem´atica. 2. Disciplina formal: Razona se sobre a estrutura das coisas. 3. Quere se estudar o racioc´ınio, e n˜ao as verdades contingentes. 4. Quere se estudar a no¸c˜ao de consequˆencia: - Se(acontece, ocorre que, sabe se que,. . .) A ´ e verdadeiro, - Ent˜ ao(acontece, ocorre que, sabe se que, pode se provar que. . .) B ´ e verdadeiro,

Prof. Miguel Zamora

L´ ogica Matem´ atica

Os Silogismo do c˜ao

Todos os c˜aes latem. Bobby ´e um c˜ao. Logo, Bobby late. Todos os gatos latem. Caetano ´e um gato. Logo, Caetano late.

Prof. Miguel Zamora

Todos os c˜aes latem. Bobby n˜ao ´e um gato. Logo, Bobby late. Todos os P s˜ao L. B ´e um P. Logo, B ´e um L.

L´ ogica Matem´ atica

No¸co˜es por tr´as do Racioc´ınio

1

Na ideia intuitiva do racioc´ınio que est´a se estudando, existe pelo menos trˆes elementos envolvidos: Uma no¸c˜ao de verdade:Existem coisas que s˜ao verdades e outras que s˜ao falsas. Uma no¸c˜ao de processo:Usando algum mecanismo, somos capaces de decidir que se determinadas coisas s˜ao certas, ent˜ao outras coisas devem ser certas tamb´em. Uma no¸c˜ao de validade do processo, dada pela forma do planteo.

Prof. Miguel Zamora

L´ ogica Matem´ atica

Justifica¸c˜ao da validade do racioc´ınio

1

Dois maneiras diferentes de justificar: Justifica¸c˜ao que a verdade das hip´ oteses implica a veracidade da conclus˜ao(sem´antica). Dar uma demonstra¸c˜ao que prove `a conclus˜ao a partir das hip´ oteses, atraves dos passos devidamente justificados(sint´actica).

2

Ambas formas de justificar s˜ao equivalentes? Sim, isso veremos na disciplina.

Prof. Miguel Zamora

L´ ogica Matem´ atica

L´ogica Proposicional- Plano

1. Sintaxis da l´ogica proposicional:O conjunto PROP, substitui¸c˜ao. 2. Sem´antica da l´ogica proposicional:Valores de verdade, valua¸c˜oes, equivalˆencia de proposi¸c˜ oes, consequˆencia l´ogica, tautologias. 3. Provas na dedu¸c˜ao natural:Deriva¸c˜ao, consequˆencia sint´atica, teorema. 4. Metateoria da l´ogica proposicional:Consistˆencia e completitude da l´ ogica proposicional.

Prof. Miguel Zamora

L´ ogica Matem´ atica

Proposi¸co˜es e Conectivos L´ogicos

Defini¸c˜ao (Defini¸c˜oes B´asicas) 1. Senten¸ca(Sentence): Seq¨ uˆencia de s´ımbolos gr´aficos ou sonoros com significado.Podem ser: Interrogativas:Perguntas: Que horas s˜ao?; Porque ele n˜ao veio? Exclamativas:Estado de ´animo, medo, tristeza, etc.: Que dia chuvoso! Imperativas: Ordem, mandado: N˜ao fume!; Estude! Declarativas: Admitem um fato que pode ser verdadeiro ou falso: H´a 50 alunos na UFF; Jos´e ´e um n´ umero real.

´ ´ TEM SENTENC A MATEMATICA SO ¸ AS DECLARATIVAS 2. Ver pr´oximo slide

Prof. Miguel Zamora

L´ ogica Matem´ atica

2. Proposi¸c˜ ao, enunciado, afirma¸c˜ ao(Statement): Pensamento que uma senten¸ca declarativa exprime literalmente, e que n´ os podemos considerar(fa¸ca sentido) verdadeiro ou falso: 4-5=9. π ´e racional. 9 ´e n´ umero impar e primo.

Prof. Miguel Zamora

L´ ogica Matem´ atica

˜ Uma senten¸ca declarativa, S, ´e uma proposi¸c˜ao OBSERVAC ¸ AO: se faz sentido colocar S no lugar de . . . na seguinte quest˜ao: ´ certo que ...? E Por exemplo, faz sentido perguntar qualquer das seguintes quest˜oes? ´ certo que π ´ 1 E e racional? 2 3

´ certo que as fun¸c˜ E oes diferenci´ aveis s˜ ao cont´ınuas? ´ E certo que f (x) > g (y ) ?

Portanto, as seguintes senten¸cas s˜ao proposi¸c˜ oes: 1

π ´e racional.

2

As fun¸c˜oes diferenci´aveis s˜ao cont´ınuas.

3

f (x) > g (y ).

N˜ao importa se as respostas s˜ao diferentes:(i) N˜ao. (ii) Sim. (iii) Depende de quem s˜ao f , g , x, y . Prof. Miguel Zamora

L´ ogica Matem´ atica

Por outro lado, nemhuma das seguintes quest˜ oes fazem sentido: ´ 1 E certo que π ? ´ certo que o Teorema de Pit´ 2 E agoras? ´ certo que 3 + cos θ ? 3 E ´ certo que Jos´ 4 E e´ e um n´ umero real? Portanto, nemhuma das senten¸cas: 1

π.

3

3 + cos θ.

2

o Teorema de Pit´agoras.

4

Jos´e ´e um n´ umero real.

s˜ao proposi¸c˜oes. Mais proposi¸c˜oes... 1 Se ontem choveu em Niter´ oi, ent˜ ao a roupa n˜ao secou. 2 O sol gira ao redor da terra ou a terra gira ao redor do sol. 3 2 · 3 = 6 e 6 ´ e impar. 4 Todo enteiro par maior que quatro ´ e a soma de dois n´ umeros primos. 5 H´ a um n´ umero natural que ´e par e ´e primo. Prof. Miguel Zamora

L´ ogica Matem´ atica

Proposi¸co˜es para os racioc´ınios 1. Observa¸c˜oes: 1

2

Os racioc´ınios usam proposi¸c˜ oes simples e complexas que podem ser verdadeiras e falsas. Precisa-se a posibilidade de verificar os racioc´ınios sobre essas proposi¸c˜ oes.

2. Como vai ser formaizado isto 1

2

Definindo uma linguagem para ´a l´ ogica proposicional, ou seja uma linguagem de proposi¸c˜ oes em forma indutiva. O conjunto PROP. Definindo fun¸c˜ oes por recurs˜ao primitiva sobre PROP que associam valores de verdade:Valida¸c˜ oes v : PROP → {0, 1}

3

4

Introdu¸c˜ao de dois no¸c˜ oes de racioc´ınio: Uma baseada nos valores de verdade e outra na sintaxis. Verificar que as no¸c˜ oes coincidem. Prof. Miguel Zamora

L´ ogica Matem´ atica

Validade de um Racioc´ınio

Queremos saber se uma determinada conclus˜ao (uma proposi¸c˜ao) segue a partir de um conjunto de hip´ oteses (proposi¸c˜oes). Teorema (Racioc´ınio V´alido) Sempre que as hip´oteses s˜ao verdadeiras, a conclus˜ao tamb´em ´e. Teorema (Racioc´ınio Inv´alido) E´ poss´ıvel obter conclus˜ oes falsas a partir de hip´ oteses verdadeiras.

Prof. Miguel Zamora

L´ ogica Matem´ atica

1. Sintaxis da L´ogica Proposicional

Prof. Miguel Zamora

L´ ogica Matem´ atica

Linguagens Formais

Defini¸c˜ao (Alfabeto) Um alfabeto ´e qualquer conjunto, que denotaremos por Σ. Os elementos de um alfabeto, s˜ao chamados s´ımbolos ou letras. Exemplo 1

Alfabeto Bin´ario Σ = {0, 1}.

2

Alfabeto portuguˆes Σ = {A, B, . . . , Z }.

3

Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}.

Prof. Miguel Zamora

L´ ogica Matem´ atica

Defini¸c˜ao (Palavras) Uma palavra, ou cadeia ´e uma seq¨ uˆencia finita de letras. 1

010011110, 1110, etc.

2

CASA, LOGICA, KKK , etc.

3

23 + 5 = 555, = 234 = +, etc.

Dado qualquer alfabeto, existe uma palavra que n˜ao possui s´ımbolos, chamada a palavra vazia ou nula, denotado por Λ, ou ε, ou 1. O conjunto de todas as palavras de um alfabeto Σ, ´e denotado por Σ∗ . A igualdade entre palavras, denotada com o s´ımbolo =, acontece quando duas ou mais cadeias tem exatamente os mesmos s´ımbolos na mesma posi¸c˜ao e tem o mesmo comprimento(quantidade de letras). Caso contr´ario, se denota por 6=. Se w1 = luz, w2 = luz, w3 = zul, ent˜ao w1 = w2 e w1 6= w3 . Prof. Miguel Zamora

L´ ogica Matem´ atica

Defini¸c˜ao (comprimento de uma palavra) O comprimento de uma palavra w , denotado |w |, ´e o n´ umero de letras que a conformam. O comprimento da palavra vazia ´e 0. Se existem k s´ımbolos no alfabeto, ent˜ao existem k n palavras com n X k n+1 − 1 palavras de ki = comprimento n. Existem k −1 i=0 comprimento no m´aximo n, se k > 1, e n + 1 palavras se k = 1. Defini¸c˜ao (Concatena¸c˜ao ou Justaposi¸c˜ao) Sejam w1 = a1 . . . an e w2 = b1 . . . bm duas palavras, a concatena¸c˜ ao de w1 e w2 , denotada w1 w! 2, ´e a palavra definida como w1 w2 = a1 . . . an b1 . . . bm . Em algumas aplica¸c˜oes, especialmente na l´ ogica, o alfabeto ´e chamado de vocabul´ ario e as palavras de f´ ormulas ou senten¸cas. Prof. Miguel Zamora

L´ ogica Matem´ atica

Defini¸c˜ao (Linguagem) Uma linguagem L, ´e um conjunto(pode ser infinito) de palavras sobre um alfabeto finito Σ. Ou seja, L ⊂ Σ∗ . O conjunto de todas as linguagens poss´ıveis sobre um alfabeto Σ ´e co conjunto de todos os subconjuntos de Σ∗ , ou seja, P(Σ∗ ). Σ∗ ´e uma linguagem, chamada de linguagem universal sobre Σ. Exemplo Se Σ = {0, 1}, os conjuntos L1 = {ε, 01, 11, 0110} e L2 = {0n 1n ; b ≥ 0} = {ε, 01, 0011, 000111, . . .} s˜ao linguagens. Defini¸c˜ao (Gram´atica) Uma gram´ atica, G, ´e uma maneira de caracterizar a uma linguagem L, uma maneira de identificar as palavras de Σ∗ que pertencem ou n˜ao a L. Ou seja, ´e um conjunto de regras de forma¸c˜ao que determinam que s´ımbolos do alfabeto s˜ao ou n˜ao elementos de L. A gram´atica gera as palavras de L. Prof. Miguel Zamora

L´ ogica Matem´ atica

Exemplo Seja Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =} e a gram´atica G com as seguintes regras: 1

Cada cadeia n˜ao vazia que n˜ao cont´em ” + ” ou ” = ” e n˜ao come¸ca com ”0” est´a em L.

2

Uma sequˆencia contendo ” = ” est´a em L se e somente se h´a exatamente um ” = ”, e ela separa duas cadeias v´alidas de L.

3

Uma sequˆencia contendo ” + ”, mas n˜ao ” = ” est´a em L se e somente se todos os ” + ” na cadeia separam duas cadeias v´alidas de L.

4

Nenhuma cadeia est´a em L que n˜ao as sugeridas pelas regras anteriores.

Sob essas regras, a cadeia ”23 + 4 = 555” est´a em L, mas a cadeia ” = 234 = +” n˜ao est´a.

Prof. Miguel Zamora

L´ ogica Matem´ atica

`e usual descrever as regras de deriva¸c˜ao em G como x1 , . . . , xn , n ∈ N. x Entende se que os objetos do numerador dˆao origem ao do denominador. No caso em que n = 0, estaremos gerando um elemento x a partir do conjunto vazio, o qual denotaremos por . x

Prof. Miguel Zamora

L´ ogica Matem´ atica

Exemplo Exemplo Consideremos o alfabeto Σ = {a, b} e as seguintes regras: Se S ´e um s´ımbolo: g1 . S → aSb. Concatenamos as letras a e b `a esquerda e direta de S respectivamente. g2 . S → ba. Substituimos a letra S por ba. Se aplicamos (1.) duas vezes a S obtemos S → aSb, aSb → a(aSb)b = aaSbb. Agora aplicamos (2.) e obtemos aa(ba)bb = aababb. A gram´atica define a linguagem L, que ´e o conjunto infinito: L = {an bab n ; n ≥ 0} = {ba, abab, aababb, aaababbb, . . .}

Prof. Miguel Zamora

L´ ogica Matem´ atica

Defini¸c˜ao (Linguagem Formal) Uma linguagem formal ´e um par L = (Σ, G), onde Σ ´e o alfabeto, e G ´e uma gram´atica. Defini¸c˜ao (Express˜ao) Uma express˜ ao de uma linguagem, ´e uma sequencia finita de s´ımbolos do alfabeto. Defini¸c˜ao (F´ormula bem formada) Uma f´ ormula bem formada, abreviada fbf, ´e uma express˜ao que ´e parte de uma linguagem formal. Uma linguagem formal pode ser considerada como um conjunto contendo todas e apenas suas f´ ormulas.

Prof. Miguel Zamora

L´ ogica Matem´ atica

Exemplo No portuguˆes, est´a errado dizer: Meus amigos e eu vou para o cinema. E´ uma express˜ao que n˜ao ´e uma fbf, pois n˜ao tem concordancia entre o numero do sujeto(plural) e o n´ umero do verbo(singular). O certo ´e dizer Meus amigos e eu vamos para o cinema. Exemplo Na matem´atica, tamb´em est´a errado escrever: % = 4 + (78−). E´ uma express˜ao que n˜ao ´e uma fbf, pois n˜ao respeita as regras de forma¸c˜ao das f´ormulas matem´aticas. Prof. Miguel Zamora

L´ ogica Matem´ atica

Exemplo Se Σ = {a, b} e G define as fbf como aquelas cadeias que tem o mesmo n´ umero de s´ımbolos a que b. Assim, algumas fbf s˜ao ab, aabb, abab enquanto aab, babab n˜ao. Assim, LG ´e conjunto de todas essas fbf. Exemplo Na l´ogica, qualquer combina¸c˜ao dos elementos do alfabeto, n˜ao constitue uma fbf, por exemplo: 1

∧p.

2

∧p ∧ q.

3

→ p ∨ ¬.

N˜ao s˜ao fbf. Na hora de definir o conjunto PROP, os seus elementos ser˜ao as fbf.

Prof. Miguel Zamora

L´ ogica Matem´ atica

Linguagem Natural e a Linguagem Formalizado ´ a linguagem usada na vida familiar, 1. Linguagem Natural: E cotidiana. Pertencem a essa linguagem, o espanhol, inglˆes, portuguˆes, etc. ´ a linguagem usado na atividade 2. Linguagem Formalizado: E cient´ıfica. S´o serve para formular conhecimentos. Pertencem a essa linguagem, a linguagem l´ ogico e matem´atico. Exemplo Proposi¸c˜ ao na linguagem natural: Os cachorros s˜ao espertos e os gatos egoistas. p = Os cachorros s˜ao espertos. q = Os gatos s˜ao egoistas. Proposi¸c˜ ao na linguagem formal: p ∧ q (lee-se: ”p e q”).

Prof. Miguel Zamora

L´ ogica Matem´ atica