Semântica - Monteiro

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

6 - Semântica Página 89 
 
 
 
 
 
 
 
 
 
 
 
 
SEMÂNTICA 
 
 
 
 
Emissão: 02/5/2010 
Por: Luiz A. P. Monteiro 
Revisão: 25/5/2010 
Por: Maria E. M. Gonçalves 
 
6 
6 - Semântica Página 90 
 
 
 
 
 
 
6 – Semântica Página 91 
6.1 Introdução 
 
Se P : “Está chovendo” e Q = “A rua está molhada” � então P ∧ Q pode ou 
não ser verdadeira dependendo das condições climáticas 
 
Se P : “7 é maior do que 2” � então P é sempre verdadeira (não depende 
de nada) 
 
Já para P : “Esta sentença é falsa” � o resultado da interpretação da 
sentença não é verdadeiro nem falso, independente de qualquer outra 
coisa 
 
O símbolo sintático P define uma fórmula. E cada fórmula sintática está 
associada a um significado verdadeiro ou falso. 
 
 
 
 
 
 
 
 
 
Dessa maneira o mundo lógico é dividido em duas partes: 
• Mundo sintático – constituído pelos símbolos do alfabeto e as 
fórmulas. 
• Mundo semântico – onde se define o significado dos símbolos e 
fórmulas 
 
 
 
 
 
 
 
 
 
 
 
 
6.2 Interpretação 
 
Na Lógica Proposicional é possível representar fatos que podem ser 
interpretados como verdadeiros ou falsos. Assim, uma fórmula poderá ser 
verdadeira ou falsa dependendo dos diferentes significados semânticos 
de suas subfórmulas. É possível se ter: V(A) = 0 e I(A) = 1 (duas funções de 
valoração diferentes para a mesma subfórmula A) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Observação: 
O ato de programar pode 
ser entendido como uma 
tradução de um 
conhecimento semântico 
para um programa sintático 
que é manipulado por uma 
máquina. Assim, diz-se que 
a máquina é estritamente 
sintática. 
O computador é uma 
máquina estritamente 
sintática 
Fórmula 
 
1 
Símbolo 
Significado 
Fórmula 
 
1 
Símbolo 
Significado 
Mundo 
Semântico 
Mundo 
Sintático 
Para a lógica proposicional a semântica consiste em atribuir valores 
verdade às fórmulas da linguagem 
A semântica estuda o significado associado a cada fórmula/proposição 
(que é um objeto sintático). 
6 – Semântica Página 92 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplo: A: “1 + 1 = 10”. 
• Na interpretação do sistema de numeração de base 2, a 
proposição é verdadeira I(A)= 1 
• Na interpretação do sistema decimal a proposição é falsa V(A) = 0 
 
Pelo princípio da não contradição e princípio do terceiro excluído: 
 
 
 
 
O significado ou semântica dos elementos sintáticos da linguagem da 
Lógica Proposicional é determinado pela função denominada Função de 
Interpretação ou Valoração: 
V : P → {0, 1} ou V : P → {F, V} 
Onde: 
• Domínio de V � conjunto P das fórmulas 
• Contradomínio de V � conjunto {0, 1} tal que: 
- V(verdadeiro) = 1 ou V 
- V(falso) = 0 ou F 
 
V mapeia cada símbolo proposicional ou fórmula de P em um valor 
verdade (significado do símbolo). Logo, dado um símbolo proposicional P, 
então V(P) ∈ {0, 1} 
 
Assim, os valores de interpretação de uma fórmula são obtidos pela função 
V (de valoração) 
 
Para qualquer interpretação V, os valores V(verdadeiro) = 1 e V(falso) = 0 
� Todas as interpretações têm a mesma opinião sobre os significados 
dos símbolos de verdade. � 
 
 
 
 
 
 
6.3 Regras para Interpretação de Fórmulas 
 
Para que a fórmula (P ∧ Q) seja verdadeira, os significados de P e Q devem 
ser verdadeiros e o conectivo ∧ deve significar “e” � se V(P) = 1 e V(Q) = 1 
então V(P ∧ Q) = 1 
Toda proposição tem um, e um só, dos valores: ou Verdadeiro (V) ou 
Falso (F). 
A interpretação dos símbolos de verdade é fixa, ou seja: 
• Se A = verdadeiro � V(A) = 1 
• Se A = falso � V(A) = 0 
Observação: 
Na língua portuguesa é 
possível ter mais de dois 
significados diferentes para 
a mesma palavra (o que é 
diferente do contexto da 
Lógica Proposicional onde 
somente dois significados 
são possíveis) 
{0, 1} é uma limitação pois 
nem tudo pode ser 
interpretado como sendo 
verdadeiro ou falso. 
Para atribuir um valor verdade a uma fórmula, segundo as regras de 
interpretação é preciso: 
• atribuir um valor verdade para suas subfórmulas 
• depois compor o valor verdade da fórmula 
 
