Материал: 5540

Можно составить обратную задачу, т.е. по известной диаграмме (рисунок 2.9) находить отвечающее ей компактное аналитическое выражение. Для этого заштрихованные области представим в виде конституент:

С1 a b c, C2 a b c.

Искомое выражение получается при объединении этих конституент: x C1 C2 b ((a c) (a c)) b (a c).

а

C2

c C1

b

Рисунок 2.9 – Обратная задача

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

Задача 2.1. Представьте в явном виде булеву функцию, заданную таблицей:

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

f(1, 0, 1) = f(0, 1, 0) = f(1, 1, 1) = 1.

41

Задача 2.3. Ниже приведены логические функции. Максимально упростите функции, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравните ваше упрощённое выражение с исходным.

а) (a c) (a b) (b c) (a b) (c b);

б) (a c) (a b) (b c) (a b) (b c).

Задача 2.4. Аналитическим способом докажите справедливость нижеприведённых тождеств. Затем с помощью диаграмм Эйлера – Вена и с помощью таблицы истинности подтвердите справедливость этого

Задача 2.5. Ниже приведены диаграммы Эйлера – Вена. Представьте заштрихованные и отдельно не заштрихованные области максимально компактными аналитическими выражениями, в которых бы использовалось минимальное количество логических операций и букв. С этой целью сначала выразите все заштрихованные области через конституенты – конъюнкты, а незаштрихованные – через конституенты – дизъюнкты, и только после этого приступайте к упрощению совершенных форм (результаты проверьте на таблицах истинности).

42

Глава 3. ЛОГИКА ВЫСКАЗЫВАНИЙ

3.1 Классическая логика

Умение правильно рассуждать необходимо в любой области человеческой деятельности: науке и технике, юстиции и дипломатии, планировании народного хозяйства и военном деле. Но, хотя это умение исходит к древнейшим временам, логика, т. е. наука о том, какие формы рассуждений правильны, возникла лишь немногим более двух тысяч лет тому назад. Она была развита в IV веке до н.э. в работах великого древнегреческого философа Аристотеля, его учеников и последователей. Аристотель исследовал различные формы суждений и их комбинации, ввёл понятие силлогизма, т.е. рассуждения, в котором из заданных двух суждений выводится третье. Примером силлогизма может служить такое рассуждение: «Все млекопитающие имеют скелет. Все киты – млекопитающие. Следовательно, все киты имеют скелет». Ту же форму имеет силлогизм «Все квадраты ромбы, все ромбы – параллелограммы. Следовательно, все квадраты – параллелограммы». В общем виде этот силлогизм имеет форму: «Все a есть b; все b есть с. Следовательно, все а есть с». А вот пример силлогизма неправильной формы: «Все квадраты – ромбы. Некоторые ромбы имеют острый угол. Некоторые квадраты имеют острый угол». Хотя оба утверждения, из которых был сделан вывод, истинны, сам вывод о существовании квадратов с острым углом ложен. Значит, силлогизм, имеющий форму: «Все а есть b, некоторые b есть с. Значит, некоторые а есть с», может привести и к ложным выводам. Аристотель выделил четыре типа суждений:

общеутвердительные – «Все а есть b»;

частноутвердительные – «Некоторые а есть b»;

общеотрицательные – «Все а не есть b»;

часноотрицательные – «Некоторые а не есть b».

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

43

Например, утверждая, что «Все а есть b», мы говорим, что множество А всех а – подмножество множества В всех b, А В. Утверждая, что «Некоторые а есть b», мы говорим, что пересечение множеств А и В непусто (предполагаем,

фигур, логические рассуждения тоже изображаются геометрически. Например, рисунок 3.1 поясняет, что «Если все а есть b, а все b есть с, то все а есть с» (если А В и В С, то А С). Рисунок 3.2 служит для пояснения силлогизма «Если все а есть b и ни одно b не является с, то ни одно а не является с» (если А В и В С = Ø, то А С = Ø). А рисунок 3.3 а) поясняет, почему не годится силлогизм «Все а есть b, некоторые b есть с. Значит, некоторые а есть с», хотя А В и В С Ø, но А С может быть и пустым множеством. Впрочем, на рисунке 3.3 б) показан случай, когда А В и В С Ø, и А С Ø, т.е. некоторые а есть с. Это показывает, что неправильно построенное рассуждение не обязательно приводит к ложному выводу: случайно может оказаться так, что вывод будет истинным. Но логика считает допустимым только такие формы рассуждений, которые гарантируют истинный результат во всех случаях, когда исходные утверждения истинны.

44

Пример 3.1. Для следующего рассуждения постройте его буквенную форму и проверьте с помощью диаграмм Эйлера – Вена, правильна ли эта форма: «Если всех хищников можно приручить и всех львов можно приручить, то все львы хищники».

Решение. Обозначим через а – хищника, через b – животное, которое можно приручить, через с – льва. Буквенная форма рассуждения имеет вид: «Если все а являются b и все с являются b, то все с являются а».

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

СВ. На диаграмме Эйлера – Венна (рисунок 3.4) это выглядит так:

В

С

А

Рисунок 3.4 – Диаграмма Эйлера – Венна

Из диаграммы видно, что могут быть такие элементы с из множества С, которые не принадлежат множеству А. Значит рассуждение неправильное.

Задача 3.1. Нарисуйте диаграммы Эйлера – Венна, иллюстрирующие суждения:

а) все а являются b;

б) некоторые а являются b; в) ни одно а не является b;

г) некоторые а не являются b.

45