©Prof. Lineu MialaretAula 8 - 1/43Matemática Discreta 1 Instituto Federal de Educação, Ciência e Tecnologia de São Paulo - IFSP Campus de Caraguatatuba

©Prof. Lineu MialaretAula 8 - 1/43Matemática Discreta 1

Instituto Federal de Educação, Ciência e Tecnologia de São Paulo - IFSP

Campus de Caraguatatuba

10 Semestre de 2013

Matemática Discreta 1 – MD 1 Prof. Lineu Mialaret

Aula 8: Lógica Proposicional


Introdução

A alegação do advogado apresentada na aula 2 consistiu de uma série de declarações (supostamente verdadeiras), seguido de um pedido ao júri para se chegar numa conclusão específica com base nessas declarações.Já se aprendeu a usar a notação da Lógica Matemática

para representar proposições. As formas simbólicas como fbfs em lógica formal para representar proposições são chamadas fbfs proposicionais.

Será usado agora ferramental da Lógica Matemática para ver como chegar a conclusões a partir de proposições dadas.

O sistema formal que usa fbfs proposicionais é chamado de Lógica Proposicional, Lógica Declarativa ou Cálculo Proposicional.


Argumentos Válidos (1)

Um argumento pode ser representado simbolicamente como:

P1 ∧ P2 ∧ P3 ∧ P4 ... ∧ ∧ Pn → Q

onde, P1, P2, ..., Pn são proposições dadas, denominadas de

hipóteses (ou premissas) do argumento. Q é a conclusão do argumento.

Argumento Válido:Informalmente, um argumento é válido quando Q é uma

conclusão lógica de P1, P2, ..., Pn sempre que a verdade das proposições P1, P2, ..., Pn implicarem a verdade de Q.

Ou seja, quando o condicional P1 ∧ P2 ∧ P3 ∧ P4 ... ∧ ∧ Pn → Q for

verdadeiro.



Exemplo - Seja o seguinte argumento :George Washington foi o primeiro presidente dos EUA.

Thomas Jefferson escreveu a Declaração da Independência dos EUA.

Portanto, todo dia tem 24 horas.O argumento tem duas hipóteses:

George Washington foi o primeiro presidente dos EUA. Thomas Jefferson escreveu a Declaração da

Independência dos EUA.E a conclusão é:

Todo dia tem 24 horas.



Embora cada hipótese individual, bem como a conclusão, sejam proposições verdadeiras, o argumento não deve ser considerado válido.A conclusão é meramente um fato verdadeiro isolado, que

não está relacionado com, nem segue de, as hipóteses.Um argumento válido deve portanto ser verdadeiro

baseado inteiramente em sua estrutura interna. Definição: Argumento Válido

A fbf proposicional P1 ∧ P2 ∧ P3 ∧ P4 ... ∧ ∧ Pn → Q é um argumento válido quando for uma tautologia.

Exemplo: no caso anterior apresentado, pode-se simbolizar o argumento como a ∧ b → c, o que não é uma tautologia.



Para se verificar se P1 ∧ P2 ∧ P3 ∧ P4 ... ∧ ∧ Pn → Q representa uma tautologia, será usado um sistema de regras de dedução, que modificam uma fbf de modo a preservar seu valor lógico.Começa-se com as hipóteses P1, P2, ..., Pn (que se supõe

verdadeiras) e tenta-se aplicar as regras de dedução de modo a se terminar com a conclusão Q (que então tem que ser verdadeira).


Seqüencia de Demonstração

Uma seqüência de demonstração é uma seqüência de fbfs nas quais cada uma é uma hipótese ou o resultado de se aplicar regras de dedução do sistema formal as fbfs anteriores na seqüência.

Usando lógica matemática para provar que Q é uma conclusão válida de P1, P2, ..., Pn , deve-se produzir uma seqüência de demonstração no seguinte formato:P1 (hipótese)

P2 (hipótese)

...

fbf1 (obtida aplicando-se regra de dedução)

fbf2 (obtida aplicando-se regra de dedução)

...Q (obtida aplicando-se regra de dedução)