6 – Semântica Página 93 
A valoração de uma fórmula é feita por indução sobre a sua estrutura 
segundo as regras: 
 
 
 
 
 
 
 
 
 
 
 
 
 
As regras semânticas são apresentadas em tabelas da verdade 
p q ¬¬¬¬p p ∨ q p ∧∧∧∧ q p → q p ↔ q 
V V F V V V V 
V F F V F F F 
F V V V F V F 
F F V F F V V 
 
Observar que V(p → q) = V sse V(p) = F ou V(q) = V 
 
Exemplo 
Tabela verdade associada a uma fórmula 
H = ((¬P) ∨ Q) → (Q ∧ P) 
 
Colocando-se as subfórmulas de H 
 P Q ¬P ¬P ∨ Q Q ∧ P ¬P ∨ Q → Q ∧ P 
 
Escrevendo-se todas as possibilidades de V e F para os átomos: 
P Q ¬P ¬P ∨ Q Q ∧ P ¬P ∨ Q → Q ∧ P 
V V 
V F 
F V 
F F 
 
Resolvendo com a álgebra das proposições: 
P Q ¬P ¬P ∨ Q Q ∧ P ¬P ∨ Q → Q ∧ P 
V V F V V V 
V F F F F V 
F V V V F F 
F F V V F F 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Se A = P � V(A) = V(P) com V(P) ∈ {0, 1} 
Se A = verdadeiro � V(A) = 1 
Se A = falso � V(A) = 0 
V(¬A) = 1 se, e somente se V(A) = 0 o valor de V(¬A) é oposto ao valor de V(A) 
V(A ∧ B) = 1 sse V(A) = 1 e V(B) = 1 o valor de V(A ∨ B) é 1 sse as interpretações de A e B 
são iguais a 1 
V(A ∨ B) = 1 sse V(A) = 1 ou V(B) = 1 o valor de V(A ∨ B) é 1 sse as interpretações de A e B 
são iguais a 1 ou apenas uma delas é igual a 1 
V(A → B) = 1 sse V(A) = 0 ou V(B) = 1 
V(A ↔ B) = 1 sse V(A) = V(B) 
 
Problema da Tabela da 
Verdade: 
À medida que aumentam o 
número de fórmulas 
atômicas, torna-se difícil a 
manipulação das tabela-
verdade. 
Por exemplo: se o número 
de fórmulas atômicas for 
superior a cinco ou seis, 
resultará numa tabela-
verdade com 32 ou 64 
linhas 
6 – Semântica Página 94 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6.4 Semântica do conectivo “→→→→” (implicação) 
 
p q p → q 
V V V 
V F F 
F V V 
F F V 
 
(i) Um enunciado verdadeiro (V(P)=1) implica outro verdadeiro (V(Q)=1) 
� se as interpretações de P e Q são verdadeiras então a interpretação da 
fórmula P → Q é também verdadeira � o significado de toda inferência é 
verdadeiro quando os significados das fórmulas P e Q são verdadeiros 
p q p → q 
V V V 
V F F 
F V V 
F F V 
 
(ii) É falso concluir um enunciado falso (V(Q)=0) a partir de outro 
verdadeiro (V(P)=1), pois uma inferência que conclui um falso a partir de 
um verdadeiro é uma inferência falsa � se a interpretação de P é 
verdadeira e de Q é falsa então a interpretação da fórmula P → Q é falsa 
 
p q p → q 
V V V 
V F F 
F V V 
F F V 
 
(iii) A partir de um enunciado falso (V(P)=0) é possível concluir qualquer 
tipo de enunciado. � Ou seja V(P → Q) = 1 mesmo se V(P) = 0 dado que 
V(Q) = 1 ou
V(Q) = 0, ou seja: V(P → Q) = 1 independentemente de V(Q) 
 
A partir de um antecedente falso, uma inferência que conclui fatos 
verdadeiros ou falsos é uma inferência verdadeira � Não é necessária a 
relação de causa e efeito entre P e Q para que se tenha V(P → Q) = 1 � O 
conectivo → não expressa a semântica da causalidade 
 
p q p → q 
V V V 
V F F 
F V V 
F F V 
 
Conclusão: V(P → Q) = 1 sse V(P) = 0 ou V(Q) = 1 
6 – Semântica Página 95 
Exemplo: 
Q = “o sol é redondo” � interpretação: V(Q) = 1 � V(P → Q) = 1 mesmo 
se P for: 
P = “Pedro Álvares Cabral foi presidente do Brasil”(não há relação de causa 
e efeito entre P e Q) 
 
P = ”dois objetos diferentes ocupam um mesmo local no espaço” � V(P) = 
0 � V(P → Q) = 1 qualquer que seja o enunciado de Q (não há relação de 
causa e efeito entre P e Q) 
 
 
 
Assim, se 2 + 2 = 5 então eu sou o papa! 
 
