<!--
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<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<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> </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> </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> </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> ≡ <b>(não A) ou (não B)</b><br/>
<b>não (A ou B)</b> ≡ <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>