Дискретная математика

Задачи для решения (типовой расчет)

1.Доказать теоремы 1-10.

2.Для заданной функции f1 построить таблицу истинности. Выписать соответствующие ей совершенные дизъюнктивную и конъюнктивную нормальные формы.

3.Привести заданную функцию f2 к базису (если номер варианта нечетный, то выбрать базис 1 , а если четный – то 2 ). Построить таблицу истинности исходной и преобразованной функций.

4.Определить классы Поста для функций f1 и f2. Дополнить ФПС ={f1 ,f2 } до базиса.

Функции для заданий 2-4

13

Дискретная математика

Логика и исчисление предикатов

Предикатом называется функция P(x1 , x 2 ,…, x n ) , переменные которой принимают значения из некоторого множества M, а сама она принимает два значения T (true – истина), или F(false - ложь). Таким образом, предикат есть отображение P(x1 , x 2 ,…x n ) : M n →{F, T} .

Иногда, как и в булевой алгебре, значения {F,T} заменяются на {0,1}. Предикат от n переменных называется n-местным предикатом. В частности, высказывания являются нульместными предикатами. На практике чаще всего имеют дело с предикатами первого порядка. Пример 1. Рассмотрим примеры предикатов разной местности.

n=0 P {0,1} нульместный предикат, например, «идет снег».

n=1 P(x) {0,1} одноместный предикат или предикат свойства, например, «трава зеленая»: P = “быть зеленым”, x = “трава”.

n=2 P(x,y) {0,1} двуместный предикат или предикат отношения, например, «x брат y», «x больше y» и т.д.

Смысл понятия «предикат» можно сопоставить с высказыванием относительно свойств объектов или их отношений.

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

Квантор всеобщности. Пусть P(x) – некоторый предикат, принимающий значение T или F для каждого элемента множества M. Тогда под записью x P(x) будем подразумевать высказывание, истинное, когда P(x) истинно для каждого элемента x M, и ложное – в противном случае. Читается эта запись так: “для всех x (выполняется, верно) P(x)”. Это новое высказывание уже от x не зависит. Символ называется квантором всеобщности.

Квантор существования. Пусть P(x) – некоторый предикат. Под выражением x P(x) будем понимать высказывание, истинное, когда существует элемент (хотя бы один) множества M, для которого P(x) истинно, и ложное – в противном случае. Читается эта запись так: “существует x такое, что (выполняется, верно) P(x)”. Это новое высказывание от x не зависит. Символ называется квантором существования.

Пример 2. Пусть P(x) = {x: “x делится на 2”}, Q(x) = {x: “x делится на 3”}. Рассмотрим два новых предиката R1 (x) = P(x) Q(x) и R 2 (x) = P(x) Q(x) , из определения которых

следует, что R1(x)=T “x делится одновременно на 2 и на 3”, а R2(x)=T “x делится на 2 или на 3”. Тогда высказывание x R1 (x) – истинное, а x R1 (x) – ложное, поскольку в

первом случае очевидно, что существуют такие числа, которое одновременно делятся на 2 и на 3 (например, 6), а во втором – не все возможные числа одновременно делятся на 2 и на 3 (например, 4). Аналогично, высказывание x R 2 (x) будет ложным, а x R 2 (x) – истинным.

Свойства кванторов.

14

Дискретная математика

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

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

1)«Все люди смертны»;

2)«Некоторые треугольники не прямоугольные».

Решение.

1)Введем в рассмотрение предикатные символы P(x) = T x – человек, Q(x) = T x – смертен. Тогда первое утверждение может быть записано как A = x (P(x) Q(x)), т.е. «для любого x верно, что если x-человек, то он смертен». Построим отрицание этого утверждения и преобразуем его согласно формулам (4)-(5) и законам логики:

¬A = A = ¬( x (P(x) Q(x)) = x ¬(P(x) Q(x)) = x ¬(P(x) Q(x)) = x (P(x) Q(x)) .

Последнее утверждение читается как «есть такие x, которые одновременно являются людьми и не являются смертными», или иначе «существуют бессмертные люди». Очевидно, что истинным является первое высказывание A.

2)Во втором случае рассмотрим предикаты P(x) = T x – треугольник, Q(x) = T x – прямоугольный. Тогда соответствующее утверждение может быть записано в следующем виде: B = x (P(x) Q(x)) , т.е. «существуют такие треугольники x, которые не являются прямоугольными». Построим отрицание этого утверждения и преобразуем его:

¬B = B = ¬( x (P(x) Q(x)) = x ¬(P(x) Q(x)) = x (P(x) Q(x)) ,

что читается как «произвольный объект x не является треугольником или является прямоугольным». Очевидно, что высказывание B является истинным.

Исчисление одноместных предикатов как исчисление классов. Силлогистика Аристотеля.

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

15

Дискретная математика

Категорическим суждением в логике Аристотеля называется высказывание о двух классах. Всего выделяется четыре вида категорических суждений.

Тип A. Высказывание вида “Все предметы класса P суть предметы класса Q” называется

общеутвердительным.

Тип E. Высказывание вида “Все предметы класса P не суть предметы класса Q” называется

общеотрицательным.

Тип I. Высказывание вида “Некоторые предметы класса P суть предметы класса Q”

называется частноутвердительным.

Тип O. Высказывание вида “Некоторые предметы класса P не суть предметы класса Q”

называется частноотрицательным.

Категорическим силлогизмом называется конструкция из трех категорических суждений о трех классах, в которой третье суждение логически следует из двух первых. При этом первое суждение называется большой посылкой, второе – малой посылкой, а третье – заключением. Класс, присутствующий в большой и малой посылках, называется средним и обозначается буквой P. Класс, присутствующий в большой посылке и заключении, называется большим и обозначается буквой Q. Наконец класс, присутствующий в малой посылке и заключении, называется малым и обозначается буквой S.

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

Пользуются этими именами следующим образом. Гласные буквы подставляются в заданном соответствующим именем порядке в шаблон группы модусов. Эти буквы означают тип категорического суждения.

Пример 4. Построить силлогизм по модусу Festino.

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

Qe P “Все киты – не сухопутные” – высказывание общеотрицательное

Si P “Некоторые млекопитающие - сухопутные” – высказывание частноутвердительное

16