O enunciado da forma “Se A, então B” é falso só quando A é verdadeiro e B 
é falso e é verdadeiro sempre que 
• B é verdadeiro (independente da veracidade de A) 
• A é falso (independente da veracidade de B) 
 
6.5 Exercícios 
 
a) Seja Q: “o sol é redondo” e P: ? 
Qual a interpretação de P → Q ? Como V(Q) = V, então V(P → Q) = 1 
independente de V(P) 
 
b) Seja P: “Pedro Álvares Cabral foi presidente do Brasil” e Q:? 
Qual a interpretação de P → Q ? Como V(P) = F, então V(P → Q) = 1 
independente de V(Q) 
 
c) Seja: H = ((¬P) ∨ (¬Q)) → R 
E as interpretações: V(P) = 1, V(Q) = 0, V(R) = 1 
 
P Q R ¬P ¬Q ¬P V ¬Q ¬P V ¬Q → R 
1 0 1 0 1 1 1 
 
Então, para essas interpretações: V(H) = 1 
 
 
 
 
 
 
 
 
 
 
 
De um enunciado falso pode-se concluir (implicar) tudo o que se queira. 
6 – Semântica Página 96 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6.6 Propriedades Semânticas da fórmula única 
 
São relações obtidas no mundo semântico a partir das interpretações de 
fórmulas que pertencem ao mundo sintático 
 
Dado uma fórmula A, ela é: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Toda fórmula válida (V(A) = 1) é também satisfazível (V(A) = 1) 
Toda fórmula insatisfazível (V(A) = 0) é falsificável (V(A) = 0) 
Uma fórmula não pode ser satisfazível (V(A) = 1) e insatisfazível (V(A) = 0) 
ao mesmo tempo 
Uma fórmula não pode ser válida (V(A) = 1) e falsificável (V(A) = 0) ao 
mesmo tempo 
 
Se A é válida, então ¬A é insatisfazível 
Se A é insatisfazível, então ¬A é válida 
Se A é satisfazível, então ¬A é falsificável 
Se A é falsificável, então ¬A é satisfazível 
 
Existem fórmulas que são tanto satisfazíveis como falsificáveis 
 
6.6.1 Validade ou Tautologia 
 
Uma fórmula “A” é uma tautologia (ou é válida) quando qualquer 
interpretação V faz a interpretação de “A” como sendo verdadeira V(A) = 1 
 
 
 
 
Uma proposição composta é chamada Tautologia se for verdadeira 
independentemente dos valores lógicos de suas proposições simples 
componentes 
 
Válida ou 
Tautologia 
sse para toda interpretação / 
valoração V de seus átomos 
tem-se: V(A) = 1 se todas as linhas da 
coluna A contiverem 1 
Factível ou 
Satisfatível ou 
Satisfazível 
sse existe pelo menos uma 
interpretação/valoração V de 
seus átomos 
tal que V(A) = 1 se alguma linha da 
coluna A contiver I 
Contraditória ou 
insatisfazível ou 
inválida 
sse para toda interpretação / 
valoração V de seus átomos 
tem-se: V(A) = 0 se todas as linhas da 
coluna A contiverem 0 
Falsificável sse existe uma valoração V 
de seus átomos 
tal que V(A) = 0 se alguma linha da 
coluna A contiver 0 
 
“A” é tautologia quando todas as interpretações a valorizam como 
sendo verdadeira 
Toda fórmula válida 
(V(A) = 1) é também 
satisfazível (V(A) = 1) 
Toda fórmula insatisfazível 
(V(A) = 0) é falsificável 
(V(A) = 0) 
6 – Semântica Página 97 
A validade ou tautologia é muito mais do que a veracidade, pois uma 
fórmula “A” pode ser verdadeira segundo uma interpretação I , mas ser 
falsa sob outra interpretação J (duas linhas I e J da tabela da verdade). 
 
Se I(A) = 1 mas J(A) = 0 � “A” é apenas factível ou satisfatível, não é 
tautologia 
 
a) Exemplo-1: Princípio da Identidade: 
 
p → p e p ↔ p são tautológicas 
 
b) Exemplo-2: Princípio do Terceiro Excluído: 
 
Toda proposição ou é verdadeira ou é falsa (nunca um terceiro caso é 
verificado) � (p V ~p) é tautológico (sempre verdadeiro) 
 
Demonstração 
(i) Usando a tabela da verdade: H : (p ∨ ¬p), 
 
p ¬¬¬¬p H = p ∨∨∨∨ ¬¬¬¬p 
0 1 1 
1 0 1 
 
V(H) = V(p ∨ ¬p)=V, com qualquer valoração para p, isto é, V(p)=V ou 
V(p)=F � Assim, dizer que uma proposição é sempre verdadeira ou falsa, é 
sempre verdadeiro 
 
