Ir al contenido

Fórmula proposicional

De Wikipedia, la enciclopedia libre

En la lógica proposicional,una fórmula proposicional es un tipo de fórmula sintáctica la cual está bien formada y tiene un valor verdadero. Si los valores de todas las variables en una fórmula proposicional son dados, es determinado un único valor verdadero. Una fórmula proposicional también puede ser llamada una expresión proposicional, una frase, o una fórmula sentencial.

Una fórmula proposicional es construida por una simple proposición, como "5 es mayor que 3" o variables proposicionales como P y Q, usando conectores como NO, Y, O e IMPLICADORES.

  1. (P Y NO Q) IMPLICA (P O Q).

En mátematicas, una fórmula proposicional es a menudo más brevemente referido a una "proposición", pero, más precisamente, una fórmula proposicional no es una proposición pero una expresión formal que denota una proposición, un objeto formal bajo discusión, al igual que una expresión como "x + y" no es un valor. En algunos contextos, mantener la distinción puede ser importante.

Proposiciones

[editar]

A los efectos del cálculo proposicional, las proposiciones (enunciados, oraciones, aserciones) se consideran simples o compuestas. Las proposiciones compuestas se consideran vinculadas por conexiones oracionales, algunas de las más comunes son "Y", "O", "SI ... ENTONCES ...", "NI ... NI ...", "... ES EQUIVALENTE A ...". El punto y coma de enlace ";" y el conector "PERO" se consideran expresiones de "AND". Se considera que una secuencia de oraciones discretas está vinculada por "Y", y el análisis formal aplica una "regla de paréntesis" recursiva con respecto a secuencias de proposiciones simples (ver más abajo sobre fórmulas bien formadas).

Las proposiciones simples son de carácter declarativo, es decir, hacen aseveraciones sobre la condición o naturaleza de un objeto de sensación particular, por ejemplo. "Esta vaca es azul", "¡Hay un coyote!" ("Ese coyote está allí, detrás de las rocas"). Por lo tanto, las afirmaciones simples "primitivas" deben referirse a objetos específicos o estados mentales específicos. Cada uno debe tener al menos un sujeto (un objeto inmediato de pensamiento u observación), un verbo (en la voz activa y el tiempo presente preferido), y quizás un adjetivo o adverbio. "¡Perro!" probablemente implica "Veo un perro", pero debe rechazarse por ser demasiado ambiguo.

A los fines del cálculo proposicional, una proposición compuesta generalmente puede refórmularse en una serie de oraciones simples, aunque el resultado probablemente sonará forzado.

Relación entre fórmulas proposicionales y predicados

[editar]

El cálculo de predicados va un paso más allá del cálculo proposicional hacia un "análisis de la estructura interna de proposiciones" . Se divide una oración simple en dos partes (i) su sujeto (el objeto (singular o plural) del discurso) y (ii) un predicado (un verbo o posiblemente cláusula verbal que afirma una cualidad o atributo del objeto (s)). El cálculo de predicados luego generaliza la forma "sujeto | predicado" (donde | simboliza la concatenación (encadenamiento) de símbolos) en una forma con la siguiente estructura de sujeto en blanco "___ | predicado", y el predicado a su vez se generaliza a todas las cosas con esa propiedad.

La generalización de "este cerdo" a un (potencial) miembro de dos clases "cosas aladas" y "cosas azules" significa que tiene una relación de verdad con ambas clases. En otras palabras, dado un dominio del discurso "cosas aladas", o encontramos que p es un miembro de este dominio o no. Por lo tanto, tenemos una relación W (alada) entre p (pig) y {T, F},W (p) se evalúa como {T, F}. Del mismo modo para B (azul) y p (cerdo) y { T, F}: B (p) evalúa a {T, F}. Entonces, ahora podemos analizar las aserciones conectadas "B (p) AND W (p)" para su valor de verdad general, es decir:

