Законы алгебры высказываний

Операции над высказываниями

Основные понятия

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

ЛЕКЦИЯ №3

Контрольные вопросы

1. Запишите ассоциативный, дистрибутивный и коммутативный законы операций над множествами. 2. Свойства идемпотентности операций объединения и пересечения. 3. Законы де Моргана. 4. Какие числа называются натуральными? 5. Позиционная и непозиционная система счисления. 6. Какие числа называются целыми? 7. Рациональные числа. 8. Какие числа называются иррациональными? 9. Алгебраические числа и трансцендентные. 10. Действительные числа. 11. Комплексные числа.

План

1. Основные понятия

2. Операции над высказываниями

3. Законы алгебры высказываний

4. Строение математической теоремы

Математическая логика – современный вид формальной логики, изучающей правила выведения следствий из различных посылок, истинность которых очевидна. Математическая логика возникла в середине XIX в для потребностей математики и стала применяться в самых различных областях знаний, в том числе и в правоприменительной деятельности.

Появление математической логики математики связывают с Джорджем Булем (1815-1864), с его работами «Математический анализ логики» (1847), «Логическое исчисление» (1848) и «Законы мысли» (1854). В этих работах было показано, что законы формальной логики, представленные в виде кодов еще Аристотелем, сами могут быть предметом исчисления. Это были первые работы, объединяющие логику и математику. В 40-50-х гг. ХX века математическая логика получила особенное значение в связи с развитием вычислительной техники.

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

Основным понятием математической логики является понятие высказывания (высказывания будем обозначать латинскими буквами: ).

Определение 3.1. Высказыванием называется повествовательное предложение естественного языка, о котором имеет смысл говорить истинно оно или ложно.

Пример 3.1. «Москва – столица России» – истинное высказывание.

2х5=43 – ложное высказывание.

5>10 – ложное высказывание.

Какая сегодня погода? – не является высказыванием, т.к. здесь ничего не утверждается.

Пример 3.2. . При – высказывание истинное, при – ложное.

Пример 3.3. «Река впадает в Каспийское море». Если в таком предложении вместо вписать название конкретной реки, то получим высказывание, которое будет ложно или истинно. Высказывание «Река Волга впадает в Каспийское море» является истинным.

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

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

Рассматриваемые высказывания – нуль мерные предикаты. Поэтому логика предикатов, как частный случай, включает в себя логику высказываний.

Множество истинности неопределенных высказываний (предикатов) будем обозначать прописными буквами: .

Пример 3.4. Для следующего неопределенного высказывания : найдем множество истинности. Решив неравенство, получим: .

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

Пример 3.5. Равносильными будут следующие предикаты: и .

Каждому логическому высказыванию поставим в соответствие численное значение: 1 – если высказывание истинно, 0 – если высказывание ложное. Рассматривая высказывания как величины, принимающие значения 1 и 0, можно определить над ними операции, которые позволяют получать новые высказывания из данных. Эти операции будут выражать логические связи, употребляемые в обычной речи, например: не, и, или, если - то, тогда и только тогда и т.д.

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

Определение 3.3. Отрицанием высказывания называется высказывание, истинное тогда и только тогда, когда p ложно. Отрицание обозначается или и читается «не ».

В естественном языке отрицание соответствует составлению из высказывания p нового высказывания «неверно, что », или «не ».

Соотношение между , можно определить, воспользовавшись диаграммой Эйлера-Венна (рис. 3.1).

Составим таблицу истинности операции отрицания.

Отрицание истинного высказывания является ложным высказыванием, отрицание ложного – истинное высказывание. Двойное отрицание обозначается .

Таблица 3.1

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

отрицания

Пример 3.5. Для высказывания «Река Волхов вытекает из озера Ильмень» отрицанием будет высказывание «Неверно, что река Волхов вытекает из озера Ильмень» или «Река Волхов не вытекает из озера Ильмень», а двойным отрицанием будет высказывание «Неверно, что река Волхов не вытекает из озера Ильмень».

Определение 3.3. Конъюнкцией двух высказываний и называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания. Конъюнкция высказываний обозначается , или и читается «и ».

В естественном языке конъюнкция соответствует соединению высказываний союзом «и».

Составим таблицу истинности операции конъюнкции. Множество истинности для конъюнкции между и можно определить., воспользовавшись диаграммой Эйлера – Венна (рис. 3.2). Для этого определим: – множество истинности для высказывания , Q - множество истинности для высказывания . Множество истинности для высказывания является множество . Оно представлено на диаграмме закрашенной областью.

Таблица 3.2

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

конъюнкции

Пример 3.6. Для высказываний «8 делится на 2», «8 делится на 4» их конъюнкцией будет высказывание «8 делится на 2 и 4», которое, очевидно, будет истинным.

