Информатика

Основные логические операции


Суждения в математической логике могут быть простыми и сложносоставными. Примеры простых суждений:

х = 1                рост < 160

А                     цена (х, у)

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

не, выражающих три основных логических операции:

логическая связка не                         -

отрицание суждений;

логическая связка или                      - конъюнкция

суждений;

логическая связка и                          -

дизъюнкция суждений.

Примеры сложносоставных суждений:

не А                                                                - неверно суждение А



С или В                                              - истинно С или В

(х > 0) и (у > 0)                                  - (х больше 0) и (у

больше 0)

(глаза = синие) или (глаза = голубые)

Логическая связка не используется для выражения отрицаний. Примеры:

не (глаза = синие),                            - неверно, что глаза синие

не или

В),                                     - неверно, что выполняется А или В

не (любит (Саша, конфеты))            - неверно, что Саша любит конфеты

Наглядной иллюстрацией этих логических связок с предикатами служат следующие диаграммы:

Отрицание не А истинно или ложно в зависимости от истинности исходного суждения А. Свойства отрицания не как логической связки можно описать таблицей истинности:

Таблица истинности:

А                     не А

да

нет

нет

да

Свойства отрицаний:

НЕ1: Отрицание ложно, если суждение истинно.

НЕ2: Отрицание истинно, если суждение ложно.

Для понимания отрицаний важно уметь выражать их в позитивной форме. Приведем примеры отрицания математических неравенств и их позитивные переформулировки:

не

(х = 0)        º          (х ¹ 0)

не (х ¹

0)        º          (х = 0)

не

(х > 0)        º          (х £ 0)


не

(х < 0)        º          (х ³ 0)

не

(х ³ 0)        º          (х < 0)

не

(х £ 0)        º          (х > 0)

Свойства отрицаний, записанные в таблицу истинностности, могут быть описаны как факты на языке Пролог:

не (да, нет);

не (нет, да);

После ввода этих фактов в ЭВМ с помощью запросов можно перепроверить свойства отрицаний:

? не (А, нет)

А = да

? не (А, да)

А = нет

Логическая связка и в математической логике называется конъ­юнкцией. Таблица истинности

конъюнкции:


А                           В                           А и В

да

да

да

да

нет

нет

нет

да

нет

нет

нет

нет

Свойства конъюнкции:

И1: Конъюнкция А и В истинна, когда истинны оба суждения.

И 2: Конъюнкция А и В ложна, когда ложно хотя бы одно из суж­дений А или В.

Логическая связка или в математической логике называется дизъ­юнкцией. Таблица истинности

дизъюнкции:


 

 

А                            В                          А или В

да

да

да

да

нет

да

нет

да

да

нет

нет

нет

Свойства дизъюнкции:

ИЛИ1: Дизъюнкция А или В истинна, когда истинно любое из суждений А или В.

ИЛИ2: Дизъюнкция А или В ложна, когда ложны оба суждения А и В.

Свойства конъюнкции и дизъюнкции также можно описать в виде фактов на языке Пролог:

Дизъюнкция:                                     Конъюнкция:

или (да, да, да);                                 и2 (да, да, да);

или (да, нет, да);                               и2 (да, нет, нет);

или (нет, да, да);                               и2 (нет, да, нет);

или (нет, нет, нет);                           и2 (нет, нет, нет);

Опираясь на эти факты можно получить ответы на вопросы о свойствах дизъюнкции и конъюнкции с помощью ЭВМ:

? или (А, В, нет)                               ? и 2 (А, В, да)

А = нет В = нет                                 А = да В = да



? или (А, В, да)                                 ? и 2 (А, В, нет)

А = да В = да                                     А = да В = нет

А = да В = нет                                   А = нет В = да

А = нет В = да                                   А = нет В = нет

Одной из важнейших логических связок математической логики является импликация А ® В. Эта связка в математической логике используется для определения правил логического вывода.

Импликация А ® В

- это логическое следование. Импликация А ® В

читается: «если А, то В». Первое суждение в импликации называется посылкой, а второе суждение - следствием.

Приведем примеры правил логического вывода:

а) с использованием высказываний:

если «на улице дождь», то «на улице мокро»,

б) с использованием предикатов:

любит (х, конфеты) ® сластена (х).

Таблица истинности импликации:

А                         В                       А ® В

да

да

да

да

нет

нет

нет

да

да

нет

нет

да

Свойства импликации:                       

П1: «Импликация А ® В ложна,

когда посылка А истинна, а следствие В - ложно».

П2: «Импликация А ® В истинна,

когда истинно следствие либо ложны и посылка и следствие».

В языке Пролог импликации используются для описания правил вывода и определения новых логических понятий. Например, поня­тие «сластена» в языке .Пролог описывается следующим образом:

сластена (х) ¬ любит (х, конфеты);

 

Описание этого правила позволяет вводить в ЭВМ вопросы о «сластенах» и получать осмысленные ответы, исходя из сведений, хранящихся в базе данных:

? сластена (х)    - Кто сластена?

х = Маша

 

С помощью таблиц истинности могут быть описаны и проверены свойства любых сложносоставных высказываний. Соответственно с помощью этих таблиц на ЭВМ средствами языка Пролог могут быть проверены любые сложносоставные высказывания и законы исчис­ления высказываний.

Задача 1. Проверьте закон двойного отрицания в исчислении высказываний



не (не А) º А

Р е ш е н и е . Рассмотрим объединенную таблицу истинности вы­сказываний

      А                   не А               не (неА)

да

нет

да

нет

да

нет

 

Сравнение крайних столбцов показывает, что всюду, где выска­зывание А истинно, там же истинно и двойное отрицание не (не А). И наоборот, всюду, где ложно А, там ложно и двойное отрицание не (не А). Следовательно, двойное отрицание тождественно исходному высказыванию: не

(не А) º А.

Задача 2. Сравните с помощью таблиц истинности отрицание дизъюнкции и отрицание конъюнкции неи

В) и неили В).

Р е ш е н и е .

А                        В                    А и В                 не (А и В)              А или В           не (А или В)

да

да

да

нет

да

нет

да

нет

нет

да

да

нет

нет

да

нет

да

да

нет

нет

нет

нет

да

нет

да

 

В о п р о с ы

 

1. Когда истинно отрицание?

2. Когда ложна дизъюнкция?

3. Когда истинна конъюнкция?

4. Когда ложна импликация?

З а д а н и е

1. Составьте таблицы истинности для утверждений:

а) (не А) и (не В);       в) (не

А) или (не В);

б) А и (не В);               г) А или (не

В).

2. Сравните с помощью таблиц истинности логические выражения:

а) неи В);               в) (не А) или

(не В);

б) неи В);               г) (не А) или

(не В).

3. Проверьте по таблицам истинности логические законы:

а) отрицание конъюнкции:

неи

В) = (не А) или (не

В);

б) отрицание дизъюнкции:

неили

В) = (не А) и (не В);

в) отрицание импликации:

не (А ® В) º (не В) ® (не

А).


Содержание раздела