En particular, las oraciones simples que emplean nociones de "todos", "algunos", "unos pocos", "uno de", etc. son tratados por el cálculo de predicados. Junto con el nuevo simbolismo de función "F (x)" se introducen dos nuevos símbolos: ∀ (Para todos), y ∃ (Existe ..., Al menos uno de ... existe, etc.). El cálculo del predicado, pero no el cálculo proposicional, puede establecer la validez formal de la siguiente afirmación:

Identidad

[editar]

Tarski afirma que la noción de IDENTIDAD (a diferencia de la EQUIVALENCIA LÓGICA) se encuentra fuera del cálculo proposicional; sin embargo, señala que si una lógica debe ser útil para las matemáticas y las ciencias, debe contener una "teoría" de IDENTIDAD. Algunos autores se refieren a "lógica de predicados con identidad" para enfatizar esta extensión. Ver más sobre esto a continuación.

Un álgebra de proposiciones, el cálculo proposicional

[editar]

Un álgebra (y hay muchos diferentes), definida de manera vaga, es un método mediante el cual una colección de símbolos llama variables junto con algunos otros símbolos como paréntesis (, ) y algún subconjunto de símbolos como *, +, ~ , &, ∨, =, ≡, ∧, ¬ son manipulados dentro de un sistema de reglas. Se dice que estos símbolos y cadenas bien formadas de ellos representan objetos, pero en un sistema algebraico específico, estos objetos no tienen significados. Así, el trabajo dentro del álgebra se convierte en un ejercicio para obedecer ciertas leyes (reglas) de la sintaxis del álgebra (formación de símbolos) más que en la semántica (significado) de los símbolos. Los significados se encuentran fuera del álgebra.

Para que una secuencia de símbolos bien formada en el álgebra -una fórmula- tenga cierta utilidad fuera del álgebra, a los símbolos se les asignan significados y, finalmente, a las variables se les asignan valores; luego, mediante una serie de reglas, se evalúa la fórmula.

Cuando los valores se restringen a solo dos y se aplican a la noción de oraciones simples (por ejemplo, declaraciones verbales o afirmaciones escritas) vinculadas por conectivos proposicionales, este sistema algebraico completo de símbolos y reglas y métodos de evaluación se denomina cálculo proposicional o cálculo sentencial .

Si bien algunas de las reglas familiares del álgebra aritmética continúan vigentes en el álgebra de proposiciones (por ejemplo, las leyes conmutativa y asociativa para AND y OR), otras no (por ejemplo, las leyes distributivas para AND, OR y NOT).

Utilidad de fórmulas proposicionales

[editar]

Análisis: en el razonamiento deductivo, los filósofos, los retóricos y los matemáticos reducen los argumentos a las fórmulas y luego las estudian (generalmente con tablas de verdad) para la corrección (solidez). Por ejemplo: ¿Suena el siguiente argumento?

"Dado que la conciencia es suficiente para una inteligencia artificial y solo las entidades conscientes pueden pasar la prueba de Turing, antes de que podamos concluir que un robot es una inteligencia artificial, el robot debe pasar la prueba de Turing".

Los ingenieros analizan los circuitos lógicos que han diseñado utilizando técnicas de síntesis y luego aplican diversas técnicas de reducción y minimización para simplificar sus diseños.

Síntesis: los ingenieros en particular sintetizan fórmulas proposicionales (que eventualmente terminan como circuitos de símbolos) a partir de tablas de verdad. Por ejemplo, uno podría escribir una tabla de verdad sobre cómo debería comportarse la adición binaria dada la adición de las variables "b" y "a" y "carry_in" "ci", y los resultados "carry_out" "co" y "sum" Σ :

  • Ejemplo: en la fila 5, ((b + a) + ci) = ((1 + 0) + 1) = el número "2". escrito como un número binario esto es 102, donde "co" = 1 y Σ = 0 como se muestra en las columnas más a la derecha.
row b a ci (b+a)+ci co Σ
0 0 0 0 0 0 0
1 0 0 1 1 0 1
2 0 1 0 1 0 1
3 0 1 1 2 1 0
4 1 0 0 1 0 1
5 1 0 1 2 1 0
6 1 1 0 2 1 0
7 1 1 1 3 1 1

