CAPÍTULO 4 Cálculo proposicional Paulette · CAPÍTULO 4 – Cálculo proposicional Paulette 33 CÁLCULO PROPOSICIONAL 1. PROPOSIÇÕES Uma proposição é uma sentença declarativa

CAPÍTULO 4 – Cálculo proposicional Paulette

33

CÁLCULO PROPOSICIONAL

1. PROPOSIÇÕES

Uma proposição é uma sentença declarativa que pode ser verdade ou falsa, mas não ambas. As

proposições podem ser divididas em proposições simples e compostas.

1.1. Proposições simples

a) Pedro é aluno do Curso de Informática.

b) A terra gira em torno do sol.

c) O leite é branco.

d) 7 é quadrado perfeito.

1.2. Proposições compostas

e) Cabral descobriu o Brasil e Colombo a América.

f) Bruno cursa Informática e Mariel Estatística.

g) O triângulo ABC é isóscele ou retângulo.

h) Se Pedro é estudioso, então será aprovado.

i) ABC é triângulo equilátero se, e somente se, é que iângulo.

1.3. Princípio da não contradição

Uma proposição não pode ser verdadeira e falsa ao mesmo tempo.

São verdadeiras (a), (b) e (c) e falsa (d).

1.4. Princípio do terceiro excluído.

Toda proposição ou é verdadeira ou falsa. Sempre ocorrem esses casos e nunca um terceiro.

2. OPERAÇÕES LÓGICAS

O cálculo das proposições consiste nas operações fundamentais que partem de proposições

simples para se chegar às proposições compostas. As operações que podem ser efetuadas são:

A negação, a conjunção, a disjunção, a condicional e a bicondicional.

2.1. Conectivos

O Cálculo das proposições destaca cinco operadores lógicos, a saber:

...não...(denota-se “ ”)

... e... (denota-se “ ”)

...ou...(denota-se “ ”)

...se,... então... (denota-se “ ”)

...se, e somente se ... (denota-se “ ”)


34

O primeiro operador “ ” é dito unário, pelo fato de operar sobre um só operando, os demais são

operadores binários, já que operam sobre dois operandos.

2.2. Negação ( )

É a mais simples operação-verdade. Se a proposição A é verdadeira, então A é falsa, se A é

falsa, então A é verdadeira.

A: 2/3 é um número racional. (verdade)

A: 2/3 não é um número racional. (falso) ou

A: 2/3 é um número irracional. (falso)

Tabela verdade para a negação

2.3. Conjunção ( )

Essa operação verdade corresponde ao termo “e” e seu símbolo é “ ”. Por meio da conjunção é

possível, dadas duas proposições simples A e B obter-se outra composta A B que será verdadeira

somente quando A e B forem verdadeiras.

A: Recife é a capital de Pernambuco.

B: Manaus é a capital do Amazonas.

A B: Recife é a capital de Pernambuco e Manaus é a capital do Amazonas.

A B A B A B A B

V V V 1 1 1

V F F 1 0 0

F V F 0 1 0

F F F 0 0 0

Exemplo 1:

Verifique se a composta é verdadeira ou falsa.

a) José de Alencar escreveu o Guarani e Machado de Assis Capitu. ( V V = V)

b) 5+2=7 e 3> 5. ( V F = F )

c) > 4 e 7 é número primo. ( F V = F )

d) > 4 e 8 é número ímpar. ( F F = F )

A A A A

V F 1 0

F V 0 1


35

2.4. Disjunção ( )

Essa operação verdade corresponde ao termo “ou” e seu símbolo é “ ”. Por meio da disjunção é

possível, dadas duas proposições simples A e B obter-se outra composta A B que será falsa somente

quando A e B forem falsas.

A: Recife é a capital de Pernambuco.

B: Manaus é a capital do Amazonas.

A B: Recife é a capital de Pernambuco ou Manaus é a capital do Amazonas.

A B A B A B A B

V V V 1 1 1

V F V 1 0 1

F V V 0 1 1

F F F 0 0 0

Exemplo 2:


a) 2+2=4 ou 5>3 ( V V = V)

b) 4 ou 7 é número primo. ( F V =V)

