No mundo de hoje, usamos cada vez mais uma variedade de carros e gadgets. E não apenas quando é necessário aplicar uma força literalmente desumana: mover a carga, levantá-la a uma altura, cavar uma vala longa e profunda etc. realizado por calculadoras. Cada vez mais ouvimos a expressão "álgebra booleana". Talvez seja hora de entender o papel do homem na criação de robôs e a capacidade das máquinas de resolver não apenas problemas matemáticos, mas também lógicos.
Lógica
Traduzida do grego, a lógica é um sistema ordenado de pensamento que cria relações entre determinadas condições e permite tirar conclusões com base em premissas e suposições. Muitas vezes perguntamos uns aos outros: "É lógico?" A resposta recebida confirma nossas suposições ou critica a linha de pensamento. Mas o processo não para: continuamos a raciocinar.
Às vezes o número de condições (introdutórias) é tão grande, e as relações entre elas são tão intrincadas e complexas que o cérebro humano não é capaz de "digerir" tudo de uma vez. Pode levar mais de um mês (semana, ano) para entender o que está acontecendo. Masa vida moderna não nos dá esses intervalos de tempo para tomar decisões. E recorremos à ajuda dos computadores. E é aí que surge a álgebra da lógica, com suas próprias leis e propriedades. Ao baixar todos os dados iniciais, permitimos que o computador reconheça todas as relações, elimine contradições e encontre uma solução satisfatória.
Matemática e Lógica
O famoso Gottfried Wilhelm Leibniz formulou o conceito de "lógica matemática", cujos problemas eram compreensíveis apenas para um círculo restrito de cientistas. Essa direção não despertou interesse particular e, até meados do século 19, poucas pessoas sabiam sobre lógica matemática.
O grande interesse da comunidade científica gerou uma disputa em que o inglês George Boole anunciou sua intenção de criar um ramo da matemática que não tem absolutamente nenhuma aplicação prática. Como lembramos da história, a produção industrial estava se desenvolvendo ativamente naquela época, todos os tipos de máquinas auxiliares e máquinas-ferramentas estavam sendo desenvolvidas, ou seja, todas as descobertas científicas tinham um foco prático.
Olhando adiante, digamos que a álgebra booleana é a parte da matemática mais usada no mundo moderno. Então Bull perdeu seu argumento.
George Buhl
A própria personalidade do autor merece atenção especial. Mesmo considerando que no passado as pessoas cresciam antes de nós, ainda é impossível não notar que, aos 16 anos, J. Buhl lecionava em uma escola da aldeia e, aos 20 anos, abriu sua própria escola em Lincoln. O matemático era fluente em cinco línguas estrangeiras e, em seu tempo livre, lia obrasNewton e Lagrange. E tudo isso é sobre o filho de um simples trabalhador!
Em 1839 Boole submeteu seus trabalhos científicos pela primeira vez ao Cambridge Mathematical Journal. O cientista tem 24 anos. O trabalho de Boole interessou tanto os membros da Royal Society que em 1844 ele recebeu uma medalha por sua contribuição ao desenvolvimento da análise matemática. Vários outros trabalhos publicados, que descreviam os elementos da lógica matemática, permitiram ao jovem matemático assumir o cargo de professor no Cork County College. Lembre-se que o próprio Buhl não teve educação.
Ideia
Em princípio, a álgebra booleana é muito simples. Existem afirmações (expressões lógicas) que, do ponto de vista da matemática, podem ser definidas apenas por duas palavras: “verdadeiro” ou “falso”. Por exemplo, na primavera as árvores florescem - é verdade, no verão neva - uma mentira. A beleza dessa matemática é que não há necessidade estrita de usar apenas números. Quaisquer declarações com um significado inequívoco são bastante adequadas para a álgebra de julgamentos.
Assim, a álgebra da lógica pode ser usada literalmente em todos os lugares: na programação e na escrita de instruções, na análise de informações conflitantes sobre eventos e na determinação da sequência de ações. A coisa mais importante é entender que é completamente sem importância como determinamos a verdade ou falsidade da afirmação. Esses "comos" e "porquês" precisam ser abstraídos. Apenas a declaração do fato importa: verdadeiro-falso.
Claro que, para programação, são importantes as funções da álgebra da lógica, que são escritas pelo correspondentesinais e símbolos. E aprendê-los significa dominar uma nova língua estrangeira. Nada é impossível.
Conceitos básicos e definições
Sem entrar em profundidade, vamos lidar com a terminologia. Então a álgebra booleana assume:
- instruções;
- operações lógicas;
- funções e leis.
Declarações são quaisquer expressões afirmativas que não podem ser interpretadas de forma ambígua. Eles são escritos como números (5 > 3) ou formulados em palavras familiares (o elefante é o maior mamífero). Ao mesmo tempo, a frase “a girafa não tem pescoço” também tem o direito de existir, apenas a álgebra booleana a definirá como “falsa”.
Todas as declarações devem ser inequívocas, mas podem ser elementares e compostas. Os últimos usam conectivos lógicos. Ou seja, na álgebra dos julgamentos, os enunciados compostos são formados pela adição de enunciados elementares por meio de operações lógicas.
Operações de álgebra booleana
Já nos lembramos que as operações na álgebra de julgamentos são lógicas. Assim como a álgebra numérica usa a aritmética para somar, subtrair ou comparar números, os elementos da lógica matemática permitem que você faça declarações complexas, negue ou calcule o resultado final.
As operações lógicas para formalização e simplicidade são escritas por fórmulas que nos são familiares em aritmética. As propriedades da álgebra booleana permitem escrever equações e calcular incógnitas. As operações lógicas geralmente são escritas usando uma tabela verdade. Suas colunasdefinem os elementos do cálculo e a operação que é realizada neles, e as linhas mostram o resultado do cálculo.
Ações lógicas básicas
As operações mais comuns em álgebra booleana são negação (NOT) e AND e OR lógicos. Quase todas as ações na álgebra de julgamentos podem ser descritas dessa maneira. Vamos estudar cada uma das três operações com mais detalhes.
Negação (não) se aplica a apenas um elemento (operando). Portanto, a operação de negação é chamada unária. Para escrever o conceito de "não A" use os seguintes símbolos: ¬A, A¯¯¯ ou !A. Em forma de tabela fica assim:
A função de negação é caracterizada pela seguinte afirmação: se A é verdadeiro, então B é falso. Por exemplo, a Lua gira em torno da Terra - verdade; A terra gira em torno da lua - falso.
Multiplicação lógica e adição
O AND lógico é chamado de operação de conjunção. O que isso significa? Em primeiro lugar, que pode ser aplicado a dois operandos, ou seja, E é uma operação binária. Em segundo lugar, que somente no caso da verdade de ambos os operandos (ambos A e B) a expressão em si é verdadeira. O provérbio "Paciência e trabalho vão moer tudo" sugere que apenas os dois fatores ajudarão a pessoa a lidar com as dificuldades.
Símbolos usados para escrever: A∧B, A⋅B ou A&&B.
Conjunção é semelhante à multiplicação na aritmética. Às vezes eles dizem isso - multiplicação lógica. Se multiplicarmos os elementos da tabela linha por linha, obtemos um resultado semelhante ao raciocínio lógico.
Disjunção é uma operação lógica OR. Leva o valor da verdadequando pelo menos uma das afirmações for verdadeira (A ou B). É escrito assim: A∨B, A+B ou A||B. As tabelas verdade para essas operações são:
Disjunção é como adição aritmética. A operação de adição lógica tem apenas uma limitação: 1+1=1. Mas lembramos que em formato digital, a lógica matemática é limitada a 0 e 1 (onde 1 é verdadeiro, 0 é falso). Por exemplo, a afirmação “em um museu você pode ver uma obra-prima ou conhecer um interlocutor interessante” significa que você pode ver obras de arte ou conhecer uma pessoa interessante. Ao mesmo tempo, a possibilidade de ambos os eventos ocorrerem simultaneamente não é descartada.
Funções e leis
Então, já sabemos quais operações lógicas a álgebra booleana usa. As funções descrevem todas as propriedades dos elementos da lógica matemática e permitem simplificar condições compostas complexas de problemas. A propriedade mais compreensível e simples parece ser a rejeição de operações derivadas. As derivadas são OR exclusivo, implicação e equivalência. Como estudamos apenas as operações básicas, também consideraremos as propriedades apenas delas.
Associatividade significa que em declarações como "e A, e B e C", a ordem dos operandos não importa. A fórmula é escrita assim:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Como você pode ver, isso é característico não só da conjunção, mas também da disjunção.
Comutatividade afirma que o resultadoconjunção ou disjunção não depende de qual elemento foi considerado primeiro:
A∧B=B∧A; A∨B=B∨A.
Distributividade permite expandir parênteses em expressões lógicas complexas. As regras são semelhantes a abrir colchetes na multiplicação e adição em álgebra:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
As propriedades de um e zero, que podem ser um dos operandos, também são semelhantes à multiplicação algébrica por zero ou um e adição por um:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotência nos diz que se, em relação a dois operandos iguais, o resultado de uma operação for semelhante, podemos “jogar fora” os operandos extras que complicam o curso do raciocínio. Tanto a conjunção quanto a disjunção são operações idempotentes.
B∧B=B; B∨B=B.
Absorção também nos permite simplificar equações. Absorção afirma que quando outra operação com o mesmo elemento é aplicada a uma expressão com um operando, o resultado é o operando da operação de absorção.
A∧B∨B=B; (A∨B)∧B=B.
Sequência de operações
A sequência de operações não é de pouca importância. Na verdade, quanto à álgebra, há uma prioridade de funções que a álgebra booleana usa. As fórmulas podem ser simplificadas somente se a significância das operações for observada. Ordenando do mais significativo para o menos, obtemos a seguinte sequência:
1. Negação.
2. Conjunção.
3. Disjunção, exclusivoOU.
4. Implicação, equivalência.
Como você pode ver, apenas a negação e a conjunção não têm igual precedência. E a prioridade de disjunção e XOR são iguais, assim como as prioridades de implicação e equivalência.
Funções de implicação e equivalência
Como já dissemos, além das operações lógicas básicas, a lógica matemática e a teoria dos algoritmos usam derivadas. Os mais usados são implicação e equivalência.
Implicação, ou consequência lógica, é uma declaração na qual uma ação é uma condição e a outra é uma consequência de sua implementação. Em outras palavras, esta é uma frase com preposições "se… então". "Se você gosta de andar, ame andar de trenó." Ou seja, para esquiar, você precisa apertar o trenó morro acima. Se não há desejo de descer a montanha, você não precisa carregar o trenó. Está escrito assim: A→B ou A⇒B.
Equivalência assume que a ação resultante ocorre somente quando ambos os operandos são verdadeiros. Por exemplo, a noite se transforma em dia quando (e somente quando) o sol nasce no horizonte. Na linguagem da lógica matemática, esta declaração é escrita da seguinte forma: A≡B, A⇔B, A==B.
Outras leis da álgebra booleana
A álgebra dos julgamentos está se desenvolvendo, e muitos cientistas interessados formularam novas leis. Os postulados do matemático escocês O. de Morgan são considerados os mais famosos. Ele notou e definiu propriedades como negação próxima, complemento e negação dupla.
Fechar negação significa que não há negação antes do parêntese:não (A ou B)=não A ou NÃO B.
Quando um operando é negado, independente de seu valor, fala-se de um complemento:
B∧¬B=0; B∨¬B=1.
E finalmente, a dupla negação compensa a si mesma. Aqueles. ou a negação desaparece antes do operando, ou apenas um permanece.
Como resolver testes
Lógica matemática implica a simplificação de equações dadas. Assim como na álgebra, você deve primeiro tornar a condição o mais fácil possível (livrar-se de entradas e operações complexas com elas) e então começar a procurar a resposta certa.
O que pode ser feito para simplificar? Converta todas as operações derivadas em simples. Em seguida, abra todos os colchetes (ou vice-versa, retire-o dos colchetes para encurtar esse elemento). O próximo passo deve ser aplicar as propriedades da álgebra booleana na prática (absorção, propriedades de zero e um, etc.).
Em última análise, a equação deve consistir no número mínimo de incógnitas combinadas por operações simples. A maneira mais fácil de encontrar uma solução é obter um grande número de negativos próximos. Então a resposta aparecerá como se fosse por si mesma.
