Valoração

$$ \Huge v\at{p} $$

Definição (Valoração)

Uma valoração é qualquer função $v$ que associa um valor booleano, $\ndV$ ou $\ndF$, a cada proposição, de forma que:

• Para cada átomo $a, b, \cdots, p, q, r, \ldots, x, y, z$ o valor é definido explicitamente.
• Para cada conectivo $\neg, \land, \lor, \to$, resulta da tabela

$$\Large \begin{array}{cc||c|c|c|c} p & q & \neg p & p \land q & p \lor q & p \to q \cr \hline \ndT & \ndT & \ndF & \ndT & \ndT & \ndT \cr \ndT & \ndF & \ndF & \ndF & \ndT & \ndF \cr \ndF & \ndT & \ndT & \ndF & \ndT & \ndT \cr \ndF & \ndF & \ndT & \ndF & \ndF & \ndT \end{array} $$

Exemplo. Valorações

Sejam $p, q$ duas proposições atómicas.

Se $v\at{p} = \ndT, v\at{q} = \ndT$ então $$ \begin{aligned} v\at{\neg p} & = \ndF & v\at{\neg q} & = \ndF & v\at{p \land q} & = \ndT \cr v\at{p \lor q} & = \ndT & v\at{p \to q} & = \ndT & v\at{p \to \neg q} & = \ndF \end{aligned} $$

Se $v\at{p} = \ndF, v\at{q} = \ndT$ então $$ \begin{aligned} v\at{\neg p} & = \ndT & v\at{\neg q} & = \ndF & v\at{p \land q} & = \ndF \cr v\at{p \lor q} & = \ndT & v\at{p \to q} & = \ndT & v\at{p \to \neg q} & = \ndT \end{aligned} $$

O valor booleano de uma proposição depende apenas dos valores booleanos dos átomos que ocorrem nessa proposição.

A definição de $\bot$.

Previamente $\bot$ foi definido como uma “representação” de $p \land \neg p$. Então foi questionado se o $\bot$ que representa $p \land \neg p$ será o mesmo que representa, por exemplo, $q \land \neg q$.

• Na tabela de $p \land \neg p$ todas as linhas são $\ndF$, tal como serão em $q \land \neg q$ ou em $r \land \neg r$ ou …
• …ou em qualquer outra proposição que resulte de substituir $p$ em $p \land \neg p$, como $\del{p \lor r} \land \del{\neg r \land \neg p}$ por exemplo.

Isto é, $\bot$ é “sempre $\ndF$”. Analogamente, $\top$ é “sempre $\ndT$”.

Número de Valorações

Dados dois átomos, $p$ e $q$, quantas valorações diferentes existem para $p,q$?

• Como $v\at{p}$ só pode ter dois valores, e $v\at{q}$ também, as valorações possíveis para $p, q$ são:

$$ \begin{aligned} v_1\at{p} &= \ndT && v_1\at{q} &= \ndT \cr v_2\at{p} &= \ndT && v_2\at{q} &= \ndF \cr v_3\at{p} &= \ndF && v_3\at{q} &= \ndT \cr v_4\at{p} &= \ndF && v_4\at{q} &= \ndF \cr \end{aligned} $$

ou em tabela

$$ \begin{array}{c:c:c} v & p & q \cr \hline v_1 & \ndT & \ndT \cr v_2 & \ndT & \ndF \cr v_3 & \ndF & \ndT \cr v_4 & \ndF & \ndF \end{array} $$

Em geral, para $n$ átomos $p_1, \ldots, p_n$ existem $2^n$ valorações diferentes.

Modelos de Proposições

$$\Huge v \models p \qquad v \models H $$

Definições (Modelo e Refutação) ($\models, \not\models$)

Modelos

• Seja $p$ uma proposição. Um modelo de $p$ é uma valoração $v$ tal que $v\at{p} = \ndT$. Nesse caso escreve-se $v \models p$.
• Se $H$ for um conjunto de proposições, um modelo de $H$ é um modelo de todos os seus elementos: $v \models H$ se e só se $v \models h$ para cada $h \in H$.

Refutações

• Uma refutação de $p$ é uma valoração $v$ tal que $v\at{p} = \ndF$. Nesse caso escreve-se $v \not\models p$.
• Se $H$ for um conjunto de proposições, uma refutação de $H$ é uma refutação de algum dos seus elementos: $v \not\models H$ se e só se $v \not\models h$ para algum $h \in H$.

Por exemplo, se for $v\at{p} = \ndT$ então $v$ é modelo de

• $p$ (trivialmente)
• $p \lor q$ porque $v\at{p \lor q} = \ndT$ (ver a tabela na definição de valoração)
• $\neg p \to p$ porque, pela tabela, $$ \begin{aligned} v\at{\neg p \to p} &= \begin{cases} \ndF &\text{se}\quad v\at{\neg p} = \ndT \land v\at{p} = \ndF \cr \ndT &\text{caso contrário} \end{cases} \end{aligned} $$ Como $v\at{\neg p} = \ndF$ e $v\at{p} = \ndT$ estamos no segundo caso, $v\at{\neg p \to p} = \ndT$.

Resumindo, se $v \models p$ (isto é, se $v\at{p} = \ndT$) então

$$ \begin{aligned} v \models p, &&\quad v \models p \lor q, &&\quad v \models \neg p \to p \end{aligned} $$ ou seja $$ v \models \set{p, p \lor q, \neg p \to p} $$

Cálculo de valores usando uma árvore

Qualquer proposição pode ser representada graficamente por uma árvore de sintaxe e essa representação pode ser útil no cálculo de valores booleanos.

Por exemplo, para verificar que $v \models \neg p \to p$ sabendo que $v \models p$:

%%{init: {'theme':'neutral'}}%%

flowchart TD
impl([$$\to$$]) --> negp([$$\neg$$])
negp --> p([$$p$$])
impl --> pp([$$p$$])
p -.-> |$$v$$| negp
pp -.-> |$$v$$| impl
negp -.-> |$$f$$| impl

Cálculo de valores usando uma tabela

Sabendo que $v \models p$:

Tipos de Proposições

Uma proposição pode ter zero, um ou vários modelos ou refutações.

Definição (Tipos de Proposições)

Uma proposição $p$ é:

• Compatível ou Satisfazível se tem algum modelo: existe $v$ tal que $v \models p$.
• Válida ou Tautologia se qualquer valoração é modelo: para qualquer $v$, $v \models p$.
• Contingente se tem um modelo e uma refutação: existem $u,v$ tais que $u \models p$ e $v \not\models p$.
• Contradição ou Incompatível se não tem modelos: para qualquer $v$, $v \not\models p$.

Exemplo. Tipos de Proposições

• Compatíveis: $p \lor q, p, p \to r, p \lor \neg p.$
• Válidas: $p \lor \neg p, \del{p \land q} \to q, p \to \del{q \to p}.$
• Contingentes: $p, p \land q, p \lor q.$
• Contradições: $p \land \neg p, p \land \del{p \to \neg p}, \del{p \land q} \to \neg q.$