c) 4 ou 8 é número primo. ( F F =F )

2.5. Condicional ( )

Essa operação verdade corresponde ao termo “...se,... então...”. Por meio da condicional é

possível, dadas duas proposições simples A e B obter-se outra composta A B que será falsa somente

quando A for V e B for falsa.

Se chover, então irei ao cinema.

Se estudar, então serei aprovado.

Seja A: estudar

B: serei aprovado

A partir de duas proposições A e B, construímos uma nova proposição.

A B (lê-se, se A, então B) ou A implica B.

A tabela verdade é dada por:

A B A B A B A B

V V V 1 1 1

V F F 1 0 0

F V V 0 1 1

F F V 0 0 1


36

Observação 01:

Da teoria dos conjuntos sabemos que A B B ou A B A , assim, se x A B ,

então ,x B isto é, sempre é verdade que se x está em A B , então x está em .B Logo, na

tabela A B B é sempre verdadeira.

A B A B A B B

V V V V V V

V F F F V F

F V F F V V

F F F F V F

Observando as três últimas colunas podemos escrever:

V V = V

F F = V

F V = V

Observação 02:

Uma proposição A B é sempre Verdadeira (V) desde que A seja Falsa (F), independente do

valor de B.

Exemplo 3:


1) Se 2 + 2 =5, então 1 1. (verdade)

2) Se 2 + 2 =5, então 1 = 1. (verdade)

3) Se o Papa joga no Corinthians, então o Palmeiras será campeão. (verdade)

4) Se o Papa joga no Corinthians, então todos os alunos de Matemática Discreta serão

aprovados. (verdade)

Observação 03:

As proposições no Exemplo 03 são trivialmente verdadeiras pois, sendo a hipótese falsa, como

em, A : 2 + 2 = 5 ou A: O Papa joga no Corinthians, então a composta é verdadeira.

2.6. Bicondicional ( )

Para definirmos a tabela verdade da bicondicional escrevemos:

“A se, e somente se, B ”e é definida por (A B) ( B A)

A B A B B A (A B) ( B A)

V V V V V

V F F V F

F V V F F

F F V V V


37

Segue, portanto, a tabela verdade para a bicondicional.

A B A B A B A B

V V V 1 1 1

V F F 1 0 0

F V F 0 1 0

F F V 0 0 1

Exercícios de aplicação 9:

Escreva em linguagem corrente.

1) A: Está frio.

B: Está chovendo.

a) A:

b) A B:

c) A B:

d) A B;

e) A B:

f) A B:

g) A B:

2) Analogamente:

A: Pedro é aluno de ADS

B: ADS é Curso da Fatecsp

a) A:

b) A B:

c) A B:

d) A B;

e) A B:

f) A B:

g) A B:


38

3) Escreva em linguagem simbólica as sentenças.

p: Carolina é alta.

q: Carolina é elegante.

a) Carolina é alta e elegante.

b) Carolina é alta, mas não é elegante.

c) É falso, que Carolina é baixa ou elegante.

d) Carolina não é nem baixa nem elegante.

e) Carolina é alta, ou ela é baixa e elegante

4) Dar o valor lógico das proposições.

a) Porto Alegre é a capital do Estado do Paraná ou 10 é par. ( )

b) Se 3 > , então 2 é racional. ( )

c) Se 3 > , então o Corinthians será campeão Paulista de 2011. ( )

d) Se 1 1, então 4 9 5 . ( )

e) 2+3=5 se, e somente se 36 6. ( )

f) 32 6 se, e somente se 2+2+2=6. ( )

2.7. Formas sentenciais

Quando estudamos as expressões numéricas, observamos expressões com as operações de

adição, subtração, multiplicação e divisão organizadas com parênteses, colchetes e chaves. Da mesma

forma ocorrem as formas sentenciais usando , , , e .


39

2.8. Tabela verdade

Para cada forma sentencial podemos montar uma tabela verdade.

Exemplo 4:

Construir a tabela verdade relativa à forma sentencial

[( ) ( )] ( )A B A C B C

A B C A B A A C C B C

V V V V F V F F F

V V F V F F F V V

V F V F F V V F F