Regras de Dedução (1)

As regras de dedução para a lógica proposicional são de dois tipos:Equivalências e Inferências.

As regras de equivalência permitem que fbfs individuais sejam reescritas mantendo o mesmo valor lógico.

As regras de inferência permitem a dedução de novas fbfs a partir de fbfs anteriores na seqüência de demonstração.

As regras de equivalência dizem que determinados pares de fbfs são equivalentes (R S, onde R ↔ S é uma tautologia).A proposição R pode ser substituída por S sem mudança

do valor lógico. As regras preservam os valores.



As regras de equivalência dizem que determinados pares de fbfs são equivalentes:

Lembrar que R S, Significa que R ↔ S é uma tautologia.

A proposição R pode ser substituída pela proposição S sem mudança do seu valor lógico.

As regras de equivalência preservam os valores lógicos, pois uma fbf verdadeira continua verdadeira, se for feita uma substituição numa de suas proposições componentes.

A seguir, na próxima transparência é apresentado uma síntese das principais regras de equivalência já apresentadas.





Exercício: Mostrar que a expressão proposicional abaixo é uma tautologia.(P Q) ↔ (¬P ∨ Q)



Exemplo: Suponha que uma hipótese de um argumento proposicional seja expressa da seguinte forma:(¬A ¬∨ B) ∨ C

Então uma seqüência de demonstração para o argumento poderia começar com os seguintes passos:1. (¬A ¬∨ B) ∨ C hipótese.

2. ¬(A ∧ B) ∨ C 1, De Morgan.

3. (A ∧ B) C 2, cond.

Obs.: Tem-se então na seqüência de demonstração a

substituição da proposição (¬A ¬∨ B) ∨ C pela proposição (A ∧ B) C sem nenhuma perda de informação.



As regras de inferência dizem que se uma ou mais fbfs, contidas na primeira coluna da Tabela de Regras de Inferência (apresentada na próxima transparência), fazem parte de uma seqüência de demonstração, então pode-se adicionar uma nova fbf na seqüência, substituindo as anteriores pelas fbfs correspondentes na segunda coluna da tabela.A idéia básica de usar inferência é a da dedução de novas

proposições, a partir de proposições já conhecidas.

Ao contrário das regras de equivalência, elas não funcionam em ambas as direções.

A Tabela de Regras de Inferência (ou Tabela de Inferência ou Regras de Inferência) é apresentada a seguir na próxima transparência.



*

* P → Q, P



Silogismo:O silogismo é uma forma de raciocínio dedutiva. Na sua

forma padronizada é constituído por três proposições, sendo que as duas primeiras denominam-se de premissas e a terceira de conclusão.

Silogismo Condicional: Silogismo em que a premissa maior não afirma nem nega de

modo absoluto, mas sim a título condicional.

Exemplo

Se chover, não vamos ao futebol.

Chove.

Portanto não iremos ao futebol.



Modus Ponens:(em latim: modo de afirmar) é um dos modos dos

silogismos condicionais, (normalmente abreviado para mp). Se P, então Q.

P.

Portanto Q.

O argumento tem duas premissas. A primeira premissa é a condição "se, ..., então",

nomeadamente que P implica em Q.

A segunda premissa é que P é verdadeiro. Destas duas premissas pode ser logicamente concluído que Q tem de ser também verdadeiro.



Exemplo:



Exemplo: Se aquele animal for um gato, então aquele animal é

preguiçoso.

Aquele animal é um gato.

Logo, aquele animal é preguiçoso.

Outro Exemplo:Se Maria ou Juliana vier então a festa será alegre e

divertida.

Ou Maria ou Juliana virá a festa.

Portanto, a festa será alegre e divertida.



Modus Tollens:(em latim: modo que nega) é o nome formal para a prova

indireta. Normalmente abreviado para mt.É um argumento comum, simples:

Se P, então Q. Q é falso. Logo, P é falso.

O argumento tem duas premissas. A primeira premissa é a condição "se, ..., então",

nomeadamente que P implica Q. A segunda premissa é que Q é falso. Destas duas premissas

