intr_prog/introducao_logica.html

<!--
Introdução elementar à Lógica
Prof. Leônidas de Oliveira Brandão
Material didático para apoio aos cursos de Introdução à Programação
Direitos reservados
Pode ser usado mediante citação de autoria (Prof. Leônidas de Oliveira Brandão) e origem (https://www.ime.usp.br/~leo/mac2166/introducao/)
-->

  <meta http-equiv='Content-Type' content='text/html; charset=UTF-8'>
  <meta name='keywords' content='mac0122, material, professores, leonidas de oliveira brandao'>
  <link rel='stylesheet' type='text/css' href='css_img_js_conf/all.css'>
  <link rel='stylesheet' type='text/css' href='css_img_js_conf/line_introducao_programacao.css'>
  <script src="css_img_js_conf/defineLInE.js"></script> <!-- para referencias 'a documentos internos -->
<div class="pagina">


<p class="secao">Introdução elementar à Lógica</p>

<p>
  O <a href="#" onclick="trocaPagina('introducao_if.html')" title="examinar o desvio de fluxo de execução: comando 'se'">desvio de fluxo de execução</a>
  é essencial para a construção de algoritmos, esse tipo de comando permite algoritmos cujo "comportamento" é alterado de
  acordo com os
  <a href="#" onclick="trocaPagina('introducao_entrada_saida_dados.html')" title="examinar o que é entrada/saida de dados">dados de entrada</a>.

  
  Na seção apresento os princípios da lógica <i>booleana</i>, lembrando o que é <i>tabela verdade</i>
  e as leis de De Morgan.
  <!--
  Augustus De Morgan -  27 June 1806 – 18 March 1871 - https://en.wikipedia.org/wiki/Augustus_De_Morgan
  https://www.ime.usp.br/~bianconi/recursos/lo.pdf
  -->
</p>

<span style="color: #0055AA"><b>Sentenças lógicas e conjuntos</b></span>

<p>
  A lógica é essencial para a matemática como ciência, ela ajuda a estruturar a linguagem matemática.
  Pode-se considerar cada afirmação matemática como uma sentança lógica, um teorema pode ser visto como uma
  sentença do tipo <i>A implica B</i>.
</p>

<p>
  Existem três operadores básicos para lógica, a
  <b style="color:#0000aa;" title="!A verdade <=> A falso">negação</b>, a
  <b style="color:#0000aa;" title="(A e B) verdade <=> A verdade e B verdade">conjunção</b> e a
  <b style="color:#0000aa;" title="(A ou B) verdade <=> A verdade ou B verdade">disjunção</b>,
  respectivamente os operadores <b>não</b>, <b>e</b> e <b>ou</b>. Seu significado pode ser entendido pelas <b>tabelas verdade</b>, vide tabela 1.
  <br/>
  <i>Nota sobre a linguagem C</i>: os operadores lógicos em <i>C</i> são respectivamente <tt>!</tt>, <tt>&&</tt> e <tt>||</tt>.<br/>
     Exemplo <i>C</i>: <tt>if (!(a>b) && (b&lt;c)) <cyan>// equivale que a<=b e b>c, ou seja, b e' maximo</cyan></tt>.
  <br/>
  <i>Nota sobre a linguagem Python</i>: os operadores lógicos em <i>Python</i> são respectivamente <tt>not</tt>, <tt>and</tt> e <tt>or</tt>.<br/>
     Exemplo <i>Python</i>: <tt>if (!(a>b) && (b&lt;c)) <cyan># equivale que a<=b e b>c, ou seja, b e' maximo</cyan></tt>.  
</p>

<p>
  De outra parte, cada sentença lógica pode ser examinada sob o de vista de conjuntos.
  No exemplo <i>A implica B</i>, se entendermos <i>A</i> e <i>B</i> como conjuntos, a implicação indica que
  o conjunto <i>A</i> está contido no conjunto <i>B</i>. Isso está ilustrado na figura <i>1.a</i>, na qual usamos
  <a href="https://pt.wikipedia.org/wiki/Diagrama_de_Venn" title="Estudar diagrama de Venn na WikiPedia" target="_blank"><b>diagrama de Venn</b></a>
</p>

<p>
  Assim a sentença <i>não A</i> pode ser entendida como o complemento do conjunto <i>A</i>, ilustrado na figura <i>1.b</i>.
  E podemos compor as sentenças, por exemplo, criando a sentença <i>não A e B</i>, ou seja, como conjunto, os elementos
  que não estão em <i>A</i> e que simultaneamente estão em <i>B</i>, como ilustrado na figura <i>1.c</i>.
</p>

<p>
A figura <i>1.a</i> apresenta o conjunto <i>B</i> (azul mais claro), contendo o conjunto <i>A</i>.
A figura <i>1.b</i> apresenta o <b>complemento</b> ao conjunto <i>A</i> (azul mais claro), ou seja,
os elementos que não estão em <i>A</i>.
A figura <i>1.c</i> mostra a interseção (equivalente à disjunção) entre o complemento ao conjunto <i>A</i> interseção com o conjunto <i>B</i>
(azul mais claro), ou seja, os elementos que estão no complemento de <i>A</i> com aqueles que
estão em <i>B</i>.
<center>
  <img src="img/img_conj_a_contido_b.png" title="imagem ilustrando conjunto A contido no conjunto B"/>
  <img src="img/img_conj_nao_a.png" title="imagem ilustrando conjunto nao A"/>
  <img src="img/img_conj_nao_a_e_b.png" title="imagem ilustrando conjunto nao A e B"/>
  <br/>
  <i title="Representação gráfica para operações com conjuntos">
    Fig. 1. Representação gráfica com conjuntos: (a) A contido em B; (b) complemento de A; e (c) B\A (em B, mas não em A).</i>
</center>
</p>


<a name="explog"><span style="color: #0050A0">Tabela verdade</span></a>

<p>
  Do ponto de vista da lógica, cada <i>sentença</i> deve ser ou <i>verdadeira</i> ou </i>falsa</i>
  (isto é, pode ocorrer apenas uma das duas opções, sendo um "ou exclusivo").
  Em termos práticos para a <i>programação</i>, o que interessa é a construção de
  <b style="color:#0000aa" title="EL = verdadeiro | falso | não EL | EL e EL | EL ou EL">expressões lógicas (EL)</b>,
  de modo análogo às <i>expressões aritméticas (EA)</i>.
  Assim, a <i>EL</i> mais elementar é aquela com a constante <i>verdadeiro</i> ou <i>falso</i>, como uma <i>EA</i> elementar
  seria um <i>número</i>.
</p>

<p>
  Os operadores lógicos são a <b style="color:#0000aa" title="não A">negação</b> inverte o valor lógico da expressão,
  a <b style="color:#0000aa" title="A e B">conjunção (e)</b> resulta verdadeiro se, e somente se, ambos os operandos são verdadeiro e
  a <b style="color:#0000aa" title="A ou B">disjunção (ou)</b> resulta falso se, e somente se, ambos os itens forem falsos.
  O resultado de cada um desses operadores é dado por sua
  <b style="color:#0000aa" title="Tabela definindo os resultados das operações lógicas">tabela verdade</b>, como indicada abaixo.
  <!-- https://pt.wikipedia.org/wiki/Tabela-verdade -->
</p>

<p>
  As tabelas abaixo representam as sentenças das operações básicas <i>não A</i>, <i>A e B</i> e <i>A ou B</i>.
  Simplificaremos escrevendo "verd" para "verdadeiro" (<i>1</i> em <i>C</i> e <i>true</i> em <i>Python</i>) e
  "fals" para "falso" (<i>0</i> em <i>C</i> e <i>false</i> em <i>Python</i>).
  <center>
  <i>Tab. 1. Tabela verdade para (a) negação, para (b) conjunção <i>e</i> e para (c) disjunção <i>ou</i>.</i>
  <table><tr>
    <td>
    <table class="tbCodeLinCol">
     <tr><th>A</th> <th>não A</th></tr>
     <tr><td>verd</td><td>fals</td></tr>
     <tr><td>fals</td><td>verd</td></tr>
    </table></td>
    <td> &nbsp; </td>
    <td>
    <table class="tbCodeLinCol">
     <tr><th>A</th> <th>B</th> <th>A e B</th></tr>
     <tr><td>verd</td><td>verd</td><td>verd</td></tr>
     <tr><td>verd</td><td>fals</td><td>fals</td></tr>
     <tr><td>fals</td><td>verd</td><td>fals</td></tr>
     <tr><td>fals</td><td>fals</td><td>fals</td></tr>
    </table></td>
    <td> &nbsp; </td>
    <td>
    <table class="tbCodeLinCol">
     <tr><th>A</th> <th>B</th> <th>A ou B</th></tr>
     <tr><td>verd</td><td>verd</td><td>verd</td></tr>
     <tr><td>verd</td><td>fals</td><td>verd</td></tr>
     <tr><td>fals</td><td>verd</td><td>verd</td></tr>
     <tr><td>fals</td><td>fals</td><td>fals</td></tr>
    </table></td>
    <td> &nbsp; </td>
    </tr>
  </table>
  </center>
</p>

<p>
  De modo geral, para cada <i>sentença</i>, ou <i>expressão lógica</i>, pode-se construir sua corresponde <i>tabela-verdade</i>.
  Assim, dada uma <i>sentença</i> formada com <i>k</i> itens lógicos (ou <i>sentenças elementares</i>),
  pode-se fazer uma tabela com <i>k+1</i> colunas, sendo a primeira formada pelo item 1,
  a segunda pelo item 2 e assim por diante.

  Por exemplo,  e nas demais <i>k=3</i>.
  Por exemplo, se a sentença tem apenas um item (como na tabela 1.(a), <i>k=1</i>), existem <i>2<sup>1</sup></i> linhas e
  na última coluna está precisamente o valor da expressão.
  Se a sentença tiver dois itens (como na tabela 1.(b), <i>k=2</i>), então teremos <i>2<sup>2</sup>=4</i> linhas e o valor lógico
  resultante na última coluna.
  <br/>
  Generalizando, uma <i>expressão lógica</i> com <i>k</i> itens terá (além da linha título) <i>2<sup>k</sup></i> linhas,
  cada linha terá uma das possíveis <i>combinações</i> para os valores <i>verdadeiro</i> ou </i>falso</i> e em sua última
  coluna <i>k+1</i> o resultado da <i>sentença</i> completa.
  <br/>
  Portanto, a tabela terá <i>2<sup>k</sup></i> linhas, cada linha terá uma <i>combinação</i>
  possível para os valores <i>verdadeiro</i> ou </i>falso</i>.
</p>

<p>
  Assim, dada uma sentença formada com <i>k</i> itens lógicos (ou sentenças elementares),
  pode-se fazer uma tabela com <i>k+1</i> colunas, sendo a primeira formada pelo item 1,
  a segunda pelo item 2 e assim por diante. A coluna <i>k+1</i> representa a sentença completa.
  Nesse caso a tabela terá <i>2<sup>k</sup></i> linhas, cada linha terá uma <i>combinação</i>
  possível para os valores <i>verdadeiro</i> ou </i>falso</i>.
</p>



<p>
  Note que tanto a disjunção quanto a conjunção são operações comutativas e associativas.
  Comutativas:
    <i>A e B</i> é o mesmo que <i>B e A</i> (produz a mesma tabela verdade);
    <i>A ou B</i> é o mesmo que <i>B ou A</i>.
  Associativas:
    <i>A e (B e C)</i> é o mesmo que <i>(A e B) e C</i>;
    <i>A ou (B ou C)</i> é o mesmo que <i>(A ou B) ou C</i>.
</p>


<a name="exp-py"><span style="color: #0050A0">Leis de De Morgan</span></a>

<p>
  Do mesmo modo que na aritmética podemos compor expressões com diferentes operadores (como '+' e '-'),
  também podemos compor sentenças misturando os três operadores.
  Para isso é interessante perceber que valem as seguintes equivalências, denominadas
  <i><a href="https://en.wikipedia.org/wiki/Augustus_De_Morgan" title="examinar WikiPedia sobre Augustus De Morgan">leis de De Morgan</a></i>:
  <center>
    <b>não (A e B)</b> &equiv; <b>(não A) ou (não B)</b><br/>
    <b>não (A ou B)</b> &equiv; <b>(não A) e (não B)</b><br/>
  </center>
</p>

<p>
  Se não estiver clara a equivalência, monte as tabelas verdade para cada par de sentença e observe que ambas
  produzem os mesmo resultados.
</p>



<p>
  Algumas fontes para aprofundamento:
  na <i>WikiPedia</i> examinar os vocábulos
  <a href="https://en.wikipedia.org/wiki/De_Morgan%27s_laws" title="seguir para o vocabulo De_Morgan na WikiPedia em Ingles">
  De_Morgan%27s_laws</a> ou
  <a href="https://pt.wikipedia.org/wiki/Teoremas_de_De_Morgan" title="seguir para o vocabulo De_Morgan na WikiPedia em Portugues">
  Teoremas_de_De_Morgan</a>.
  Se desejar aprofundar o entendimento sobre a linguagem matemática
  pegue a apostila do professor
  <a href="https://www.ime.usp.br/~bianconi/recursos/lo.pdf" title="pegar a apostila sobre logica de Bianconi">
  Ricardo Bianconi</a>.
</p>


<p class="autoria">
 <a href="https://www.ime.usp.br/~leo" target="_blank" title="seguir para a pagina do prof. Leônidas">Leônidas de Oliveira Brandão</a><br/>
 <a href="http://www.ime.usp.br/~leo" target="_blank" title="seguir para a página do LInE">http://line.ime.usp.br</a>
</p>

<p class="rodape">
  <b>Alterações</b>:<br/>
  2020/08/19: várias pequenas correções, texto da seção "Tabela verdade" completamente reescrito<br/>
  2020/08/15: novo formato, pequenas revisões<br/>
  2020/08/07: revisão geral<br/>
  2018/04/16: primeira versão
</p>

</div>