Lógica de muitos valores - Many-valued logic

Na lógica , uma lógica de muitos valores (também a lógica de vários ou vários valores ) é um cálculo proposicional no qual existem mais de dois valores verdade . Tradicionalmente, em Aristóteles 's cálculo lógico , havia apenas dois valores possíveis (ou seja, 'verdadeiro' e 'falso') para qualquer proposição . Classical lógica de dois valores pode ser alargado para n lógica -valued para n maior do que 2. Os mais populares na literatura são de três valores (por exemplo, de Łukasiewicz e Kleene do que aceitar os valores "verdadeiro", "falso", e " desconhecido "), o valor finito ( valor finito-muitos) com mais de três valores, e o valor infinito ( valor infinito-muitos), como lógica difusa e lógica de probabilidade .

História

O primeiro lógico clássico conhecido que não aceitou totalmente a lei do terceiro excluído foi Aristóteles (que, ironicamente, também é geralmente considerado o primeiro lógico clássico e o "pai da lógica"). Aristóteles admitiu que suas leis não se aplicavam a eventos futuros ( De Interpretatione , cap. IX ), mas ele não criou um sistema de lógica multivalorada para explicar esta observação isolada. Até o advento do século 20, os lógicos posteriores seguiram a lógica aristotélica , que inclui ou pressupõe a lei do terceiro excluído .

O século 20 trouxe de volta a ideia da lógica multivalorada. O lógico e filósofo polonês Jan Łukasiewicz começou a criar sistemas de lógica de muitos valores em 1920, usando um terceiro valor, "possível", para lidar com o paradoxo de Aristóteles da batalha naval . Enquanto isso, o matemático americano Emil L. Post (1921) também introduziu a formulação de graus de verdade adicionais com n  ≥ 2, onde n são os valores de verdade. Mais tarde, Jan Łukasiewicz e Alfred Tarski juntos formularam uma lógica sobre n valores de verdade onde n  ≥ 2. Em 1932, Hans Reichenbach formulou uma lógica de muitos valores de verdade onde n → ∞. Kurt Gödel em 1932 mostrou que a lógica intuicionista não é uma lógica com muitos valores finitos e definiu um sistema de lógica de Gödel intermediário entre a lógica clássica e intuicionista; tais lógicas são conhecidas como lógicas intermediárias .

Exemplos

Kleene (forte) K ₃ e lógica do sacerdote P ₃

Kleene 's 'lógica (forte) de indeterminação' K ₃ (às vezes ) e Priest ' s 'lógica do paradoxo' adicionar um terceiro 'indefinido' ou 'indeterminada' valor de verdade eu . As funções de verdade para negação (¬), conjunção (∧), disjunção (∨), implicação (${\ displaystyle K_ {3} ^ {S}}$→K) e bicondicional (↔K) são fornecidos por:

¬   T F eu eu F T

∧ T eu F T T eu F eu eu eu F F F F F

∨ T eu F T T T T eu T eu eu F T eu F

→K T eu F T T eu F eu T eu eu F T T T

↔K T eu F T T eu F eu eu eu eu F F eu T

A diferença entre as duas lógicas está em como as tautologias são definidas. Em K ₃ única T é um valor designado verdade , enquanto em P ₃ tanto T e I são (uma fórmula lógica é considerado um tautologia se for avaliado como um valor verdade designado). Na lógica de Kleene I pode ser interpretada como sendo "indeterminada", não sendo nem verdadeiro nem falso, enquanto na lógica de Priest I pode ser interpretada como sendo "sobredeterminado", sendo verdadeira e falsa. K ₃ não tem nenhuma tautologia, enquanto P ₃ tem as mesmas tautologias que a lógica clássica de dois valores.

A lógica interna de três valores de Bochvar

Outra lógica é a lógica de três valores "interna" de Dmitry Bochvar , também chamada de lógica de três valores fraca de Kleene. Exceto para negação e bicondicional, suas tabelas de verdade são todas diferentes das anteriores. ${\ displaystyle B_ {3} ^ {I}}$

∧+ T eu F T T eu F eu eu eu eu F F eu F

∨+ T eu F T T eu T eu eu eu eu F T eu F

→+ T eu F T T eu F eu eu eu eu F T eu T

O valor de verdade intermediário na lógica "interna" de Bochvar pode ser descrito como "contagioso" porque se propaga em uma fórmula independentemente do valor de qualquer outra variável.

Lógica de Belnap ( B ₄ )

A lógica B _{4 de} Belnap combina K ₃ e P ₃ . O valor verdade sobredeterminado é aqui denotado como B e o valor de verdade subdeterminada como N .

