Высказывания и логические операции над ними. Предикарты

Тема: ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД НИМИ.

ПРЕДИКАТЫ 

1. Понятие тавтологии и равносильные формулы.
2. Совершенная конъюнктивная нормальная формула (СКНФ) и совершенная дизъюнктивная нормальная формула (СДНФ).
3. Понятие предиката. Операции над предикатами.

 
 

1. Основные понятия алгебраической логики.

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

    Логика  как наука сформировалась в трудах Аристотеля. Он сформулировал три закона логики:

               1) А является А – закон тождественности. Некоторая вещь всегда равна самой себе, суждение означает само себя.

                2) А не является не А – закон противоречия. Вещь не может одновременно обладать и не обладать некоторым свойством; никакое суждение не является одновременно истинным и ложным.

                3) Имеет место либо А, либо не А – закон исключенного третьего. Вещь либо обладает, либо не обладает некоторым свойством, любое суждение либо истинно, либо ложно.

    Алгебра логики занимается законами построения правильных, истинных рассуждений. На основе этих законов можно определить, является ли предложение истинным или ложным.

    Одно  из основных понятий логики – понятие  высказывания.

    Определение: Высказывание – это любое утверждение, которое можно быть либо истинным, либо ложным.

Пример:

1) Мы учимся в Москве. – ложь высказывание.                                                                                                2) Земля – планета Солнечной системы. – истина                                                                          3) Математика – интересный предмет.  Не существует единого мнения – истина или ложь фраза не является высказыванием.

4) В нашей Галактике есть и кроме земной разумные цивилизации. – высказывание, т.к. объективно оно либо истинно либо ложно

5) Все  лето было дождливое. – не  высказывание, т.к. не ясно , о каком  лете идет речь, необходима конкретизация.

6) Они любят друг друга. – не высказывание, т.к. нет конкретности

7) Зеленый чай – полезный напиток. – истина

8) Зеленый чай – вкусный напиток. – не высказывание

    Высказывания 5) и 6) не конкретные. Выделим в них неизвестные параметры: для 5) - это лето года Х имеем предложение: Все лето года Х было дождливое.; для 6) - У и Z любят друг друга. 

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

    Предложения 5) и 6) – высказывательные формы. 

2. Логические операции  над высказываниями. 

Над высказываниями можно проводить логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

    2.1. Определение:  Отрицанием высказывания А называется высказывание , которое истинно, если А ложно, и ложно, если А истинно.

    Высказывание  читается так:  «не А»

    

    Таблица истинности для  имеет вид:

                                                                                                                                    

    Здесь: 1 – истина, 0 – ложь. 

    Примеры:

    1. Х: треугольник АВС – остроугольный.  Х: неверно, что треугольник  АВС – остроугольный. Это все равно, что:  Х: треугольник АВС – прямоугольный или тупоугольный

    2. А: Иванова М. На экзамене  по математике получила 4. : Неверно, что Иванова М. по математике получила 4. 

    2.2. Определение:  Дизъюнкцией высказывания А и В называется высказывание А В, истинное при условии, что хотя бы одно из высказываний А или В истинно.

    Его читают «А или В».

      Таблица истинности для А В

      
 
 
 
 
 
 

Пример: 1. По математике будет зачет или  экзамен.

    2. 10 – простое или составное  число. 

    Определение:  Конъюнкцией высказываний А и В называется высказывание А В, которое истинно лишь при условии, что истинны оба высказывания и А, и В.

    Высказывание А В читается «А и В».

    

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

     
Пример: 1. На этот раз ответчик явился и суд состоялся. – истина

           2. В прямоугольном треугольнике сумма двух любых углов больше или равна третьего угла и гипотенуза меньше катета. – ложь 

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

    Его читают: «Если А, то В».

    

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

     
Пример: 1. Если я сдам зачет, то пойду  в кино.

           2. Если треугольник равнобедренный, то углы при его основании  равны.

    Определение: Эквиваленцией высказываний А и В называется высказывание А В, истинное в том и только в том случае, когда А и В имеют одну и ту же истинность (т.е. либо оба истинны, либо оба ложны).

    Читают: «А тогда и только тогда, когда В» или «А необходимо и достаточно для В»

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

      
 
 
 
 
 

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

Пример: Составить таблицу истинности высказывания, если оно задано следующей формулой:    (Х У) У 

 

    Вторая  задача, решаемая средствами алгебры высказываний, состоит в том, чтобы определить истинность конкретного высказывания на основе составления его формулы (процесс формализации) и составления таблицы истинности.

Пример: Если Саратов расположен на берегу Невы, то в Африке обитают белые медведи.

    А: Саратов расположен на берегу реки Невы;

    В: В Африке обитают белые медведи

    

    А В     
 
 
 

3. При составлении таблицы истинности может получиться, что формула является истинной при любых значениях составляющих ее высказывательных переменных.

Пример: Министр образования России –  мужчина или женщина.

    Введем  обозначения: Х – министр – мужчина, тогда – министр – женщина.

    Следовательно, высказывание можно представить формулой Х .    

      
 
 
 

    Определение: Формула, которая истинна независимо от того, какие значения принимают входящие в нее высказывательные переменные, называется тавтологией или тождественно истинной формулой.

    Определение: Формулы F₁ и F₂ называются равносильными, если их эквиваленция – тавтология.

    Определение: Если формулы F₁ и F₂  равносильны, то предложения Р₁ и Р₂ , которые инициируют эти формулы, называются равносильными в логике высказываний .

    Основные, наиболее часто встречающиеся равносильности, называют законами логики. Перечислим некоторые из них: