[obm-l] Re: [obm-l] Funções booleanas

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro Domingos Jr.:

Interessante a sua prova por indução. Pra mim, o seguinte argumento já seria
convincente:

Dado que:
1)  p => q     =     (NÃO-p) OU q
2)  p <=> q     =     ( p => q ) E ( q => q )
3)  p ou q mas não ambos     =     ( p OU q ) E NÃO-( p E q )
e dadas as leis de DeMorgan, idempotência, etc., as quais podem ser provadas
por meio de tabelas-verdade, concluímos que qualquer sentença envolvendo
quaisquer conectivos pode ser re-escrita usando-se apenas E, OU e NÃO.

Na verdade, eu tenho a impressão de que basta usar o conectivo NÃO-OU (NOU),
cuja definição é:
p NOU q  <==>  NÃO-( p OU q ), para que se possa expressar qualquer
sentença.

Por exemplo:
NÃO-p  =  p NOU p
p E q  =  ( p NOU p ) NOU ( q NOU q )
p OU q  =  ( p NOU q ) NOU ( p NOU q )

************

Uma aplicação que me interessa é o uso destas expressões booleanas para se
resolver problemas de lógica. Por exemplo, o das escravas de olhos azuis do
Homem que Calculava. Suponha que existam N escravas, cujos olhos estão
escondidos. Sabe-se que existem escravas de olhos azuis e de olhos pretos.
As de olhos azuis mentem sempre e as de olhos pretos sempre falam a verdade.
Que pergunta você faria a uma delas (escolhida ao acaso já que não se pode
ver os olhos de nehuma), a fim de descobrir qual a cor dos olhos de cada uma
delas?


Um abraço,
Claudio.

----- Original Message -----
From: "Domingos Jr." <dopikas@uol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, March 04, 2003 2:24 PM
Subject: [obm-l] Funções booleanas


> Este foi um fato discutido numa aula de booleana: os únicos conectivos
> necessários para representar todas as expressões possíveis de n variáveis
> booleanas são \/ (OU) /\ (E) ¬ (NEGAÇÃO). [nota: pode-se usar parênteses
ou
> qualquer outra coisa para alterar a precedência desses conectivos]
>
> Eu consegui fazer uma prova disso e achei bem interessante, vou deixar um
> espaço em branco pra quem quiser pensar um pouco e discutir idéias e mais
> embaixo coloco a minha resposta:
>
>
>
>
>
>
>
>
>
>
>
> -----
> V := verdadeiro, F := falso
>
> caso 1 variável:
>     as funções booleanas de 1 variável são f1(X) = V, f2(X) = F, f3(X) =
X,
> f4(X) = ¬X
> f1 e f2 podem ser expressas com os conectivos E e OU e a negação:
> f1(X) = X \/ ¬X
> f2(X) = X /\ ¬X
>
> suponha que para funções com número de variáveis 1 <= k <= n seja possível
> expressá-las somente com os 3 conectivos mencionados.
>
> seja f(X1, X2, ..., X[k+1]) uma função booleana com k+1 variáveis.
>     defina g(X1, ..., Xk) = f(X1, X2, ... Xk, V)
>               h(X1, ..., Xk) = f(X1, X2, ... Xk, F)
>
> pela hipótese de indução, g e h podem ser expressas através dos 3
> conectivos.
> f(X1, X2, ..., X[k+1]) = X[k+1] /\ g(X1, ..., Xk) /\ ¬ X[k+1] /\ h(X1,
...,
> Xk)
>
> se trocarmos g e h por suas expressões expandidas teremos formado uma
> expressão booleana representando f usando somente os 3 conectivos e, sendo
> assim, segue por indução para toda função com n >= 1 variáveis booleanas.
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================