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

Размещено на http://www.allbest.ru/

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

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 - простое или составное число.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А	В	АВ
Л	Л	И

АВ

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

Х		Х
И	Л	И
Л	И	И

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

СДНФ:

СКНФ:

5. Рассмотрим высказывательные форму «Река впадает в Черное море». Она содержит одну переменную и может быть представлена в виде «Река х впадает в Черное море».

В зависимости от значений переменной Х предложение является либо истинным, либо ложным, т.е. задается отображение множества рек на двух элементное множество . Обозначим это отображение , тогда:

Таким образом, имеем функцию, все значения которой принадлежат множеству .

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

Буквы , обозначающие предикаты, называют предикатными символами.

Предикаты могут задаваться:

a) высказывательной формулой,

b) формулой, т.е. задавая интерпретацию предикатного символа,

c) таблицей.

Пример:

1) Р - «впадать в Черное море».

. Эта формула означает, что «Река а впадает в Черное море».

2) Предикат Р задан высказывательной формулой: «быть простым числом на множестве первых 15 натуральных чисел».

3) В табличной форме предикат имеет вид:

Х	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	Л	И	И	Л	И	Л	И	Л	Л	Л	И	Л	И	Л	Л

Областью определения предикатов может быть любое множество.

Если предикат при каком-либо наборе входящих переменных теряет смысл, то принято считать, что этому набору соответствует значение Л.

Если предикат содержит одну переменную, то его называют одноместным, две переменные - двуместным, n переменных - n-местным предикатом.

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

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

Определение: Подмножество множества М, на котором задан предикат Р, состоящий из тех и только тех элементов М, которым соответствует значение И предиката Р, называется множеством истинности предиката Р.

Множество истинности обозначается .

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

Обозначается отрицание .

Пример:

- быть студентом АБиК.

- не быть студентом АБиК.

Если , то множество , где М - множество, на котором заданы предикаты Р и Q .

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

Пример:

- быть футболистом

- быть студентом

: быть футболистом и быть студентом.

Определение: дизъюнкцией предикатов и называется предикат ложный при тех наборах входящих в него переменных, которые обращают оба предиката в ложные

Пример:

- быть четным натуральным числом

- быть нечетным натуральным числом

: быть натуральным числом.



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

Обозначается:

Пример:

- быть простым числом на множестве N

- быть нечетным числом

- ложен при и истинным при других натуральных числах.

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

Обозначается:

Пример:

- «выигрывать», т.е. х выигрывает у

- лучше знать шахматную историю, х знает лучше у

обозначает, что х выигрывает у у в шахматы тогда и только тогда, когда он лучше знает теорию.

Определение: Предикат следует из предиката если импликация истинна при любых входящих в нее значениях переменных.

Обозначаются следования: .

- быть студентом

- ходить в институт

Для превращения предиката в высказывание существуют 2 пути:

1) придание переменной конкретного значения

; х - студент

Иванов

Иванов - студент.

2) Навешивание кванторов - любой, всякий, каждый

- существует, имеется.

Запись , где обладает свойством Р означает, что всякий предмет х обладает свойством Р. Или по другому, «все х обладают свойством Р».

Запись означает, что существует предмет х, обладающий свойством Р.

Размещено на Allbest.ru