Definimos p \downarrow q ("nem p nem q ", ou “flecha de Peirce”) da seguinte forma: p \downarrow q é verdadeira somente se ambas as proposições p e q forem falsas. Nos demais casos, p \downarrow q é falsa. Justifique que
a) p \downarrow q \Longleftrightarrow \neg(p \vee q) \quad (por isto esta operação também é conhecida como NOU (NOR em inglês)
b) \neg p \Longleftrightarrow p \downarrow p
c) p \vee q \Longleftrightarrow(p \downarrow q) \downarrow(p \downarrow q)
d) Toda proposição envolvendo os conectivos \neg, \vee, \wedge, \rightarrow \mathrm{e} \leftrightarrow é logicamente equivalente a uma proposição envolvendo somente o conectivo \downarrow. (Basta mostrar análogos aos itens b, c para cada um desses conectivos)
OBS. Sheffer (1882-1964) em 1913 provou que todas as expressões lógicas poderiam ser escritas em função de uma única operação lógica, no caso \downarrow.

Passo 1

O enunciado define a operação “nor” p\downarrow q como verdadeira somente se ambas p e q forem falsas. Precisamos mostrar:
a) p\downarrow q\iff\neg(p\vee q)
b) \neg p\iff p\downarrow p
c) p\vee q\iff(p\downarrow q)\downarrow(p\downarrow q)
d) Que qualquer fórmula com \neg,\vee,\wedge,\to,\leftrightarrow pode ser reescrita usando só \downarrow.
Usaremos tabelas-verdade e equivalências lógicas.

Passo 2

Para (a) comparamos, em tabela-verdade, as colunas de \neg(p\vee q) e de p\downarrow q:
\begin{array}{c c | c | c | c} p & q & p\vee q & \neg(p\vee q) & p\downarrow q\\hline \mathrm V & \mathrm V & \mathrm V & \mathrm F & \mathrm F\\\ \mathrm V & \mathrm F & \mathrm V & \mathrm F & \mathrm F\\\ \mathrm F & \mathrm V & \mathrm V & \mathrm F & \mathrm F\\\ \mathrm F & \mathrm F & \mathrm F & \mathrm V & \mathrm V \end{array}
As últimas duas colunas coincidem em todas as linhas, logo
p\downarrow q\;\Longleftrightarrow\;\neg(p\vee q).

Passo 3

Para (b) basta aplicar (a) com q=p:
p\downarrow p\;\Longleftrightarrow\;\neg(p\vee p)\;\Longleftrightarrow\;\neg p.

Passo 4

Em (c) note que, por (b),
(p\downarrow q)\downarrow(p\downarrow q) é \neg(p\downarrow q).
Então
(p\downarrow q)\downarrow(p\downarrow q) \;\Longleftrightarrow\; \neg(p\downarrow q) \;\Longleftrightarrow\; \neg\bigl(\neg(p\vee q)\bigr) \;\Longleftrightarrow\; p\vee q.

Passo 5

Para (d), já vimos que \neg e \vee saem de \downarrow. Como o conjunto \{\neg,\vee\} é funcionalmente completo, qualquer conector \wedge,\to,\leftrightarrow se obtém via equivalências conhecidas e, em cada uma delas, basta substituir \neg e \vee pelas fórmulas em \downarrow. Por exemplo:
p\wedge q\;\Longleftrightarrow\;\neg(\neg p\vee\neg q)\;\Longleftrightarrow\;(p\downarrow p)\downarrow(q\downarrow q),
p\to q\;\Longleftrightarrow\;\neg p\vee q\;\Longleftrightarrow\;(p\downarrow p)\downarrow q,
p\leftrightarrow q\;\Longleftrightarrow\;(p\to q)\wedge(q\to p)
e assim por diante. Portanto, \downarrow só é suficiente.

Resposta

a) p\downarrow q\iff\neg(p\vee q).
b) \neg p\iff p\downarrow p.
c) p\vee q\iff(p\downarrow q)\downarrow(p\downarrow q).
d) A operação \downarrow é funcionalmente completa: qualquer fórmula com \neg,\vee,\wedge,\to,\leftrightarrow pode ser reescrita usando apenas \downarrow.

Exercícios relacionados