Sintaxe da Lógica Proposicional

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

$$\begin{array}{cc}\neg p& p\wedge q\\ p\vee q& p\to q\end{array}$$

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

$$\begin{array}{c}\text{Lisboa eˊ a Capital de Portugal},\text{Estaˊ a chover},\text{2 eˊ maior que 3}\\ \text{Quando haˊ nuvens o Sol na˜o brilha},\text{As plantas na˜o sa˜o animais}\\ \text{Todos os ano˜es sa˜o amigos dos elfos}\end{array}$$

Uma proposição descreve um facto.

Definição (Proposição)

Seja $\mathcal{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 $\mathcal{A}$. $$a,b,\dots ,p,q,\dots ,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{array}{rl}& (p\wedge q)\\ & (p\vee q)\\ & (p\to q)\end{array}$$ 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\vee (c\wedge d)))$$ pode ser simplificada como $$\neg a\to b\vee c\wedge 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\vee c\wedge d$ não é uma proposição. Mas as regras de precedência definem sem ambiguidade a proposição $((\neg a)\to (b\vee (c\wedge d)))$.

Árvore de Sintaxe

Uma proposição pode ser representada graficamente.

Por exemplo $$\neg a\to b\vee c\wedge d$$ define a árvore

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

enquanto que $$(\neg a\to b)\vee c\wedge d$$ define

%%{init: {'theme':'neutral'}}%%
    graph TD
        or(($$\vee$$)) --> impl(($$\to$$))
        impl --> nota(($$\neg$$))
        impl --> b(($$b$$))
        nota --> a(($$a$$))
        or --> andcd(($$\wedge$$))
        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\wedge b$: "está a chover e o número cinco é par".
• $a\wedge \neg a$: "está a chover e não está a chover".
• $a\wedge a$: "está a chover e está a chover".
• $a\to \neg b\wedge 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\wedge c)$ ou $(a\to \neg b)\wedge c$?
• $a\vee b$: "está a chover ou cinco é par".
• $a\vee \neg a$: "ou está a chover ou não está a chover".
• $a\vee a$: "está a chover ou está a chover".
• $a\vee (\neg b\wedge 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".
• $\text{penso}\to \text{existo}$: "penso, logo existo".

Observações

• Erros sintáticos: $p\wedge \wedge q,q\neg \wedge ,\dots$
• 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\vee 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

$$\begin{array}{ccccc}\neg & \wedge & \top & \uparrow & \leftrightarrow \\ \vee & \to & \perp & \downarrow & \oplus \end{array}$$

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

A definição de proposição exclui certos conectivos comuns, como $\top ,\perp ,\leftrightarrow$ e $\oplus$. De facto, é possível dispensar quase todos os conectivos e começar apenas com, por exemplo $\neg ,\vee$ 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 \left(p\leftrightarrow q\right)$ que, por sua vez, é uma abreviatura de $\neg \left(\left(p\to q\right)\wedge \left(q\to p\right)\right)$ e esta expressão já é uma proposição.