V F F F F F V V F

F V V V V V F F F

F V F V V V V V V

F F V V V V F F F

F F F V V V F V F

Exemplo 5:

Construir a tabela verdade relativa à forma sentencial

[( ) ( ] ( )A B B C A C

A B C A B B C A C

V V V V V V V

V V F V F V F

V F V F V V V

V F F F V V F

F V V V V V V

F V F V F V V

F F V V V V V

F F F V V V V


40

Exemplo 6:

Tabela verdade pode ser feita do modo simplificado como segue.

( ) ( )A B A B

V V V V F V V

V F F V F F F

F V V V V V V

F V F V V V F


Construir a tabela verdade relativa à forma sentencial (Simplificada ou não).

1) ( ) ( )p q p q

2) [ ( )] ( )A B C A C


41

3) [( ) ( )] ( )A B C D D A

4) [( ) ( )] [( ) ( )]A C B C B A A C

5) [( ) ( )] [( ) ( )]A B C A A B C A


42

6) [( ) ( )] [( ) ( )]A B C A A B C B

2.9. Tautologia – contradição

Uma forma sentencial diz-se tautologia, se assumir valor V (verdade) para quaisquer que sejam

os valores atribuídos às variáveis e se assumir o valor F diremos que é uma contradição.

Exemplo 7:

A forma sentencial que segue é uma tautologia.

( ) ( )A B A B

V V V V F V V

V F F V F F F

F V V V V V V

F V F V V V F

Exemplo 8:

A forma sentencial que segue é uma contradição.

( ) ( )A B A B

V V V F F F F

V V F F F F V

F V V F V F F

F F F F V V V


43

Exemplo 9:

Se a forma sentencial ( ( )) ( )A B C B C é falsa,

quais valores possíveis de verdade que podem assumir A, B e C?

( ( )) ( )A B C B C

____________________0___________ 1ª conclusão

_1_________________________ 0______ 2ª conclusão

_______ 1_____0__________1_____0___ 3ª conclusão

______0_____________________________4ª conclusão

_0___________0_________________________5ª conclusão

Assim, A=0, B=1 e C=0


As formas sentencias que seguem são falsas, quais valores possíveis de verdade, que podem assumir

A, B, C , D e E?

1) [ ( )] ( )A B D A B C

2) ( ) [( ) ]A B B C C


44

3) ( ( ) ) (( ) ( )A B C D B E C D

4) A B B C

5) Se a forma sentencial ( ) ( )A B C B C A é falsa, e a sentença

C B é verdadeira. Quais os valores possíveis de verdade que podem assumir A, B e C?


45

6) Se a forma sentencial ( ) { [ ( )]}A B C D B C E é falsa. Quais os

valores possíveis de verdade que podem assumir A, B, C, D e E?

7) [( ( ) ) (( ) ( ))]B C D B E C D A

8) ( ) [(( ) ) ( ( ))]A B C B A B B D


46

2.10. Implicações e equivalências lógicas (~)

Dizemos que uma forma sentencial X implica logicamente uma forma sentencial Y, se a forma

sentencial X Y for uma tautologia.

Exemplo 10.

Seja X: A B e Y: A B , mostremos que X ~ Y isto é

( )A B ( )A B

A B A B A B

V V V V F V V

V F F V F F F

F V V V V V V

F F V V V V F

2.11. Equivalências lógicas fundamentais

1E : Lei da dupla negação: ~A A

A A A

V F V

F V F

Exemplo 11. Não entendi nada desta explicação ~ entendi tudo.

A : Entendi essa explicação.

A: Não entendi essa explicação.

A : Não entendi nada essa explicação A : entendi tudo.

2E : Lei da idempotência: ~ ~A A A e A A A

A A A A

V V V V

F F V F

A A A A


47

V V V V

F F V F

3E : Lei da Comutatividade:

a) ~A B B A

A B B A V V V V V V V

V F F V F F V

F F V V V F F

F F F V F F F

b) ~A B B A

A B B A V V V V V V V

V F F V F F V

F F V V V F F

F F F V F F F

4E : Leis da associatividade:

a) ( ) ~ ( )A B C A B C