f ¬   T F B B N N F T

f ∧ T B N F T T B N F B B B F F N N F N F F F F F F

f ∨ T B N F T T T T T B T B T B N T T N N F T B N F

Lógicas de Gödel G _k e G _∞

Em 1932, Gödel definiu uma família de lógicas de muitos valores, com muitos valores de verdade finitos , por exemplo, tem os valores de verdade e tem . De maneira semelhante, ele definiu uma lógica com infinitos valores de verdade , em que os valores de verdade são todos os números reais no intervalo . O valor de verdade designado nessas lógicas é 1. ${\ displaystyle G_ {k}}$${\ displaystyle 0, {\ tfrac {1} {k-1}}, {\ tfrac {2} {k-1}}, \ ldots, {\ tfrac {k-2} {k-1}}, 1 }$${\ displaystyle G_ {3}}$${\ displaystyle 0, {\ tfrac {1} {2}}, 1}$${\ displaystyle G_ {4}}$${\ displaystyle 0, {\ tfrac {1} {3}}, {\ tfrac {2} {3}}, 1}$${\ displaystyle G _ {\ infty}}$${\ displaystyle [0,1]}$

A conjunção e a disjunção são definidas respectivamente como o mínimo e o máximo dos operandos: ${\ displaystyle \ wedge}$${\ displaystyle \ vee}$

${\ displaystyle {\ begin {alinhado} u \ wedge v &: = \ min \ {u, v \} \\ u \ vee v &: = \ max \ {u, v \} \ end {alinhado}}}$

Negação e implicação são definidas da seguinte forma: ${\ displaystyle \ neg _ {G}}$${\ displaystyle {\ xrightarrow [{G}] {}}}$

${\ displaystyle {\ begin {alinhado} \ neg _ {G} u & = {\ begin {cases} 1, & {\ text {if}} u = 0 \\ 0, & {\ text {if}} u> 0 \ end {casos}} \\ u {\ xrightarrow [{G}] {}} v & = {\ begin {cases} 1, & {\ text {if}} u \ leq v \\ v, & {\ texto {if}} u> v \ end {casos}} \ end {alinhado}}}$

As lógicas de Gödel são completamente axiomatizáveis, isto é, é possível definir um cálculo lógico no qual todas as tautologias são prováveis.

Łukasiewicz lógicas L _v e L _∞

Implicação e negação foram definidas por Jan Łukasiewicz por meio das seguintes funções: ${\ displaystyle {\ xrightarrow [{L}] {}}}$${\ displaystyle {\ underset {L} {\ neg}}}$

${\ displaystyle {\ begin {align} {\ underset {L} {\ neg}} u &: = 1-u \\ u {\ xrightarrow [{L}] {}} v &: = \ min \ {1,1 -u + v \} \ end {alinhado}}}$

No início, Łukasiewicz usou essas definições em 1920 para sua lógica de três valores , com valores de verdade . Em 1922, ele desenvolveu uma lógica com infinitos valores , em que os valores verdadeiros abrangiam os números reais no intervalo . Em ambos os casos, o valor verdade designado foi 1. ${\ displaystyle L_ {3}}$${\ displaystyle 0, {\ tfrac {1} {2}}, 1}$${\ displaystyle L _ {\ infty}}$${\ displaystyle [0,1]}$

Ao adotar valores de verdade definidos da mesma forma que para a lógica de Gödel , é possível criar uma família de lógicas de valor finito , a citada acima e a lógica , em que os valores de verdade são dados pelos números racionais no intervalo . O conjunto de tautologias em e é idêntico. ${\ displaystyle 0, {\ tfrac {1} {v-1}}, {\ tfrac {2} {v-1}}, \ ldots, {\ tfrac {v-2} {v-1}}, 1 }$${\ displaystyle L_ {v}}$${\ displaystyle L _ {\ infty}}$${\ displaystyle L _ {\ aleph _ {0}}}$${\ displaystyle [0,1]}$${\ displaystyle L _ {\ infty}}$${\ displaystyle L _ {\ aleph _ {0}}}$

Lógica do produto Π

Na lógica do produto, temos valores de verdade no intervalo , uma conjunção e uma implicação , definidos como segue ${\ displaystyle [0,1]}$${\ displaystyle \ odot}$${\ displaystyle {\ xrightarrow [{\ Pi}] {}}}$

${\ displaystyle {\ begin {alinhado} u \ odot v &: = uv \\ u {\ xrightarrow [{\ Pi}] {}} v &: = {\ begin {cases} 1, & {\ text {if}} u \ leq v \\ {\ frac {v} {u}}, & {\ text {if}} u> v \ end {casos}} \ end {alinhado}}}$