pode ser logicamente concluído que P tem de ser falso. (Por quê? Porque se P fosse verdadeiro, então Q seria verdadeiro, pela premissa 1, mas não é, pela premissa 2).



Exemplo:



Exemplo: Se meu carro estiver no estacionamento, então estou no

IFSP.

Eu não estou na IFSP.

Logo, meu carro não está no estacionamento.

Outro Exemplo:Se meu animal de estimação for um gato ou um cão, então

ele será um mamífero.

Meu animal de estimação não é um mamífero.

Portanto, meu animal de estimação não é nem um gato nem um cão.



Exemplo: Suponha duas hipóteses (ou premissas) de um argumento proposicional sejam expressas da seguinte forma:A (B ∧ C)

A

Então uma seqüência de demonstração para o argumento poderia começar com os seguintes passos:1. A (B ∧ C) hipótese.

2. A hipótese.

3. B C∧ 1,2, mp.



Exemplo: Suponha duas hipóteses de um argumento proposicional sejam expressas da seguinte forma:(A ¬∧ B) C

¬C

Então uma seqüência de demonstração para o argumento poderia começar com os seguintes passos:1. (A ¬∧ B) C hipótese.

2. ¬C hipótese.

3. ? 1,2, ?.



Exemplo: Suponha duas hipóteses de um argumento proposicional sejam expressas da seguinte forma:(A B) ∨ C

A

Então uma seqüência de demonstração para o argumento poderia começar com os seguintes passos:1. (A B) ∨ C hipótese.

2. A hipótese.

3. ? mp não se aplica.

Para se aplicar regras de inferências, as fbfs tem que ter a mesma forma apresentada na tabela de inferência.



Exemplo: Usando lógica proposicional, provar que o argumento abaixo é valido.A (∧ B C) ((∧ A ∧ B) (D ¬∨ C)) ∧ B D



Exemplo: Usando lógica proposicional, provar que o argumento abaixo é valido.A (∧ B C) ((∧ A ∧ B) (D ¬∨ C)) ∧ B D



Exemplo: Usando lógica proposicional, provar que o argumento abaixo é valido.((A ¬∨ B) C) (∧ C D) ∧ A D



Exemplo: Usando lógica proposicional, provar que o argumento abaixo é valido.((A ¬∨ B) C)) (∧ C D) ∧ A D



Sugestões para a dedução:Modus ponens é a regra de inferência mais intuitiva e deve

ser usada muitas vezes.

Expressões (fbfs) da forma ¬(P ∧ Q) e ¬(P ∨ Q) dificilmente são úteis em uma seqüência de demonstração.

Usar as leis de De Morgan para convertê-las em ¬P ¬∨ Q e ¬P ¬∧ Q.

Expressões (fbfs) na forma P ∨ Q também não são úteis em seqüência de demonstração.

Usar a dupla neg.para converter P ∨ Q em ¬(¬P) ∨ Q; e

Depois usar a prop. condicional para obter ¬P Q.


Método Dedutivo (1)

Suponha que o argumento que se deseja provar tenha o seguinte formato,

P1 ∧ P2 ∧ P3 ∧ P4 ... ∧ ∧ Pn → (R → S),

onde a conclusão é uma implicação.

Em vez de se usar P1, ..., Pn como hipóteses e inferir a condicional R → S, o método dedutivo permite que se adicione a proposição R como uma hipótese adicional e depois se faça a inferência de S.

Ou seja, deve-se provar

P1 ∧ P2 ∧ P3 ∧ P4 ... ∧ ∧ Pn ∧ R → S


Exemplo: Usando lógica proposicional, provar que o argumento abaixo é valido.(A (A B)) (A B)

equivale a

(A (A B)) ∧ A B



Exemplo: Usando lógica proposicional, provar que o argumento abaixo é valido.(A B) (∧ B C) (A C)

equivale a

(A B) (∧ B C) ∧ A C

A demonstração acima descreve o que se denomina de Silogismo Hipotético (sh).



No Silogismo Hipotético, a regra é:de P Q R, pode-se deduzir P R.