b) ( ) ~ ( )A B C A B C

5E : Leis de De Morgan

a) ( ) ~ ( )A B A B

b) ( ) ~ ( )A B A B

Demonstração: Usaremos 1 para V e 0 para F

a) ( ) ~ ( )A B A B

A B A B 0 1 1 1 1 0 0 0

0 1 1 0 1 0 0 1

0 0 1 1 1 1 0 0

1 0 0 0 1 1 1 1


48

b) ( ) ~ ( )A B A B

A B A B 0 1 1 1 1 0 0 0

0 1 1 0 1 0 0 1

0 0 1 1 1 1 0 0

1 0 0 0 1 1 1 1

Mostre as equivalências lógicas usando as tabelas verdade.

6E : Leis distributivas ou de fatoração

a) ( ) ~ ( ) ( )A B C A B A C

b) ( ) ~ ( ) ( )A B C A B A C

7E : Leis de absorção

1) ( ) ~A A B A

2) ( ) ~A A B A

3) ( ) ~ ( )A B B A B

4) ( ) ~ ( )A B B A B

5) Se T é tautologia e F uma contradição, então

a) ( ) ~T A A b) ( ) ~T A T

c) ( ) ~F A F d) ( ) ~F A A

Mostremos, a) ( ) ~T A A

T A A

1 1 1 1 1

1 1 1 1 1

1 0 0 1 0

1 0 0 1 0

Mostre as propriedades b) c) d) usando as tabelas verdade.


49

8E : Contra positivo.

( ) ~ ( )A B B A

A B B A 1 1 1 1 0 1 0

1 0 0 1 1 0 0

0 1 1 1 0 1 1

0 1 0 1 1 1 1

9E : Eliminação da condicional

a) ( ) ~ ( )A B A B

A B A B 1 1 1 1 0 1 1

1 0 0 1 0 0 0

0 1 1 1 1 1 1

0 1 0 1 1 1 1

b) ( ) ~ ( )A B A B

A B A B B 1 1 1 1 1 0 0

1 0 0 1 0 1 1

0 1 1 1 1 0 0

0 1 0 1 1 0 1

10E : Eliminação da Bicondicional

a) ( ) ~ ( ) ( )A B A B A B

A B A B A B 1 1 1 1 1 1 0

1 0 0 1 0 0 0

0 0 1 1 0 0 0

0 1 0 1 0 1 1


50

b) ( ) ~ ( ) ( )A B A B B A

A B A B B A 1 1 1 1 1 1 1

1 0 0 1 0 0 1

0 0 1 1 1 0 0

0 1 0 1 1 1 1


Nota: Nos exercícios que se seguem use as equivalências lógicas apresentadas, indicando qual

está sendo usada para a solução do exercício.

1) A forma sentencial ( ) ( )A B A B B é logicamente equivalente a

a) A B b) A B c) A B d) A B

2) A forma sentencial [( ) ] ( )B C A C B é logicamente equivalente a

a) ( )C A B b) ( )C A B c) ( )C A B


51

3) A forma sentencial ( ) [ ( )]A A B A B B é logicamente equivalente a

a) ( )A B b) A B c) A B d) ( )B A

4) A forma sentencial ( ) [( ) ]A B C A B C é logicamente equivalente a

a) ( )C A B b) ( )C A B c) ( )A B C

5) A forma sentencial ( ) ( ) {[ ( ) ( ) ( )] ( )}A B B A A B B A C A C C é

logicamente equivalente a

a) ( )A B b) ( )C A B c) ( )A B C d)( )A B C


52

6) A forma sentencial [( ) ( )] ( )A B A B A B é logicamente equivalente a

a) A B b) A B c)Tautologia d)Contradição

7) A forma sentencial ( [( ( )) ( )]A C B B C A B é logicamente equivalente a

A B b) A B c)Tautologia d)Contradição

8) A forma sentencial ( ) ( ) [( ) ]A C B C A B C é logicamente equivalente a

A B b) A B c) A B d) ( )A B C

9) A forma sentencial {[( ) ( )] [ ( )]} {[( ) ] }A C B C B B C A C B A é logicamente

equivalente a