(ii) Sem usar a Tabela da Verdade: H : (p ∨ ¬p) 
V(H) = 1 
⇔ V(p ∨ ¬p) = 1 
⇔ V(p) = 1 ∨ V(¬p) = 1 
⇔ V(p) = 1 ∨ V(p) = 0 
V(H) = 1 sendo V(p) = 0 ou 1, ou seja, independente da interpretação de p 
(ou 0 ou 1) a interpretação de H será sempre verdadeira 
 
c) Exemplo-3: Princípio da não contradição: 
 
Uma proposição não pode ser simultaneamente verdadeira e falsa 
¬(p Λ ¬p) é tautológico (sempre verdadeiro) 
 
p ¬¬¬¬p p ∧∧∧∧ ¬¬¬¬p H = ¬¬¬¬(p ∧∧∧∧ ¬¬¬¬p) 
0 1 0 1 
1 0 0 1 
 
 
 
 
 
 
 
H é uma tautologia 
(ou uma fórmula válida), 
pois todas as valorações 
para H geram 1 em todas 
as linhas 
H é uma tautologia 
(ou uma fórmula válida), 
pois todas as valorações 
para H geram 1 em todas 
as linhas 
6 – Semântica Página 98 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
d) Outros Exemplos 
a) Seja H : p1 ∧ p2 ∧ p3 ∧ q → q 
V(H) = 1 ⇔ V(p1 ∧ p2 ∧ p3 ∧ q → q) = 1 ⇔ Se V(p1 ∧ p2 ∧ p3 ∧ q) = 1 
então V(q) = 1 � H é uma tautologia 
 
b) Todas as proposições abaixo são tautológicas 
(¬p ∨ q) ↔ (p→q) 
p ∨ ¬(p ∧ q) 
p ∧ q → (p ↔ q) 
p ∨ (q ∧ ¬q) ↔ p 
p ∧ r → ¬q ∨ r 
 
c) No final tudo dá certo! (se não deu certo ainda não chegou ao final) 
 
e) Contra-Exemplo 
H : (p ∨ q), sem usar a Tabela da Verdade: 
� Existe uma interpretação: I(p) = 1 e I(q) = 0 � I(H) = 1 
� Existe outra interpretação: J(p) = 0 e J(q) = 0 � J(H) = 0 
Logo H é satisfatível, mas não é tautologia. 
 
6.6.2 Satisfazibilidade ou Contingência 
 
Uma proposição composta é chamada Contingência se houver pelos menos 
uma combinação de seus átomos tal que seja verdadeira e pelo menos 
uma outra tal que seja falsa. 
 
Seja: A : (p ∨ q) ∧ (¬p ∨ ¬q) 
 
Construindo uma tabela da verdade para A: 
• Inicialmente monta-se uma lista de subfórmulas, ordenando-as, da 
esquerda para direita, em ordem de tamanho (a fórmula A é a última): 
 
p q ¬p ¬q p ∨ q ¬p ∨ ¬q A = (p ∨ q) ∧ (¬p ∨ ¬q) 
 
• Colocam-se as valorações (ou interpretações) para os átomos (se uma 
fórmula contém n átomos, o número de valorações possíveis para 
esses átomos é 2n, o que significa 2n linhas na tabela): 
 
p q ¬p ¬q p ∨ q ¬p ∨ ¬q A = (p ∨ q) ∧ (¬p ∨ ¬q) 
0 0 
0 1 
1 0 
1 1 
Se uma fórmula contém 
n átomos, o número de 
valorações possíveis para 
esses átomos é 2n, o que 
significa 2n linhas na tabela 
6 – Semântica Página 99 
 
• Preenchem-se as colunas de cada subfórmula, de acordo
com a 
definição de valoração, da esquerda para direita, até completar toda a 
tabela: 
 
p q ¬p ¬q p ∨ q ¬p ∨ ¬q A = (p ∨ q) ∧ (¬p ∨ ¬q) 
0 0 1 1 0 1 0 
0 1 1 0 1 1 1 
1 0 0 1 1 1 1 
1 1 0 0 1 0 0 
 
p q ¬p ¬q p ∨ q ¬p ∨ ¬q A = (p ∨ q) ∧ (¬p ∨ ¬q) 
0 0 1 1 0 1 0 
0 1 1 0 1 1 1 
1 0 0 1 1 1 1 
1 1 0 0 1 0 0 
 
Dessa tabela pode-se inferir que: 
• A é satisfazível 
• A é falsificável 
 
Outro exemplo: p → ¬p 
p ¬¬¬¬p p →→→→ ¬¬¬¬p 
1 0 0 
0 1 1 
 
 
6.6.3 Contradição ou insatisfazível 
 
Uma proposição composta é chamada Contradição se for sempre falsa 
independentemente dos valores lógicos de suas proposições simples 
componentes. 
 
 
 
 
 
Exemplos: 
a) G = p ∧ ¬p � Usando a Tabela da Verdade 
 