Além disso, há um valor designado negativo que denota o conceito de falso . Por meio desse valor é possível definir uma negação e uma conjunção adicional da seguinte forma: ${\ displaystyle {\ overline {0}}}$${\ displaystyle {\ underset {\ Pi} {\ neg}}}$${\ displaystyle {\ underset {\ Pi} {\ wedge}}}$

${\ displaystyle {\ begin {align} {\ underset {\ Pi} {\ neg}} u &: = u {\ xrightarrow [{\ Pi}] {}} {\ overline {0}} \\ u {\ underset {\ Pi} {\ wedge}} v &: = u \ odot (u {\ xrightarrow [{\ Pi}] {}} v) \ end {alinhado}}}$

e então . ${\ displaystyle u {\ underset {\ Pi} {\ wedge}} v = \ min \ {u, v \}}$

Pós lógicas P _m

Em 1921 Post definiu uma família de lógicas com (como em e ) os valores de verdade . Negação e conjunção e disjunção são definidas da seguinte forma: ${\ displaystyle P_ {m}}$${\ displaystyle L_ {v}}$${\ displaystyle G_ {k}}$${\ displaystyle 0, {\ tfrac {1} {m-1}}, {\ tfrac {2} {m-1}}, \ ldots, {\ tfrac {m-2} {m-1}}, 1 }$${\ displaystyle {\ underset {P} {\ neg}}}$${\ displaystyle {\ underset {P} {\ wedge}}}$${\ displaystyle {\ underset {P} {\ vee}}}$

${\ displaystyle {\ begin {align} {\ underset {P} {\ neg}} u &: = {\ begin {cases} 1, & {\ text {if}} u = 0 \\ u - {\ frac { 1} {m-1}}, & {\ text {if}} u \ not = 0 \ end {cases}} \\ u {\ underset {P} {\ wedge}} v &: = \ min \ {u , v \} \\ u {\ underset {P} {\ vee}} v &: = \ max \ {u, v \} \ end {alinhado}}}$

Lógicas de rosas

Em 1951, Alan Rose definiu outra família de lógicas para sistemas cujos valores de verdade formam reticulados .

Semântica

Semântica de matriz (matrizes lógicas)

Veja a matriz lógica

Relação com a lógica clássica

As lógicas são geralmente sistemas destinados a codificar regras para preservar algumas propriedades semânticas de proposições nas transformações. Na lógica clássica , essa propriedade é "verdade". Em um argumento válido, a verdade da proposição derivada é garantida se as premissas forem conjuntamente verdadeiras, porque a aplicação de etapas válidas preserva a propriedade. No entanto, essa propriedade não precisa ser de "verdade"; em vez disso, pode ser algum outro conceito.

As lógicas multivaloradas têm como objetivo preservar a propriedade da designação (ou de ser designada). Visto que há mais de dois valores de verdade, as regras de inferência podem ter a intenção de preservar mais do que apenas o que corresponde (no sentido relevante) à verdade. Por exemplo, em uma lógica de três valores, às vezes os dois maiores valores de verdade (quando eles são representados como, por exemplo, inteiros positivos) são designados e as regras de inferência preservam esses valores. Precisamente, um argumento válido será tal que o valor das premissas tomadas em conjunto será sempre menor ou igual à conclusão.

Por exemplo, a propriedade preservada pode ser justificação , o conceito fundamental da lógica intuicionista . Assim, uma proposição não é verdadeira ou falsa; em vez disso, é justificado ou falho. Uma diferença chave entre justificação e verdade, neste caso, é que a lei do terceiro excluído não se aplica: uma proposição que não é falha não é necessariamente justificada; em vez disso, só não está provado que seja falho. A principal diferença é a determinação da propriedade preservada: pode-se provar que P é justificado, que P é defeituoso ou ser incapaz de provar qualquer um deles. Um argumento válido preserva a justificação entre as transformações, portanto, uma proposição derivada de proposições justificadas ainda é justificada. No entanto, existem provas na lógica clássica que dependem da lei do terceiro excluído; uma vez que essa lei não é utilizável sob este esquema, existem proposições que não podem ser provadas dessa forma.

Tese de suszko

Completude funcional de lógicas de muitos valores

Completude funcional é um termo usado para descrever uma propriedade especial de lógicas e álgebras finitas. O conjunto de conectivos de uma lógica é considerado funcionalmente completo ou adequado se e somente se seu conjunto de conectivos puder ser usado para construir uma fórmula correspondente a todas as funções de verdade possíveis . Uma álgebra adequada é aquela em que todo mapeamento finito de variáveis ​​pode ser expresso por alguma composição de suas operações.