A B b) A B c) A B d) ( )A B C e) )A B C


53

Observação:

Nos exercícios que seguem é importante conhecer a leitura das proposições e sua simbologia.

Assim,

A B : lê-se: Se A , então B

A, somente se B

A é condição suficiente para B .

B é condição necessária para A .

A B : A é condição necessária é suficiente para B .

Exemplo 12:

Indique em quais dos seguintes casos, A é condição necessária (c.n) para B, em quais A é

condição suficiente (c.s) para B e em quais A é condição necessária e suficiente (c.n.s) para B.

a) A: n é divisível por 6 B: n número par (c.s)

b) A: x < 0 e y < 0 B: x .y > 0 (c.s)

c) A: x é ímpar B: 2x é impar (c.n.s)

d) A: x = 2 B: 2x =4 (c.s)

e) A: 2x =4 B: x = 2 (c.n)

Exemplo 13:

Dar a negação em linguagem corrente da proposição.

As rosas são amarelas e os cravos brancos.

Solução:

Definindo:

A: As rosas são amarelas.

B: Os cravos brancos.

Assim, podemos escrever: A B

Negação de A B é ( )A B ~ A B (Leis de De Morgan).Assim em linguagem corrente

escrevemos:

As rosas não são amarelas ou os cravos não são brancos.

Exemplo 14:


Se estiver cansado ou com fome, não consigo estudar.

Definindo:

C: estiver cansado

F: com fome

E: consigo estudar

E: não consigo estudar.


54

Da proposição podemos escrever: ( )C F E , negando e usando as equivalências

lógicas, segue:

[( ) ] ~ [ ( ) ]C F E C F E ~( )C F E .

Portanto, em linguagem corrente escrevemos:

Mesmo cansado ou com fome eu estudo ou ainda

Estando cansado ou com fome consigo estudar.

Exemplo 15:


A temperatura diminuirá somente se chover ou nevar.

Definindo: D: A temperatura diminuirá

C: chover

N: nevar

Assim, podemos escrever: ( )D C N , negando e usando as equivalências lógicas, segue:

[ ( )]D C N ~ [ ( )]D C N ~ ( )D C N ~ )D C N

Em linguagem corrente escrevemos:

A temperatura diminuirá mesmo não chovendo e não nevando.

Não choverá e não nevará e mesmo assim a temperatura diminuirá.


Dar a negação em linguagem corrente das proposições.

1) Fará sol se, e somente se não chover.

2) Bruno é aluno MD ou pesquisador.


55

3) Existe menina feia.

4)Todo menino gosta de futebol.

5) Nenhuma menina gosta do Corinthians.

6) Tudo que é bom engorda.

7) Todos os homens são mortais.

8) Thaís é inteligente e estuda.


56

9) O Corinthians ganhará o campeonato brasileiro se o juiz roubar ou os santos ajudarem.

10)Se eu estudar matemática discreta e tiver sorte na prova, então serei aprovado.

11) Se é domingo ou faz chuva, então é feriado e é noite.

12) Ficarei rico, se estudar ou ganhar na loteria.

13) A laranja não cai do pé, a menos que esteja madura ou haja uma forte ventania.


57

3. ARGUMENTOS

Sejam 1 2, ,...,

nP P P e Q proposições. Denomina-se argumento a toda afirmação de que uma

dada seqüência finita de proposições 1 2, ,...,

nP P P acarreta uma proposição final Q .

1 2, ,...,

nP P P , denominam-se premissas, e Q conclusão. Lê-se

1 2, ,...,

nP P P , acarreta Q ou Q decorre de

1 2, ,...,

nP P P .

Um argumento que consiste em duas premissas e uma conclusão denomina-se silogismo.

Um argumento 1 2, ,...,

nP P P Q é valido se, e somente se a condicional

1 2( ... )

nP P P Q é uma tautologia.

Exemplo 16:

Verifique em cada um dos casos abaixo, se a argumentação é válida ou é uma falácia.

1) Sejam as Premissas:

i) Se um homem é feliz, ele não é solteiro.

ii) Se um homem não é feliz, ele morre cedo.

Conclusão:

Homens solteiros morrem cedo.

Chamando