p ¬¬¬¬p G = p ∧∧∧∧ ¬¬¬¬p 
0 1 0 
1 0 0 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A é satisfazível 
A é falsificável 
Nota: 
Por causa do crescimento 
exponencial, método da 
tabela da verdade não é 
recomendado para 
fórmulas com muitos 
átomos (4 átomos é o limite 
de realização de uma tabela 
da verdade) 
“A” é contraditória quando todas as interpretações a validam como 
sendo falsa (não há interpretações que a validem como sendo 
verdadeira). É o oposto da tautologia. 
G é uma contradição 
(ou uma fórmula inválida), 
pois todas as valorações 
para G geram 0 em todas 
as linhas 
6 – Semântica Página 100 
b) Seja G : p ∧ ¬p � Sem usar a Tabela da Verdade: 
V(G) = 1 ⇔ V(p ∧ ¬p) = 1 ⇔ V(p) = 1 ∧ V(¬p) = 1 ⇔ V(p) = 1 ∧ V(p) = 0 � 
Como a interpretação V é uma função binária, então só pode ocorrer uma 
possibilidade, logo G não pode assumir o valor 0 e 1 simultaneamente � G 
é uma afirmação falsa 
 
c) p: √2 = m/n com m/n fração irredutível �gera uma contradição, pois p é 
uma proposição falsa. 
 
6.7 Propriedades Semânticas para diversas fórmulas 
 
Dados duas fórmulas A e B 
 
 
 
 
 
 
B é conseqüência lógica de A se toda valoração que satisfaz A também 
satisfaz B (são exatamente as mesmas valorações que satisfazem B) 
A e B são logicamente equivalentes, ou seja: A ≡ B se A ⇒ B e B ⇒ A (numa 
tabela da verdade as colunas para A e para B são idênticas) 
 
 
 
 
 
 
 
 
 
 
 
6.7.1 Conseqüência Lógica 
 
H implica logicamente G (ou G é consequência lógica de H) quando para 
toda interpretação V, se V(H) = 1 então V(G) = 1 
 
Dada uma interpretação V, se V interpreta H como sendo verdadeira, 
então V interpreta G como sendo verdadeira � Isso não quer dizer que, 
para toda interpretação V, as valorações de H e G segundo V coincidem ou 
são iguais a verdade, têm a mesma opinião sobre H e G. 
 
Além disso, caso exista uma interpretação J tal que J(H) = 1, então nada 
pode ser dito sobre J(G) (é possível ter J(G) = 1 ou J(G) = 0) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
B é Conseqüência Lógica de A ou 
A implica logicamente B (A ⇒ B) 
sse para toda 
interpretação V 
se V(A) = 1 
então V(B) = 1 
toda linha da coluna A que 
contém 1 também contém 1 
na coluna para B 
A Equivale a B (A ≡ B ou A ⇔ 
B) 
sse para toda 
interpretação V 
tem-se V(A) = 
V(B) 
as colunas para A e para B 
são idênticas 
 
Nota: 
a) Não há relação entre os símbolos ⇒ e → 
 O símbolo → é o “se-então” da sintaxe da lógica proposicional 
 O símbolo ⇒ é o “se-então” da semântica 
 
b) Não há relação entre os símbolos ⇔ e ↔ 
 O símbolo ↔ é o “se e somente se” da sintaxe da lógica proposicional 
 O símbolo ⇔ é o “se e somente se” da semântica 
 
6 – Semântica Página 101 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
a) H : p ∨ q → r ⇒ p → r 
 
p q r p ∨ q p ∨ q → r p → r 
0 0 0 0 1 1 
0 0 1 0 1 1 
0 1 0 1 0 1 
0 1 1 1 1 1 
1 0 0 1 0 0 
1 0 1 1 1 1 
1 1 0 1 0 0 
1 1 1 1 1 1 
 
Vê-se que p ∨ q → r implica logicamente p → r, pois toda linha da coluna p 
∨ q → r que contém 1 também contém 1 na coluna para p → r 
 
b) H : p ∧ q → r ⇒ p → r 
Vê-se que p ∧ q → r não implica logicamente p → r pois existe valoração 
de p ∧ q → r que falsifica p → r 
 
p q r p ∧ q p ∧ q → r p → r 
0 0 0 0 1 1 
0 0 1 0 1 1 
0 1 0 0 1 1 
0 1 1 0 1 1 
1 0 0 0 1 0 
1 0 1 0 1 1 
1 1 0 1 0 0 
1 1 1 1 1 1 
 
c) Sejam: 
H : (p ∧ q) 
E : ((p ∧ q) ∨ q) 
G : p → q 
 
p q H = (p ∧∧∧∧ q) E = ((p ∧∧∧∧ q) ∨∨∨∨ q) G = p →→→→ q 
0 0 0 0 1 
0 1 0 1 1 
1 0 0 0 0 
1 1 1 1 1 
 
E implica G pois se V(E) = 1 então V(G) = 1 
H implica E pois se V(H) = 1 então V(E) = 1 
H implica G pois se V(H) = 1 então V(G) = 1 
H implica p pois se V(H) = 1 então V(p) = 1 
 