Lógica clássica: CL = ({0,1}, ¬ , →, ∨, ∧, ↔) é funcionalmente completa, enquanto nenhuma lógica Łukasiewicz ou lógica com muitos valores infinitos tem esta propriedade.

Podemos definir uma lógica com muitos valores finitos como sendo L _n ({1, 2, ..., n } ƒ ₁ , ..., ƒ _m ) onde n ≥ 2 é um dado número natural. Pós (1921) prova que assumindo uma lógica é capaz de produzir uma função de qualquer m ^th modelo fim, existe alguma combinação correspondente de conectivos em uma lógica L adequado _n que pode produzir um modelo de ordem M + 1 .

Formulários

As aplicações conhecidas da lógica de muitos valores podem ser classificadas em dois grupos. O primeiro grupo usa lógica de muitos valores para resolver problemas binários com mais eficiência. Por exemplo, uma abordagem bem conhecida para representar uma função booleana de saída múltipla é tratar sua parte de saída como uma única variável de muitos valores e convertê-la em uma função característica de saída única (especificamente, a função de indicador ). Outras aplicações da lógica de muitos valores incluem projeto de matrizes lógicas programáveis (PLAs) com decodificadores de entrada, otimização de máquinas de estado finito , teste e verificação.

O segundo grupo visa o projeto de circuitos eletrônicos que empregam mais de dois níveis discretos de sinais, como memórias de muitos valores, circuitos aritméticos e matrizes de portas programáveis ​​em campo (FPGAs). Os circuitos de muitos valores têm várias vantagens teóricas sobre os circuitos binários padrão. Por exemplo, a interconexão on e off chip pode ser reduzida se os sinais no circuito assumirem quatro ou mais níveis em vez de apenas dois. No design de memória, armazenar dois em vez de um bit de informação por célula de memória dobra a densidade da memória no mesmo tamanho de dado . Os aplicativos que usam circuitos aritméticos geralmente se beneficiam do uso de alternativas aos sistemas de números binários. Por exemplo, sistemas numéricos residuais e redundantes podem reduzir ou eliminar os transportadores de ondulação que estão envolvidos na adição ou subtração binária normal, resultando em operações aritméticas de alta velocidade. Esses sistemas numéricos têm uma implementação natural usando circuitos de muitos valores. No entanto, a praticidade dessas vantagens potenciais depende muito da disponibilidade de realizações de circuitos, que devem ser compatíveis ou competitivas com as tecnologias padrão atuais. Além de auxiliar no projeto de circuitos eletrônicos, a lógica de muitos valores é amplamente utilizada para testar circuitos em busca de falhas e defeitos. Basicamente, todos os algoritmos conhecidos de geração automática de padrão de teste (ATG) usados ​​para teste de circuito digital requerem um simulador que pode resolver a lógica de 5 valores (0, 1, x, D, D '). Os valores adicionais - x, D e D'- representam (1) desconhecido / não inicializado, (2) a 0 em vez de 1 e (3) a 1 em vez de 0.

Locais de pesquisa

Um Simpósio Internacional IEEE em Lógica de Valores Múltiplos (ISMVL) foi realizado anualmente desde 1970. Ele atende principalmente a aplicações em design e verificação digital. Há também um Journal of Multiple-Value Logic and Soft Computing .

Veja também

Lógica matemática

• Graus de verdade
• Lógica Fuzzy
• Lógica de Gödel
• Lógica Jaina de sete valores
• Lógica Kleene
• Álgebra de Kleene (com involução)
• Lógica Łukasiewicz
• MV-álgebra
• Pós-lógica
• Princípio de bivalência
• AN anterior
• Lógica de Relevância

Lógica filosófica

• Falso dilema
• Mu

Lógica digital

• MVCML , lógica de modo de corrente de valor múltiplo
• IEEE 1164, um padrão de nove valores para VHDL
• IEEE 1364, um padrão de quatro valores para Verilog
• Lógica de três estados
• Lógica baseada em ruído

Referências

Leitura adicional

Em geral

• Augusto, Luis M. (2017). Lógica de muitos valores: uma introdução matemática e computacional. Londres: Publicações da faculdade. 340 páginas. ISBN  978-1-84890-250-3 . Página da web
• Béziau J.-Y. (1997), O que é lógica de muitos valores? Proceedings of the 27th International Symposium on Multiple-Valued Logic , IEEE Computer Society, Los Alamitos, pp. 117-121.
• Malinowski, Gregorz, (2001), Many-Valued Logics, em Goble, Lou, ed., The Blackwell Guide to Philosophical Logic . Blackwell.
• Bergmann, Merrie (2008), Uma introdução à lógica fuzzy e de muitos valores: semântica, álgebras e sistemas de derivação , Cambridge University Press, ISBN 978-0-521-88128-9
• Cignoli, RLO, D'Ottaviano, I, ML , Mundici, D., (2000). Fundamentos algébricos do raciocínio de muitos valores . Kluwer.
• Malinowski, Grzegorz (1993). Lógicas de muitos valores . Clarendon Press. ISBN 978-0-19-853787-8.
• S. Gottwald , A Treatise on Many-Valued Logics. Studies in Logic and Computation, vol. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001.
• Gottwald, Siegfried (2005). "Lógica de muitos valores" (PDF) . Arquivado do original em 03/03/2016. Citar diário requer |journal=( ajuda )CS1 maint: bot: status do URL original desconhecido ( link )
• Miller, D. Michael; Thornton, Mitchell A. (2008). Lógica de múltiplos valores: conceitos e representações . Aulas de síntese sobre circuitos e sistemas digitais. 12 . Morgan & Claypool Publishers. ISBN 978-1-59829-190-2.
• Hájek P. , (1998), Metamathematics of fuzzy logic . Kluwer. (Lógica difusa entendida como lógica sui generis de muitos valores .)

Específico

• Alexandre Zinoviev , Philosophical Problems of Many-Valued Logic , D. Reidel Publishing Company, 169p., 1963.
• Anterior A. 1957, Time and Modality. Oxford University Press , com base em suas palestras de John Locke de 1956
• Goguen JA 1968/69, A lógica dos conceitos inexatos , Synthese, 19, 325-373.
• Chang CC e Keisler HJ 1966. Continuous Model Theory , Princeton, Princeton University Press.
• Gerla G. 2001, Fuzzy logic: Mathematical Tools for Approximate Reasoning , Kluwer Academic Publishers, Dordrecht.
• Pavelka J. 1979, On fuzzy logic I: Many-valorized rules of inference , Zeitschr. f. matemática. Logik und Grundlagen d. Math., 25, 45–52.
• Metcalfe, George; Olivetti, Nicola; Dov M. Gabbay (2008). Teoria da Prova para Lógica Fuzzy . Springer. ISBN 978-1-4020-9408-8. Abrange a teoria da prova de lógicas de muitos valores também, na tradição de Hájek.
• Hähnle, Reiner (1993). Dedução automatizada em lógicas de múltiplos valores . Clarendon Press. ISBN 978-0-19-853989-6.
• Azevedo, Francisco (2003). Resolução de restrições em lógicas multivaloradas: aplicação a circuitos digitais . IOS Press. ISBN 978-1-58603-304-0.
• Bolc, Leonard; Borowik, Piotr (2003). Lógica de muitos valores 2: Raciocínio automatizado e aplicações práticas . Springer. ISBN 978-3-540-64507-8.
• Stanković, Radomir S .; Astola, Jaakko T .; Moraga, Claudio (2012). Representação de funções lógicas de múltiplos valores . Morgan & Claypool Publishers. doi : 10.2200 / S00420ED1V01Y201205DCS037 . ISBN 978-1-60845-942-1.
• Abramovici, Miron; Breuer, Melvin A .; Friedman, Arthur D. (1994). Teste de sistemas digitais e design testável . Nova York: Computer Science Press. ISBN 978-0-7803-1062-9.

links externos

• Gottwald, Siegfried (2009). "Lógica de muitos valores" . Stanford Encyclopedia of Philosophy . Laboratório de Pesquisa Metafísica, Universidade de Stanford.
• Stanford Encyclopedia of Philosophy : " Truth Values " - de Yaroslav Shramko e Heinrich Wansing.
• IEEE Computer Society 's Comitê Técnico de Lógica de valor múltiplo
• Recursos para a lógica de muitos valores por Reiner Hähnle, Chalmers University
• Servidor Logics W3 de muitos valores (arquivado)
• Yaroslav Shramko e Heinrich Wansing (2020). "Tese de Suszko" . Stanford Encyclopedia of Philosophy .CS1 maint: usa o parâmetro de autores ( link )
• Carlos Caleiro, Walter Carnielli, Marcelo E. Coniglio e João Marcos, empresa Two: "A farsa de muitos valores lógicos" in Jean-Yves Beziau, ed. (2007). Logica Universalis: Rumo a uma Teoria Geral da Lógica (2ª ed.). Springer Science & Business Media. pp. 174–194. ISBN 978-3-7643-8354-1.