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

ГАОУ ВПО «Дагестанский государственный институт народного хозяйства»

Факультет «Информационные технологии»

 

 

РЕФЕРАТ

 

 

на тему:

«ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД НИМИ.»

 

 

 

 

 

 

 

 

 

 

 

Подготовил студент 1 курса 4 группы - Джалилов Б.С

Проверил(а) - _____________

(с) Махачкала 2014

 

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

логика алгебраический предикат истинность

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

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

А
1	0
0	1

 

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

Примеры:

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

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

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

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

 

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

А	В	А В
0	0	0
0	1	1
1	0	1
1	1	1

 

Пример:

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

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

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

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

 

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

А	В	А В
0	0	0
0	1	0
1	0	0
1	1	1

 

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

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

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

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

 

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

А	В	А В
0	0	1
0	1	1
1	0	0
1	1	1

 

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

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

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

Читают:

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

 

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

А	В	А В
0	0	1
0	1	0
1	0	0
1	1	1

 

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

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

Таблицу истинности высказывания

Х	У				( У)
И	И	Л	Л	И	Л
Л	Л	И	И	И	И
И	Л	Л	И	И	И
Л	И	И	Л	И	Л

 

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

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

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

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

 

А	В	А В
Л	Л	И

 

А В

3. При составлении таблицы истинности может получиться, что формула является истинной при любых значениях составляющих ее высказывательных переменных. Пример: Министр образования России - мужчина или женщина. Введем обозначения: Х - министр - мужчина, тогда - министр - женщина. Следовательно, высказывание можно представить формулой Х .

 

Х		Х
И	Л	И
Л	И	И

 

 

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

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

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

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

 Х Х - закон тождества

 Х Л - закон противоречия

 Х И - закон исключения третьего

Х - закон двойного отрицания

законы коммутативности

6. Х (У Z) (Х У) Z закон ассоциативности

Х (У Z) (Х У) Z закон дистрибутивности

7. законы Де Моргана

8. законы сочленения переменной с константой

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

Пример:

2.7 4. Из множества формул, равносильных между собой, рассмотрим две. Это - совершенная конъюнктивная нормальная форма (СКНФ) и совершенная дизъюнктивная нормальная форма (СДНФ). Они строятся для данной формулы на основе ее таблицы истинности.

 

Построение СДНФ:

-- выбираются строки, соответствующие значениям истинности (1) данной формулы;

-- для каждой выделенной строки составляем конъюнкцию переменных или их отрицаний так, чтобы наборам значений переменных, представленных в строке, соответствовали истинные значения конъюнкции (для этого надо переменные, которые в этой строке принимали значения ложь (0) взять со знаком отрицания, а переменные, принимающие значения истинности (1) без отрицания);

-- составляется дизъюнкция полученных конъюнкций.

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

Составление СКНФ осуществляется по следующему алгоритму:

-- выделить те строки таблицы, в которых формула принимает значение ложь (0);

-- из переменных, стоящих в каждой такой строке, составить дизъюнкцию, которая должна принимать значения - ложь (0). Для этого все переменные должны войти в нее со значением ложь, следовательно те, которые истинны (1), надо заменить их отрицанием;

-- из полученных дизъюнкций составить конъюнкцию.

Очевидно, что любая формула, не являющаяся тавтологией, имеет СКНФ.

СДНФ и СКНФ используются для получения следствий из данной формулы.

Пример: Составить таблицу истинности СДНФ и СКНФ для формулы: .

 

 

Таблица истинности СДНФ и СКНФ

1 1 0 0	1 0 1 0	0 0 1 1	0 1 0 1	1 0 0 0	1 1 1 0	1 1 1 1	1 1 0 0