{"id":90,"date":"2014-09-23T07:23:23","date_gmt":"2014-09-23T07:23:23","guid":{"rendered":"https:\/\/www.uniessa.hiperlogic.com.br\/?p=90"},"modified":"2014-09-23T07:24:05","modified_gmt":"2014-09-23T07:24:05","slug":"regras-de-equivalencia-formas-de-validacao-e-formas-normais","status":"publish","type":"post","link":"https:\/\/www.uniessa.hiperlogic.com.br\/?p=90","title":{"rendered":"Regras de Equival\u00eancia, Formas de Valida\u00e7\u00e3o e Formas Normais"},"content":{"rendered":"<p>&nbsp;<\/p>\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">Identifica\u00e7\u00e3o<\/td>\n<td valign=\"top\">Formula H<\/td>\n<td valign=\"top\">F\u00f3rmula G<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Dupla Negativa<\/td>\n<td valign=\"top\">\u00ac(\u00acE)<\/td>\n<td valign=\"top\">E<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Propriedades de Identidade<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">E \u2228 False<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">E \u2227 True<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">E<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">E<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Propriedades Complementares<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">E \u2228 \u00ac E<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">E \u2227 \u00ac E<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">True<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">False<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Leis de DeMorgan<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">\u00ac(E \u2227 R)<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">\u00ac(E \u2228 R)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">\u00acE \u2228 \u00acR<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">\u00acE \u2227 \u00acR<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Contraposi\u00e7\u00e3o<\/td>\n<td valign=\"top\">E \u2192 R<\/td>\n<td valign=\"top\">\u00acR \u2192 \u00acE<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Propriedades de Substitui\u00e7\u00e3o<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">E \u2192 R<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">E \u2194 R<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">\u00acE \u2228 R<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">(E \u2192 R) \u2227 (R \u2192 E)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Propriedades Comutativas<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">E \u2228 R<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">E \u2227 R<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">R \u2228 E<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">R \u2227 E<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Propriedades Associativas<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">E \u2228 (R \u2228 S)<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">E \u2227 (R \u2227 S)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">(E \u2228 R) \u2228 S<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">(E \u2227 R) \u2227 S<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Propriedades Distributivas<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">E \u2228 (R \u2227 S)<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">E \u2227 (R \u2228 S)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<td valign=\"top\">\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">(E \u2228 R) \u2227 (E \u2228 S)<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">(E \u2227 R) \u2228 (E \u2227 S)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">Prova Condicional<\/td>\n<td valign=\"top\">E \u2192 (R \u2192 S)<\/td>\n<td valign=\"top\">(E \u2227 R) \u2192 S<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<div>Exerc\u00edcio: Sejam P e Q \u2208 L\u2205. Demonstre, com o aux\u00edlio das equival\u00eancias cl\u00e1ssicas, que as f\u00f3rmulas abaixo s\u00e3o equivalentes: E = Q \u2192 (Q \u2227 P) e G = (\u00acQ \u2228 Q) \u2227 (\u00acQ \u2228 P).<\/div>\n<div><\/div>\n<div>Solu\u00e7\u00e3o: Q \u2192 (Q \u2227 P)<\/div>\n<div>\u00a0\u21d4 \u00acQ \u2228 (Q \u2227 P) (aplicando a Propriedade de Substitui\u00e7\u00e3o do \u2192)<\/div>\n<div>\u00a0\u21d4 (\u00acQ \u2228 Q) \u2227 (\u00acQ \u2228 P) (aplicando a Propriedade Distributiva)<\/div>\n<div><\/div>\n<div><b>M\u00e9todos de Valida\u00e7\u00e3o de F\u00f3rmulas<\/b><\/div>\n<div><\/div>\n<div>\n<ul>\n<li>Tabela-Verdade<\/li>\n<\/ul>\n<div>A tabela-verdade \u00e9 um m\u00e9todo de valida\u00e7\u00e3o baseada na for\u00e7a bruta. Isso ocorre, porque devemos mapear todas as poss\u00edveis combina\u00e7\u00f5es dos s\u00edmbolos\/vari\u00e1veis proposicionais.<\/div>\n<div>Assim, seja P uma f\u00f3rmula proposicional e \u03b1 o conjunto de vari\u00e1veis proposicionais existentes em P (\u03b1 = {X1, X2, \u2026, XN}). A tabela-verdade de P \u00e9 uma tabela com pelo menos N+1 colunas e exatamente 2N linhas. As N primeiras colunas representam as vari\u00e1veis proposicionais, enquanto a (N+1)-\u00e9sima coluna representa a f\u00f3rmula P. Cada linha representa uma poss\u00edvel combina\u00e7\u00e3o de valores (T ou F) das vari\u00e1veis pertencentes a \u03b1 e o valor verdade de P resultante desta combina\u00e7\u00e3o.<\/div>\n<div><\/div>\n<div><b>TABELA-VERDADE X PROPRIEDADES SEM\u00c2NTICAS<\/b><\/div>\n<div>1- Uma f\u00f3rmula \u00e9 uma tautologia se a \u00faltima coluna de sua tabela-verdade cont\u00e9m somente<\/div>\n<div>valores T ou 1.<\/div>\n<div>2- Uma f\u00f3rmula \u00e9 uma contradi\u00e7\u00e3o se a \u00faltima coluna de sua tabela-verdade cont\u00e9m somente<\/div>\n<div>valores F ou 0 (zero).<\/div>\n<div>3- Uma f\u00f3rmula \u00e9 fact\u00edvel se a \u00faltima coluna de sua tabela-verdade cont\u00e9m pelo menos um valor<\/div>\n<div>T ou 1.<\/div>\n<div>4- Duas f\u00f3rmulas s\u00e3o equivalentes semanticamente quando, para cada linha da tabela-verdade,<\/div>\n<div>suas colunas apresentam o mesmo valor.<\/div>\n<div>5- Uma f\u00f3rmula G implica semanticamente na f\u00f3rmula H se, para toda linha cujo valor da coluna<\/div>\n<div>de G \u00e9 verdadeiro, o valor da coluna de H tamb\u00e9m \u00e9 verdadeiro.<\/div>\n<ul>\n<li>\u00c1rvore Sem\u00e2ntica<\/li>\n<\/ul>\n<div>Este m\u00e9todo determina a validade de uma f\u00f3rmula a partir de uma estrutura denominada \u00e1rvore.<\/div>\n<div>Uma \u00e1rvore \u00e9 um conjunto de n\u00f3s (v\u00e9rtices) ligados por arestas. Os n\u00f3s finais s\u00e3o chamados \u201cfolhas\u201d, o n\u00f3 inicial \u00e9 denominado \u201craiz\u201d, enquanto os demais n\u00f3s s\u00e3o intermedi\u00e1rios.<\/div>\n<div><\/div>\n<div>Exemplo de \u00c1rvore:<\/div>\n<p><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-18.23.40.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-92\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-18.23.40.png\" alt=\"Captura de Tela 2014-09-22 \u00e0s 18.23.40\" width=\"221\" height=\"180\" \/><\/a><\/p>\n<\/div>\n<div><\/div>\n<div>\n<p>Durante a valida\u00e7\u00e3o, as arestas que ligam o n\u00f3 raiz aos outros n\u00f3s recebem um r\u00f3tulo, indicando os poss\u00edveis valores de uma determinada vari\u00e1vel proposicional, escolhida aleatoriamente. Se a partir de uma interpreta\u00e7\u00e3o for poss\u00edvel obter o valor da f\u00f3rmula, este \u00e9 associado ao n\u00f3 folha correspondente. Caso n\u00e3o seja poss\u00edvel tal aferi\u00e7\u00e3o, cria-se mais duas arestas, aumentando a ramifica\u00e7\u00e3o da \u00e1rvore. Para a rotula\u00e7\u00e3o dessas arestas, escolhemos uma outra vari\u00e1vel proposicional. Este processo \u00e9 repetido at\u00e9 que todos os n\u00f3s folhas tenham valores associados \u00e0 f\u00f3rmula.<\/p>\n<div>Exerc\u00edcio: Demonstre, atrav\u00e9s de \u00e1rvores sem\u00e2nticas, a validade de H = (P \u2192 Q) \u2194 (\u00acQ \u2227 \u00acP).<\/div>\n<div>Solu\u00e7\u00e3o:<\/div>\n<div><\/div>\n<div><\/div>\n<div><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-18.24.55.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone  wp-image-93\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-18.24.55-300x65.png\" alt=\"Captura de Tela 2014-09-22 \u00e0s 18.24.55\" width=\"457\" height=\"99\" srcset=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-18.24.55-300x65.png 300w, https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-18.24.55.png 633w\" sizes=\"auto, (max-width: 457px) 100vw, 457px\" \/><\/a><\/div>\n<div><\/div>\n<div><b>\u00c1RVORE SEM\u00c2NTICA X PROPRIEDADES SEM\u00c2NTICAS<\/b><\/div>\n<div>1- Uma f\u00f3rmula \u00e9 uma tautologia se s\u00f3 t\u00eam valores T ou 1 em seus n\u00f3s folhas.<\/div>\n<div>2- Uma f\u00f3rmula \u00e9 uma contradi\u00e7\u00e3o se s\u00f3 t\u00eam valores F ou 0 (zero) em seus n\u00f3s folhas.<\/div>\n<div>3- Uma f\u00f3rmula \u00e9 fact\u00edvel se pelo menos um n\u00f3 folha com valor T ou 1.<\/div>\n<div>4- Duas f\u00f3rmulas G e H s\u00e3o equivalentes semanticamente, se a \u00e1rvore sem\u00e2ntica<\/div>\n<div>correspondente \u00e0 f\u00f3rmula G \u2194 H for uma tautologia.<\/div>\n<div>5- Uma f\u00f3rmula G implica semanticamente na f\u00f3rmula H, se a \u00e1rvore sem\u00e2ntica correspondente<\/div>\n<div>\u00e0 f\u00f3rmula G \u2192 H for uma tautologia.<\/div>\n<p>&nbsp;<\/p>\n<ul>\n<li>M\u00e9todo da Nega\u00e7\u00e3o ou Absurdo<\/li>\n<\/ul>\n<div>O m\u00e9todo da nega\u00e7\u00e3o ou absurdo \u00e9 um m\u00e9todo geral de demonstra\u00e7\u00e3o. Ele consiste em negar a afirma\u00e7\u00e3o que se deseja provar e, a partir de um conjunto de dedu\u00e7\u00f5es, concluir um fato contradit\u00f3rio ou absurdo (ex: I[P] = T e I[P] = F).<\/div>\n<div>A aplica\u00e7\u00e3o deste m\u00e9todo \u00e9 recomendada nos casos onde a nega\u00e7\u00e3o da afirma\u00e7\u00e3o nos leva a casos determin\u00edsticos, ou seja, com uma \u00fanica possibilidade de interpreta\u00e7\u00e3o para a f\u00f3rmula, pois isto simplifica a demonstra\u00e7\u00e3o. Tal situa\u00e7\u00e3o ocorre quando a nega\u00e7\u00e3o acarreta a falsidade dos conectivos \u2192 e \u2228 e a veracidade do conectivo \u2227.<\/div>\n<div><\/div>\n<div>Exerc\u00edcio: Demonstrar, atrav\u00e9s do m\u00e9todo da nega\u00e7\u00e3o, a validade da Lei de Transitividade do<\/div>\n<div>conectivo \u2192: H = ((P \u2192 Q) \u2227 (Q \u2192 R)) \u2192 (P \u2192 R)<\/div>\n<div>Solu\u00e7\u00e3o: validade = tautologia. Logo, devemos provar que \u2200 I | I[H] = T.<\/div>\n<div>\u00a0Supondo que H N\u00c3O \u00e9 tautologia, ent\u00e3o \u2203 I | I[H] = F.<\/div>\n<div>I[((P \u2192 Q) \u2227 (Q \u2192 R)) \u2192 (P \u2192 R)] = F \u21d2 I[((P \u2192 Q) \u2227 (Q \u2192 R))] = T e I[(P \u2192 R)] = F<\/div>\n<div>\u00a0Para I[(P \u2192 R)] = F \u21d2 I[P] = T e I[R] = F<\/div>\n<div>\u00a0Para I[((P \u2192 Q) \u2227 (Q \u2192 R))] = T \u21d2 I[P \u2192 Q] = T e I[Q \u2192 R] = T<\/div>\n<div>\u00a0Se I[P \u2192 Q] = T \u21d2 I[P] = F e\/ou I[Q] = T, mas como I[P] = T, logo: \u00a0 I[Q] = T<\/div>\n<div>\u00a0Se I[Q \u2192 R] = T \u21d2 I[Q] = F e\/ou I[R] = T, mas como I[R] = F, logo: \u00a0 I[Q] = F<\/div>\n<div><\/div>\n<div>\u00a0ABSURDO: Q N\u00c3O pode assumir dois valores (T e F) no mesmo instante.<\/div>\n<div>Portanto, a suposi\u00e7\u00e3o inicial est\u00e1 errada e H \u00e9 tautologia.<\/div>\n<div><\/div>\n<div>O objetivo deste m\u00e9todo \u00e9 deduzir uma contradi\u00e7\u00e3o \/ absurdo a partir da nega\u00e7\u00e3o da f\u00f3rmula em prova. Entretanto, nem sempre isto ocorre. Nestes casos, NADA se pode concluir sobre a veracidade da asser\u00e7\u00e3o inicial. Al\u00e9m disso, quando existem mais de uma possibilidade testada, originada de cl\u00e1usulas e\/ou, todas devem gerar uma contradi\u00e7\u00e3o.<\/div>\n<div><\/div>\n<div><b>M\u00c9TODO DA NEGA\u00c7\u00c3O OU ABSURDO X PROPRIEDADES SEM\u00c2NTICAS<\/b><\/div>\n<div>1- Uma f\u00f3rmula H \u00e9 uma tautologia se a suposi\u00e7\u00e3o \u2203 I | I[H] = F gerar contradi\u00e7\u00e3o.<\/div>\n<div>2- Uma f\u00f3rmula H \u00e9 uma contradi\u00e7\u00e3o se a suposi\u00e7\u00e3o \u2203 I | I[H] = T gerar contradi\u00e7\u00e3o.<\/div>\n<div>3- Uma f\u00f3rmula H \u00e9 fact\u00edvel quando ela n\u00e3o for tautologia, nem contradi\u00e7\u00e3o. Neste caso, basta<\/div>\n<div>apresentar duas interpreta\u00e7\u00f5es para H (I e J), onde I[H] = T e J[H] = F.<\/div>\n<div>4- Duas f\u00f3rmulas G e H s\u00e3o equivalentes semanticamente, se for poss\u00edvel provar que a f\u00f3rmula<\/div>\n<div>G \u2194 H for uma tautologia.<\/div>\n<div>5- Uma f\u00f3rmula G implica semanticamente na f\u00f3rmula H, se for poss\u00edvel provar que a f\u00f3rmula<\/div>\n<div>G \u2192 H for uma tautologia.<\/div>\n<div><\/div>\n<ul>\n<li>Princ\u00edpio da Indu\u00e7\u00e3o Finita<\/li>\n<\/ul>\n<div>Apesar de n\u00e3o fazer parte da l\u00f3gica, este princ\u00edpio \u00e9 um dos principais m\u00e9todos utilizados na demonstra\u00e7\u00e3o de resultados. Na ci\u00eancia da computa\u00e7\u00e3o, tal princ\u00edpio \u00e9 usado para demonstrar resultados em linguagens formais, teoria de algoritmos, teoria dos c\u00f3digos, etc.<\/div>\n<\/div>\n<div><\/div>\n<div><b>Paradigma da Indu\u00e7\u00e3o<\/b><\/div>\n<div><\/div>\n<div>Considere um conjunto de pe\u00e7as de domin\u00f3 enfileiradas e enumeradas. Elas est\u00e3o dispostas de modo que, se o domin\u00f3 1 \u00e9 derrubado para direita, ent\u00e3o o subseq\u00fcente (domin\u00f3 2) tamb\u00e9m cai, e assim sucessivamente.<\/div>\n<div>Diante disto, surge a pergunta: \u201cO que \u00e9 suficiente para um domin\u00f3 N cair?\u201d<\/div>\n<div><\/div>\n<div>Resposta: que qualquer um dos domin\u00f3s que o antecede caia para direita, ou seja, existem (N-1) condi\u00e7\u00f5es suficientes.<\/div>\n<div><\/div>\n<div>Suponhamos que o domin\u00f3 1 caia para direita, logo o domin\u00f3 N tamb\u00e9m cai. Agora surge outra pergunta: \u201cQual \u00e9 a condi\u00e7\u00e3o necess\u00e1ria para que o domin\u00f3 1 possa cair para direita?\u201d.<\/div>\n<div><\/div>\n<div>Resposta: que os domin\u00f3s subseq\u00fcentes possam ser derrubados.<\/div>\n<div><\/div>\n<div>A partir deste cen\u00e1rio, observamos que existem v\u00e1rias condi\u00e7\u00f5es suficientes para que todos os domin\u00f3s sejam derrubados. Exemplo:<\/div>\n<div>Se o domin\u00f3 1 \u00e9 derrubado para direita, ent\u00e3o o domin\u00f3 N cai, ou simplesmente, D1 \u2192 DN.<\/div>\n<div>Dentre eles, destacamos 2 conjuntos:<\/div>\n<div><\/div>\n<div><b>1\u00ba conjunto:<\/b><\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Condi\u00e7\u00e3o b\u00e1sica: O domin\u00f3 1 \u00e9 derrubado para direita.<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Condi\u00e7\u00e3o indutiva: Seja N um n\u00ba arbitr\u00e1rio. Se o domin\u00f3 N \u00e9 derrubado para direita, ent\u00e3o o domin\u00f3 N+1 tamb\u00e9m cai.<\/div>\n<div><b>2\u00ba conjunto:<\/b><\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Condi\u00e7\u00e3o b\u00e1sica: O domin\u00f3 1 \u00e9 derrubado para direita.<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Condi\u00e7\u00e3o indutiva: Seja N um n\u00ba arbitr\u00e1rio. Se todos os domin\u00f3s at\u00e9 N s\u00e3o derrubados para direita, ent\u00e3o o domin\u00f3 N+1 tamb\u00e9m cai.<\/div>\n<div><\/div>\n<div>Note, que ambos tem a mesma condi\u00e7\u00e3o b\u00e1sica. Entretanto, a condi\u00e7\u00e3o indutiva \u00e9 ligeiramente modificada.<\/div>\n<div>O princ\u00edpio da indu\u00e7\u00e3o finita possui 2 formas que correspondem a estes conjuntos. Neste curso iremos abordar apenas a 1\u00aa forma.<\/div>\n<div><\/div>\n<div><\/div>\n<div><\/div>\n<div>\n<ul>\n<li><b>1a Forma de Indu\u00e7\u00e3o<\/b><\/li>\n<\/ul>\n<div><\/div>\n<\/div>\n<div>Suponha que para cada N (N \u2265 1), seja dada a asser\u00e7\u00e3o A(N). Para concluirmos que A(N) \u00e9 verdadeira para todo inteiro N, deve ser poss\u00edvel demonstrar as seguintes propriedades:<\/div>\n<div>\u2022 Base da Indu\u00e7\u00e3o: A asser\u00e7\u00e3o A(1) \u00e9 verdadeira.<\/div>\n<div>\u2022 Passo Indutivo: Dado um inteiro N (N \u2265 1), se A(N) \u00e9 verdadeira, ent\u00e3o A(N+1) tamb\u00e9m \u00e9 verdadeira.<\/div>\n<div><\/div>\n<div>Exerc\u00edcio: Demonstre, atrav\u00e9s do princ\u00edpio da indu\u00e7\u00e3o finita, que: dada a progress\u00e3o geom\u00e9trica\u00a0a<span style=\"font-size: 9px;\">i+1<\/span> = a<span style=\"font-size: 9px;\">i+<\/span>q, para q \u2260 1. A soma dos N primeiros termos desta progress\u00e3o pode ser calculada por:<\/div>\n<div><\/div>\n<div><\/div>\n<div><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-23-\u00e0s-04.18.36.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone  wp-image-100\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-23-\u00e0s-04.18.36-300x195.png\" alt=\"Captura de Tela 2014-09-23 \u00e0s 04.18.36\" width=\"498\" height=\"324\" srcset=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-23-\u00e0s-04.18.36-300x195.png 300w, https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-23-\u00e0s-04.18.36-1024x668.png 1024w, https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-23-\u00e0s-04.18.36.png 1101w\" sizes=\"auto, (max-width: 498px) 100vw, 498px\" \/><\/a><\/div>\n<div><\/div>\n<div><\/div>\n<div><\/div>\n<div><\/div>\n<div><\/div>\n<div><b>Formas Normais<\/b><\/div>\n<div><b>\u00a0<\/b><\/div>\n<div>As f\u00f3rmulas da l\u00f3gica proposicional podem ser expressas utilizando v\u00e1rios conjuntos de conectivos completos. Al\u00e9m disso, tamb\u00e9m podemos represent\u00e1-las atrav\u00e9s de estruturas pr\u00e9-definidas, denominadas formas normais. S\u00e3o elas:<\/div>\n<div><\/div>\n<div>\u2022 Forma Normal Disjuntiva (FND): se a f\u00f3rmula \u00e9 uma disjun\u00e7\u00e3o de conjun\u00e7\u00f5es de literais<\/div>\n<div>(s\u00edmbolos proposicionais ou suas nega\u00e7\u00f5es).<\/div>\n<div>\u2022 Forma Normal Conjuntiva (FNC): se a f\u00f3rmula \u00e9 uma conjun\u00e7\u00e3o de disjun\u00e7\u00f5es de literais.<\/div>\n<div><\/div>\n<div>Ex: H = (\u00acP \u2227 Q) \u2228 (\u00acR \u2227 \u00acQ \u2227 P) \u2228 (P \u2227 S) FND<\/div>\n<div>\u00a0G = (\u00acP \u2228 Q) \u2227 (\u00acR \u2228 \u00acQ \u2228 P) \u2227 (P \u2228 S) FNC<\/div>\n<div><\/div>\n<div><b>Obten\u00e7\u00e3o das Formas Normais<\/b><\/div>\n<div><b>\u00a0<\/b><\/div>\n<div>Considere a f\u00f3rmula: H = (P \u2192 Q) \u2227 R. Podemos escrever H1 e H2, de modo que H1 seja H na FND e H2 seja H na FNC, com segue:<\/div>\n<div><\/div>\n<div><\/div>\n<div>\n<table border=\"1\" width=\"100%\" cellspacing=\"0\" cellpadding=\"2\">\n<tbody>\n<tr>\n<td valign=\"top\">P<\/td>\n<td valign=\"top\">Q<\/td>\n<td valign=\"top\">R<\/td>\n<td valign=\"top\">H<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">T<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">T<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">t<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">F<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">F<\/td>\n<td valign=\"top\">F<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">T<\/td>\n<td valign=\"top\">T<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><b>2\u00ba Passo<\/b>: Gera\u00e7\u00e3o de H1 (<b>FND<\/b>).<\/p>\n<div>&#8211; Extrair as linhas da tabela-verdade onde I[H] = T. Para cada linha N, gerar uma f\u00f3rmula YN, formada apenas pela conjun\u00e7\u00e3o de literais, de modo que I[YN] = T, como apresentado abaixo:<\/div>\n<div>2\u00aa linha: I[P] = F, I[Q] = F, I[R] = T \u21d2 Y2 = (\u00acP \u2227 \u00acQ \u2227 R).<\/div>\n<div>4\u00aa linha: I[P] = F, I[Q] = T, I[R] = T \u21d2 Y2 = (\u00acP \u2227 Q \u2227 R).<\/div>\n<div>8\u00aa linha: I[P] = T, I[Q] = T, I[R] = T \u21d2 Y2 = (P \u2227 Q \u2227 R).<\/div>\n<div>&#8211; Gerar H1 a partir da disjun\u00e7\u00e3o das f\u00f3rmulas geradas no item anterior.<\/div>\n<div><b>H1 = (\u00acP \u2227 \u00acQ \u2227 R) \u2228 (\u00acP \u2227 Q \u2227 R) \u2228 (P \u2227 Q \u2227 R)\u00a0<\/b><\/div>\n<div><\/div>\n<div><\/div>\n<div><b>3\u00ba Passo<\/b>: Gera\u00e7\u00e3o de H2 (<b>FNC<\/b>).<\/div>\n<div>&#8211; Extrair as linhas da tabela-verdade onde I[H] = F. Para cada linha N, gerar uma f\u00f3rmula XN, formada apenas pela disjun\u00e7\u00e3o de literais, de modo que I[XN] = T, como apresentado abaixo:<\/div>\n<div>1\u00aa linha: I[P] = F, I[Q] = F, I[R] = F \u21d2 X1 = (P \u2228 Q \u2228 R).<\/div>\n<div>3\u00aa linha: I[P] = F, I[Q] = T, I[R] = F \u21d2 X3 = (P \u2228 \u00acQ \u2228 R).<\/div>\n<div>5\u00aa linha: I[P] = T, I[Q] = F, I[R] = F \u21d2 X5 = (\u00acP \u2228 Q \u2228 R).<\/div>\n<div>6\u00aa linha: I[P] = T, I[Q] = F, I[R] = T \u21d2 X6 = (\u00acP \u2228 Q \u2228 \u00acR).<\/div>\n<div>7\u00aa linha: I[P] = T, I[Q] = T, I[R] = F \u21d2 X7 = (\u00acP \u2228 \u00acQ \u2228 R).<\/div>\n<div>&#8211; Gerar H2 a partir da conjun\u00e7\u00e3o das f\u00f3rmulas geradas no item anterior.<\/div>\n<div><b>H2 = (P \u2228 Q \u2228 R) \u2227 (P \u2228 \u00acQ \u2228 R) \u2227 (\u00acP \u2228 Q \u2228 R) \u2227 (\u00acP \u2228 Q \u2228 \u00acR) \u2227 (\u00acP \u2228 \u00acQ \u2228 R)\u00a0<\/b><\/div>\n<div><b>\u00a0<\/b><\/div>\n<div><b>\u00a0<\/b><\/div>\n<div><b>Dedu\u00e7\u00e3o de Teoremas<\/b><\/div>\n<div>O processo de prova por dedu\u00e7\u00e3o consiste em demonstrar que, dadas algumas express\u00f5es como verdadeiras (hip\u00f3teses ou premissas), uma nova senten\u00e7a tamb\u00e9m \u00e9 verdadeira. Quando isso ocorre, dizemos que a senten\u00e7a provada \u00e9 um teorema com respeito \u00e0s hip\u00f3teses.<\/div>\n<div>A prova de um teorema consiste em derivar a express\u00e3o desejada H a partir das hip\u00f3teses \u03b2, utilizando os recursos dispon\u00edveis em algum dos sistemas de dedu\u00e7\u00e3o v\u00e1lidos (\u03b2 |\u2013 H).<\/div>\n<div>Defini\u00e7\u00e3o (sistemas de dedu\u00e7\u00e3o): tamb\u00e9m denominados sistemas formais, s\u00e3o completos (se \u03b2 \u21d2 H, ent\u00e3o \u03b2 |\u2013 H) e corretos (se \u03b2 |\u2013 H, ent\u00e3o \u03b2 \u21d2 H) e estabelecem estruturas que permitem a representa\u00e7\u00e3o e dedu\u00e7\u00e3o do conhecimento.<\/div>\n<div><\/div>\n<div>\n<ul>\n<li><b>TIPOS DE SISTEMAS DE DEDU\u00c7\u00c3O<\/b><\/li>\n<\/ul>\n<\/div>\n<div>Os sistemas de dedu\u00e7\u00e3o podem ser divididos em 2 grupos, como segue:<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Sistemas de dif\u00edcil implementa\u00e7\u00e3o computacional:<\/div>\n<div>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Sistema Axiom\u00e1tico<\/div>\n<div>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Dedu\u00e7\u00e3o Natural<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Sistemas mais adequados para implementa\u00e7\u00e3o computacional:<\/div>\n<div>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 o Tableaux Sem\u00e2nticos<\/div>\n<div>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 o Resolu\u00e7\u00e3o<\/div>\n<div>Neste curso, apresentaremos o sistema axiom\u00e1tico e a resolu\u00e7\u00e3o.<\/div>\n<div><\/div>\n<div><b>Sistema Axiom\u00e1tico<\/b><\/div>\n<div><b>\u00a0<\/b><\/div>\n<div>O sistema axiom\u00e1tico \u00e9 uma estrutura para representa\u00e7\u00e3o e dedu\u00e7\u00e3o do conhecimento baseado em axiomas. Ele \u00e9 definido pela composi\u00e7\u00e3o de 4 elementos:<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Alfabeto da l\u00f3gica proposicional;<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Conjunto de f\u00f3rmulas proposicionais (Hip\u00f3teses)<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Subconjunto de f\u00f3rmulas, denominados axiomas; e<\/div>\n<div>\u00a0 \u00a0 \u00a0\u2022 Conjunto de regras de infer\u00eancia.<\/div>\n<div><\/div>\n<div><b>HIP\u00d3TESES<\/b><\/div>\n<div>As hip\u00f3teses ou premissas s\u00e3o f\u00f3rmulas proposicionais tidas (assumidas) como verdadeiras.<\/div>\n<div>Assim, caso se descubra que uma das hip\u00f3teses pode ser falsa, toda prova feita a partir desta hip\u00f3tese perde sua validade.<\/div>\n<div><\/div>\n<div><b>AXIOMAS<\/b><\/div>\n<div><b>\u00a0<\/b><\/div>\n<div>Os axiomas representam o conhecimento dado a priori. No caso do sistema axiom\u00e1tico, este conhecimento \u00e9 representado por tautologias.<\/div>\n<div><\/div>\n<div>O conjunto de f\u00f3rmulas axiom\u00e1ticas pode variar entre os sistemas axiom\u00e1ticos. Por\u00e9m, independente do conjunto adotado, o mesmo deve assegurar o sistema axiom\u00e1tico seja completo e correto.<\/div>\n<div>Neste curso, adotaremos um sistema cujos axiomas s\u00e3o determinados pelos esquemas:<\/div>\n<div>\u2022 Ax1 = \u00ac(H \u2228 H) \u2228 H \u21d4 (H \u2228 H) \u2192 H<\/div>\n<div>\u2022 Ax2 = \u00acH \u2228 (G \u2228 H) \u21d4 H \u2192 (G \u2228 H)<\/div>\n<div>\u2022 Ax3 = (\u00ac(\u00acH \u2228 G)) \u2228 ((\u00ac(E \u2228 H)) \u2228 (G \u2228 E)) \u21d4 (H \u2192 G) \u2192 ((E \u2228 H) \u2192 (G \u2228 E))<\/div>\n<div><\/div>\n<div>sendo, H, G e E quaisquer f\u00f3rmulas preposicionais.<\/div>\n<div><\/div>\n<div><\/div>\n<div><b>REGRAS DE INFER\u00caNCIA<\/b><\/div>\n<div><b>\u00a0<\/b><\/div>\n<div>As regras de infer\u00eancia s\u00e3o implica\u00e7\u00f5es sem\u00e2nticas. Elas s\u00e3o utilizadas para fazer infer\u00eancias, ou seja, executar os \u201cpassos\u201d de uma demonstra\u00e7\u00e3o ou dedu\u00e7\u00e3o.<\/div>\n<div>Assim como os axiomas, o conjunto de regras de infer\u00eancia adotado em um sistema axiom\u00e1tico pode variar, desde que mantenham as propriedades de completude e corre\u00e7\u00e3o. Quanto menor o conjunto de regras de infer\u00eancia, mais elegante \u00e9 o sistema axiom\u00e1tico.<\/div>\n<div>Abaixo ser\u00e3o listadas algumas regras de infer\u00eancia que podem ser utilizadas em um sistema<\/div>\n<div>axiom\u00e1tico:<\/div>\n<div><\/div>\n<div><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.05.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-95\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.05-285x300.png\" alt=\"Captura de Tela 2014-09-22 \u00e0s 19.10.05\" width=\"285\" height=\"300\" srcset=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.05-285x300.png 285w, https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.05.png 486w\" sizes=\"auto, (max-width: 285px) 100vw, 285px\" \/><\/a><\/div>\n<p><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.29.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-96\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.29-300x53.png\" alt=\"Captura de Tela 2014-09-22 \u00e0s 19.10.29\" width=\"300\" height=\"53\" srcset=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.29-300x53.png 300w, https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.10.29.png 613w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<\/div>\n<div><\/div>\n<div><\/div>\n<div>OBS: A maioria dos sistemas axiom\u00e1ticos costuma utilizar apenas o Modus Ponens (MP) como regra de infer\u00eancia.<\/div>\n<div><\/div>\n<div><\/div>\n<div><b>PROVA EM UM SISTEMA AXIOM\u00c1TICO<\/b><\/div>\n<div>Uma prova ou demonstra\u00e7\u00e3o atrav\u00e9s do sistema axiom\u00e1tico consiste em apresentar a seq\u00fc\u00eancia de passos necess\u00e1rios para derivar a f\u00f3rmula desejada a partir das hip\u00f3teses. Cada passo pode ser a gera\u00e7\u00e3o de um axioma ou a aplica\u00e7\u00e3o de uma regra de infer\u00eancia.<\/div>\n<div>Proposi\u00e7\u00e3o: dado um teorema com as hip\u00f3teses H1, H2, \u2026, HN e a f\u00f3rmula a ser provada C. Ele \u00e9 verdadeiro sempre que:<\/div>\n<div><\/div>\n<div><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.11.39.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-97\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.11.39-300x27.png\" alt=\"Captura de Tela 2014-09-22 \u00e0s 19.11.39\" width=\"300\" height=\"27\" srcset=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.11.39-300x27.png 300w, https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.11.39.png 611w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/div>\n<div><\/div>\n<div>Exerc\u00edcio 1: Prove P \u2192 (S \u2228 G) atrav\u00e9s de um sistema axiom\u00e1tico que utiliza todas as regras de<\/div>\n<div>infer\u00eancia apresentadas acima e com o seguinte conjunto de hip\u00f3teses:<\/div>\n<div>P \u2192 (Q \u2228 R)<\/div>\n<div>Q \u2192 S<\/div>\n<div>R \u2192 G<\/div>\n<div>Solu\u00e7\u00e3o:<\/div>\n<div>&#8211; considerando as hip\u00f3teses:<\/div>\n<div>P \u2192 (Q \u2228 R) (1)<\/div>\n<div>Q \u2192 S (2)<\/div>\n<div>R \u2192 G (3)<\/div>\n<div>&#8211; Aplicando o dilema construtivo entre (2) e (3), temos:<\/div>\n<div>(Q \u2228 R) \u2192 (S \u2228 G) (4)<\/div>\n<div>&#8211; Aplicando o silogismo hipot\u00e9tico entre (1) e (4), temos:<\/div>\n<div>P \u2192 (S \u2228 G) c.q.d<\/div>\n<div><\/div>\n<div><\/div>\n<div>PROVA POR ABSURDO<\/div>\n<div>Neste tipo de prova, nega-se a f\u00f3rmula que se deseja provar, a inclui no conjunto de hip\u00f3teses e aplica as regras de infer\u00eancia at\u00e9 se obter um absurdo.<\/div>\n<div><\/div>\n<div>Exerc\u00edcio: A partir das hip\u00f3teses abaixo e utilizando apenas o Modus Ponens (MP) como regra de infer\u00eancia, prove P.<\/div>\n<div><\/div>\n<div>\u00acS \u2192 P<\/div>\n<div>R \u2228 \u00acP<\/div>\n<div>\u00acS<\/div>\n<div><\/div>\n<div>Solu\u00e7\u00e3o:<\/div>\n<div><\/div>\n<div>&#8211; Considerando as hip\u00f3teses:<\/div>\n<div>\u00a0 \u00a0 \u00a0\u00acS \u2192 P (1)<\/div>\n<div>\u00a0 \u00a0 \u00a0R \u2228 \u00acP (2)<\/div>\n<div>\u00a0 \u00a0 \u00a0\u00acS (3)<\/div>\n<div>\u00a0 \u00a0 \u00a0\u00acP (4) Nega\u00e7\u00e3o do teorema<\/div>\n<div>&#8211; Aplicando a equival\u00eancia (G \u2192 H \u21d4 \u00acH \u2192 \u00acG) em (1), temos:<\/div>\n<div>\u00a0 \u00a0 \u00a0\u00acP \u2192 S (5)<\/div>\n<div>&#8211; Aplicando MP entre (4) e (5), temos:<\/div>\n<div>\u00a0 \u00a0 \u00a0S (6)<\/div>\n<div><\/div>\n<div>Como (6) contradiz (3), conclui-se que a suposi\u00e7\u00e3o inicial (\u00acP) \u00e9 falsa. Logo \u03b2 |\u2013 P c.q.d.<\/div>\n<div><\/div>\n<div><\/div>\n<div><b>DERIVA\u00c7\u00c3O SEM HIP\u00d3TESES<\/b><\/div>\n<div>Al\u00e9m das provas onde uma f\u00f3rmula G \u00e9 derivada a partir de um conjunto de hip\u00f3teses \u03b2 (\u03b2 |\u2013 G), existem casos onde o sistema axiom\u00e1tico n\u00e3o possui hip\u00f3teses (\u03b2 \u00e9 vazio) e a f\u00f3rmula desejada \u00e9 derivada somente a partir dos axiomas, denotamos: |\u2013 G.<\/div>\n<div>Ex: Utilizando um sistema axiom\u00e1tico sem hip\u00f3teses e apenas com Modus Ponens como regra de infer\u00eancia, prove (P \u2228 \u00acP).<\/div>\n<div><\/div>\n<div>&#8211; Para gerar uma senten\u00e7a que contenha a f\u00f3rmula a ser derivada, utilizamos o Ax3 com H = (P \u2228 P), E = \u00acP e G = P, temos:<\/div>\n<div>\u00a0 \u00a0 \u00a0((P \u2228 P) \u2192 P) \u2192 ((\u00acP \u2228 (P \u2228 P)) \u2192 (P \u2228 \u00acP)) (1)<\/div>\n<div>&#8211; Note que a parte antecedente de (1) pode ser gerada a partir de Ax1 para H = P:<\/div>\n<div>\u00a0 \u00a0 \u00a0(P \u2228 P) \u2192 P (2)<\/div>\n<div>&#8211; Aplicando MP entre (2) e (1), temos:<\/div>\n<div>\u00a0 \u00a0 \u00a0 ((\u00acP \u2228 (P \u2228 P)) \u2192 (P \u2228 \u00acP)) (3)<\/div>\n<div>&#8211; A parte antecedente de (3) pode ser gerada a partir de Ax2 para H = P e G = P:<\/div>\n<div>\u00a0 \u00a0 \u00a0\u00acP \u2228 (P \u2228 P) (4)<\/div>\n<div>&#8211; Aplicando MP entre (4) e (3), temos:<\/div>\n<div>\u00a0 \u00a0 \u00a0(P \u2228 \u00acP) c.q.d.<\/div>\n<div><\/div>\n<div><\/div>\n<div><b>Resolu\u00e7\u00e3o<\/b><\/div>\n<div>Ao contr\u00e1rio do sistema axiom\u00e1tico, no m\u00e9todo de resolu\u00e7\u00e3o n\u00e3o se tem axiomas. Portanto, este m\u00e9todo \u00e9 definido pela composi\u00e7\u00e3o dos seguintes elementos:<\/div>\n<div>\u2022 Alfabeto da l\u00f3gica proposicional;<\/div>\n<div>\u2022 Conjunto de cl\u00e1usulas, geradas a partir de f\u00f3rmulas proposicionais (Hip\u00f3teses)<\/div>\n<div>\u2022 Regra de infer\u00eancia.<\/div>\n<div>A resolu\u00e7\u00e3o \u00e9 um m\u00e9todo de prova aplicado sobre f\u00f3rmulas que est\u00e3o na forma de conjun\u00e7\u00f5es de disjun\u00e7\u00f5es, conhecida como forma normal conjuntiva (FNC).<\/div>\n<div>Ex: H = (P \u2228 \u00acQ \u2228 R) \u2227 (R \u2228 Q) \u2227 (\u00acP \u2228 \u00acR \u2228 \u00acP)<\/div>\n<div>Cada f\u00f3rmula \u00e9, ent\u00e3o, representada na forma de conjunto de cl\u00e1usulas (FCC). Nesta nota\u00e7\u00e3o, cada disjun\u00e7\u00e3o \u00e9 um subconjunto (cl\u00e1usula), onde o conectivo ou \u00e9 trocado por uma v\u00edrgula. Al\u00e9m disso, as v\u00edrgulas entre os subconjuntos representam a conjun\u00e7\u00e3o (conectivo e) das disjun\u00e7\u00f5es.<\/div>\n<div>Ex: H = {{P, \u00acQ, R}, {R, Q}, {\u00acP, \u00acR}}<\/div>\n<div>Note que no exemplo acima, {\u00acP, \u00acR} representa (\u00acP \u2228 \u00acR \u2228 \u00acP). Isto ocorre, pois n\u00e3o se representa duplicidade na nota\u00e7\u00e3o de conjuntos (FCC).<\/div>\n<div><\/div>\n<div><b>REGRA DE INFER\u00caNCIA<\/b><\/div>\n<div>O mecanismo de infer\u00eancia da resolu\u00e7\u00e3o utiliza apenas uma regra, denominada regra de resolu\u00e7\u00e3o, como segue:<\/div>\n<div><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.19.43.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-98\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.19.43.png\" alt=\"Captura de Tela 2014-09-22 \u00e0s 19.19.43\" width=\"273\" height=\"65\" \/><\/a><\/div>\n<div><\/div>\n<div><a href=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.19.58.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone  wp-image-99\" src=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.19.58-300x69.png\" alt=\"Captura de Tela 2014-09-22 \u00e0s 19.19.58\" width=\"452\" height=\"104\" srcset=\"https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.19.58-300x69.png 300w, https:\/\/www.uniessa.hiperlogic.com.br\/wp-content\/uploads\/2014\/09\/Captura-de-Tela-2014-09-22-\u00e0s-19.19.58.png 634w\" sizes=\"auto, (max-width: 452px) 100vw, 452px\" \/><\/a><\/div>\n<div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; Identifica\u00e7\u00e3o Formula H F\u00f3rmula G Dupla Negativa \u00ac(\u00acE) E Propriedades de Identidade E \u2228 False E \u2227 True &nbsp; E E &nbsp; Propriedades Complementares E \u2228 \u00ac E E \u2227 \u00ac E True False Leis de DeMorgan \u00ac(E \u2227 R) \u00ac(E \u2228 R) \u00acE \u2228 \u00acR \u00acE \u2227 \u00acR Contraposi\u00e7\u00e3o E \u2192 R \u00acR [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-90","post","type-post","status-publish","format-standard","hentry","category-logica"],"_links":{"self":[{"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=\/wp\/v2\/posts\/90","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=90"}],"version-history":[{"count":1,"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=\/wp\/v2\/posts\/90\/revisions"}],"predecessor-version":[{"id":101,"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=\/wp\/v2\/posts\/90\/revisions\/101"}],"wp:attachment":[{"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=90"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=90"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.uniessa.hiperlogic.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=90"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}