Toda linha da coluna p ∨∨∨∨ q →→→→ r 
que contém 1 também contém 
1 na coluna para p →→→→ r 
Existe valoração de p ∧∧∧∧ q →→→→ r 
que falsifica p →→→→ r 
E implica G pois quando se tem 
se V(E) = 1 também se tem 
 V(G) = 1 
6 – Semântica Página 102 
G não implica E pois existe V(G) = 1 com V(E) = 0 
G não implica H pois existe V(G) = 1 com V(H) = 0 
E não implica H pois existe V(E) = 1 com V(H) = 0 
 
Mesmo tendo que H implica G, quando H é interpretada como sendo “0”, 
nada se pode concluir sobre a interpretação de E e de G 
 
6.7.2 Equivalência Lógica 
 
A equivale a B sse para toda interpretação V, tem-se V(A) = V(B) 
 
Para demonstrar que V(A) = V(B) basta: 
a) Demonstrar que V(A) = 0 ⇔ V(B) = 0 ou que V(A) = 1 ⇔ V(B) = 1 
b) Construir uma tabela verdade associada a A e B e verificar se as duas 
colunas coincidem 
 
Sejam: H = (¬p ∧ ¬q) e G = ¬(p ∨ q) 
As duas fórmulas são equivalentes (Lei de De Morgan) pois: 
 
p q ¬¬¬¬p ¬¬¬¬q H = (¬¬¬¬p ∧∧∧∧ ¬¬¬¬q) p ∨∨∨∨ q G = ¬¬¬¬(p ∨∨∨∨ q) 
0 0 1 1 1 0 1 
0 1 1 0 0 1 0 
1 0 0 1 0 1 0 
1 1 0 0 0 1 0 
 
Ou, de outro modo: 
V(H) = 1 ⇔ V(¬p ∧ ¬q) = 1 
 ⇔ V(¬p) = 1 ∧ V(¬q) = 1 
 ⇔ V(p) = 0 ∧ V(q) = 0 
 ⇔ V(p ∨ q) = 0 
 ⇔ V(¬ (p ∨ q)) = 1 
 ⇔ V(G) = 1 � V(H) = 1 ⇔ V(G) = 1 
 
Por outro lado: 
V(H) = 0 ⇔ V(¬p ∧ ¬q) = 0 
 ⇔ V(¬p) = 0 ∨ V(¬q) = 0 
 ⇔ V(p) = 1 ∨ V(q) = 1 
 ⇔ V(p ∨ q) = 1 
 ⇔ V(¬ (p ∨ q)) = 0 
 ⇔ V(G) = 0 � V(H) = 0 ⇔ V(G) = 0 
 
Portanto V(H) = V(G) � H e G são equivalentes 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
As duas colunas são iguais ���� 
H e G são equivalentes 
6 – Semântica Página 103 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6.8 Equivalências Notáveis 
 
As fórmulas αααα e ββββ são tautologicamente equivalentes e indicamos α⇔βα⇔βα⇔βα⇔β se 
e somente se a fórmula α↔βα↔βα↔βα↔β é uma tautologia 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6.8.1 Da Conjunção 
 
a) Idempotente: p ∧ p ⇔ p (a bicondicional p ∧ p ↔ p é tautológica) 
b) Comutativa: p ∧ q ⇔ q ∧ p (a bicondicional p ∧ q ↔ q ∧ p é tautológica) 
c) Associativa: (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r) (as tabelas-verdade são idênticas) 
d) Identidade: Para t = 1 (elemento neutro da conjunção) e c = 0 (elemento 
absorvente da conjunção),
tem-se: p ∧ t ⇔ p e p ∧ c ⇔ c 
 
Exemplo: Sabendo-se que V(|x | < 0) = 0 tem-se: x ≠ 1 ∧ |x | < 0 ⇔ |x | < 0 
 Sabendo-se que V(|x | ≥ 0) = 0 tem-se: x ≠ 1 ∧ |x | ≥ 0 ⇔ x ≠ 1 
 
6.8.2 Da Disjunção 
 
a) Idempotente: p ∨ p ⇔ p (a bicondicional p ∨ p ↔ p é tautológica) 
b) Comutativa: p ∨ q ⇔ q ∨ p (a bicondicional p ∨ q ↔ q ∨ p é tautológica) 
c) Associativa: (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (as tabelas-verdade são idênticas) 
d) Identidade: Para t = 1 (elemento absorvente da disjunção) e c = 0 
(elemento neutro da disjunção), tem-se: p ∨ t ⇔ t e p ∨ c ⇔ p 
 
