Valoração

$v (p)$

Definição (Valoração)

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

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

$p v v f f q v f v f \neg p f f v v p \land q v f f f p \lor q v v v f p \to q v f v v$

Exemplo. Valorações

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

Se $v (p) = v, v (q) = v$ então $v (\neg p) v (p \lor q) = f = v v (\neg q) v (p \to q) = f = v v (p \land q) v (p \to \neg q) = v = f$

Se $v (p) = f, v (q) = v$ então $v (\neg p) v (p \lor q) = v = v v (\neg q) v (p \to q) = f = v v (p \land q) v (p \to \neg q) = f = v$

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

A definição de $⊥$ .

Previamente $⊥$ foi definido como uma "representação" de $p \land \neg p$ . Então foi questionado se o $⊥$ 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 $f$ , 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 $(p \lor r) \land (\neg r \land \neg p)$ por exemplo.

Isto é, $⊥$ é "sempre $f$ ". Analogamente, $⊤$ é "sempre $v$ ".

Número de Valorações

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

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

$v_{1} (p) v_{2} (p) v_{3} (p) v_{4} (p) = v = v = f = f v_{1} (q) v_{2} (q) v_{3} (q) v_{4} (q) = v = f = v = f$

ou em tabela

$v v_{1} v_{2} v_{3} v_{4} p v v f f q v f v f$

Em geral, para $n$ átomos $p_{1}, \dots, p_{n}$ existem $2^{n}$ valorações diferentes.

Modelos de Proposições

$v ⊨ p v ⊨ H$

Definições (Modelo e Refutação) ( $⊨, \neq ⊨$ )

Modelos

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

Refutações

Uma refutação de $p$ é uma valoração $v$ tal que $v (p) = f$ . Nesse caso escreve-se $v \neq ⊨ p$ .
Se $H$ for um conjunto de proposições, uma refutação de $H$ é uma refutação de algum dos seus elementos: $v \neq ⊨ H$ se e só se $v \neq ⊨ h$ para algum $h \in H$ .

Por exemplo, se for $v (p) = v$ então $v$ é modelo de

$p$ (trivialmente)
$p \lor q$ porque $v (p \lor q) = v$ (ver a tabela na definição de valoração)
$\neg p \to p$ porque, pela tabela, $v (\neg p \to p) = {f v se v (\neg p) = v \land v (p) = f caso contr \overset{a}{ˊ} rio$ Como $v (\neg p) = f$ e $v (p) = v$ estamos no segundo caso, $v (\neg p \to p) = v$ .

Resumindo, se $v ⊨ p$ (isto é, se $v (p) = v$ ) então

$v ⊨ p, v ⊨ p \lor q, v ⊨ \neg p \to p$ ou seja $v ⊨ {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 ⊨ \neg p \to p$ sabendo que $v ⊨ 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 ⊨ p$ :

$p$	$\neg p$	$\neg p \to p$
$v$	$\neg v = f$	$f \to v = v$

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 ⊨ p$ .
Válida ou Tautologia se qualquer valoração é modelo: para qualquer $v$ , $v ⊨ p$ .
Contingente se tem um modelo e uma refutação: existem $u, v$ tais que $u ⊨ p$ e $v \neq ⊨ p$ .
Contradição ou Incompatível se não tem modelos: para qualquer $v$ , $v \neq ⊨ 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, (p \land q) \to q, p \to (q \to p) .$
Contingentes: $p, p \land q, p \lor q .$
Contradições: $p \land \neg p, p \land (p \to \neg p), (p \land q) \to \neg q .$

Lógica e Computação

Valoração

Modelos de Proposições

Cálculo de valores usando uma árvore

Cálculo de valores usando uma tabela

Tipos de Proposições