Lógica Computacional: Introdução e Princípios

Prévia do material em texto

Lógica Computacional
Diego Silveira Costa Nascimento
Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Norte
diego.nascimento@ifrn.edu.br
25 de julho de 2016
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 2 / 101
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 3 / 101
Motivações
O estudo desta disciplina faz o aluno adquirir ou aperfeiçoar seu raciocínio
lógico no intuito de desenvolverem programas e sistemas em uma
determinada linguagem de programação.
A Lógica é apresentada como uma técnica eficiente para:
a organização de conhecimentos em qualquer área;
raciocinar corretamente sem esforço consciente;
interpretar e analisar informações rapidamente;
aumentar a competência linguística (oral e escrita);
adquirir destreza com o raciocínio quantitativo; e
detectar padrões em estruturas (premissas, pressuposições, cenários,
etc.)
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 4 / 101
Lógica
Definição
É a ciência das leis ideais do pensamento e a arte de aplicá-las à pesquisa e
à demonstração da verdade.
Deriva do Grego (logos); e
Significa:
palavra;
pensamento;
ideia;
argumento;
relato;
razão
lógica; ou
princípio lógico.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 5 / 101
Origem da Lógica
A Lógica teve início na Grécia em 342 a.C.;
Aristóteles sistematizou os conhecimentos existentes em Lógica,
elevando-a à categoria de ciência;
Obra chamada Organon (Ferramenta para o correto pensar);
Aristóteles preocupava-se com as formas de raciocínio que, a partir de
conhecimentos considerados verdadeiros, permitiam obter novos
conhecimentos; e
A partir dos conhecimentos tidos como verdadeiros, caberia à Lógica a
formulação de leis gerais de encadeamentos lógicos que levariam à
descoberta de novas verdades.
Aristóteles Organon
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 6 / 101
Argumento Lógico
Em Lógica, o encadeamento de conceitos é chamado de argumento;
As afirmações de um argumento são chamadas de proposições;
Um argumento é um conjunto de proposições tal que se afirme que
uma delas é derivada das demais;
Usualmente, a proposição derivada é chamada de conclusão, e as
demais, de premissas; e
Em um argumento válido, as premissas são consideradas provas
evidentes da verdade da conclusão.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 7 / 101
Exemplo de Argumento
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 8 / 101
Princípios Lógicos
A Lógica Formal repousa sobre três princípios fundamentais que permitem
todo seu desenvolvimento posterior, e que dão validade a todos os atos do
pensamento e do raciocínio. São eles:
Princípio da Identidade
Afirma A = A e não pode ser B , o que é, é;
Princípio da Não Contradição
A = A e nunca pode ser não-A, o que é, é e não pode ser sua
negação, ou seja, o ser é, o não ser não é; e
Princípio do Terceiro Excluído
Afirma que Ou A é x ou A é y , não existe uma terceira possibilidade.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 9 / 101
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 10 / 101
Proposição
Chama-se proposição todo o conjunto de palavras ou símbolos que
exprimem um pensamento de sentido completo;
As proposições transmitem pensamentos; e
Afirmam fatos ou exprimem juízos que formamos a respeito de
determinados entes.
Exemplos
A Lua é um satélite da Terra;
Sócrates é um homem;
Eu estudo Lógica; ou
Não está chovendo.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 11 / 101
A Linguagem da Lógica Proposicional
Considere o conjunto de símbolos:
A = {(, ),¬,∧,∨,→,↔, p, q, r , s, . . .}
A esse conjunto é chamado de alfabeto da Lógica Proposicional;
As letras são símbolos não lógico (letras sentenciais); e
O restante são símbolos lógicos (parênteses e conectivos lógicos);
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 12 / 101
Letras Sentenciais
As letras sentenciais são usadas para representar proposições elementares
ou atômicas, isto é, proposições que não possuem partes que sejam
também proposições.
Exemplos
p = O céu é azul;
Q = Eu estudo lógica;
r = 2 + 2 = 4; ou
s = Sócrates é um homem.
Importante
As partes dessas proposições não são proposições mais simples, mas sim,
componentes subsentenciais: expressões, palavras, sílabas ou letras.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 13 / 101
Conectivos Lógicos
As proposições compostas são obtidas combinando proposições
simples através de certos termos chamados conectivos;
A Lógica dispõe de cinco tipos de conectivos e seus operadores:
Não (Negação), ¬ ;
E (Conjunção), ∧;
Ou (Disjunção), ∨;
Se – então (Condicional), →;e
Se e somente se (Bicondicional), ↔.
Exemplos
Não está chovendo;
Está chovendo e está ventando;
Está chovendo ou está nublado;
Se choveu, então está molhado; ou
Será aprovado se e somente se estudar.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 14 / 101
Operador de Negação: ¬
A característica peculiar da negação, tal como ela se apresenta na lógica
proposicional clássica, é que toda proposição submetida à operação de
negação resulta na sua contraditória.
Exemplo
p = Está chovendo.
Ler-se ¬p, como: “Não está chovendo.”
Importante
O fato expresso por uma proposição não pode ocorrer ao mesmo tempo e
sob o mesmo modo e circunstância que o fato expresso pela negação dessa
mesma proposição.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 15 / 101
Tabela Verdade: ¬
Se p é uma proposição, a expressão ¬p é chamada negação de p; e
Claramente, a negação inverte o valor verdade de uma expressão.
Exemplo
p ¬p
V F
F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 16 / 101
Operador de Conjunção: ∧
A característica peculiar da conjunção está no fato de fórmulas conjuntivas
expressarem a concomitância de fatos. A fórmula (p ∧ q) expressa que o
fato expresso por p ocorre ao mesmo tempo que o fato expresso por q.
Exemplo
p = Está chovendo.
q = Está ventando.
Ler-se p ∧ q, como: “Está chovendo e está ventando.”
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 17 / 101
Tabela Verdade: ∧
Se p e q são proposições, a expressão p ∧ q é chamada conjunção de p
e q; e
As proposições p e q são chamadas fatores da expressão.
Exemplo
p q p∧q
V V V
V F F
F V F
F F F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 18 / 101
Operador de Disjunção: ∨
A característica peculiar da disjunção consiste no fato de proposições
disjuntivas expressarem que pelo menos um de dois fatos ocorre. A fórmula
(p ∨ q) expressa que, dentre os fatos expressos por p e q respectivamente,
pelo menos um deles ocorre.
Exemplo
p = Está nublado.
q = Está chovendo.
Ler-se p ∨ q, como: “Está nublado ou está chovendo.”
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 19 / 101
Tabela Verdade: ∨
Se p e q são proposições, a expressão p ∨ q é chamada disjunção
inclusiva de p e q; e
As proposições p e q são chamadas parcelas da expressão.
Exemplo
p q p∨q
V V V
V F VF V V
F F F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 20 / 101
Operador Condicional: →
A característica peculiar dessa operação consiste em que um condicional
(p → q) expressa que a ocorrência do fato expresso por p garante
necessariamente a ocorrência do fato expresso por q.
Exemplo
p = Choveu.
q = Está molhado.
Ler-se p → q, como: “Se choveu, então está molhado.”
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 21 / 101
Tabela Verdade: →
Se p e q são proposições, a expressão p → q é chamada condicional
de p e q;
A proposição p é chamada antecedente, e a proposição q consequente
da condicional; e
A operação de condicionamento indica que o acontecimento de p é
uma condição para que q aconteça.
Exemplo
p q p→q
V V V
V F F
F V V
F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 22 / 101
Operador Bicondicional: ↔
A característica peculiar dessa operação consiste em que um bicondicional
(p ↔ q) assevera que os fatos expressos por p e q são interdependentes,
isto é, ou os dois ocorrem juntos ou nenhum dos dois ocorrem.
Exemplo
p = Será aprovado.
q = Estudar.
Ler-se p ↔ q, como: “ Será aprovado, se e somente se estudar.”
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 23 / 101
Tabela Verdade: ↔
Se p e q são proposições, a expressão p ↔ q é chamada bicondicional
de p e q; e
A operação de bicondicionamento indica que p é uma condição para
que q aconteça, e vice-versa.
Exemplo
p q p↔q
V V V
V F F
F V F
F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 24 / 101
Parênteses: (e)
A necessidade de usar parênteses na simbolização das proposições se deve
ao fato de se evitar qualquer tipo de ambiguidade.
Exemplo
p = Estudar.
q = Fazer a prova.
r = Fazer o trabalho.
s = Serei aprovado.
Ler-se ((p ∧ q) ∨ r)→ s, como:
“ Se ((estudar e fazer a prova) ou fazer o trabalho), então será aprovado.”
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 25 / 101
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 26 / 101
Tabela-verdade de uma Proposição Composta
Dadas várias proposições simples p, q, r , . . ., podemos combiná-las pelos
operadores lógicos ∧,∨,→,↔ e construir proposições compostas:
Exemplo
P(p, q) = ¬p ∨ (p → q)
Q(p, q) = (p ↔ ¬q) ∧ q
R(p, q, r) = (p → ¬q ∨ r) ∧ ¬(q ∨ (p ↔ ¬r))
Então, com o emprego das tabelas-verdade das operações lógicas
fundamentais já estudadas: ¬p, p ∧ q, p ∨ q, p → q e p ↔ q;
É possível construir a tabela-verdade correspondente a qualquer
proposição composta; e
A tabela-verdade exibirá exatamente os casos em que a proposição
composta será verdadeira (V ) ou falsa (F ), admitindo-se que o seu
valor lógico só depende dos valores lógicos das proposições simples.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 27 / 101
Ordem de Precedência dos Operadores
1 Percorra a expressão da esquerda para a direita, executando as
operações de negação, na ordem em que aparecerem;
2 Percorra novamente a expressão, da esquerda para a direita,
executando as operações de conjunção e disjunção, na ordem em que
aparecerem;
3 Percorra outra vez a expressão, da esquerda para a direita, executando
desta vez as operações de condicionamento, na ordem em que
aparecerem; e
4 Percorra uma última vez a expressão, da esquerda para a direita,
executando as operações de bicondicionamento, na ordem em que
aparecerem.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 28 / 101
Construindo a Tabela-verdade
Dada uma expressão proposicional composta, e dados os valores lógicos das
proposições simples que a compõe, podemos, com a ordem de precedência,
calcular o valor lógico da expressão dada.
Expressão Proposicional Composta
P(p, q) = ¬(p ∧ ¬q)
Forma-se, em primeiro lugar, o par de colunas correspondentes às duas
proposições simples p e q. O total de linhas é igual a 2n, onde n
corresponde ao número de proposições simples.
Exemplo
p q
V V
V F
F V
F F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 29 / 101
Construindo a Tabela-verdade (cont.)
Em seguida, forma-se a coluna para ¬q.
Exemplo
p q ¬q
V V F
V F V
F V F
F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 30 / 101
Construindo a Tabela-verdade (cont.)
Depois, forma-se a coluna para p ∧ ¬q.
Exemplo
p q ¬q p∧¬q
V V F F
V F V V
F V F F
F F V F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 31 / 101
Construindo a Tabela-verdade (cont.)
Por fim, forma-se a coluna relativa aos valores lógicos da proposição
composta ¬(p ∧ ¬q).
Exemplo
p q ¬q p∧¬q ¬(p∧¬q)
V V F F V
V F V V F
F V F F V
F F V F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 32 / 101
Tautologia
Definição
Tautologia é toda proposição composta P(p, q, r , . . .) cujo valor lógico é
sempre verdadeiro, quaisquer que sejam os valores lógicos das proposições
simples p, q, r , . . .
As tautologias são também denominadas proposições tautológicas ou
proposições logicamente verdadeiras.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 33 / 101
Tautologia: Demonstração I
Proposição
¬(p ∧ ¬p)
Exemplo
p ¬p p∧¬p ¬( p∧¬p)
V F F V
F V F V
Portanto, dizer que uma proposição não pode ser simultaneamente
verdadeira e falsa é sempre verdadeiro.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 34 / 101
Tautologia: Demonstração II
Proposição
p ∨ ¬p
Exemplo
p ¬p p∨¬p
V F V
F V V
Portanto, dizer que uma proposição ou é verdadeira ou é falsa é sempre
verdadeiro.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 35 / 101
Contradição
Definição
Contradição é toda proposição composta P(p, q, r , . . .) cujo valor lógico é
sempre falso, quais quer que sejam os valores lógicos das proposições
simples p, q, r , . . .
As contradições são também denominadas proposições contraválidas ou
proposições logicamente falsas.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 36 / 101
Contradição: Demonstração I
Proposição
p ∧ ¬p
Exemplo
p ¬p p∧¬p
V F F
F V F
Portanto, dizer que uma proposição pode ser simultaneamente verdadeira e
falsa é sempre falso.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 37 / 101
Contradição: Demonstração II
Proposição
p ↔ ¬p
Exemplo
p ¬p p↔ ¬p
V F F
F V F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 38 / 101
Contingência
Definição
Contingencia é toda a proposição composta que não é tautologia nem
contradição.
As contingências são também denominadas proposições contingentes ou
proposições indeterminadas.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 39 / 101
Contingência: Demonstração I
Proposição
p → ¬p
Exemplo
p ¬p p→ ¬p
V F F
F V V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 40 / 101
Contingência: Demonstração II
Proposição
p ∨ q → p
Exemplo
p q p∨q p∨q → p
V V V V
V F V V
F V V F
F F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 41 / 101
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 42 / 101
Implicação Lógica
Definição
Diz-se que uma proposição P(p, q, r , . . .) implica logicamente uma
proposição Q(p, q, r , . . .), se Q(p, q, r , . ..) é verdadeiro todas as vezes em
que P(p, q, r , . . .) é verdadeiro.
Notação
P(p, q, r , . . .)⇒ Q(p, q, r , . . .)
Importante
Em particular, toda proposição implica uma tautologia e somente uma
contradição implica uma contradição.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 43 / 101
Propriedades da Implicação Lógica
É imediato que a relação de implicação lógica entre proposições utiliza-se
das propriedades reflexiva (R) e transitiva (T).
Exemplo
(R) P(p, q, r , . . .)⇒ P(p, q, r , . . .)
(T) Se P(p, q, r , . . .)⇒ Q(p, q, r , . . .) e
Q(p, q, r , . . .)⇒ R(p, q, r , . . .), então
P(p, q, r , . . .)⇒ R(p, q, r , . . .)
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 44 / 101
Demonstração de Implicação Lógica I
Proposições
p ∧ q, p ∨ q e p ↔ q
Exemplo
p q p∧q p∨q p↔q
V V V V V
V F F V F
F V F V F
F F F F V
A proposição p ∧ q é verdadeira somente na linha 1, e nesta linha, as
proposições p ∨ q e p ↔ q também são verdadeiras. Logo, a primeira
proposição implica cada uma das outras duas proposições, isto é:
p ∧ q ⇒ p ∨ q e p ∧ q ⇒ p ↔ q
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 45 / 101
Demonstração de Implicação Lógica II
Proposições
p ↔ q, p → q e q → p
Exemplo
p q p↔q p→q q→p
V V V V V
V F F F V
F V F V F
F F V V V
A proposição p ↔ q é verdadeira nas linhas 1 e 4 e, nestas linhas,
proposições p → q e q → p também são verdadeiras. Logo, a primeira
proposição implica cada uma das outras duas proposições, isto é:
p ↔ q ⇒ p → q e p ↔ q ⇒ q → p
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 46 / 101
Tautologias e Implicação Lógica
Teorema
A proposição P(p, q, r , . . .) implica a proposição Q(p, q, r , . . .) isto é:
P(p, q, r , . . .)⇒ Q(p, q, r , . . .)
se e somente se a condicional:
P(p, q, r , . . .)→ Q(p, q, r , . . .)
é tautológica.
Importante
Os símbolos → e ⇒ são distintos, pois o primeiro é de operação lógica
(aplicado, por ex., às proposições p e q dá a nova proposição p → q),
enquanto que o segundo é de relação (estabelece que a condicional
P(p, q, r , . . .)→ Q(p, q, r , . . .) é tautológica).
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 47 / 101
Demonstração de Tautologia e Implicação Lógica
Condicional
(p → q) ∧ p → q
Exemplo
p q p→q (p→q)∧ p (p→q)∧ p → q
V V V V V
V F F F V
F V F F V
F F V F V
Portanto, simbolicamente: (p → q) ∧ p ⇒ q
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 48 / 101
Equivalência Lógica
Definição
Diz-se que uma proposição P(p, q, r , . . .) é logicamente equivalente a uma
proposição Q(p, q, r , . . .), se as tabelas-verdade destas duas proposições
são idênticas.
Notação
P(p, q, r , . . .)⇔ Q(p, q, r , . . .)
Importante
Em particular, se as proposições P(p, q, r , . . .) e Q(p, q, r , . . .) são ambas
tautológicas ou são ambas contradições, então são equivalentes.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 49 / 101
Propriedades da Equivalência Lógica
É imediato que a relação de equivalência lógica entre proposições utiliza-se
das propriedades reflexiva(R), simétrica (S) e transitiva (T), isto é,
simbolicamente:
Exemplo
(R) P(p, q, r , . . .)⇔ P(p, q, r , . . .)
(S) Se P(p, q, r , . . .)⇔ Q(p, q, r , . . .), então
Q(p, q, r , . . .)⇔ P(p, q, r , . . .)
(T) Se P(p, q, r , . . .)⇔ Q(p, q, r , . . .) e
Q(p, q, r , . . .)⇔ R(p, q, r , . . .), então
P(p, q, r , . . .)⇔ R(p, q, r , . . .)
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 50 / 101
Demonstração de Equivalência Lógica I
Proposições
¬p → p e p
Exemplo
p ¬p ¬p→p
V F V
F V F
A proposição ¬p → p e p são equivalentes nas colunas 1 e 2, isto é:
¬p → p ⇔ p
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 51 / 101
Demonstração de Equivalência Lógica II
Proposições
p → p ∧ q e p → q
Exemplo
p q p∧q p→p∧q p→q
V V V V V
V F F F F
F V F V V
F F F V V
A proposição p → p ∧ q e p → q são equivalentes nas colunas 4 e 5, isto é:
p → p ∧ q ⇔ p → q
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 52 / 101
Tautologias e Equivalência Lógica
Teorema
A proposição P(p, q, r , . . .) é equivalente à proposição Q(p, q, r , . . .), isto é:
P(p, q, r , . . .)⇔ Q(p, q, r , . . .)
se e somente se a bicondicional:
P(p, q, r , . . .)↔ Q(p, q, r , . . .)
é tautológica.
Importante
Os símbolos ↔ e ⇔ são distintos, pois o primeiro é de operação lógica
(aplicado, por ex., às proposições p e q dá a nova proposição p ↔ q),
enquanto que o segundo é de relação (estabelece que a bicondicional
P(p, q, r , . . .)⇔ Q(p, q, r , . . .) é tautológica).
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 53 / 101
Demonstração de Equivalência Lógica
Proposições
(p ∧ ¬q → c) e (p → q)
Exemplo
p q c p∧¬q p∧¬q→c p→q (p∧¬q→c) ↔ (p→q)
V V F F V V V
V F F V F F V
F V F F V V V
F F F F V V V
...
...
...
...
...
...
...
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 54 / 101
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 55 / 101
Dedução
Definição
Dado um argumento P1,P2 e P3 → Q chama-se demonstração ou
dedução de Q a partir das premissas P1,P2, . . .Pn, a sequência finita de
proposições X1,X2, . . .Xm, tal que cada Xi ou é uma premissa ou decorre
logicamente de proposições anteriores da sequência, e de tal modo que a
última proposição Xm seja a conclusão Q do argumento dado.
Desta forma, se for possível obter a conclusão Q através do procedimento
de dedução, o argumento é válido, caso contrário, não é válido.
O método dedutivo é mais eficente para demonstração de implicações e
equivalências lógicas do que quando utiliza-se de tabelas-verdade.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 56 / 101
Álgebra das Proposições
Propriedades da Conjunção;
Propriedades da Disjunção;
Propriedades da Conjunção e Disjunção;
Negação da Condicional; e
Negação da Bicondicional.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 57 / 101
Propriedades da Conjunção
Seja p, q e r proposições simples quaisquer e sejam t e c proposições
também simples cujos valores lógicos respectivos são verdadeiro e falso,
temos as propriedades a seguir: idempotente, comutativa, associativa e
identidade.
Idempotente
p ∧ p ⇔ p
Exemplo
p p∧p p∧p↔p
V V V
F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 58 / 101
Propriedades da Conjunção (cont.)
Comutativa
p ∧ q ⇔ q ∧ p
Exemplo
p q p∧q q∧p p∧q↔q∧p
V V V V V
V F F F V
F V F F V
F F F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 59 / 101
Propriedades da Conjunção (cont.)
Associativa
(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
Exemplo
p q r p∧q (p∧q)∧r q∧r p∧(q∧r)
V V V V V V V
V V F V F F F
V F V F F F F
V F F F F F F
F V V F F V F
F V F F F F F
F F V F F F F
F F F F F F F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 60 / 101
Propriedades da Conjunção (cont.)
Identidade
p ∧ t ⇔ p e p ∧ c ⇔ c
Exemplo
p t c p∧t p∧c p∧t↔p p∧c↔c
V V F V F V V
F V F F F V V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 61 / 101
Propriedades da Disjunção
Seja p, q e r proposições simples quaisquer e sejam t e c proposições
também simples cujos valores lógicos respectivos são verdadeiro e falso,
temos as propriedades a seguir: idempotente, comutativa, associativa e
identidade.
Idempotente
p ∨ p ⇔ p
Exemplo
p p∨p p∨p↔p
V V V
F F V
Diego S. C. Nascimento (IFRN) Lógica ComputacionalApresentação 62 / 101
Propriedades da Disjunção (cont.)
Comutativa
p ∨ q ⇔ q ∨ p
Exemplo
p q p∨q q∨p p∨q↔q∨p
V V V V V
V F V V V
F V V V V
F F F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 63 / 101
Propriedades da Disjunção (cont.)
Associativa
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)
Exemplo
p q r p∨q (p∨q)∨r q∨r p∨(q∨r)
V V V V V V V
V V F V V V V
V F V V V V V
V F F V V F V
F V V V V V V
F V F V V V V
F F V F V V V
F F F F F F F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 64 / 101
Propriedades da Disjunção (cont.)
Identidade
p ∨ t ⇔ t e p ∨ c ⇔ p
Exemplo
p t c p∨t p∨c p∨t↔t p∨c↔p
V V F V V V V
F V F V F V V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 65 / 101
Propriedades da Conjunção e Disjunção
Seja p, q e r proposições simples quaisquer, podemos representar as
propriedades: distributiva, absorção e regras De Morgan.
Distributiva
p ∧ (q ∨ r)⇔ (p ∧ q) ∨ (p ∧ r) e p ∨ (q ∧ r)⇔ (p ∨ q) ∧ (p ∨ r)
Exemplo
p q r q∨r p∧(q∨r) p∧q p∧r (p∧q) ∨ (p∧r)
V V V V V V V V
V V F V V V F V
V F V V V F V V
V F F F F F F F
F V V V F F F F
F V F V F F F F
F F V V F F F F
F F F F F F F F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 66 / 101
Propriedades da Conjunção e Disjunção (cont.)
Absorção
p ∧ (p ∨ q)⇔ p e p ∨ (p ∧ q)⇔ p
Exemplo
p q p∨q p∧(p∨q) p∧(p∨q)↔p
V V V V V
V F V V V
F V V F V
F F F F V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 67 / 101
Propriedades da Conjunção e Disjunção (cont.)
Regras De Morgan (1806–1871)
¬(p ∧ q)⇔ ¬p ∨ ¬q e ¬(p ∨ q)⇔ ¬p ∧ ¬q
Exemplo
p q p∧q ¬(p∧q) ¬p ¬q ¬p∨¬q
V V V F F F F
V F F V F V V
F V F V V F V
F F F V V V V
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 68 / 101
Negação da Condicional
Demonstração
Como p → q ⇔ ¬p ∨ q, temos:
¬(p → q)⇔ ¬(¬p ∨ q)⇔ ¬¬p ∧ ¬q
ou seja:
¬(p → q)⇔ p ∧ ¬q
Exemplo
p q p→q ¬(p→q) ¬q p∧¬q
V V V F F F
V F F V V V
F V V F F F
F F V F V F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 69 / 101
Negação da Bicondicional
Demonstração
Como p ↔ q ⇔ (p → q) ∧ (q → p), temos:
p ↔ q ⇔ (¬p ∨ q) ∧ (¬q ∨ p)
e portanto:
¬(p ↔ q)⇔ ¬(¬p ∨ q) ∨ ¬(¬q ∨ p)⇔ (¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p)
ou seja:
¬(p ↔ q)⇔ (p ∧ ¬q) ∨ (¬p ∧ q)
Exemplo
p q ¬p ¬q p∧¬q ¬p∧q (p∧¬q) ∨ (¬p∧q) p↔q ¬(p↔q)
V V F F F F F V F
V F F V V F V F V
F V V F F V V F V
F F V V F F F V F
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 70 / 101
Demonstração da Implicação I
Implicação
p ∧ q ⇒ p
Exemplo
p ∧ q → p ⇔
¬(p ∧ q) ∨ p ⇔
(¬p ∨ ¬q) ∨ p ⇔
(¬p ∨ p) ∨ ¬q ⇔
Tautologia ∨¬q ⇔
Tautologia
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 71 / 101
Demonstração da Implicação II
Implicação
(p → q) ∧ p ⇒ q
Exemplo
((p → q) ∧ p)→ q ⇔
¬((p → q) ∧ p) ∨ q ⇔
(¬(p → q) ∨ ¬p) ∨ q ⇔
(¬(¬p ∨ q) ∨ ¬p) ∨ q ⇔
((¬¬p ∧ ¬q) ∨ ¬p) ∨ q ⇔
((p ∧ ¬q) ∨ ¬p) ∨ q ⇔
((¬p ∨ p) ∧ (¬p ∨ ¬q)) ∨ q ⇔
(Tautologia ∧ (¬p ∨ ¬q)) ∨ q ⇔
(¬p ∨ ¬q) ∨ q ⇔
¬p ∨ (¬q ∨ q)⇔
¬p ∨ Tautologia⇔ Tautologia
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 72 / 101
Demonstração da Equivalência I
Equivalência
p → q ⇔ p ∨ q → q
Exemplo
p ∨ q → q ⇔
¬(p ∨ q) ∨ q ⇔
(¬p ∧ ¬q) ∨ q ⇔
(¬p ∨ q) ∧ (¬q ∨ q)⇔
(¬p ∨ q) ∧ Tautologia ⇔
p → q
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 73 / 101
Demonstração da Equivalência II
Equivalência
(p → q) ∧ (p → ¬q)⇔ ¬p
Exemplo
(¬p ∨ q) ∧ (¬p ∨ ¬q)⇔
¬p ∨ (q ∧ ¬q)⇔
¬p∨ Contradição ⇔
¬p
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 74 / 101
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 75 / 101
Inferência
Definição
É o processo pelo qual se chega a uma proposição, firmada na base de uma
ou outras mais proposições aceitas como ponto de partida do processo.
Um método mais eficiente para demonstrar, verificar ou testar a
validade de um dado argumento P1,P2, . . . ,Pn ` Q consiste em deduzir
a conclusão Q a partir das premissas P1,P2, . . . ,Pn mediante o uso de
certas regras de inferência.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 76 / 101
Regras de Inferência
Regra de Adição (AD);
Regra de Simplificação (SIMP);
Regra da Conjunção (CONJ);
Regra de Absorção (ABS);
Regra Modus ponens (MP);
Regra Modus tollens (MT);
Regra do Silogismo disjuntivo (SD);
Regra do Silogismo hipotético (SH);
Regra do Dilema construtivo (DC); e
Regra do Dilema destrutivo (DD).
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 77 / 101
Regra da Adição
Definição
Dada uma proposição p, dela se pode deduzir a sua disjunção com
qualquer outra proposição, isto é, deduzir p ∨ q, ou p ∨ r , etc.
Exemplo
p
p ∨ q
p
q ∨ p
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 78 / 101
Regra de Simplificação
Definição
Da conjunção p ∧ q de duas proposições se pode deduzir cada uma das
proposições, p ou q.
Exemplo
p ∧ q
p
p ∧ q
q
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 79 / 101
Regra da Conjunção
Definição
Permite deduzir de duas proposições dadas p e q (premissas) a sua
conjunção p ∧ q ou q ∧ p (conclusão).
Exemplo
p
q
p ∧ q
p
q
q ∧ p
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 80 / 101
Regra da Absorção
Definição
Está regra permite, dada uma condicional p → q como premissa, dela
deduzir como conclusão uma outra condicional com o mesmo antecedente
p e cujo consequente é a conjunção p ∧ q das duas proposições que
integram a premissa, isto é, p → p ∧ q.
Exemplo
p → q
p → (p ∧ q)
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 81 / 101
Regra Modus Ponens
Definição
Também é chamada Regra de Separação e permite deduzir q
(conclusão) a partir de p → q e p (premissas).
Exemplo
p → q
p
q
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 82 / 101
Regra Modus Tollens
Definição
Permite, a partir das premissas p → q (condicional) e ¬q (negação do
consequente), deduzir como conclusão ¬p (negação do antecedente).
Exemplo
p → q
¬q
¬p
p → ¬q
q
¬p
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 83 / 101
Regra do Silogismo Disjuntivo
Definição
Permite 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).
Exemplo
p ∨ q
¬p
q
p ∨ q
¬q
p
¬p ∨ q
p
q
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 84 / 101
Regra do Silogismo Hipotético
Definição
Esta regra permite, dada duas condicionais: p → q e q → r (premissas),
tais que o consequente da primeira coincide com o antecedente da segunda,
deduzir uma terceira condicional p → r (conclusão) cujo antecedente e
consequente são respectivamente o antecedente da premissa p → q e o
consequente da outra premissa q → r .
Exemplo
p → q
q → r
p → r
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 85 / 101
Regra do Dilema Construtivo
Definição
Nesta regra, as premissas são duas condicionais e a disjunção dos seus
antecedentes, e a conclusão é a disjunção dos consequentes destas
condicionais.
Exemplo
p → q
r → s
p ∨ r
q ∨ s
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 86 / 101
Regra do Dilema Destrutivo
Definição
Nesta regra, as premissas são duas condicionais e a disjunção da negação
dos seus consequentes, e a conclusão é a disjunção da negação dos
antecedentes destas condicionais.
Exemplo
p → q
r → s
¬q∨ ¬s
¬p ∨ ¬r
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 87 / 101
Validade Mediante Regras de Inferência I
Argumento
p → q, p ∧ r ` q
Exemplo
(1) p → q
(2) p ∧ r
(3) p 2 – SIMP
(4) q 1,3 – MP
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 88 / 101
Validade Mediante Regras de Inferência II
Argumento
p ∧ q, p ∨ r → s ` p ∧ s
Exemplo
(1) p ∧ q
(2) p ∨ r → s
(3) p 1 – SIMP
(4) p ∨ r 3 – AD
(5) s 2,4 – MP
(6) p ∧ s 3,5 – CONJ
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 89 / 101
Ementa do Curso
1 Introdução
2 Lógica Proposicional
3 Construção de Tabelas-verdade
4 Implicação e Equivalência Lógica
5 Método Dedutivo
6 Inferência Lógica
7 Lógica de Predicados
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 90 / 101
Termo e Predicado
Na Lógica Proposicional as interpretações não dependem da estrutura
interna de suas proposições, mas unicamente no modo como se
combinam;
Já lógica de Predicados, dada uma proposição simples qualquer, pode
destacar dela dois entes:
Termo; e
Predicado.
O termo pode ser entendido como o sujeito da sentença declarativa; e
O predicado é uma declaração a respeito do termo.
Exemplos
Sócrates é mortal
Termo: Sócrates
Predicado: é mortal
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 91 / 101
Função Proposicional
Seja T um conjunto de termos, uma função proposicional em T é um
predicado p associado a um termo x , p(x);
A expressão p(a) é verdadeira só e somente se a ∈ T ; e
Nas funções proposicionais, os termos são variáveis, enquanto que as
proposições são constantes.
Exemplos
Seja o conjunto Z = {1, 2, 3, 4, . . . }, são funções proposicionais:
par(x)
primo(x)
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 92 / 101
Quantificadores
Definição
São operadores lógicos que restringem as funções proposicionais, de forma
que elas se refiram a todo um conjunto de termos T , ou parte dele.
Há dois tipos de quantificadores:
Universal: ∀; e
Existencial: ∃.
Exemplos
∀x(matematica(x)), ler-se: Tudo é matemática.
¬∃x(homem(x) ∧ infiel(x)), ler-se: Não existe homem infiel.
∀x(homem(x)→ mortal(x)), ler-se: Todos os homens são mortais.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 93 / 101
Negação dos Quantificadores
Se usarmos a para representar um predicado associado aos termos de um
conjunto T , as seguintes equivalências se verificam:
¬∀x(p(a))⇔ ∃x¬(p(a))
¬∃x(p(a))⇔ ∀x¬(p(a)).
Importante
As equivalências já estudada no cálculo proposicional podem ser usadas nas
funções proposicionais.
Exemplo
Não existe baleia que seja réptil
¬∃x(baleia(x) ∧ reptil(x))⇔ ∀x¬(baleia(x) ∧ reptil(x))⇔
∀x(¬baleia(x) ∨ ¬reptil(x))⇔ ∀x(baleia(x)→ ¬reptil(x))
Todas as baleias não são répteis.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 94 / 101
Validade de Argumentos com Quantificadores
É possível provar a validade de argumentos que envolva proposições
quantificadas;
Para isso, é necessário transformar os argumentos com quantificadores
em argumentos não quantificados, por meio de exemplificações;
Em seguida, aplicar as regras de inferências lógicas já estudadas; e
Por fim, uma vez concluída a prova de validade do argumento, usa-se
a generalização para obter a conclusão do argumento quantificado.
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 95 / 101
Exemplificação Existencial
Definição
Dado um conjunto de termos T e um predicado qualquer p. Se existe um
termo associado ao predicado p, estipulamos que tal termo seja c .
Exemplo
∃x(p(x))
p(c)
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 96 / 101
Exemplificação Universal
Definição
Dado um conjunto de termos T e um predicado qualquer p. Se todos os
termos são associado ao predicado p, escolhemos um deles, c , um termo
constante.
Exemplo
∀x(p(x))
p(c)
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 97 / 101
Generalização Existencial
Definição
Dado um conjunto de termos T e um predicado qualquer p. Se concluímos
que um termo c constante está associado ao predicado p, então existe um
termo associado a p.
Exemplo
p(c)
∃x(p(x))
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 98 / 101
Generalização Universal
Definição
Dado um conjunto de termos T e um predicado qualquer p. Se o termo c
tomado na exemplificação pode ser qualquer um, ou seja, pode ser tomado
aleatoriamente, então qualquer termo está associado ao predicado p.
Exemplo
p(c)
∀x(p(x))
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 99 / 101
Validade Mediante Regras de Inferência I
Argumento
Todos os jogadores são atletas.
Todos os atletas sofrem contusões.
Logo, todos os jogadores sofrem contusões.
Exemplo
(1) ∀x(jogador(x)→ atleta(x))
(2) ∀x(Atleta(x)→ contusao(x))
(3) jogador(Zico)→ atleta(Zico) 1 – EU
(4) Atleta(Zico)→ contusao(Zico) 2 – EU
(5) jogador(Zico)→ contusao(Zico) 3,4 – SH
(6) ∀x(jogador(x)→ contusao(x)) 5 – GU
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 100 / 101
Validade Mediante Regras de Inferência II
Argumento
Todos que estavam doentes foram medicados.
Alguns não foram medicados.
Logo, nem todos estavam doentes.
Exemplo
(1) ∀x(doente(x)→ medicado(x))
(2) ∃x¬(medicado(x))
(3) doente(Pedro)→ medicado(Pedro) 1 – EU
(4) ¬medicado(Pedro) 2 – EE
(5) ¬doente(Pedro) 3,4 – MT
(6) ¬∀x(doente(x))
Diego S. C. Nascimento (IFRN) Lógica Computacional Apresentação 101 / 101
	Introdução
	Lógica Proposicional
	Construção de Tabelas-verdade
	Implicação e Equivalência Lógica
	Método Dedutivo
	Inferência Lógica
	Lógica de Predicados