Sintaxe da Lógica Proposicional

A sintaxe é o início da formalização da dedução.

$$ \Huge \begin{matrix} \neg p & p \land q \cr p \lor q & p \to q \end{matrix} $$

Sobre a definição das proposições:

• Intuitivamente uma “proposição” é uma frase que podemos dizer que é “verdadeira” ou “falsa”.
• Formalmente uma “proposição” é uma estrutura que resulta de “conectivos” aplicados a “átomos”.
• Casos atómicos: proposições indivisíveis (“está a chover.”).
• Casos estruturados:
  • negação “não está a chover”
  • conjunção “está a chover e a fazer sol”
  • disjunção “está a chover ou a fazer sol”
  • implicação “se está a fazer sol então não está a chover”

Nesta parte não interessa ainda o valor (verdade/falso) duma proposição, mas na sua sintaxe.

Proposições

$$\large \begin{gathered} \lit{Lisboa é a Capital de Portugal}, \lit{Está a chover}, \lit{2 é maior que 3} \cr \lit{Quando há nuvens o Sol não brilha}, \lit{As plantas não são animais}\cr \lit{Todos os anões são amigos dos elfos} \end{gathered} $$

Uma proposição descreve um facto.

Definição (Proposição)

Seja $\cat{A}$ um conjunto de símbolos.

Uma proposição é uma expressão que resulta exclusivamente de um dos seguintes casos:

• Um átomo (ou proposição atómica ou letra proposicional) é um elemento de $\cat{A}$. $$ a, b, \ldots, p, q, \ldots, x, y, z $$
• A negação de uma proposição. Se $p$ é uma proposição então $$ (\neg p) $$ é uma proposição.
• A conjunção, a disjunção, ou a implicação de duas proposições. Se $p$ e $q$ forem proposições então $$ \begin{aligned} & (p \land q) \cr & (p \lor q) \cr & (p \to q) \end{aligned} $$ também são proposições.

Regras de Precedência

Usam-se regras de precedência para simplificar proposições.

Por exemplo, a proposição $$ ((\neg a) \to (b \lor (c \land d))) $$ pode ser simplificada como $$ \neg a \to b \lor c \land d. $$

Regras de Precedência

1. Os parêntesis têm precedência sobre os conectivos.
2. A negação tem precedência sobre os outros conectivos.
3. A conjunção e a disjunção têm precedência sobre a implicação.
4. A conjunção tem precedência sobre a disjunção.

Formalmente, a expressão $\neg a \to b \lor c \land d$ não é uma proposição. Mas as regras de precedência definem sem ambiguidade a proposição $((\neg a) \to (b \lor (c \land d)))$.

Árvore de Sintaxe

Uma proposição pode ser representada graficamente.

Por exemplo $$\neg a \to b \lor c \land d$$ define a árvore

%%{init: {'theme':'neutral'}}%%
    graph TD
        impl(($$\to$$)) --> nota(($$\neg$$))
        nota --> a(($$a$$))
        impl --> or(($$\lor$$))
        or --> b(($$b$$))
        or --> andcd(($$\land$$))
        andcd --> c(($$c$$))
        andcd --> d(($$d$$))

enquanto que $$(\neg a \to b) \lor c \land d$$ define

%%{init: {'theme':'neutral'}}%%
    graph TD
        or(($$\lor$$)) --> impl(($$\to$$))
        impl --> nota(($$\neg$$))
        impl --> b(($$b$$))
        nota --> a(($$a$$))
        or --> andcd(($$\land$$))
        andcd --> c(($$c$$))
        andcd --> d(($$d$$))

Exemplos de Proposições

• $a$ representa “está a chover”.
• $b$ representa “o número cinco é par”.
• $c$ representa “Coimbra fica em Portugal”.
• $\neg a$: “não está a chover”.
• $\neg b$: “o número cinco é ímpar”.
• $\neg c$: “Coimbra não fica em Portugal”.
• $\neg \neg a$: “é falso que não está a chover”.
• $a \land b$: “está a chover e o número cinco é par”.
• $a \land \neg a$: “está a chover e não está a chover”.
• $a \land a$: “está a chover e está a chover”.
• $a \to \neg b \land c$: “Se está a chover então o número cinco não é par e Coimbra fica em Portugal”.
  • A escrita natural é ambígua: “Coimbra fica em Portugal” depende, ou não, de “Está a chover”? isto é, aquela frase significa $a \to (\neg b \land c)$ ou $(a \to \neg b) \land c$?
• $a \lor b$: “está a chover ou cinco é par”.
• $a \lor \neg a$: “ou está a chover ou não está a chover”.
• $a \lor a$: “está a chover ou está a chover”.
• $a \lor (\neg b \land c)$: “ou está a chover ou cinco não é par e Coimbra fica em Portugal”.
• $a \to b$: “se está a chover então cinco é par”.
• $a \to \neg a$: “se está a chover então não está a chover”.
• $a \to a$: “se está a chover então está a chover”.
• $b \to \neg c$: “Coimbra não fica em Portugal porque cinco é par”.
• $\lit{penso} \to \lit{existo}$: “penso, logo existo”.

Observações

• Erros sintáticos: $p \land \land q,~q\neg\land,~\ldots$
• Não são proposições: perguntas “O café está frio?” e imperativos “Corre!”.
• Coloquialismos, ie frases comuns que correspondem a proposições:
  • “a exceto se b”, “a a não ser que b”: $a \lor b$
    • “chove exceto se faz sol”, “chove a não ser que faça sol”
    • Um caso é alternativo ao outro; Acontece um sempre que não acontece o outro.
  • “b porque a”, “quando a também b”, “b sempre que a”: $a \to b$.
    • “quando faz sol também passeio”,
    • “passeio sempre que faz sol”,
    • “passeio porque faz sol”
      • Se fizer sol então passeio. Porém, também posso passear sem que faça sol.

Conectivos Derivados

$$ \Huge \begin{matrix} \neg & \land & \top & \uparrow & \liff \cr \lor & \to & \bot & \downarrow & \oplus \end{matrix} $$

Os símbolos $\neg, \land, \lor, \to$ designam-se conectivos pois conectam (ligam) proposições mais simples.

A definição de proposição exclui certos conectivos comuns, como $\top, \bot, \liff$ e $\oplus$. De facto, é possível dispensar quase todos os conectivos e começar apenas com, por exemplo $\neg, \lor$ e definir os restantes conectivos à custa destes.

Como numa linguagem de programação, onde instruções e operações simples definem outras mais complexas.

No entanto, para facilitar a escrita é comum usarem-se outros conectivos.

Definição (Conectivos Derivados)

Sejam $p, q$ duas proposições.

Embora sintaticamente estes novos conectivos sejam representados por símbolos “novos”, o que esta tabela define é a “forma equivalente” que fica “abreviada” de acordo com esta tabela.

Isto é $p \otimes q$ não é uma proposição mas uma “abreviatura” da “forma expandida” $\neg\del{p \liff q}$ que, por sua vez, é uma abreviatura de $\neg\del{\del{p \to q} \land \del{q \to p}}$ e esta expressão já é uma proposição.