F: Homem é feliz

S: Solteiro

C: morre Cedo

Podemos escrever a forma simbólica argumentação como:

[( ) ( )] ( )F S F C S C

______1________ 1__________1___________hip_1_______ 1ª conclusão

___________1_______________________________________ 2ª conclusão

_________0_________________________________________ 3ª conclusão

_0_____________________0___________________________ 4ª conclusão

_____________________1________1__________________1_ 5ª conclusão

______________________________________1_______1____ final

Portanto, a argumentação é verdadeira.


i) Se um homem não fuma, então é atleta ou não é alcoólatra.

ii) Se um homem fuma, então tem câncer.

iii) Paulo não é atleta, mas alcoólatra.

Conclusão:

Paulo tem câncer.


58

Chamando

F: Fuma

C: Câncer

At: Atleta

Al: Alcoólatra

( ( )) ( )t l t l

F A A F C A A C

______ 1____________________1__________ __ 1_________1ª conclusão

______________________________________1__ ___1____ 2ª conclusão

___________0______1_____________________0____________3ª conclusão

________________0____________________________________4ª conclusão

______________0______________________________________5ª conclusão

___0_________________________________________________6ª conclusão

_____1____________________1_____1_________________ 1_ 7ª conclusão

_________________________________________________1__ Verdade__



i) Se eu não jogar xadrez, jogarei futebol.

ii) Se estiver machucado, não jogarei futebol.

Conclusão:

Se estiver machucado jogarei xadrez.

Chamando

X: jogar Xadrez

F: Futebol

M: Machucado

X F M F M X

______ V_____________ V_____________________ 1ª conclusão

_______________V____________________ V(hip) ___ 2ª conclusão

___________________V_________________________ 3ª conclusão

___________F________________F________________ 4ª conclusão

___F__________________________________________ 5ª conclusão

______V____________________________________V__ 6ª conclusão

_________________________________________V_____7ª conclusão

__________________________________V____________Verdade



59


Verifique em cada um dos casos abaixo, se a argumentação é válida ou é uma falácia.


i) Os bebes não são lógicos.

ii) Quem consegue amestrar um crocodilo não é desprezado.

iii) Pessoas não lógicas são desprezadas.

Conclusão:

Bebes não conseguem amestrar crocodilo.


i) O professor não erra.

ii) Andréia é distraída.

iii) Quem é distraído erra

Conclusão:

a) Andréia não é professora. b) Nenhum professor é distraído.


60


i) Ana Carolina é estudiosa.

ii) Todo estudioso é aprovado em Matemática discreta.

Conclusão:

Ana Carolina será reprovada em Matemática discreta.


i) Se uma mulher é do signo de câncer, então não deve ser dançarina ou deve ser cozinheira e

manequim.

ii) Toda mulher que não é do signo de câncer é carinhosa.

iii) Luíza não é cozinheira, mas é dançarina.

Podemos concluir que:

Luíza é carinhosa.


i) Se trabalho, não posso estudar.

ii) Trabalho ou serei aprovado em Matemática Discreta.

iii) Trabalhei


Fui reprovado em M. D.


61

6)Suponha que:

“Se o representante sindical ou o dirigente industrial forem teimosos, então a greve será decretada se, e

somente se, houver uma injunção governamental sem o envio de tropas policiais junto à fabrica”.

i) Verifique se é possível o fato.

“O representante sindical ser teimoso, o dirigente não, a greve se decretada e haver uma injunção

governamental com envio de tropas”

6i) Não é possível

ii) “Dirigente e representante são ambos teimosos, a greve não é decretada, não há injunção

governamental mas envio de tropas policiais.”

6ii) Esse fato é possível

7) Sejam as premissas:

i) Se um aluno é feliz, ele faz matemática discreta.

ii) Se um aluno não é feliz, ele não é estudioso.


Alunos que não fazem matemática discreta, não são estudiosos.

Documents

CAPÍTULO 4 Cálculo proposicional Paulette · CAPÍTULO 4 – Cálculo proposicional Paulette 33 CÁLCULO PROPOSICIONAL 1. PROPOSIÇÕES Uma proposição é uma sentença declarativa