Вопросы и упражнения

1. Что называется предикатом? Приведите примеры предикатов.

2. Что называется областью определения предиката? Множеством истинности предиката?

3. Перечислите операции, которые можно осуществлять над предикатами. Что такое квантор?

4. Какая операция называется квантификацией?

5. Что называется формулой логики предикатов?

6. Какая формула называется выполнимой; тождественно истинной, тождественно ложной?

7. Какие формулы называются эквивалентными?

8. Что значит высказывание: «предикат находится в приведённой форме»?

9. Определить область истинности I_p предиката, заданного предикатной формулой:

a. P(X,Y)=((X+Y) – нечётно)&( ), где X={5,8,9}, Y={4,7,8,10}.

b. P(X,Y)=((X,Y) – нечётно)&(max(X,Y) – нечётно), где X={2,5,6,8}, Y={3,6,9}.

c. P(X,Y)=((X-Y) – делится на 3)→(X+Y) >6), где X={1,4,5,6}, Y={2,3,4}.

d. P(X,Y)=((X+Y) – нечётно) (X-Y) – делится на 3), где X={1,3,6,7}, Y={2,4.5}.

10. Проверить истинность предикатной формулы, содержащей двухместный предикат P(X,Y) с конечной предметной областью, обе переменные которого связаны кванторами. Предикат задан следующей таблицей:

Определить значения высказываний (0-местных предикатов):

11. Построить n – местные предикаты на множестве такие, что , - выполним.

12. Представить предикат в приведённой форме.

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

14. Дать словесную формулировку составного высказывания:

,

где S и D – предикаты суммы и делимости соответственно

15. Пусть предикат « - натуральное число». Рассмотреть варианты навешивания кванторов. Проинтерпретировать полученные высказывания и определить их истинность.

16. Пусть описывает отношение « любит y» на множестве людей. Рассмотреть варианты навешивания кванторов. Проинтерпретировать полученные высказывания и определить их истинность.

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

18. Рассмотреть все возможные варианты навешивания кванторов на предикат – “х делится на у”, определённый на множестве натуральных чисел (без нуля). Дать словесные формулировки полученных высказываний и определить их истинность.

19. Какой смысл имеют предикатные формулы:

(1) ;

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

20. Определить истинность, ложность или выполнимость формул:

(1) ;

(2) ;

(3) ;

(4) ;

(5)

21. Показать истинность формулы .

22. Представить в приведённой форме предикат:

(1) ⅂( ;

(2) ;

(3) .

Список литературы

1. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики [Текст]: Учебное пособие. М.:Форум: ИНФРА-М, 2006.

2. Канцедал С.А. Дискретная математика [Текст]. – М.:ИД «Форум»: ИНФРА-М, 2007.

3. Судоплатов С.В. Элементы дискретной математики [Текст]. – М.: ИНФРА – М, Новосибирск: Изд-во НГТУ, 2008г.

Оглавление

Тема 1. Введение в теорию логики. Логические операции.. 2

Тема 2. Законы логики.. 8

Тема 3. Нормальные формы алгебры высказываний. Теорема о функциональной полноте ……. 10

Тема 4. Минимизация булевых функций в классе ДНФ. Метод минимизирующих карт …………………………….14

Тема 5. Метод неопределённых коэффициентов. 15

Тема 6. Метод квайна. 18

Тема 7. Метод квайна-мак-класки.. 20

Тема 8. Полные системы булевых функций.. 22

Тема 9. Логика предикатов. 25

Список литературы.. 35