aula1 Lógica Proposicional -Material Prof César

Prévia do material em texto

' $
LO´GICA PROPOSICIONAL
Prof. Ce´sar Francisco de Moura Couto
Matema´tica Discreta
& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• O que e´ lo´gica?
• Proposic¸a˜o: Uma sentenc¸a que declara um fato, que pode ser verdadeiro (V) ou falso (F),
mas na˜o ambos.
• Sentenc¸as que sa˜o proposic¸o˜es:
– Bras´ılia e´ a capital do Brasil.
– New York e´ a capital dos EUA.
– 1 + 1 = 2
– 2 + 2 = 3
• Sentenc¸as que na˜o sa˜o proposic¸o˜es:
– Que horas sa˜o?.
– Leia isto cuidadosamente.
– x + 1 = 2
– x + y = z
• Varia´veis proposicionais: P,Q,R, S, ...
Prof. Ce´sar Francisco de Moura Couto 1& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Definic¸a˜o 1: Seja p uma proposic¸a˜o. A negac¸a˜o de p, indicada por ¬p, e´ a
sentenc¸a ”Na˜o e´ o caso de p”.
– Qual e´ a negac¸a˜o da proposic¸a˜o ”Hoje e´ sexta-feira”?
– Soluc¸a˜o: ”Hoje na˜o e´ sexta-feira”.
– Qual e´ a negac¸a˜o da proposic¸a˜o ”No m´ınimo 10 mm de chuva ca´ıram hoje
em Belo Horizonte”?
– Soluc¸a˜o: ”Menos de 10 mm de chuva ca´ıram hoje em Belo Horizonte”.
Negac¸a˜o
p ¬p
V F
F V
• ¬ e´ o operador lo´gica da negac¸a˜o. Um operador lo´gico tem a func¸a˜o de criar
novas proposic¸o˜es a partir de outras.
Prof. Ce´sar Francisco de Moura Couto 2& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Definic¸a˜o 2: Sejam p e q proposic¸o˜es. A conjunc¸a˜o de p e q, indicada por
p ∧ q, e´ a proposic¸a˜o ”p e q”. A conjunc¸a˜o p ∧ q e´ verdadeira quando ambas
sa˜o verdadeiras, e falsa caso contra´rio.
– Qual e´ a conjunc¸a˜o das proposic¸o˜es p e q, em que p e´ a proposic¸a˜o ”Hoje e´
sexta-feira”e q e´ a proposic¸a˜o ”Hoje esta´ chovendo”.
– Soluc¸a˜o: ”Hoje e´ sexta-feira e esta´ chovendo”.
Conjunc¸a˜o
p q p ∧ q
V V V
V F F
F V F
F F F
Prof. Ce´sar Francisco de Moura Couto 3& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Definic¸a˜o 3: Sejam p e q proposic¸o˜es. A disjunc¸a˜o de p e q, indicada por
p ∨ q, e´ a proposic¸a˜o ”p ou q”. A disjunc¸a˜o p ∨ q e´ falsa quando ambas sa˜o
falsas, e verdadeira caso contra´rio.
– Qual e´ a disjunc¸a˜o das proposic¸o˜es p e q, em que p e´ a proposic¸a˜o ”Hoje e´
sexta-feira”e q e´ a proposic¸a˜o ”Hoje esta´ chovendo”.
– Soluc¸a˜o: ”Hoje e´ sexta-feira ou hoje esta´ chovendo”.
Disjunc¸a˜o
p q p ∨ q
V V V
V F V
F V V
F F F
• Em qual situac¸a˜o a proposic¸a˜o acima e´ verdadeira?
Prof. Ce´sar Francisco de Moura Couto 4& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Qual e´ o significado da palavra ”ou”em portugueˆs? Inclusivo, exclusivo, ou
ambos?
• Definic¸a˜o 4: Sejam p e q proposic¸o˜es. A disjunc¸a˜o exclusiva de p e q,
indicada por p⊕ q, e´ a proposic¸a˜o que e´ verdadeira quando exatamente uma
das duas e´ verdadeira e falsa nos outros casos.
Disjunc¸a˜o
p q p⊕ q
V V F
V F V
F V V
F F F
Prof. Ce´sar Francisco de Moura Couto 5& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Definic¸a˜o 5: Sejam p e q proposic¸o˜es. A proposic¸a˜o condicional p→ q e´ a
proposic¸a˜o ”se p, enta˜o q”. A condicional p→ q e´ falsa quando p e´
verdadeiro e q e´ falsa e verdadeira em qualquer outro caso.
• Outras formas para expressar a condicional:
”se p, enta˜o q”
”se p, q”
”p e´ suficiente para q”
( a veracidade de p e´ suficiente para q ser verdadeiro.)
”q se p”
”q quando ocorrer p”
”q a menos que ¬p”
”p implica q”
”p apenas se q”
”uma condic¸a˜o suficiente para q e´ p”
Prof. Ce´sar Francisco de Moura Couto 6& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• continuac¸a˜o:
”q sempre que p”
”q e´ necessa´rio para p”
( a veracidade de q e´ necessa´ria para quando p for verdadeiro.)
”q segue de p”
• Uma condicional representa um contrato. Se o contrato for quebrado a
condicional e´ falsa. Exemplos:
– ”Se eu for eleito, enta˜o vou diminuir os impostos.”
– ”Se voceˆ tirar nota 10 no exame final, enta˜o tera´ conceito A.”
• Seja p a proposic¸a˜o ”Maria aprende matema´tica discreta”e q a proposic¸a˜o
”Maria vai conseguir um bom emprego”. Expresse p→ q em portugueˆs.
• Soluc¸a˜o: ”Se Maria aprender matema´tica discreta, enta˜o ela vai conseguir um
bom emprego.”
Prof. Ce´sar Francisco de Moura Couto 7& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Quando que as condicionais abaixo sa˜o verdadeiras?
– ”Se hoje esta´ ensolarado, enta˜o vou a` praia.”
– ”Se hoje e´ sexta-feira, enta˜o 2 + 3 = 5.”
– ”Se hoje e´ sexta-feira, enta˜o 2 + 3 = 6.”
Condicional
p q p→ q
V V V
V F F
F V V
F F V
Prof. Ce´sar Francisco de Moura Couto 8& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Oposta: A proposic¸a˜o q → p e´ chamada de oposta a p→ q.
• Inversa: A proposic¸a˜o ¬p→ ¬q e´ chamada de inversa de p→ q.
• Contrapositiva: A proposic¸a˜o ¬q → ¬p e´ chamada de contrapositiva de
p→ q.
• Qual e´ a contrapositiva, a oposta e a inversa da proposic¸a˜o condicional ”Se esta´
chovendo, enta˜o o time da casa ganha.”?
• Soluc¸a˜o:
– Contrapositiva: ”Se o time da casa na˜o ganha, enta˜o na˜o esta´ chovendo.”
– Oposta: ”Se o time da casa ganha, enta˜o esta´ chovendo.”
– Inversa: ”Se na˜o esta´ chovendo, enta˜o o time da casa na˜o ganha.”
• Contrapositiva e´ equivalente a` condicional.
Prof. Ce´sar Francisco de Moura Couto 9& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Definic¸a˜o 6: Sejam p e q proposic¸o˜es. A proposic¸a˜o bicondicional p↔ q e´ a
proposic¸a˜o ”p se e somente se q”. A bicondicional p↔ q e´ verdadeira sempre
que p e q tem o mesmo valor verdade e falsa caso contra´rio.
• Outras formas para expressar a condicional:
”p e´ necessa´ria e suficiente para q”
”se p enta˜o q e vice-versa”
”p sse q”
• Seja p a proposic¸a˜o ”Voceˆ pode tomar o avia˜o”e q a proposic¸a˜o ”Voceˆ
comprou uma passagem”.
• Enta˜o p↔ q e´ a proposic¸a˜o: ”Voceˆ pode tomar o avia˜o se e somente se voceˆ
comprou uma passagem”.
Prof. Ce´sar Francisco de Moura Couto 10& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Observe esta´ proposic¸a˜o: ”Se terminar o almoc¸o enta˜o voceˆ pode comer a
sobremesa”. E´ condicional ou bicondicional?
• Bicondicional. A linguagem natural e´ imprecisa.
Bicondicional
p q p↔ q
V V V
V F F
F V F
F F V
Prof. Ce´sar Francisco de Moura Couto 11& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Como podemos traduzir esta sentenc¸a do portugueˆs para expresso˜es lo´gicas?
”Voceˆ pode acessar a Internet a partir deste campus somente se voceˆ e´ um
expert em cieˆncia da computac¸a˜o ou na˜o e´ um novato.”
• Soluc¸a˜o: a, c e f representam ”Voceˆ pode acessar a Internet a partir deste
campus”, ”Voceˆ e´ um expert em cieˆncia da computac¸a˜o”e ”Voceˆ e´ um novato”,
respectivamente.
• Assim podemos representar a sentenc¸a por: a↔ (c ∨ ¬f)
Prof. Ce´sar Francisco de Moura Couto 12& %
' $
CEFET-MG Lo´gica Proposicional
Lo´gica Proposicional
• Determine se o sistema de especificac¸o˜es e´ consistente:
– ”A mensagem de diagno´stico e´ armazenada no buffer ou e´ retransmitida.”
– ”A mensagem de diagno´stico na˜o e´ armazenada no buffer.”
– ”Se a mensagem de diagno´stico e´ armazenada no buffer, enta˜o ela e´
retransmitida.”
• Soluc¸a˜o: Seja p ”A mensagem de diagno´stico e´ armazenada no buffer”e q ”A
mensagem de diagno´stico e´ retransmitida”. As especificac¸o˜es podem ser escritas
com p ∨ q, ¬p e p→ q. Consistente, por queˆ?
• O sistema de especificac¸a˜o continua consistente se for adicionado a
especificac¸a˜o ”A mensagem de diagno´stico na˜o e´ retransmitida.”?
Prof. Ce´sar Francisco de Moura Couto 13& %