Logica Matematica 08

Prévia do material em texto

1
Lógica Matemática
Argumentos: Regras de Inferência
Fábio Gondim
fmgondim@terra.com.br
http://fabio.iesp.googlepages.com
Argumento:
Raciocínio, indício ou prova pelo qual se tira
uma conseqüência ou dedução (Dicionário
Aurélio).
Um argumento é um conjunto de proposições
em que se pretende justificar ou defender
uma delas, a conclusão, com base nas
outras, que se chamam premissas.
2
Inferência
1. Ato ou efeito de inferir; indução, conclusão, 
ilação. 
2. Lóg. Passagem da premissa à conclusão; 
ilação.
(Dicionário Aurélio)
Inferir
1. Tirar por conclusão; deduzir pelo raciocínio
(Dicionário Aurélio)
3
Argumento na Lógica Proposicional
(Fonte: Iniciação a Lógica Matemática de Edgard de Alencar Filho)
Argumento:
Sejam P1, P2, ..., Pn (n ≥ 1) e Q proposições
quaisquer, simples ou compostas.
Definição – Chama-se argumento toda a
afirmação de que uma dada seqüência finita P1,
P2, ..., Pn (n ≥ 1) de proposições tem como
conseqüência ou acarreta uma proposição
final Q.
4
As proposições P1, P2, . . . , Pn são as premissas
do argumento, e a proposição final Q é a
conclusão do argumento.
Um argumento de premissas P1, P2, ..., Pn e de
conclusão Q indica-se por:
P1, P2, ..., Pn ├── Q
E pode ser lido das seguintes formas:
a) “P1, P2, ..., Pn acarretam Q”
b) “Q decorre de P1, P2, ..., Pn”
c) “Q se deduz de P1, P2, ..., Pn”
d) “Q se infere de P1, P2, ..., Pn”
5
Validade de um Argumento
Um argumento P1, P2, ..., Pn ├── Q é válido se e
somente se a conclusão Q é verdadeira todas as
vezes que as premissas P1, P2, ..., Pn são
verdadeiras. Um argumento não-válido é um
sofisma.
Teorema – Um argumento P1, P2, ..., Pn ├── Q é
válido se e somente se a condicional:
(P1 ∧ P2 ∧ ... ∧ Pn ) → Q
é tautológica.
Esta proposição resultante é denominada 
CONDICIONAL ASSOCIADA 6
2
Condicional Associada
Dado um argumento P1, P2, ..., Pn ├── Q, obtém-se a sua
condicional associada trocando-se o símbolo de acarreta
(├──) pela implicação (→) e dispondo a conjunção das
premissas como o antecedente e a conclusão como
conseqüente.
Exemplo:
Construir a “condicional associada” a cada um dos
seguintes argumentos:
a) ~P, ~Q → P├── Q
(~P ∧ (~Q → P) ) → Q
b) P, P→ Q, ~Q ∨ (R ∧ S) ├── R ∧ S
(P ∧ (P→ Q) ∧ (~Q ∨ (R ∧ S) ) ) → (R ∧ S)
7
Validade Mediante Tabelas-Verdade
As tabelas-verdade podem ser usadas para demonstrar a
validade de qualquer argumento.
Para verificar a validade de um argumento P1, P2, ..., Pn
├── Q, utilizando-se este método, obtém-se a sua
condicional associada: (P1 ∧ P2 ∧ ... ∧ Pn ) → Q e
constrói-se a tabela-verdade da expressão resultante.
O argumento será considerado válido se a tabela-verdade
da condicional associada representar uma tautologia, ou
seja a última coluna, a da expressão, só apresentar
valores lógicos verdadeiros.
Ex.: Demonstrar, usando tabela-verdade, a validade do
seguinte argumento: P↔ Q, Q ├── P.
8
Argumento: P ↔ Q, Q ├── P
Condicional Associada: ((P ↔ Q) ∧ Q) → P
9
P Q P ↔ Q (P ↔ Q) ∧∧∧∧ Q ((P ↔ Q) ∧∧∧∧ Q) → P
V V V V V
V F F F V
F V F F V
F F V F V
A condicional associada ao argumento é tautológica, logo 
o argumento é válido.
Exercícios
Demonstrar, usando tabela-verdade, a validade dos
seguintes argumentos:
a) P ├── P ∨ Q
b) P ∧ Q ├── P
c) P, Q ├── P ∧ Q
d) P→ Q ├── P → (P ∧ Q)
e) P→ Q, P ├── Q
f) P→ Q, ~Q ├── ~P
g) P ∨ Q, ~P ├── Q
h) P→ Q, Q → R ├── P → R 10
Argumentos Válidos Fundamentais
Os argumentos básicos, de uso corrente, a seguir, são
considerados argumentos válidos fundamentais:
01) Adição (AD): p ├── p ∨ q; p ├── q ∨ p;
02) Simplificação (SIMP): p ∧ q ├── p; p ∧ q ├── q;
03) Conjunção (CONJ): p, q ├── p ∧ q; p, q ├── q ∧ p;
04) Absorção (ABS): p → q ├── p → (p ∧ q);
05) Modus ponens (MP): p → q, p ├── q;
06) Modus tollens (MT): p → q, ~q ├── ~p;
07) Silogismo disjuntivo (SD): p ∨ q, ~p ├── q; p ∨ q, ~q ├── p;
08) Silogismo hipotético (SH): p → q, q → r ├── p → r;
09) Dilema construtivo (DC): p → q, r → s, p ∨ r ├── q ∨ s;
10) Dilema destrutivo (DD): p → q, r → s, ~q ∨ ~s ├── ~p ∨ ~r;
11
Regras de Inferência
Os argumentos da lista anterior são usados para
fazer inferências, isto é, executar os passos de uma
dedução ou demonstração, e por isso chamam-se,
também, regras de inferência.
É habitual escrevê-los na forma padronizada
indicada a seguir – colocando-se as premissas
sobre um traço horizontal e a conclusão sob o
mesmo traço.
12
3
13
Regra da Adição (AD)
Dada uma proposição p, dela se pode deduzir a sua
disjunção com qualquer outra proposição.
p
─────────
p ∨ q
p
─────────
q ∨ p
Exemplo: r ∧ s
─────────
(r ∧ s) ∨ t
14
Regra da Simplificação (SIMP)
Da conjunção (p ∧ q) de duas proposições se pode
deduzir cada uma das proposições, p ou q.
p ∧ q
─────────
p
p ∧ q
─────────
q
Exemplo: r ∧ (s ∨ t)
─────────
(s ∨ t)
15
Regra da Conjunção (CONJ)
Permite deduzir de duas proposições dadas: p e q
(premissas), a sua conjunção: p ∧ q ou q ∧ p (conclusão)
p
q
─────────
p ∧ q
p
q
─────────
q ∧ p
Exemplo: r
s ∨ t
─────────
r ∧ (s ∨ t)
16
Regra da Absorção (ABS)
Dada uma condicional (p → q) como premissa, dela se
pode deduzir, como conclusão, outra condicional com o
mesmo antecedente p e cujo conseqüente é a conjunção
(p ∧ q) das duas proposições que integram a premissa.
p → q
──────────
p → (p ∧ q)
Exemplo: r → (s ∨ t)
──────────
r → (r ∧ (s ∨ t))
17
Regra Modus Ponens (MP)
A partir de p → q e p (premissas) permite deduzir
q (conclusão) .
p → q
p
─────────
q
Exemplo: r → (s ∨ t)
r
──────────
s ∨ t
18
Regra Modus Tollens (MT)
Permite, a partir das premissas: p → q (condicional) e
~q (negação do conseqüente), deduzir como
conclusão ~p (negação do antecedente).
p → q
~q
─────────
~p
Exemplo: r → (s ∨ t)
~(s ∨ t)
──────────
~r
4
19
Regra do Silogismo Disjuntivo (SD)
Possibilita deduzir da disjunção (p ∨ q) de duas
proposições e da negação ~p (ou ~q) de uma delas a
outra proposição q (ou p).
p ∨ q
~p
─────────
q
p ∨ q
~q
─────────
p
Exemplo: r ∨ (s ∨ t)
~(s ∨ t)
──────────
r
20
Regra do Silogismo Hipotético (SH)
Permite, dadas duas condicionais: p → q e q → r
(premissas), tais que o conseqüente da primeira coincide
com o antecedente da segunda, deduzir uma terceira
condicional p → r (conclusão) cujo antecedente e
conseqüente são respectivamente o antecedente da
premissa p → q e o conseqüente da outra premissa q → r.
p → q
q → r
─────────
p → r
Exemplo:
(r ∨ s) → p
p → (s ∧ t)
────────────
(r ∨ s) → (s ∧ t)
21
Regra do Dilema Construtivo (DC)
Dadas duas condicionais e a disjunção de seus
antecedentes, como premissas, podemos deduzir como
conclusão a disjunção dos conseqüentes das duas
condicionais.
p → q
r → s
p ∨ r
─────────
q ∨ s
Exemplo:
p → (r ∧ s)
r → t
p ∨ r
─────────
(r ∧ s) ∨ t
22
Regra do Dilema Destrutivo (DD)
Dadas duas condicionais e a disjunção da negação de
seus conseqüentes podemos deduzir, como conclusão, a
disjunção da negação dos antecedentes destas
condicionais.
p → q
r → s
~q ∨ ~s
─────────
~p ∨ ~r
Exemplo:
p → (r ∧ s)
q → t
~(r ∧ s) ∨ ~t
─────────
~p ∨ ~q
Adição (AD) Modus Ponens (MP) Modus Tollens (MT)
p
─────
p ∨ q
p
─────
q ∨ p
p → q
p
──────
q
p → q
~q
──────
~p
Simplificação (SIMP) Silogismo Disjuntivo (SD)
p ∧ q
─────
p
p ∧ q
─────
q
p ∨ q
~p
──────
q
p ∨ q
~q
──────
p
Conjunção (CONJ) Silogismo Hipotético (SH)
p
q
─────
p ∧ q
p
q
─────
q ∧ p
p → q
q → r
──────
p → r
Absorção (ABS) Dilema Construtivo (DC) Dilema Destrutivo (DD)
p → q
────────
p → (p ∧ q)
p → q
r → s
p ∨ r
───────
q ∨ s
p → q
r → s
~q ∨ ~s
───────
~p ∨ ~r
Exemplo 1
Demonstrar, usando Regras de Inferência, a
validade do argumento:
p → q, p ∧ r├── q
(1) p → q PREMISSA
(2) p ∧ r PREMISSA
─────────────────────
(3) p 2 – SIMP
(4) q 1, 3 – MP
24
5
Exemplo 2
Demonstrar, usando Regras de Inferência, a
validade do argumento:
p → (q → r), p → q, p ├── r
(1) p → (q → r) PREMISSA
(2) p → q PREMISSA
(3) p PREMISSA
─────────────────────
(4) q → r 1, 3 – MP
(5) q 2, 3 – MP
(6) r 4, 5 – MP
25
Exemplo 3
Demonstrar, usando Regras de Inferência, a
validade do argumento:
p ∧ q, p ∨ r → s ├── p ∧∧∧∧ s
(1) p ∧ q PREMISSA
(2) p ∨ r → s PREMISSA
─────────────────────
(3) p 1 – SIMP
(4) p ∨ r 3 – AD
(5) s 2, 4 – MP
(6) p ∧∧∧∧ s 3, 5 – CONJ
26
Validade Utilizando Regras de 
Inferência e Equivalências
Alguns argumentos não podem ser demonstrados com o
uso exclusivo das dez regras de Inferência vistas. Algumas
vezes é necessário que se recorra a um princípio de
inferência adicional chamado “Regra de substituição”.
Regra de substituição:
Uma proposição qualquer P, ou apenas uma parte dela,
pode ser substituída por uma proposição equivalente, e a
proposição Q obtida é equivalente à P.
Isto significa que as premissas que compõem o
argumento, ou apenas algumas delas, podem ser
substituídas por uma equivalência qualquer que o
argumento resultante será equivalente conforme
demonstrado no exemplo a seguir.
27
Exemplo
Demonstrar a validade do argumento:
p ∨ (q ∧ r), p ∨ q → s ├── p ∨∨∨∨ s
(1) p ∨ (q ∧ r) PREMISSA
(2) p ∨ q → s PREMISSA
─────────────────────────────
(3) (p ∨ q) ∧ (p ∨ r) 1 – DIST
(4) p ∨ q 3 – SIMP
(5) s 2,4 – MP
(6) p ∨∨∨∨ s 5 – AD
28
Exercícios
Usando Regras de Inferência, prove a validade dos 
seguintes argumentos:
1) P → (Q → R), P → Q, P ├── R
2) P ∨ Q → ~R, P, S → R ├── ~S
3) P → Q, P ∧ Q → R, ~(P ∧ R) ├── ~P
4) P ∧ (Q ∨ R), Q ∨ R → ~S, S ∨ T ├── T
5) P ∨ Q → ~R, Q, S ∧ T → R ├── ~(S ∧ T)
6) P → Q, ~Q, ~P ∨ ~R → S ├── S
7) S ∧ ~R, Q → R, ~Q → T ├── S ∧ T
8) ~S ∨ (T ∧ R), S, R → ~Q, P → Q ├── ~P
29
Demonstração Condicional
Método útil para demonstrar a validade de um argumento e
que pode ser utilizado, apenas, quando a sua conclusão
tem a forma condicional:
P1, P2, ..., Pn ├── Q → R
Ele consiste em adicionar o antecedente da condicional ao
conjunto de premissas do argumento fazendo com que o
conseqüente se torne a conclusão:
P1, P2, ..., Pn, Q ├── R
E então provar que é tautológica a condicional:
(P1 ∧ P2 ∧ ... ∧ Pn, Q ) → R
30
6
Esta técnica baseia-se em que, pela “Regra de
Importação”, subsiste a seguinte equivalência:
(P1 ∧ P2 ∧ ... ∧ Pn) → (Q → R)
⇔⇔⇔⇔
((P1 ∧ P2 ∧ ... ∧ Pn) ∧ Q )) → R
31
Exemplo 1
Demonstrar, usando Demonstração Condicional, a
validade do argumento:
R ∧ P → ~S, P, Q → S ├── R → ~Q
(1) R ∧ P → ~S PREMISSA
(2) P PREMISSA
(3) Q → S PREMISSA
(4) R PREMISSA ADICIONADA
────────────────────────────────
(5) R ∧ P 2, 4 – CONJ
(6) ~S 1, 5 – MP
(7) ~Q 3,6 – MT
32
Exemplo 2
Demonstrar, usando Demonstração Condicional, a
validade do argumento:
p ∨ (q → r), ~r ├── q → p
(1) p ∨ (q → r) PREMISSA
(2) ~r PREMISSA
(3) q PREMISSA ADICIONADA
────────────────────────────────
(4) p ∨ (~q ∨ r) 1 – COND
(5) (p ∨ ~q) ∨ r 4 – ASSOC
(6) p ∨ ~q 2, 5 – SD
(7) ~~q 3 – DN
(8) p 6, 7 – SD
33
Exercícios
Utilizando D.C., prove a validade dos seguintes 
argumentos:
1) P → Q, P ∨ ~R ├── R → Q
2) P ∨ (Q → R), ~R ├── Q → P
3) ~P, ~R → Q, ~S → P ├── ~(R ∧ S) → Q
4) R ∧ P → ~S, P, Q → S ├── R → ~Q
5) ~R ∨ ~S, Q → S ├── R → ~Q
6) P → ~Q, ~ ( R ∧ ~P ) ├── Q → ~R
7) P ∨ Q → R, S → ~R ∧ ~T, S ∨ U ├── P → U
34
Demonstração Indireta
Neste método, para provar a validade do argumento: P1,
P2, ..., Pn ├── Q, devemos provar que a partir das
premissas P1, P2, ..., Pn, Q (premissa adicionada),
podemos chegar a uma contradição do tipo P ∧ ~P.
Teorema:
O argumento P1, P2, ..., Pn ├── Q é válido SSE (se e
somente se) o argumento P1, P2, ..., Pn, Q ├── F* for
válido.
*F representa uma contradição do tipo: P ∧ ~P.
A técnica da demonstração indireta é bastante utilizada na
matemática e pode ser chamada também de
demonstração por absurdo.
35
Exemplo 1: 
Demonstrar a validade do argumento utilizando D.I.:
p → ~q, r → q ├── ~(p ∧ r)
(1) p → ~q PREMISSA
(2) r → q PREMISSA
(3) p ∧ r PREMISSA ADICIONADA
(negação da conclusão)
──────────────────────────────────
(4) p 3 – SIMP
(5) r 3 – SIMP
(6) ~q 1, 4 – MP
(7) q 2, 5 – MP
(8) q ∧ ~q 6, 7 – CONJ
(Contradição)
36
7
Exemplo 2: 
Demonstrar a validade do argumento utilizando D.I.:
~p → q, ~q ∨ r, ~r ├── p ∨ s
(1) ~p → q PREMISSA
(2) ~q ∨ r PREMISSA
(3) ~r PREMISSA
(4) ~(p ∨ s) PREMISSA ADICIONADA
(negação da conclusão)
──────────────────────────────────
(5) ~p ∧ ~s 4 – DM
(6) ~p 5 – SIMP
(7) q 1, 6 – MP
(8) ~q 2, 3 – MP
(9) q ∧ ~q 7, 8 – CONJ
(Contradição) 37
Exercícios
Usando Demonstração Indireta, prove a validade 
dos seguintes argumentos:
1) P → Q ∨ R , ~R , P ├── Q
2) ~P → Q , ~Q ∨ R , ~R ├── P ∨ S
3) ~( P ∧ Q ), P → R, Q ∨ ~R ├── ~P
4) P → ~Q, ~R → ~P, Q ∨ ~R ├── ~P
5) ~P ∨ ~Q, R ∨ S → P, Q ∨ ~S, ~R ├── ~(R ∨ S)
6) P ∨ Q, S → ~P, ~(Q ∨ R) ├── ~S
38
Bibliografia
• ABE, Jair Minoro; SCALZITTI, Alexandre; FILHO, João I. da Silva.
Introdução à lógica para a ciência da computação. São Paulo: Arte
& Ciência, 2002.
• ALENCAR FILHO, Edgard de. Iniciação à lógica matemática. São
Paulo: Nobel, 2002.
• DAGHLIAN, Jacob. Lógica e álgebra de Boole. 4. ed. São Paulo:
Atlas, 2006.
• SILVA, Flávio S. Corrêa da; FINGER, Marcelo; MELO, Ana C. Vieira de.
Lógica para computação. São Paulo: Thompson Learning, 2006.
39