Proposições, conectivos e tautologia na lógica matemática
1) Proposição
Proposição é uma sentença declarativa que pode ter valor de verdade: verdadeiro (V) ou falso (F). Nem toda frase é proposição; por exemplo, perguntas ou expressões sem contexto podem não ter valor lógico definido.
Exemplos interpretados no vídeo: - 2 é primo: verdadeiro. - A Terra é plana: falso. - X é maior que 20: depende do domínio de X, não é uma proposição sem esse contexto. - A inflação será melhor este ano: é uma proposição com valor de verdade atribuído de acordo com o cenário (pode ser verdadeiro ou falso).
Observação: para combinar proposições usamos conectivos lógicos.
2) Conectivos lógicos e valores lógicos
2.1 Negação
A negação inverte o valor lógico de uma proposição: se P é verdadeiro, ¬P é falso, e vice-versa. Cuidados: a negação de frases que dependem de contexto pode não ser simples, por exemplo “vai chover amanhã” pode não ter valor único sem um estado do tempo definido.
2.2 Conjunção
Conjunção (e, representado por ∧) é verdadeira somente quando ambas as proposições são verdadeiras.
2.3 Disjunção
Disjunção (ou, representado por ∨) é verdadeira quando pelo menos uma das proposições é verdadeira. Pode ser inclusiva (qualquer uma) ou exclusiva (somente uma delas, XOR).
2.4 Disjunção exclusiva (XOR)
Disjunção exclusiva (⊕) é verdadeira quando exatamente uma das proposições é verdadeira.
2.5 Condicional
Condicional (se A, então B) é falsa apenas quando A é verdadeira e B é falsa. Leitura comum: A implica B. Pode ser visto como uma relação de antecedente (A) e consequente (B).
2.6 Bicondicional
Bicondicional (A ↔ B) é verdadeiro quando A e B têm o mesmo valor lógico (ambos verdadeiros ou ambos falsos).
2.7 Forma bem formulada (FBF) e precedência
Uma expressão proposicional bem formulada é uma cadeia de proposições e conectivos que resulta em uma proposição. A precedência típica é: negação > conjunção > disjunção > condicional > bicondicional. Parênteses ajudam a esclarecer a ordem de avaliação.
2.8 Proposições compostas e quantas possibilidades existem
Se há n proposições simples, existem 2^n combinações de valores de verdade para avaliá-las. Cada caminho na árvore de avaliação representa uma combinação possível.
3) Tautologia, contradição e equivalência autológica
3.1 Tautologia
Uma tautologia é uma expressão que é verdadeira para qualquer atribuição de valores de verdade. Exemplo clássico: A ∨ ¬A (lei do terceiro excluded) é sempre verdadeira.
3.2 Contradição
Contradição é uma proposição que é falsa em todas as interpretações. Exemplo: A ∧ ¬A (uma afirmação e a sua negação ao mesmo tempo).
3.3 Equivalência autológica
Um bicondicional é autológico quando é verdadeiro em todas as interpretações, ou seja, A ↔ B é uma tautologia. Por exemplo, a equivalência entre A e B pode ser demonstrada por meio de leis lógicas como DeMorgan e leis de identidade.
3.4 Leis úteis (exemplos)
Algumas propriedades importantes são a comutatividade (A ∧ B = B ∧ A), a distributividade (A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)), e os elementos neutros (A ∨ F = A, A ∧ T = A, onde F=false e T=true).
4) Aplicação prática: simplificação de expressões e código
Em prática de programação, usamos a lógica para simplificar condições e gerar código mais eficiente. Por exemplo, combinar leis de De Morgan para simplificar uma expressão de negações, ou distribuir um conectivo para reduzir o número de operações condicionais.
Observação: a prática envolve transformar expressões lógicas em código, levando em conta a eficiência de avaliação e legibilidade.
Questões sobre o assunto
Resposta correta: B) X é maior que 20
Justificativa: para ser proposição é necessário ter um domínio definido para X. Sem o domínio, a frase não é uma proposição; as demais opções são proposições com valor verdadeiro ou falso já atribuível.
Resposta correta: C) ¬A ∨ B
Justificativa: a negação de (A ∧ ¬B) é ¬A ∨ B (Lei de De Morgan). Para a proposição original “A é verdadeira e B é falsa”, a negação é equivalente a “A é falsa ou B é verdadeira”.
Resposta correta: B) Falso
Justificativa: uma proposição condicional A → B é falsa quando A é verdadeira e B é falsa. Aqui A = “Maria tira férias” e B = “Maria vai descansar”; se A é verdadeira e B é falsa, a condicional é falsa.
Resposta correta: A) Verdadeira em todas as interpretações
Justificativa: (A ∨ ¬A) é uma tautologia, e (B ∨ ¬B) também é uma tautologia. Uma tautologia ↔ tautologia resulta em verdadeira em qualquer interpretação.
Texto original
O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.
Texto extraído do video Fundamentos Matemáticos para Computação - Proposições, Representações Simbólicas (Libras)
Olá, alunas e alunos do curso de Fundamentos Matemáticos para a Computação, meu nome é Claudio Fabiano Matatoledo.
Eu vou acompanhar vocês na sua disciplina e neste vídeo aula vamos falar de proposições de representações simbólicas e taltológicas.
Vou começar com uma visão geral, inclusive da disciplina, depois apresentar conectivos e valores lógicos, a ideia de taltologia e contradição e equivalências taltológicas.
Onde a disciplina vai fornecer uma base matemática para auxiliar outros disciplinos como é o caso de projeto de algoritmos e noções de complexidades.
Para isso vamos introduzir os fundamentos de matemática discreta, principalmente considerando conceitos algevicos e lógicos.
Bom, nessa parte de lógica que vamos iniciar hoje, começamos estabelecendo o conceito de proposição, proposição é uma sentença que você consegue atribuir uma valor verdade, ele é falso verdadeiro.
Então 2 é primo, nós sabemos que 2 é divisível por 1 e por ele mesmo logo ao número primo, isso é verdadeiro.
Até a plana, temos já bastante ciência para sustentar o fato de que a terra não é a plana, isso é falso.
X é maior que 20, bom, nós não temos contexto domínio, nós sabemos o domínio de X, então nós não temos como, nós sabemos se X é uma coleção de objetos, se X é uma valor de inteira, então nós não temos uma ideia clara para poder estabelecer isso como uma proposição.
Por outro lado, a pergunta aqui enganhou um jogo, tem mesmo problema, quer dizer, uma pergunta como que eu vou contextualizar isso, né, e atribuir uma valor verdade.
Então, mas não temos como fazer essa tabuíção de valor verdade para ter a pergunta, esqueçam na menos, então não é uma proposição, a proposição.
A inflação será melhor este ano, algumas pessoas podem concordar, que isso seja verdadeiro, da piscenário de Podemia, outras podem descordar, que até o fim do ano ela vai disparar, o fato aqui eu consigo atribuir uma valor verdade, então é uma proposição.
Para compor proposições, nós usamos conectivos, no caso conectivo, e aqui eu estou apresentando aqui para essa ideia de convenção, ou seja, eu quero que a proposição a id ocorra para isso, mas interpretamos este conectivo com uma frase como e, mas também, além disso.
E aí nós temos aqui, Maria dentista é uma gosta de doces, então o a seria uma representação para Maria dentista, o b para a proposição Maria gosta de doces.
E aí nós podemos fazer a composição disso, a Maria dentista ou mans, represento conectivo e, e gosta de doces seria Maria gosta de doces, b, e aí temos, formamente, essa representação para a conjunção a ib.
E analisar os valores verdades, bom, para isso criamos uma tabela verdade com todas as entradas possíveis, onde, se Maria fodentista, e de fato gostar de doces, o que foi estabelecido a verdadeiro, por outro lado, se Maria dentista que não gosta de doces é falso, porque nós supunhamos as duas condições e uma delas não ocorre.
Então é falso.
O contrário, a mesma coisa, se Maria não é dentista, e gosta de doces, uma das condições não é satisfeita, então o que foi dito, não ocorra já que supunha Maria dentista e Maria gostando de doces.
Nesse caso, se Maria não é dentista e não gosta de doces, também vai ser falso, ou seja, sempre falso quando, pelo menos, uma das condições não se desverifica.
Na conjunção, na conjunção, temos a ideia do ouro, ou inclusive.
Então esse simbolo aqui, e a frase então ficaria, Maria dentista ou gosta de doces, nesse caso, basta uma das condições ocorrer.
Então, se Maria dentista, e de fato gosta de doces, cria da dê, mas se Maria dentista e não gosta de doces, continua válido, porque queremos uma proposição ou outra que acontecem.
Se Maria não é dentista, e gosta de doces, continua válido, só vai ser falso se as duas condições não se desverificarem.
Certo, então é sempre verdadeiro quando uma das condições se verifica no ouro, inclusive.
No ouro, exclusivo, conhecido como show, short, english, temos esses dois símbolos que você vão encontrar no livro para representar, e considera-se intensa.
Neste momento, João toca piano ou João toca guitarra? Nesse caso, nós estamos de supronto que, ou ele está no estado de toca piano ou no estado de toca guitarra? Se João toca piano e toca guitarra no ejo tempo, isso não faz sentido, porque nesse momento ele vai estar fazendo uma coisa ou a outra, exclusivamente.
Se ele toca piano e não toca guitarra, coerente com a proposição, a proposição se mostra se ele não toca piano, mas toca guitarra, a mesma coisa.
Agora, por outro lado, se ele não toca piano e não toca guitarra, ele era supposed que está em um dos estados, e ele não está.
Nesse momento, então é falso.
Bom, a negação faz uma inversão da proposição.
São, se Maria dentista é a proposição dada, a negação disso, Maria não é dentista.
Nós invertemos o valor verdade.
É a verdadeira, é falso, é falso, é verdadeiro.
Só que temos que tomar alguns cuidados.
Por exemplo, negar que vai fazer só amanhã seria não fazer só amanhã, uma negação válida, ou é falso que vai fazer só amanhã.
Agora, afirma como contra ponto que vai chover amanhã não seria uma negação correta, seria uma negação correta, já que, por exemplo, poderia estar no lado.
Então, temos que ter esses cuidados em lógica.
Outro caso, você comprou um joginho e ele é difícil e caro essa sua proposição.
Negar isso não é dizer que o jogo não é difícil e não é caro.
Porque lembre-se, basta que uma das condições não se verifique para isso que cai em válida, digamos assim.
Então, negar isso vai nessa linha, ou seja, o jogo não é difícil ou não é caro.
Essa seria uma negação correta, ou, se você quer usar um ontônimo, mesmo a coisa, você não vai poder afirmar o jogo é fácil e barato, e sim o jogo é fácil ou barato.
Bom, no condicional, nós temos uma ideia de uma situação levando a outra.
Por exemplo, se Maria tira férias, então ela vai descansar.
Então, a seria Maria tira férias, onde chamamos isso de antecedente, e B seria Maria descansar, que é o consequente.
Então, nós temos a verdade a implicando levando a verdade B.
Podemos fazer a leitura de A e B como C, A, então B.
Se margaram a verdade de A, se Maria tira férias, então ela vai descansar.
Se ela tira férias e descansar, o que foi dito é verdadeiro.
A férias levou Maria descansar.
Se por outro lado, Maria tira férias e não descansar significa que, o que foi estabelecido é falso.
Por outro lado, se Maria não tira férias, nós não temos como verificar essa relação de Maria tira férias levar ela a descansar.
Então, essa proposição continua sempre poder ser verificada, então, a princípio é a verdadeira.
Mesma coisa, Maria não tira férias e Maria não descansar.
Não muda nada.
Essa primeira proposição não foi verificada para a gente avaliar o consequente dela.
Então, continua valendo.
Falsos e falsos, mas o resultado é verdadeiro.
Nesse contexto, diferentes formas em português, nós passamos essa ideia.
Se a, então, b, a condicional a b, ou de interpretar isso, melhor dizer, a louco b, a só c b, ocorre, a somente c b ocorre, b segue de a, é uma condição suficiente para b, ou seja, basta a para verificarmos b.
B é uma condição necessária para a, uma vez que a foi verificada.
Então, tudo isso é uma, nos ajuda a começar a ter essa noção da implicação e os exercícios é claro, vamos ajudar a trabalhar as seis ideias.
Essa ideia.
O b, condicional, ele, ele atua de seguinte forma.
Você tem o condicional na ida e na volta, vamos pensar assim.
Maria corda cedo sem somente cedo chega no horário ao trabalho.
Então, nós temos Maria corda cedo e Maria chega no horário a nos proposições.
Então, a, sei somente c b, a condição necessária é suficiente para b, e como que ficou a louca verdade disso? Nós avaliamos a ida e a volta.
E o b, condicional, é a conjunção disso, a implicando em b e bem implicando em a.
Então, dessa forma nós vamos ter, verdadeiro, falso, falso e verdadeiro.
Então, observe que para interpretar o b, condicional, olhando as entradas, nós observamos que, quando os valores verdade são idênticos, o resultado do b, condicional é verdadeiro.
Quando os valores verdade são diferentes, o resultado do b, condicional é falso.
Bom, agora que temos a noção dos conectivos, podemos estabelecer, forma representações mais complexas e aí temos o conceito de forma uma bem formulada, que é uma cadeia que forma uma expressão válida.
Então, por exemplo, aqui temos uma expressão válida ou joão estuda ou joão trabalho.
Além disso, ele gosta de cozinhar.
Então, temos a para joão estuda, o conectivo ou b pro joão trabalho, repare que isso conectivo ou aqui é só para passar a ideia de junção.
Além disso, ou o ponto passando a ideia do ir, ele gosta de cozinhar.
C, é o próprio ele, o próprio joão.
Então, nesse caso, nós teríamos essa representação matemática, onde isso aqui forma uma proposição e essa aqui é uma outra proposição, compomba essa fórmula bem formulada.
E para isso, então, eu estou a dar essa importante estabelecer a ordem de precedência.
Então, para conectivos dentro de vários parentes, as efetoras e primeiras expressões dentro dos parentes mais internos.
Depois de umas avaliantes, a negação, com prioridade, sobre conjunção e de junção, depois o condicional, depois o bicondicional.
Então, por exemplo, uma maneira de você enxergar essa expressão, seria que você primeiro aplica a negação, depois a avalia a de junção.
E não essa forma, a negação não está aplicada a expressão como um todo.
Na proposição abaixo, nessa FBF aqui, nós vamos ter que primeiro vamos avaliar, além de se ou, para depois o condicional.
Então, nesse caso, você avalia a de junção para depois avaliar a implicação.
Essa interpretação não segue a precedência estabelecida, está errado.
Bom, nesse caso, quando mais nós, é claro, podemos usar os parentes para estabelecermos a nossa precedência.
E temos que podermos identificar nas FBFs os conectivos principais, como é o caso que o ou eu conectivo principal, o mais interno é a implicação.
O condicional, depois temos aqui a negação e o nudo tudo como o conectivo principal ou o outro.
Aqui também temos essa, identificamos essa expressão conectada pelo conectivo principal a essa segunda, e internamente os parentes temos esse e o ou, depois vamos ter aqui uma negação e uma outra implicação.
Bom, e quantos valores verdade são possíveis, dependendo da quantidade de proposições simples que está beleço? Então, se eu tenho uma proposição, ela vai ser verdadeira ou falsa.
Se eu tenho duas proposições, eu já passo a compor isso com quatro possibilidades.
Três proposições, minha lavanka, eu sei, eu estou sempre dobrando agora, oito possibilidades.
Então, observe que, quando eu falo de possibilidades, a maneira de você entender essa árvore, que para cada caminho que eu sigo, eu vou ter uma composição, uma entrada diferentes.
Então, para três proposições simples, eu vou ter todas essas entradas possíveis, como representadas por cada caminho que eu sigo aqui nessa árvore.
Então, para n proposições, como já deu para perceber aqui, eu vou ter dois elevado a n resultados possíveis de combinações para avaliar.
Bom, e aí, chegamos ao conceito de tautologia, que é uma maneira de gente estar verificando o significado dessas expressões.
Por exemplo, uma tautologia, ela é uma forma ou proposição que é sempre verdadeira, para qualquer tipo de interpretação possível.
Ou seja, Maria é médica ou Maria não é médica, quer dizer, é estranho isso, né? É como você pegasse um conjunto e o complementar dele, e o início, você tem tudo.
Então, observe verdadeiro e falso, falso e verdadeiro, compostos num ouro.
Então, nessa forma, isso aqui, esse resultado é sempre verdadeiro, não é minha tabela verdade? Fazendo com que essa expressão aqui seja uma expressão, uma forma que eu classifique como tautológica, representa uma tautologia.
Outro exemplo, amanhã não vai chover, amanhã vai chover ou o céu estar azul.
Portanto, o céu estar azul.
Então, eu tenho aqui a negação, não vai chover.
Vai chover o céu estar azul e o céu estar azul aparecendo novamente.
Ou seja, eu compone isso, ponto e com essa expressão ou essa aqui entre parênteses.
E tudo isso aqui, implicando no céu estar azul.
Dessa forma, quando eu vou avaliar essa tabela verdade, eu tenho que fazer.
Eu tenho, reparem que eu tenho o anegado, já se refere ao A, é uma aplicação sobre A.
Então, eu tenho duas proposições, o que eu vou me dar quatro entradas possíveis.
Então, eu compone o A, o B, compone o anegado e o A, o B.
E depois faço o resultado da implicação.
Que nesse caso, observe isso aqui, implicando em B, falsa e falsa.
É suposto verdadeiro, verdadeiro.
Eu verifico aqui que cala, implicou em verdadeiro.
Então, é verdadeiro.
E aqui é falsa o que já impõe a proposta, mantenha a propostação como faredade.
E eu tenho uma tautologia.
Na contradição, a forma ou a propostação, ela vai ser sempre falsa.
Para qualquer tipo de interpretação possível.
Então, por exemplo, Maria é médica e Maria não é médica.
Caramba, eu não vou conseguir ter os dois estados ao mesmo tempo.
Então, nesse caso, aqui compondo com o E, um exemplo bem claro, nós verificamos a contradição da proposição.
Então, você quer dois estados contradiórios.
Então, com outro exemplo disso, está aqui nessa implicação.
Eu tenho, já mantei aqui, parte da tabela, o que nós vamos ter? Nós vamos compor o A ou não A, o que me leva, o A ou não A, tudo verdadeiro, o B e o não B, tudo falso.
E isso, implicando isso, o que vai acontecer? Vai ser tudo falso.
Então, eu tenho uma contradição.
Porque está cada evento do antecedente, o consequente não se verifica, tudo falso, contradição.
Uma equivalência autológica é que ele ocorre quando essa bi-condicional é uma autologia.
Então, nós representamos uma bi-condicional autológica com essa expressão, que chama-nos de uma equivalência autológica.
Para indicar que é a proposição A, é equivalente a proposição B.
Ou seja, eu posso usar tanto A como B, porque ele se equivale.
Então, podemos substituir A pro B ou vice-versa.
Por exemplo, esse é o caso da lei de morga onde negar uma de junção significa negar cada termo de uma conjução.
Então, o que eu vou ter aqui? Eu vou ter o N, A, N, B, faço um A ou B aqui, nego A ou B.
Então, eu vou sempre montando passo a passo cada termo da minha autologia e agora eu tenho o que não há, eu não bebo.
Em seguida, quando estabeleço a equivalência, observe que esse meu primeiro termo, eu faço falso falso verdadeiro e esse meu segundo termo, falso falso verdadeiro.
Valores verdades iguais num bi-condicional é sempre verdadeiro.
Então, isso aqui é uma autologia e esse bi-condicional é uma equivalência estabeleço, uma equivalência autológica conhecida como lei de demórter.
Então, nós vamos ter algumas propriedades representadas por equivalência autológica.
Como é o caso da comunitatividade? Quando trocamos a ordem dos fatores, de junção ou conjução, a sociedade quer, quando distribuímos, mudamos a ordem dos parentes, quando todos os conteúdos são iguais, então isso não faz nenhuma alteração, expressão aqui vale a outra.
Temos a distributividade que, quando distribuímos aqui, por exemplo, nós temos dois conectivos diferentes, então eu distribuo aqui para dentro.
Então, essa expressão aqui, que valente é essa aqui e vice-versa, a mesma coisa que quando o e está do lado de fora, eu passo distribuo ele para dentro da expressão.
Elemento neutro, que é quando eu compõe aqui com o zero representando a situação sempre falso, uma situação sempre verdadeira, então, a ou o falso é sempre a, a in verdadeiro vai resultar em a, e o complementar a e não a é um, a ou não a é um, e a e não a é falso zero, como a gente viu nos exemplos anteriores.
Então, aqui só para verificar, nós temos o 1, sempre verdadeiro, 0, como sempre falso, o a e um verdadeiro e falso, replicando os jorudo-desdeedades do a, o a e não a sempre falso, o a e um equivalente ao a, vai ser sempre verdadeiro, e o a e não a equivalente ao falso sempre verdadeiro, que faz com que isso aqui seja uma equivalência autológica.
Onde essa forma, nós temos aqui expressões do tipo, nós podemos fazer uma aplicação disso, usando códigos, então, por exemplo, se a pressão inicial foi maior que a pressão final, e não temos a pressão inicial com maior que a final, a interpretaira maior que 20, não tem a interpretação disso, eu faço comando 1, senão eu faço comando 2.
A minha proposição seria pressão inicial, maior que pressão final, e temperatura maior que 20.
Nesse caso, o que vai acontecer? Eu tenho 1 a aqui, e negação de a e b, beleza? Temos essa proposa, essa f d, f d, f aqui.
Só que, se ela é que eu consigo simplificar ela, então o que vai acontecer? Ou, os vezes equivalências autológicas, nós vamos fazer aqui nossa primeira demonstração, para dentrozir uma expressão mais simples.
Aplicando a lei de demorga, eu troco a valoridade do a e b, para não a ou não b, a partir da negação.
Em seguida, eu utilizo a distributiva aqui, tem uma contradição e tem um elemento neutro, esse, o falso, ou, essa proposição, vai dar a própria proposição.
Dessa forma, eu saio dessa expressão e chego numa expressão mais simples, que significa representar o meu código do ponto de vista lógico com essa forma, ou seja, eu gero um código mais simples.
Bom, todos esses conceitos foram retirado da sessão 1.
1 do nosso material base, e espero que vocês estudem essa parte, e com isso encerramos a nossa primeira videoal.