Определение 3.4. Дизъюнкцией двух высказываний и называется высказывание ложное тогда и только тогда, когда ложны оба эти высказывания. Дизъюнкция высказываний и обозначается или и читается «или » (в неразделительном смысле).

В естественном языке дизъюнкция соответствует соединению высказываний союзом «или» в неразделительном смысле.

Составим таблицу истинности операции дизъюнкции. Множество истинности для дизъюнкции между и можно определить, воспользовавшись диаграммой Эйлера – Венна (аналогично конъюнкции) (рис. 3.3).

Таблица 3.3

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

дизъюнкции

– множество истинности для высказывания (на диаграмме – закрашенная область).

Пример 3.7. Высказывание «В треугольнике угол или – острый» истинно, так как обязательно истинно хотя бы одно из высказываний. «В треугольнике угол острый», «В треугольнике угол острый».

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

Импликация высказываний обозначается , или и читается: «влечет », или «если , то », или «из следует », или «является достаточным для », или «является необходимым условием для ».

Высказывание называется посылкой импликации, а – заключением.

Термин «импликация» происходит от латинского implicate – тесно связываю.

Составим таблицу для операции импликация.

Таблица 3.4

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

Пример 3.8. Сравним такие предложения: «Если число делится на 4, то оно делится на 2»; «Если Сидоров увлечен математикой, то Смирнов ничем, кроме футбола, не интересуется». Очевидно, что смысл союза «если... то...» в этих предложениях не один и тот же. В первом случае он соответствует импликации. Второе предложение не является высказыванием.

Пример 3.9. Предположим, вы работаете в юридической консультации, к вам приходит глава разорившейся фирмы (но некогда процветавшей). Фирма производила какую-то продукцию. Глава фирмы издал распоряжение следующего содержания: «Если будет улучшено качество продукции, то все получат премию», а сам улетел отдыхать на Канарские острова на месяц. По возвращении выясняется, что повышения качества не было, но управляющий премию выплатил, т.к. деньги были. Вскоре фирма разорилась (деньги предназначены были для закупки сырья материалов). Глава фирмы теперь собирается через суд взыскать большую сумму денег для компенсации потерь с управляющего, который, по мнению хозяина, исказил его распоряжение.

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

Определение импликации вынуждает считать истинными высказываниями такие предложения, как «Если 2+2=5, то Москва – столица России» или «Если 2-2=3, то существуют летающие зайцы». Эти предложения, вероятно, кажутся бессмысленными. Дело в том, что мы привыкли соединять союзом «если... то» (также как и другими союзами) предложения, связанные по смыслу. Но определениями логических операций смысл составляющих высказываний никак не учитывается; они рассматриваются как объекты, обладающие единственным свойством – быть истинными либо ложными. Поэтому не следует смущаться «бессмысленностью» некоторых составных высказываний. Их смысл не входит в предмет нашего рассмотрения.

Определение 3.6. Эквивалентностью двух высказываний и называется высказывание истинное тогда и только тогда, когда истинности и совпадают.

Эквивалентность обозначается или и читается «эквивалентно », или «тогда и только тогда, когда », или «является необходимым и достаточным для ».

Составим таблицу для операции эквивалентность.

Таблица 3.5

Таблица истинности эквивалентности

Пример 3.9. Высказывание «Треугольник с вершиной и основанием равнобедренный тогда и только тогда, когда » является истинной, так как высказывания «Треугольник с вершиной и основанием равнобедренный» и «В треугольнике с вершиной и основанием » либо одновременно истинны, либо одновременно ложны.

Эквивалентность играет важную роль в математических доказательствах.

Логические связки позволяют из простых высказываний получить новые, сколь угодно сложные высказывания. Рассмотрим пример: «Если завтра будет дождь или снег, то я возьму зонт и надену пальто или свитер». Введем обозначения: = «Завтра будет дождь»; = «Завтра будет снег»; = «Я возьму зонт»; = «Я надену пальто»; = «Я надену свитер». Тогда наше предложение можно записать в виде:

.

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

Первые три закона сформулированы еще Аристотелем.

1. – закон тождества (мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует).

2. – закон противоречия (никакое предложение не может быть истинным одновременно со своим отрицанием).

3. – закон исключения третьего (для каждого высказывания имеются лишь две возможности: это высказывание или истинно или ложно, третьего не дано).

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

5. – идемпотентность операции дизъюнкции.

6. – идемпотентность операции конъюнкции.

7. – коммутативность операции дизъюнкции.

8. – коммутативность операции конъюнкции.

9. – ассоциативность операции конъюнкции.

10. – ассоциативность операции дизъюнкции.

11. – дистрибутивность операции дизъюнкции относительно конъюнкции.

12. – дистрибутивность операции конъюнкции относительно дизъюнкции.

13. , – законы де Моргана для операций дизъюнкция и конъюнкция.

Тождества:

, , , .

Дата добавления: 2013-12-12