Comutativa p ∧∧∧∧ q ⇔⇔⇔⇔ q ∧∧∧∧ p p ∨∨∨∨ q ⇔⇔⇔⇔ q ∨∨∨∨ p 
Associativa (p ∧∧∧∧ q)∧∧∧∧ r ⇔⇔⇔⇔ p ∧∧∧∧ (q ∧∧∧∧ r) (p ∨∨∨∨ q)∨∨∨∨ r ⇔⇔⇔⇔ p∨∨∨∨ (q∨∨∨∨ r) 
Idempotente p ∧∧∧∧ p ⇔⇔⇔⇔ p p ∨∨∨∨ p ⇔⇔⇔⇔ p 
Propriedades de V p ∧∧∧∧ V ⇔⇔⇔⇔ p p ∨∨∨∨ V ⇔⇔⇔⇔ V 
Propriedades de F p ∧∧∧∧ F ⇔⇔⇔⇔ F p ∨∨∨∨ F ⇔⇔⇔⇔ p 
Absorção p ∧∧∧∧ ( p ∨∨∨∨ r ) ⇔⇔⇔⇔ p p ∨∨∨∨ (p ∧∧∧∧ r) ⇔⇔⇔⇔ p 
Distributivas p ∧∧∧∧ (q ∨∨∨∨ r) ⇔⇔⇔⇔ (p ∧∧∧∧ q ) ∨∨∨∨ (p ∧∧∧∧ r) p ∨∨∨∨ (q ∧∧∧∧ r) ⇔⇔⇔⇔ (p ∨∨∨∨ q ) ∧∧∧∧ (p ∨∨∨∨ r) 
Distributivas p →→→→ (q ∧∧∧∧ r) ⇔⇔⇔⇔ (p→→→→ q) ∧∧∧∧ (p →→→→ r) p →→→→ (q ∨∨∨∨ r) ⇔⇔⇔⇔ (p→→→→ q) ∨∨∨∨ (p →→→→ r) 
Leis de De Morgan ¬¬¬¬ (p ∧∧∧∧ q) ⇔⇔⇔⇔ ¬¬¬¬ p ∨∨∨∨ ¬¬¬¬ q ¬¬¬¬(p ∨∨∨∨ q) ⇔⇔⇔⇔ ¬¬¬¬ p ∧∧∧∧ ¬¬¬¬ q 
Def. implicação p →→→→ q ⇔⇔⇔⇔ ¬¬¬¬p ∨∨∨∨ q p →→→→ q ⇔⇔⇔⇔ ¬¬¬¬( p ∧∧∧∧¬¬¬¬ q) 
Def. bicondicional p ↔↔↔↔ q ⇔⇔⇔⇔ (p →→→→ q) ∧∧∧∧ ( q →→→→ p) p ↔↔↔↔ q ⇔⇔⇔⇔ (¬¬¬¬p ∨∨∨∨ q) ∧∧∧∧ (¬¬¬¬q ∨∨∨∨p) 
Dupla Negação ¬¬¬¬ (¬¬¬¬ p) ⇔⇔⇔⇔ p 
Contraposição p →→→→ q ⇔⇔⇔⇔ ∼∼∼∼ q →∼→∼→∼→∼ p 
Exportação(⇒ ) Importação (⇐ ) (p ∧∧∧∧ q) →→→→ r ⇔⇔⇔⇔ p →→→→ ( q →→→→ r ) 
Troca de Premissas p →→→→ (q →→→→ r ) ⇔⇔⇔⇔ q →→→→ ( p →→→→r ) 
 
6 – Semântica Página 104 
6.8.3 Da Conjunção e da Disjunção 
 
a) Distributivas: 
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) � A conjunção é distributiva em relação à 
disjunção 
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) � A disjunção é distributiva em relação à 
conjunção 
Exemplo: Carlos estuda e Jorge ouve música ou lê 
É equivalente à: Carlos estuda e Jorge ouve música ou Carlos estuda e 
Jorge lê 
 
b) Absorção: 
p ∧ (p ∨ q) ⇔ p 
p ∨ (p ∧ q) ⇔ p 
 
c) Regras de De Morgan 
¬(p ∧ q) ⇔ ¬p ∨ ¬q � Negar que duas proposições são ao mesmo 
tempo verdadeiras equivale a afirmar que uma pelo menos é falsa (ou p ou 
q é falsa) 
¬(p ∨ q) ⇔ ¬p ∧ ¬q � Negar que uma de duas proposições é verdadeira 
equivale a afirmar que ambas são falsas 
A negação transforma a conjunção em disjunção e a disjunção em 
conjunção 
Exemplo: Negar a proposição: É inteligente e estuda 
É afirmar a proposição: Não é inteligente ou não estuda 
 
6.9 Exercícios Propostos 
 
6.9.1 Dizemos que uma proposição p implica q se, e só se, a condicional p 
→ q é uma tautologia. 
Notação: p ⇒ q. 
Mostrar que: 
 i) p ↔ ¬ q não implica p → q; 
 ii) p ∧ q ⇒ p. 
 