Variables proposicionales

[editar]

El tipo más simple de fórmula proposicional es una variable proposicional. Las proposiciones que son simples (atómicas), expresiones simbólicas a menudo se denotan por las variables llamadas a, b, o A, B, etc. Una variable proposicional pretende representar una proposición atómica (aserción), como "Es sábado" = a (aquí el símbolo = significa "... se le asigna la variable llamada ...") o "Solo voy al cine el lunes" = b.

Asignaciones de valor de verdad, evaluaciones de fórmula

[editar]

La evaluación de una fórmula proposicional comienza con la asignación de un valor de verdad a cada variable. Debido a que cada variable representa una oración simple, los valores de verdad se están aplicando a la "verdad" o "falsedad" de estas oraciones simples.

Valores de verdad en retórica, filosofía y matemáticas: los valores de verdad son solo dos: {VERDAD "T", FALSA "F"}. Un empirista pone todas las proposiciones en dos amplias clases: analítico-verdadero sin importar qué (por ejemplo, tautología) y sintético-derivado de la experiencia y, por lo tanto, susceptible de confirmación por parte de terceros (la teoría de la verificación del significado). Los empiricits sostienen que, en general, para llegar al valor de verdad de una proposición sintética, primero se deben aplicar significados (plantillas de coincidencia de patrones) a las palabras, y luego estas plantillas de significado deben compararse con lo que sea que se esté afirmado Por ejemplo, mi enunciado "¡Esa vaca es azul!" ¿Es esta declaración una VERDAD? Verdaderamente lo dije. Y tal vez estoy viendo una vaca azul; a menos que mienta, mi afirmación es una VERDAD relativa al objeto de mi percepción (quizás defectuosa). Pero, ¿está la vaca azul "realmente allí"? ¿Qué ves cuando miras por la misma ventana? Para proceder con una verificación, necesitará una noción previa (una plantilla) de "vaca" y "azul", y una capacidad para hacer coincidir las plantillas con el objeto de la sensación (si es que existe).

Valores de la verdad en la ingeniería: los ingenieros intentan evitar las nociones de verdad y falsedad que acosan a los filósofos, pero en el análisis final, los ingenieros deben confiar en sus instrumentos de medición. En su búsqueda de robustez, los ingenieros prefieren extraer objetos conocidos de una pequeña biblioteca, objetos que tienen comportamientos bien definidos y predecibles incluso en grandes combinaciones (de ahí su nombre para el cálculo proposicional: "lógica combinatoria"). La menor cantidad de comportamientos de un solo objeto son dos (por ejemplo, {APAGADO, ENCENDIDO}, {abierto, cerrado}, {ARRIBA, ABAJO} etc.), y estos se colocan en correspondencia con {0, 1}. Tales elementos se llaman digitales; aquellos con un rango continuo de comportamientos se llaman análogos. Siempre que las decisiones se tomen en un sistema analógico, muy a menudo un ingeniero convertirá un comportamiento analógico (la puerta es 45.32146% UP) a digital (por ejemplo, DOWN = 0) mediante el uso de un comparador.

Por lo tanto, una asignación de significado de las variables y los dos símbolos de valor {0, 1} proviene de "afuera" de la fórmula que representa el comportamiento del objeto compuesto (generalmente). Un ejemplo es una puerta de garaje con dos "interruptores de límite", uno para UP etiquetado SW_U y uno para DOWN etiquetado SW_D, y cualquier otra cosa que esté en los circuitos de la puerta. La inspección del circuito (ya sea el diagrama o los propios objetos reales-puerta, interruptores, cables, placa de circuitos, etc.) podría revelar que, en la placa de circuito, el "nodo 22" pasa a +0 voltios cuando los contactos del interruptor "SW_D" "están mecánicamente en contacto (" cerrado ") y la puerta está en la posición" abajo "(95% hacia abajo), y" nodo 29 "va a +0 voltios cuando la puerta está 95% ARRIBA y los contactos del interruptor SW_U son en contacto mecánico ("cerrado"). El ingeniero debe definir el significado de estos voltajes y todas las combinaciones posibles (los 4), incluidos los "malos" (por ejemplo, ambos nodos 22 y 29 a 0 voltios, lo que significa que la puerta está abierta y cerrada al mismo tiempo) . El circuito responde sin pensar a cualquier voltaje que experimente sin ningún conocimiento de la VERDAD o FALSA, CORRECTO o EQUIVOCADO, SEGURO o PELIGROSO.

