A linguagem da Lógicarosalvo.oliveira/Disciplinas/2014_2/...b) Jorge é alto mas não é elegante. c) Se Jorge é alto, então é elegante. d) Jorge é alto, se e somente se é elegante

A linguagem da Lógica Proposicional (Capítulo 1)

LÓGICA APLICADA A COMPUTAÇÃO

Professor: Rosalvo Ferreira de Oliveira Neto

Estrutura

1. Definições

2. Alfabeto

3. Fórmulas bem formadas (FBF)

4. Exemplos

5. Questão desafio

6. Lista de exercício 01

Univasf – Engenharia de Computação - LÓGICA APLICADA A COMPUTAÇÃO - Prof.: Rosalvo Neto

O que é Lógica?

•Estudo do raciocínio;

•Estudo do pensamento correto e verdadeiro;

•Regras para verificação da verdade ou falsidade de um pensamento.

Definições Alfabeto FBF Exemplos Desafio Lista

04Univasf – Engenharia de Computação - LÓGICA APLICADA A COMPUTAÇÃO - Prof.: Rosalvo Neto

Como expressamos nosso raciocínio?

•Linguagem natural

•Sentenças: • Interrogativas: Qual o seu nome?•Imperativa: Lave os pratos agora!•Declarativas: João gosta de lógica

•Proposição:

•Uma sentença declarativa que é verdadeira (V) ou falsa (F), mas não ambos.

•Valor verdade:

•Resultado da avaliação de uma proposição (V ou F).



•Argumento

Seqüência de proposições seguida de uma conclusão

Exemplo:

“Se está chovendo a pista fica escorregadia”



Quais das seguintes sentenças são proposições?

1) 2 + 3 = 5

2) 3 não é um número par.

3) A Terra é arredondada.

4) x > 5

5) Esta declaração é falsa.

6) Você fala francês?

7) Leia o livro texto.



Quais das seguintes sentenças são proposições?

1) 2 + 3 = 5 → proposição, V

2) 3 não é um número par. → proposição, V

3) A Terra é arredondada. → proposição, V

4) x > 5 → asserção, mas não proposição

5) Esta declaração é falsa. → não é proposição

6) Você fala francês? → não é proposição

7) Leia o livro texto. → não é proposição




09

Para entender a sintaxe da lógica proposicional vamos fazer uma analogia com a língua portuguesa!



10

Alfabeto da Lógica Proposicional

Definição 1.1 (alfabeto) O alfabeto da Lógica Proposicional é constituído por:

•símbolos de pontuação: (; );

• símbolos de verdade: true, false;

• símbolos proposicionais:

P; Q; R; S; P1; Q1; R1; S1; P2; Q2; ...;

• conectivos proposicionais: , , , , .



11

Conectivos proposicionais

Conectivo Significado

Não

OU

E

Implicação / Se Então

Bi-implicação / Se Somente Se (SSE)



12

Fórmulas da Lógica Proposicional

Definição 1.2 (fórmula) As regras de uma fórmula da lógica proposicional são:

•Todo símbolo de verdade é uma fórmula;

•Todo símbolo proposicional é uma fórmula;

•Se H é uma fórmula, então a negação de H, dada por: (H) é uma fórmula;

•se H e G são fórmulas, então a disjunção de H e G; dada por: (H G); é uma fórmula;

•se H e G são fórmulas, então a conjunção de H e G; dada por: (H G); é uma fórmula;



13

•Se H e G são fórmulas, então a implicação de H em G; dada por: (H G); é uma fórmula;

•Se H e G são fórmulas, então a bi-implicação de H e G; dada por: (H G).



14

Assim podemos expressar o argumento abaixo utilizando a sintaxe da lógica proposicional:

“Se está chovendo então a pista fica escorregadia”

P = Está chovendo

Q = A pista fica escorregadia

P Q



15

Seja p a proposição “Jorge é alto” e q a proposição

“Jorge é elegante” . Traduzir, para a linguagem lógica proposicional,as seguintes proposições:

a) Jorge é alto e elegante.

b) Jorge é alto mas não é elegante.

c) Se Jorge é alto, então é elegante.

d) Jorge é alto, se e somente se é elegante.



16

Seja p a proposição “Jorge é alto” e q a proposição

“Jorge é elegante” . Traduzir, para a linguagem lógica proposicional,as seguintes proposições:

a) Jorge é alto e elegante. p Λ q

b) Jorge é alto mas não é elegante. p Λ q

c) Se Jorge é alto, então é elegante. p q

d) Jorge é alto, se e somente se é elegante. p q



17

Ordem de Precedência

Definição 1.3 (ordem de precedência) Na Lógica Proposicional, a ordem de precedência dos conectivos proposicionais é definida por:

maior precedência: ;

precedência intermediária: , ;

menor precedência: , .



18

Definição 1.4 (comprimento de uma fórmula) Seja H uma fórmula da Lógica Proposicional. O comprimento de H, denotado por comp[H], é definido como se segue.

•Se H = P ou é um símbolo de verdade, então comp[H] = 1;

•Comp[H] = comp[H] + 1;

•comp[H G] = comp[H] + comp[G] + 1;

•comp[H G] = comp[H] + comp [G] + 1;

•comp[H G] = comp[H] + comp[G] + 1;

•comp[H G] = comp[H] + comp[G] + 1.



19

Qual o comprimento das fórmulas abaixo?

1) (P Q)

2) (((P V S) Q) R)



20

Qual o comprimento das fórmulas abaixo?

1) (P Q) COM = 3

2) (((P V S) Q) R) COM = 7



21

Definição 1.5 (subfórmula) Seja H uma fórmula da LógicaProposicional, então:

• H é uma subfórmula de H;

•Se H é uma fórmula do tipo (G),

então G é uma subfórmula de H;

•Se H é uma fórmula do tipo: (G E), (G E), (G E) ou (G E),

então G e E são subfórmulas de H;

•Se G é subfórmula de H, então toda subfórmula de G é subfórmula de H.



22

Quais são as subfórmula da formula abaixo?

(((P V S) Q) R)



23

Quais são as subfórmula da formula abaixo?

(((P V S) Q) R) As subfórmulas são:

1. (((P V S) Q) R)

2. ((P V S) Q)

3. (P V S)

4. P

5. S

6. Q

7. R



24

Escreva um algoritmo, tal que, dado uma seqüência de caracteres ele determine se é uma fórmula da lógica proposicional



25

Resolva a primeira lista de exercício!


Documents

A linguagem da Lógicarosalvo.oliveira/Disciplinas/2014_2/...b) Jorge é alto mas não é elegante. c) Se Jorge é alto, então é elegante. d) Jorge é alto, se e somente se é elegante