6.9.2 Dizemos que uma proposição “p” é equivalente a “q” se, e só se, a 
bicondicional p ↔ q é uma tautologia. Notação: p ⇔ q. 
Verifique se são verdadeiras as afirmações abaixo: 
a) p ∧ q ⇔ q ∧ p (Comutatividade da conjunção) 
b) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r) (Associatividade da conjunção) 
c) p ∨ q ⇔ q ∨ p (Comutatividade da disjunção) 
d) (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (Associatividade da disjunção) 
e) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ ( p ∨ r) (Distributividade da disjunção com relação 
à conjunção) 
f) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ ( p ∧ r) (Distributividade da conjunção com 
relação à disjunção) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6 – Semântica Página 105 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6.9.3 Sejam A, B e C fórmulas proposicionais. Verifique se são verdadeiras 
as seguintes afirmações, justificando as e suas respostas: 
a) Toda fórmula proposicional é equivalente a si própria. 
b) Se A ⇔ B , então B ⇔ A . 
c) Se A ⇔ B e B ⇔ C , então A ⇔ C . 
d) Duas fórmulas tautológicas são sempre equivalentes. 
e) Se A e A → B são tautológicas, então B é tautológica. 
f) Se A ⇒ B , então B ⇒ A 
 
6.9.4 Mostre que 
a) A ∨ B ⇔ ¬ ( ¬ A ∧ ¬ B) 
b) Toda fórmula proposicional é equivalente a uma fórmula na qual 
aparecem apenas os conectivos ∧ e ¬. 
 
6.9.5 Seja x um número natural. 
a) Mostre que x é par se, e somente se, x2 é par. 
b) Mostre que x é ímpar se, e somente se, x2 é ímpar. 
 
6.9.6 Considere que duas proposições são equivalentes se e somente se 
possuem exatamente as mesmas valorações V e F. Neste caso, se A e B são 
equivalentes, é correto afirmar que ¬A ∧ B é uma tautologia? 
 
6.9.7 Verifique se a seguinte argumentação é uma tautologia: 
“Se meu cliente fosse culpado, então a arma do crime estaria no carro”. 
Portanto, se a arma do crime não estava no carro, 
então meu cliente não é culpado” 
 
6.9.8 Demonstrar que: 
a) A Validade (ou tautologia) é o oposto da contradição, isto é: 
Dada uma fórmula H então: 
H é válida (ou tautologia) ⇔ ¬H é contraditória 
b) Toda fórmula válida é também satisfazível, ou seja, se H é uma 
tautologia, então H é satisfatível 
c) ¬H não é satisfatível ⇔ ¬H é contraditória 
d) A relação entre a conseqüência lógica e o conectivo →, isto é: H implica 
G ⇔ (H → G) é tautologia 
e) A relação entre equivalência e o conectivo ↔, isto é: H equivale a G ⇔ 
(H ↔ G) é tautologia 
f) A relação entre equivalência e implicação, isto é: H equivale a G ⇔ H 
implica G e G implica H 
g) A transitividade da equivalência, isto é: Se E equivale a H e H equivale a 
G, então E equivale a G 
 
 
 
6 – Semântica Página 106 
6.9.9 Classificar as fórmulas a seguir de acordo com sua satisfazibilidade, 
validade, falsificabilidade ou insatisfazibilidade : 
 
a) (p → q) → (q → p) 
( )satisfazível ( ) valida ( ) falsificável ( ) insatisfazível 
 
b) (p ∧ ¬p) → q 
( )satisfazível ( ) valida ( ) falsificável ( ) insatisfazível 
 
c) (p → q) → p ∧ q 
( )satisfazível ( ) valida ( ) falsificável ( ) insatisfazível 
 
d) p → ¬¬p 
( )satisfazível ( ) valida ( ) falsificável ( ) insatisfazível 
 
e) ¬(p ∨ q → p) 
( )satisfazível ( ) valida ( ) falsificável ( ) insatisfazível 
 
f) ¬(p → p ∨ q) 
( )satisfazível ( ) valida ( ) falsificável ( ) insatisfazível 
 
g) ((p → q) ∧ (r → q)) → (p ∨ r → q) 
( )satisfazível ( ) valida ( ) falsificável ( ) insatisfazível 
 
6.9.10 Encontrar uma valoração que satisfaça as seguintes fórmulas: 
 
a) p → ¬p 
b) q → p ∧ ¬q 
c) (p → q) → p 
d) ¬(p ∨ q → q) 
e) (p → q) ∧ (¬p → ¬q) 
f) (p → q) ∧ (q → p) 
 
 
6.10 Para saber mais 
 
[1]Keller, Vicente, Bastos, Cleverson L. – Aprendendo Lógica – Editora 
Vozes; Petrópolis; 2007 
[2] Copi, Irving Marmer.- Introdução à Lógica - Editora Mestre Jou; São 
Paulo; 1978 
[3] McInerny, D.Q. – Use a lógica: um guia para o pensamento eficaz – 
Editora Best Seller; Rio de Janeiro; 2006