Conectores Proposicionales

[editar]

Las fórmulas proposicionales arbitrarias se construyen a partir de variables proposicionales y otras fórmulas proposicionales que usan conectivos proposicionales. Los ejemplos de conectivos incluyen:

  • El conectivo de negación unario. Si α es una fórmula, ¬α es una fórmula.
  • Las conexiones binarias clásicas Λ,ν,→,↔. Por lo tanto, por ejemplo, si α y β son fórmulas, también lo es (α → β)
  • Otras conexiones binarias, como NAND, NOR y XOR
  • El conectivo ternario SI ... ENTONCES ... ENTONCES ...
  • Conectivas 0-arias constantes ⊤ y ⊥ (alternativamente, constantes {T, F}, {1, 0} etc.)
  • La "teoría-extensión" conecta EQUALES (alternativamente, IDENTIDAD, o el signo "=" como se distingue de la "conexión lógica" ↔)

Conectivas de retórica, filosofía y matemáticas

[editar]

Los siguientes son los conectivos comunes a la retórica, la filosofía y las matemáticas junto con sus tablas de verdad. Los símbolos utilizados variarán de autor a autor y entre campos de esfuerzo. En general, las abreviaturas "T" y "F" representan las evaluaciones VERDAD y FALSIDAD aplicadas a las variables en la fórmula proposicional (por ejemplo, la afirmación: "Esa vaca es azul" tendrá el valor de verdad "T" para Verdad o " F "por falsedad, según sea el caso.).

Los conectivos se rigen por varios usos de palabras diferentes, p. "a IMPLIES b" también se dice "IF a THEN b". Algunos de estos se muestran en la tabla.

b only if a
b IS SUFFICIENT FOR a
a IS NECESSARY FOR b b IF AND ONLY IF a; b IFF a
inclusive OR IF b THEN a b IS NECESSARY AND SUFFICIENT FOR a
negation negation conjunction disjunction implication biconditional
variables NOT b NOT a b AND a b OR a b IMPLIES a b IS logically equivalentTO a *** f IS A tautology NEITHER a NOR b b stroke a exclusive OR
b a ¬(b) ¬(a) (b ∧ a) (b ∨ a) (b → a) (b ↔ a) (f = fórmula) (a NOR b) (b|a) various
F F T T F F T T T T T F
F T T F F T T F T F T T
T F F T F T F F T F T T
T T F F T T T T T F F F

Conectivos de ingeniería

[editar]

En general, los conectivos de ingeniería son exactamente los mismos que los conectivos matemáticos, excepto que tienden a evaluar con "1" = "T" y "0" = "F". Esto se hace con el propósito de análisis / minimización y síntesis de fórmulas mediante el uso de la noción de mini términos y mapas de Karnaugh (ver abajo). Los ingenieros también usan las palabras producto lógico de la noción de Boole (a * a = a) y suma lógica de la noción de Jevons (a + a = a).

logical product logical sum half-adder (no carry)
exclusive OR
row number variables NOT NOT AND OR NAND NOR XOR
b*21+a*20 b a ~(b) ~(a) (b & a) (b ∨ a) ~(b & a) ~(b ∨ a)
0 0 0 1 1 0 0 1 1 0
1 0 1 1 0 0 1 1 0 1
2 1 0 0 1 0 1 1 0 1
3 1 1 0 0 1 1 0 0 0