Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 13 vistas

    Semana 6 Forma Normal Conjuntiva y Disyuntiva

    Cargado por

    Edgar Chura Humora

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Semana 6 Forma Normal Conjuntiva y Disyuntiva

    Cargado por

    Edgar Chura Humora
    13 vistas6 páginas

    Título original

    Semana 6 Forma normal conjuntiva y disyuntiva

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    13 vistas6 páginas

    Semana 6 Forma Normal Conjuntiva y Disyuntiva

    Cargado por

    Edgar Chura Humora

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 6

    Forma normal conjuntiva (FNC)

    Una fórmula está en FNC, cuando está constituida por una disyunción básica o por conjunciones
    de disyunciones básicas. Si “A” es una disyunción básica entonces, esquemáticamente, una FNC es
    como sigue:

    𝐴1 ∧ 𝐴2 ∧ 𝐴3 ∧ ⋯ ∧ 𝐴𝑛
    Donde “A” y sus respectivos sub-índices representan cualesquiera disyunciones básicas, por
    ejemplo, la siguiente fórmula está en FNC.

    (𝑝 ∨∼ 𝑞 ∨ 𝑟) ∧ (𝑞 ∨∼ 𝑠 ∨∼ 𝑡) ∧ (∼ 𝑝 ∨ 𝑟 ∨ 𝑡)
    Donde (𝑝 ∨∼ 𝑞 ∨ 𝑟) puede ser 𝐴1 , (𝑞 ∨∼ 𝑠 ∨∼ 𝑡) puedes ser 𝐴2 y (∼ 𝑝 ∨ 𝑟 ∨ 𝑡)puede ser 𝐴3 .
    También llamaremos FNC a una sola disyunción básica; entonces la siguiente fórmula est´s en FNC

    𝑝 ∨∼ 𝑟 ∨ 𝑞 ∨∼ 𝑡
    Obtener la FNC de una fórmula “A” consiste en transformar “A” en una disyunción básica o en
    conjunciones de disyunciones básicas aplicando las conocidas reglas de transformación
    (equivalencias notables). En ese sentido, toda fórmula de la lógica proposicional tiene su FNC.

    FNC como procedimiento decisorio

    Como toda fórmula proposicional es reducible a una FNC, la FNC se puede usar para decidir si una
    fórmula es o no válida. Para el efecto es suficiente reconocer si una disyunción básica es o no una
    tautología. Una disyunción básica es una tautología cuando existe una misma variable negada y sin
    negar a la vez. Por ejemplo la siguiente disyunción es una tautología:

    𝑝 ∨∼ 𝑞 ∨∼ 𝑝 ∨ 𝑟 ∨∼ 𝑠
    Como se puede apreciar “p” que está sin negar y negada a la vez nos indica que es una tautología
    porque “𝑝 ∨∼ 𝑝" es la expresión del Tercio Excluido. Entonces podemos decir que una disyunción
    básica es una tautología cuando contiene el tercio excluido. Luego, una FNC es una tautología
    cuando cada disyunción básica contiene el tercio excluido, por ej:

    (𝑝 ∨∼ 𝑞 ∨ 𝑞) ∧ (∼ 𝑝 ∨ 𝑟 ∨ 𝑝) ∧ (∼ 𝑟 ∨∼ 𝑞 ∨ 𝑟)
    La primera disyunción básica es tautología por " ∼ 𝑞 ∨ 𝑞", la segunda por " ∼ 𝑝 ∨ 𝑝" y la tercera
    por ∼r∨r, por las propiedades de la equivalencia, la conjunción de tautologías equivale a una
    tautología: "𝑇1 ∧ 𝑇2 . ⟶. 𝑇3

    Procedimiento para obtener la FNC

    1. Transformar “A” sólo a operadores “∧ ", “∨ "y “∼ "


    2. Las negaciones deben afectar únicamente variables proposicionales
    3. Aplicar las reglas de la distribución o de la absorción, u otras reglas cuando éstas sean
    necesarias.
    4. Aplicar la regla de la expansión a las variables negadas o sin negar que no forman arte de
    una disyunción básica.

    Ejemplo:
    a) 1) (𝑝 → 𝑞) → (~𝑞 → ~𝑝)
    2) ~(𝑝 → 𝑞) ∨ (~𝑞 → ~𝑝) Imp
    3) ~(~𝑝 ∨ 𝑞) ∨ (~~𝑞 ∨ ~𝑝)Imp
    4) (𝑝 ∧ ~𝑞) ∨ (𝑞 ∨ ~𝑝) DM
    5) (𝑝 ∨ 𝑞 ∨ ~𝑝) ∧ (~𝑞 ∨ 𝑞 ∨ ~𝑝) Dist.
    6) (𝑝 ∨ 𝑞 ∨ ~𝑝) Elim de T.

    b) 1) (𝑝 ∧ ~𝑞) → (𝑞 ↔ ~𝑟)

    2) ~ (𝑝 ∧ ~𝑞) ∨ (𝑞 ↔ ~𝑟) Imp

    3) ~ (𝑝 ∧ ~𝑞) ∨ [(𝑞 → 𝑟)( ~𝑟 →

    Formal normal disyuntiva (FND)

    Una fórmula está en FND cuando está constituida por una conjunción básica o por disyunciones de
    conjunciones básicas. Si “A” es una conjunción básica, entonces el esquema de una FND es como
    sigue:

    𝐴1 ∨ 𝐴2 ∨ 𝐴3 ∨ ⋯ ∨ 𝐴𝑛
    Donde “A” y sus respectivos subíndices representan en cada caso, una conjunción básica
    cualquiera. Por ejemplo la siguiente fórmula es una conjunción básica y, por lo tanto está en FND

    𝑝 ∧ ~𝑞 ∧ ~𝑟 ∧ 𝑠
    O también, disyunciones de conjunciones básicas como la siguiente:

    (𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (~𝑟 ∧ 𝑠 ∧ 𝑡) ∨ (~𝑞 ∧ 𝑠 ∧ ~𝑡)

    Donde (𝑝 ∧ 𝑞 ∧ 𝑟) puede ser 𝐴1 , (~𝑟 ∧ 𝑠 ∧ 𝑡) puede ser 𝐴2 y 𝐴3 puede representar a (~𝑞 ∧ 𝑠 ∧


    ~𝑡). Entonces, obtener la FND de una fórmula “A”consiste en transformar “A” en una conjunción
    básica o en disyunciones de conjunciones básicas aplicando las conocidas reglas de transformación
    (equivalencias notables). Luego, se puede obtener la FND de cualquier fórmula de la lógica
    proposicional.

    Consistencia o inconsistencia de una FND

    Con una FND se puede determinar si una fórmula “A” es o no consistente. Una FND es consistente
    cuando por lo menos una de sus conjunciones básicas no es contradictoria. Para reconocer una
    conjunción básica contradictoria es suficiente ver la existencia de una misma variable
    proposicional negada y sin negar a la vez. Por ejemplo, la siguiente conjunción básica es
    contradictoria:

    𝑝 ∧ ~𝑞 ∧ ~𝑝 ∧ 𝑟
    Como se puede apreciar, la contradicción está en “𝑝 ∧ ~𝑝”, luego podemos afirmar que es una
    FND inconsistente, lo que significa que una FND es inconsistente cuando cada una de sus
    conjunciones básicas contiene una contradicción. Por ejemplo la siguiente FND:
    (𝑝 ∧ ~𝑞 ∧ 𝑞) ∨ (~𝑟 ∧ 𝑞 ∧ 𝑟) ∨ (𝑠 ∧ 𝑝 ∧ ~𝑠)

    En cambio, la siguiente fórmula es una FND consistente, porque ninguna de sus conjunciones
    básicas contiene una contradicción.

    (~𝑝 ∧ ~𝑞 ∧ ~𝑟) ∨ (𝑞 ∧ 𝑠 ∧ ~𝑡) ∨ (~𝑠 ∧ 𝑝 ∧ 𝑟)

    Sin embargo es suficiente que una de sus conjunciones básicas no contenga la contradicción para
    ser una FND consistente, por ejm.

    (𝑝 ∧ ~𝑞 ∧ 𝑟) ∨ (~𝑟 ∧ 𝑝 ∧ 𝑟) ∨ (𝑟 ∧ ~𝑞 ∧ 𝑞)

    En este caso, la FND puede reducirse sólo a la conjunción básica no contradictoria como sigue:

    (𝑝 ∧ ~𝑞 ∧ 𝑟)

    La regla que justifica esta reducción es: “(A∨⊥) ≡ 𝐴

    El procedimiento para obtener una FND es el mismo que se usa para obtener la FNC

    Ejemplos:

    a) 1) ~(𝑝 → 𝑞) ∧ (𝑟 → 𝑞)
    2) ~(~𝑝 ∨ 𝑞) ∧ (~𝑟 ∨ 𝑞) Imp
    3) (𝑝 ∧ ~𝑞) ∧ (~𝑟 ∨ 𝑞) DM y DN
    4) ) (𝑝 ∧ ~𝑞 ∧ ~𝑟) ∨ (𝑝 ∧ ~𝑞 ∧ 𝑞)Dist
    5) ) (𝑝 ∧ ~𝑞 ∧ ~𝑟)Elim ⊥
    FND es consistente
    b) 1) ~(𝑝 → 𝑞) ↔ (𝑞 ∨ ~𝑝)
    2) [~(𝑝 → 𝑞) → (𝑞 ∨ ~𝑝)] ∧ (𝑞 ∨ ~𝑝) → 𝑞𝑢𝑖𝑣~(𝑝 → 𝑞)Equiv
    3) (~𝑝 ∨ 𝑞 ∨ 𝑞 ∨ ~𝑝).∧. ~ (𝑞 ∨ ~𝑝) ∨ (𝑝 ∧ ~𝑞) Imp
    4) (~𝑝 ∨ 𝑞 ∨ 𝑞 ∨ ~𝑝).∧. (~𝑞 ∨ 𝑝) ∨ (𝑝 ∧ ~𝑞) DM
    5) (~𝑝 ∨ 𝑞) ∧ ( ~𝑞 ∧ 𝑝) Idem
    6) (~𝑝 ∧ ~𝑞 ∧ 𝑝) ∨ ( 𝑞 ∧ ~𝑞 ∧ 𝑝) Distr
    7) (~𝑝 ∧ ~𝑞 ∧ 𝑝) Elim ⊥
    La FND de 1 es inconsistente como se muestra en el paso 7, luego la fórmula 1 es
    contadictoria.

    TAREA

    Ejercicios

    1. Obtenga la FNC o la FND de cada una de las siguientes fórmulas aplicando solamente las
    reglas de la Distribución y de la Absorción.
    2. Obtenga la FNC de cada una de las siguientes fórmulas y diga en cada caso, si es o no
    válida.
    3. Obtenga la FND de cada una de las siguientes fórmulas y diga en cada caso, si la FND es
    consistente o inconsistente.
    Leyes de la absorción (Abs)
    𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝
    𝑝 ∨ (𝑝 ∧ 𝑞) ≡ 𝑝
    𝑝 ∧ (~𝑝 ∨ 𝑞) ≡ 𝑝 ∧ 𝑞
    𝑝 ∨ (~𝑝 ∧ 𝑞) ≡ 𝑝 ∨ 𝑞
    Leyes de la implicación (Imp)
    𝑝 → 𝑞 ≡ ~𝑝 ∨ 𝑞
    𝑝 → 𝑞 ≡ ~(𝑝 ∧ ~𝑞)

    Leyes de la Equivalencia (Equiv)


    𝑝 ↔ 𝑞 ≡ (𝑝 ⟶ 𝑞) ∧ (𝑞 → 𝑝)
    1. (𝐴 ∧ 𝑇) ≡ 𝐴
    2. (𝐴 ∨ 𝑇) ≡ 𝑇
    3. (A∧⊥) ≡⊥
    4. (A∨⊥) ≡ 𝐴

    También podría gustarte