O que essa regra diz é que: (P Q) (∧ Q R) (P R) é um argumento válido.

Exemplo:Se o pássaro está perdido, então a porta da gaiola está

aberta.

Se a porta da gaiola está aberta, então ele pode retornar a gaiola.

Logo, se o pássaro está perdido, então ele pode retornar a gaiola.



Outro Exemplo:Se meu time jogar bem, então ele vencerá suas partidas.

Se meu time vencer suas partidas, então ele se classificará para as finais.

Se meu time jogar bem, então ele se classificará para as finais.



Exemplo: Usando lógica proposicional para demonstrar que o argumento abaixo é valido:(¬A ∨ B) (∧ B C) (A C).

A seguinte seqüência de demonstração prova o resultado:

Obs.:Pode-se demonstrar a validade do argumento sem remover a proposição condicional da conclusão, ou seja,

sem transformar (¬A ∨ B) (∧ B C) (A C) em (¬A ∨ B) (∧ B C) ∧ A C.



Exemplo: Usando lógica proposicional para demonstrar que o argumento abaixo é valido, sem usar o silogismo hipotético.(¬A ∨ B) (∧ B C) (A C).(¬A ∨ B) (∧ B C) A ∧ C.

A seguinte seqüência de demonstração prova o resultado.1. ¬A ∨ B hipótese.2. B C hipótese. 3. A hipótese4. A B 1, cond.5. B 3,4, mp.6. C 2,5, mp.



Argumentos Verbais (1)

Um argumento verbal em português, (por exemplo o resumo de um advogado num tribunal, um discurso político, etc.), formado por declarações simples, pode ser testado logicamente por um processo de duas etapas:1. Simbolizar cada declaração usando fbfs proposicionais.

2. Provar a validade do argumento, construindo uma seqüência de demonstração por meio das regras de dedução.



Exemplo - Considere o seguinte argumento:Se a taxa de juros cair, o mercado imobiliário vai melhorar.

A taxa federal de descontos vai cair, ou o mercado imobiliário não vai melhorar. A taxas de juros vai cair. Portanto, a taxa federal de descontos vai cair.

Simbolizando para lógica proposicional:J: A taxa de juros vai cair.

I: O mercado imobiliário vai melhorar.

F: A taxa federal de descontos vai cair.

(J I) (∧ F ¬∨ I) ∧ J F



O argumento fica da seguinte forma:(J I) (∧ F ¬∨ I) ∧ J F

Uma seqüência de demonstração para se estabelecer a validade desse argumento é:



Exemplo - Considere o seguinte argumento:Meu cliente é canhoto mas, se o diário não tiver sumido,

então meu cliente não é canhoto; portanto, o diário sumiu.

Simbolizando para lógica proposicional:C: Meu cliente é canhoto.

D: O diário sumiu.



O argumento fica da seguinte forma:C (¬∧ D ¬C) D

Uma seqüência de demonstração para se estabelecer a validade desse argumento é:



Exercício 1 da Lista 7 – Verifique a validade do seguinte argumento:Se a segurança é um problema, então o controle será

aumentado. Se a segurança não é um problema, então os negócios na internet irão aumentar. Portanto, se o controle não for aumentado, os negócios na internet irão aumentar.

Simbolize para lógica proposicional usando as letras proposicionais S, C e N.



Exercício 2 da Lista 7 – Verifique a validade do seguinte argumento:Se meu cliente fosse culpado, a faca estaria na gaveta. Ou

a faca não estava na gaveta ou José viu a faca. Se a faca não estava lá no dia 10 de outubro, então José não viu a faca. Além disso, se a faca estava lá no dia 10 de outubro, então a faca estava na gaveta e o martelo estava no celeiro. Mas todos sabemos que o martelo não estava no celeiro. Portanto, senhoras e senhores, meu cliente é inocente.

Documents

©Prof. Lineu MialaretAula 8 - 1/43Matemática Discreta 1 Instituto Federal de Educação, Ciência e Tecnologia de São Paulo - IFSP Campus de Caraguatatuba