Математическая логика. - 4 стр.

                                         -3-                  Математическая логика




13. А → В ≡ А ∨ В
14. А ~ В ≡ АВ ∨ А В
15. А ⊕ В ≡ А В ∨ АВ
16. А | B ≡ АВ ≡ А ∨ В
17. А ↓ В ≡ А ∨ В ≡ А В

       Сложное высказывание, истинное при любых значениях входящих в него
элементарных высказываний, называется тавтологией. Отрицание тавтологией
есть противоречие.


               ФОРМЫ ПРЕДСТАВЛЕНИЕ ВЫСКАЗЫВАНИЙ.
       Одно и то же сложное высказывание может быть предоставлено в раз-
личных формах.
       Элементарной дизъюнкцией называется выражение вида А1 ∨ А 2 ∨ ...
                         (     )
∨ А n , где каждое А i i = 1, n является либо элементарным высказыванием, ли-
бо отрицанием элементарного высказывания.
       Элементарной конъюнкцией называется выражение вида В1 ⋅ В 2 ⋅ ... ⋅ В n
                    (    )
где каждое Вi i = 1, m является либо элементарным высказыванием, либо от-
рицанием элементарного высказывания.

       Примеры:
1.     x∨ y∨z           - элементарная дизъюнкция;
2.     x yz             - элементарная конъюнкция;
3.     x                - можно считать частным случаем как элементарной конъ-
                        юнкции, так и элементарной дизъюнкции;
4.     xy ∨ z           - не является ни элементарной конъюнкции, ни элементар-
                        ной дизъюнкции;
5.     x∨ y∨z           - не является ни элементарной дизъюнкцией;
6.     x yz             - не является ни элементарной конъюнкцией.

      Дизъюнктивной нормальной формой (ДНФ) данного высказывания на-
                                                                        (      )
зывается равносильное ему высказывание вида K1 ∨ K 2 ∨ ... ∨ K S , K i i = 1, s - эле-
ментарная конъюнкция.
      Конъюнктивной нормальной формой (КНФ) данного высказывания на-
зывается равносильное ему высказывание вида        D1 ∨ D1 ∨ ... ∨ D t ,
        (       )
где D i i = 1, t - элементарная дизъюнкция.
      Совершенной дизъюнктивной нормальной формой (СДНФ) называется
такая ДНФ, в которой каждая элементарная конъюнкция (называемая также
конституентой единицы) содержит все элементарные высказывания либо их от-
рицания по одному разу. Конституенты единицы в СНДФ не повторяются.
      Совершенной конъюнктивной нормальной формой (СКНФ) называется
такая КНФ, в которой каждая элементарная дизъюнкция (называемая также