Estamos a descrever um sistema formal, denominado de cálculo proposicional clássico, que formaliza a chamada lógica clássica, ou lógica proposicional clássica. O vocabulário desse sistema tem os seguintes símbolos primitivos:
As expressões da linguagem do cálculo proposicional são sequências finitas destes símbolos (\emph{strings}), como $\neg)\vee A))(\vee B$. Convém distinguir entre as expressões ou fórmulas bem formadas (fbf) das demais. Isso é feito impondo um conjunto de regras gramaticais para a linguagem.
As regras gramaticais, para esta linguagem formal, definem por fbf (expressões gramaticalmente bem formadas na linguagem) unicamente aquelas expressões $\alpha$ obtidas por alguma das seguintes cláusulas:
Na escrita das fbf do cálculo proposicional adoptámos a convenção de eliminar parêntesis externos e impondo uma ordem de precedência aos operadores. Num sistema formal é frequente a definição de novos símbolos com base em símbolos lógicos primitivos. Na literatura é frequente usar como únicos símbolos primitivos, para o cálculo proposicional, $\neg$ e $\vee$, a partir dos quais se pode definir os outros fazendo por exemplo:
Note que neste contexto os novos símbolos $\wedge,\rightarrow,\leftrightarrow$ não fazem parte do vocabulário básico da linguagem.
Quais das seguintes expressões são proposições bem formadas?
Seja $V$ um conjunto de variáveis proposicionais. A atribuição de valores às variáveis proposicionais é descrita por uma aplicação $v$ de $V$ no conjunto $\{0,1\}$. Por $P(p_1,p_2,\ldots,p_n)$ representamos uma fbf do cálculo proposicional que dependa dos símbolos proposicionais $p_1,p_2,\ldots,p_n$. Entendendo os símbolos como variáveis proposicionais $p_1,p_2,\ldots,p_n$ no conjunto $V$, a atribuição $v$ pode ser estendida a $P$, definindo a avaliação da fórmula $v(P)$. A avaliação de $P$ reflecte a sua estrutura sintáctica, sendo definida em função da avaliação das suas partes (definição indutiva):
Assumindo que as variáveis proposicionais $p$ e $q$ são verdadeiras e que $r$ e $s$ são falsas, avalie as fórmulas:
Seja $P(p_1,p_2,\ldots,p_n)$ uma fórmula proposicional nas variáveis proposicionais $p_1,p_2,$ $\ldots,p_n$. Se considerarmos todas as atribuições de valores de verdade possíveis a $p_1,p_2,\ldots,p_n$, o valor de verdade de $P(p_1,p_2,\ldots,p_n)$ define a tabela de verdade para $P$. Tal tabela com já vimos contem $2^n$ linhas.
Sejam $P,Q$ e $R$ três proposições. Se da veracidade de $P$ e $Q$ se pode concluir que a veracidade da implicação $$ (P\wedge Q)\rightarrow R, $$ ( ou seja, que da veracidade de P e Q resulta sempre a veracidade de R) então pode argumentar-se que da hipótese de $P$ e $Q$ resulta a veracidade de $R$. Assim, caso $P$ e $Q$ sejam aceites como verdadeiras bem como $(P\wedge Q)\rightarrow R$, então a veracidade de $R$ resulta logicamente dos pressupostos. A uma tal justificação damos o nome de argumento e constitui o método usado para a demonstração matemática.
De um modo geral, chama-se argumento a uma sequência finita de proposições organizadas na forma seguinte $$ P_1\wedge P_2\wedge\ldots\wedge P_n \Rightarrow Q $$ onde as proposições $P_1, P_2,\ldots\, P_n$ são designadas de premissas (ou hipóteses) e $Q$ a conclusão (ou tese). Ao fazer-se a leitura do argumento $(P_1\wedge\ldots\wedge P_n)\rightarrow Q$ é costume inserir uma das locuções ''portanto'', ''por conseguinte'', ''logo'', lendo-se por exemplo: ''$P_1,\ldots,P_n$, portanto, $Q$''. Para sugerir esta leitura usa-se, uma das seguintes notações: $$ \begin{align} \begin{array}{c} P_1 \\ \vdots \\ P_n \\ \hline Q \\ \end{array} \end{align} $$ ou
$$P_1,\ldots, P_n\therefore Q\;$$Interessa distinguir entre argumentos correctos e argumentos inválidos.
Um argumento $$P_1,\ldots, P_n\therefore Q$$ diz-se correcto ou válido se a conclusão for verdadeira sempre que as premissas $$P_1,\ldots, P_n$$ forem simultaneamente verdadeiras e diz-se incorrecto, inválido ou falacioso no caso contrário, isto é, se alguma situação permitir que as premissas sejam todas verdadeiras e a conclusão falsa.
As regras que permitem passar de hipóteses feitas e resultados já demonstrados a novas proposições são conhecidas por regras de inferência. A regra de inferência mais frequentemente usada é o \emph{modus ponens}: $$ \begin{align} \begin{array}{l} P\rightarrow Q \\ P \\ \hline Q \\ \end{array} \end{align} $$ Se a implicação $P\rightarrow Q$ é verdadeira e também a proposição $P$, então $Q$ tem de ser necessariamente verdadeira. A validade desta regra pode ser comprovada recorrendo a uma tabela de verdade.
neste caso dizemos que $P\rightarrow Q,P\therefore Q$ é um argumento válido.
De um modo geral, $$ P_1,\ldots, P_n\therefore Q $$ é um argumento válido se e só se $$ P_1\wedge P_2\wedge\ldots\wedge P_n\Rightarrow Q, $$ ou seja, se e só se $$ (P_1\wedge P_2\wedge\ldots\wedge P_n)\rightarrow Q $$ for uma tautologia.
O argumento $$p,q\rightarrow r,\neg r\therefore \neg q$$ é válido já que na tabela de verdade que relaciona os valores de verdade das proposições $p,q\rightarrow r,\neg r, \neg q$ nas linhas onde as premissas são verdadeiras a conclusão também o é. $$ \begin{align} \begin{array}{|ccc||c|c|c||c|} \hline p & q & r & p & q\rightarrow r & \neg r & \neg q \\ \hline V & V & V & V & V & F & F \\ V & V & F & V & F & V & F \\ V & F & V & V & V & F & V \\ \hline V & F & F & *V* & *V* & *V* & *V* \\ \hline F & V & V & F & V & F & F \\ F & V & F & F & F & V & F \\ F & F & V & F & V & F & V \\ F & F & F & F & V & V & V \\ \hline \end{array} \end{align} $$
Mostremos que o argumento abaixo é válido:
"Só se o Eclipse ganhar a corrida é que pagarei as minhas dívidas. Os meus credores não ficarão satisfeitos a não ser que eu pague as minhas dívidas. Logo, ou o Eclipse ganha a corrida ou os meus credores não ficarão satisfeitos."
Interpretação:
Formalização:
$$Q\rightarrow P, \neg Q\rightarrow \neg R\therefore P\vee\neg R$$
Inspector de circunstâncias:
O argumento é válido um vez que a formalização é um sequente tautológico, ou seja, a proposição $$((Q\rightarrow P)\wedge (\neg Q\rightarrow \neg R))\rightarrow (P\vee\neg R)$$ é uma tautologia.
Verifiquemos se o argumento abaixo é válido:
"Ou o Eclipse ganha a corrida ou ganha o Estrela da Manhã. Se o Eclipse ganhar, Icabod ficará satisfeito. Logo, se o Estrela da Manhã ganhar, Icabod não ficará satisfeito."
Interpretação:
Formalização:
$$P \vee Q, P\rightarrow R\therefore Q\rightarrow\neg R$$
Inspector de circunstâncias:
O argumento não é válido, pois há pelo menos uma circunstância que torna as premissas verdadeiras e a conclusão falsa o que faz com que a proposição $$((P \vee Q)\wedge ( P\rightarrow R))\rightarrow (Q\rightarrow\neg R)$$ não seja uma tautologia.
Formalize os seguintes argumentos e teste a sua validade usando inspectores de circunstância para determinar se a formalização é um sequente tautológico:
Podemos assim usar tautologias do tipo $$(A_1\wedge A_2\wedge \ldots\wedge A_n)\rightarrow B$$ para provar argumentos e definir regras de inferência.
Usando tautologias deste tipo ou inspectores de circunstância podemos mostrar serem válidas as relações de inferência da tabela que se segue.
| Name | Tautologia | Regra de inferência |
|---|---|---|
| Modus Ponens | $_{(p\wedge (p\rightarrow q))\rightarrow q}$ | $_{p, p\rightarrow q \therefore q}$ |
| Modus Tollens | $_{(\neg q\wedge (p\rightarrow q))\rightarrow \neg p}$ | $_{\neg q,p\rightarrow q\therefore \neg p}$ |
| Silogismo Hipotético | $_{((p\rightarrow q)\wedge(q\rightarrow r))\rightarrow(p\rightarrow r)}$ | $_{p\rightarrow q,q\rightarrow r\therefore p\rightarrow r}$ |
| Silogismo Disjuntivo | $_{((p\vee q)\wedge\neg p)\rightarrow q}$ | $_{p\vee q,\neg p\therefore q}$ |
| Simplificação | $_{(p \wedge q)\rightarrow p}$ | $_{p \wedge q\therefore p}$ |
| Adição | $_{p\rightarrow (p\vee q)}$ | $_{p\therefore p\vee q}$ |
| Lei da resolução | $_{((p\vee q)\wedge (\neg p\vee r))\rightarrow(q\vee r)}$ | $_{p\vee q,\neg p\vee r\therefore q\vee r}$ |
| Eliminação | $_{((p\rightarrow(q\vee r))\wedge \neg q)\rightarrow (p\rightarrow r)}$ | $_{p\rightarrow(q\vee r)), \neg q\therefore p\rightarrow r}$ |
| Prova por Casos | $_{((p\rightarrow r)\wedge (q \rightarrow r))\rightarrow ((p\vee q)\rightarrow r)}$ | $_{p\rightarrow r,q \rightarrow r\therefore (p\vee q)\rightarrow r}$ |
| Lei da combinação | $_{(p\wedge q)\rightarrow (p\wedge q)}$ | $_{p,q\therefore p\wedge q}$ |
| Redução ao absurdo | $_{(\neg p\rightarrow q \wedge \neg p \rightarrow \neg q)\rightarrow p}$ | $_{\neg p\rightarrow q, \neg p \rightarrow \neg q\therefore p}$ |
A sequência $$A_1,A_2,\ldots,A_n,B$$ é uma demonstração válida se e só se cada fórmula na sequência:
Neste caso a proposição $A_1\wedge A_2\wedge \ldots\wedge A_n \rightarrow B$, e dizemos que a sequência $$A_1,A_2,\ldots,A_n,B$$ é uma demonstração válida do sequente ou argumento $$C_1,C_2,\ldots,C_m\therefore B$$ se as únicas hipóteses usadas na demonstração $A_1,A_2,\ldots,A_n,B$, estão na sequência $C_1,C_2,\ldots,C_m$.
A definição de demonstração válida assenta nos seguintes factos:
Como exemplo de demonstração, seja $\Gamma=\{p,p\rightarrow q, q\rightarrow r\}$. Mostremos que $\Gamma\therefore r$. Com efeito, temos (1) $p$ é hipótese (está em $\Gamma$); (2) $p\rightarrow q$ é hipótese (idem); (3) $q$ (de 1 e 2, por Modus Ponens); (4) $q\rightarrow r$ é hipótese (está em $\Gamma$); (5) $r$ (de 2 e 4, por Modus Ponens). Logo, como por hipótese $p,p\rightarrow q, q\rightarrow r$ são proposições verdadeiras temos de ter $r$ verdadeira.
Admitindo agora que $\Gamma$ tem duas fórmulas contraditórias, da forma $p$ e $\neg p$. Provemos que se pode derivar qualquer fórmula $q$ a partir de $\Gamma$ (ou seja, mostramos que ''duma falsidade tudo se segue''). Como $p$ e $\neg p$ são hipóteses, proposições válidas, podemos inferir que $p\wedge\neg p$ é válida. $$ \begin{align} \begin{array}{lll} 1 & p & \text{hipótese} \\ 2 & \neg p & \text{hipótese} \\ 3 & p \rightarrow (\neg q\rightarrow p) & \text{tautologia} \\ 4 & \neg p \rightarrow (\neg q\rightarrow \neg p) & \text{tautologia} \\ 5 & \neg q\rightarrow p & \text{Modus Ponens a 2 e 3} \\ 6 & \neg q\rightarrow \neg p & \text{Modus Ponens a 1 e 4}\\ 7 & (\neg q\rightarrow \neg p)\rightarrow ((\neg q\rightarrow p)\rightarrow q) & \text{tautologia}\\ 8 & (\neg q\rightarrow p)\rightarrow q & \text{Modus Ponens a 6 e 7} \\ \hline 9 & q & \text{Modus Ponens a 5 e 8} \\ \end{array} \end{align} $$ Assim podemos concluir que se tivermos premissas contraditórias, podemos derivar qualquer proposição.
Aplicando regras de inferência, demonstremos que o argumento abaixo é correcto. $$ \neg p \rightarrow \neg q, (p \vee\neg q) \rightarrow r, \neg s \rightarrow \neg r, s\rightarrow(\neg w \vee \neg v) \therefore \neg w \vee \neg v$$
Temos: $$ \begin{align} \begin{array}{lll} 1 & \neg p \rightarrow \neg q & \text{hipótese} \\ 2 & (p \vee\neg q) \rightarrow r &\text{ hipótese} \\ 3 & \neg s \rightarrow \neg r & \text{hipótese} \\ 4 & s\rightarrow(\neg w \vee \neg v) & \text{hipótese} \\ 5 & p \vee \neg q & \text{Def. implicação em 1} \\ 6 & r & \text{Modus Ponens a 2 e 5} \\ 7 & r\rightarrow s & \text{Contraposição em 3}\\ 8 & s & \text{Modus Ponens a 6 e 7} \\ \hline 9 & \neg w \vee \neg v & \text{Modus Ponens a 4 e 8} \\ \end{array} \end{align} $$
Aplicando regras de inferência, demonstremos que o argumento abaixo é correcto. $$ \neg(\neg p \vee q),\neg r \rightarrow \neg s, (p\wedge \neg q)\rightarrow s, \neg r \vee t\therefore t$$ Temos: $$ \begin{align} \begin{array}{lll} 1 & \neg(\neg p \vee q) & \text{hipótese} \\ 2 & \neg r \rightarrow \neg s & \text{hipótese} \\ 3 & (p\wedge \neg q)\rightarrow s & \text{hipótese} \\ 4 & \neg r \vee t & \text{hipótese} \\ 5 & \neg \neg p \wedge \neg q & \text{Lei de De Morgan em 1} \\ 6 & p \wedge \neg q & \text{Dupla negação de 5} \\ 7 & s & \text{Modus Ponens a 3 e 6} \\ 8 & s\rightarrow r & \text{Modus Tollens a 2 e 7} \\ 9 & r & \text{Modus Ponens a 7 e 8} \\ 10 & r\rightarrow t & \text{Def. de implicação em 4} \\ \hline 11 & t & \text{Modus Ponens a 9 e 10} \\ \end{array} \end{align} $$
Sendo $p,q,r$ e $s$ quatro proposições, classifique os argumentos abaixo se são ou não válidos.
De forma simples podemos mostrar que o operador $\therefore$ satisfaz as seguintes propriedades:
Assim, por exemplo, como $p,p\rightarrow q\therefore q$, pelo Teorema da Dedução, temos que $p\therefore (p\rightarrow q) \rightarrow q$, ou seja $\therefore p \rightarrow((p\rightarrow q) \rightarrow q)$. Donde podemos concluir que $p \rightarrow((p\rightarrow q) \rightarrow q)$ é uma tautologia, já que é ''sempre verdadeira'' o seu valor de verdade não depende de nenhuma hipótese. Assim, sempre que a proposição $P$ é uma tautologia escrevemos que $\therefore P$ já que o seu valor de verdade não depende de nenhuma hipótese.
Mostre que:
Quatro indivíduos são suspeitos de terem cometido um crime. É sabido que um e só um deles cometeu o crime. Quando interrogados pela polícia fizeram as seguintes afirmações:
Se exactamente uma destas afirmações é falsa, quem foi o criminoso?
Quais das seguintes expressões são proposições bem formadas?
Construa a tabela de verdade para as seguintes fórmulas: 1 $\neg(\neg P \vee \neg Q)$
Assumindo que as variáveis proposicionais $P$ e $Q$ são verdadeiras e que $R$ e $S$ são falsas, determine o valor de verdade das afirmações: 1 $P\wedge(Q\vee R)$
Mostre que o valor lógico das fórmulas apresentadas abaixo é independente das suas componentes:
Assumindo que as variáveis proposicionais $P$ e $Q$ são verdadeiras e que $R$ e $S$ são falsas, determine os valores de verdade das seguintes fórmulas.
Mostre as seguintes equivalências
Mostre as seguintes equivalências:
Mostre que a conclusão $C$ segue das premissas $H_1,H_2,H_3$ nos seguintes casos:
Mostre a validade dos seguintes argumentos, onde as premissas aparecem à esquerda e as conclusões à direita:
Sendo $p,q,r$ e $s$ quatro proposições, classifique os argumentos abaixo se são ou não válidos.
Quais dos seguintes argumentos são válidos?
Usando funções implementadas no capítulo anterior, defina uma função
argumento(list, list)->bool
que verifica se a primeira lista [q1,q2,...,qm] é um argumento válido, onde cada proposição é definida por uma string e tem variáveis na segunda lista $[p1,p2,...pn]$. (USANDO: a linguagem proposicional de símbolos 0,1,\&,$|$ e $\sim$, mais as funções imp(bool,bool)->bool e biimp(bool,bool)->bool )
>>> argumento(['p1', 'imp(p1,p2)','p2'],['p1','p2'])
True(Funções do capítulo anterior que vamos usar)
In [4]:
def imp(p,q):
u''' imp(bool,bool)->bool
Operador de implicação '''
return not p or q
def biimp(p,q):
u''' biimp(bool,bool)->bool
Operador de bi-implicação'''
return imp(p,q) and imp(q,p)
def Eval(exp, atrib):
u''' Eval(string,list)->bool
Avalia a expressão proposicional, na sintaxe do Python,
associando a cada variável usada <var> o valor lógico <bool>.
A associação entre variáveis e valores lógicos deve ser descrita
por pares (<var>,<bool>) na lista que serve de argumento.
'''
for var in atrib:
exp = exp.replace(var[0],str(var[1]))
return eval(exp)
def tautologia(exp,var):
u''' tautologia(str,list)->bool
Verifica se a proposição descrita pela string é uma tautologia,
assumindo que as suas variáveis estão descritas na lista.
USANDO: a linguagem proposicional de símbolos 0,1,\&,$|$ e $\sim$,
mais as funções imp(bool,bool)->bool e biimp(bool,bool)->bool
'''
sai = True
nvar = len(var)
for n in range(2**nvar-1,-1,-1):
l=str(bin(n))[2:].rjust(nvar,'0')
cont=0
lista = []
for v in var:
lista.append((v,bool(int(l[cont]))))
cont = cont + 1
sai = sai and bool(Eval(exp,lista))
return sai
(Nova função)
In [5]:
def argumento(lista,var):
u''' tautologia(list,list)->bool
Verifica se a primeira lista [q1,q2,...,qm] é um argumento válido,
onde cada proposição é definida por uma string e tem variáveis na
segunda lista [p1,p2,...pn].
USANDO: a linguagem proposicional de símbolos 0,1,\&,$|$ e $\sim$,
mais as funções imp(bool,bool)->bool e biimp(bool,bool)->bool
'''
sequente = 'imp(' + lista[0]
for prop in lista[1:-1]:
sequente = sequente + ' and '+ prop
sequente = sequente + ',' + lista[-1] + ')'
return tautologia(sequente,var)
(teste da nova função)
In [6]:
argumento(['p1', 'imp(p1,p2)','p2'],['p1','p2'])
Out[6]:
In [ ]: