Формулы логики предикатов.

Применяя к предикатам операции отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности, квантор общности, квантор существования, получаем формулы логики предикатов.

Примеры:1.

2.

Формула логики предикатов называется тавтологией, если приподстановке любых конкретных предикатов она всегда обращается в тождественно-истинный предикат.

Сформулируем следующие правила:

1. Формула логики предикатов называется атомарной (элементарной), если в ней нет связанных переменных.

2. Если F- формула, то и - тоже формула. Свободные и связанные переменные формулы F так же являются свободными и связанными переменными в формуле .

3. Пусть F и G – формулы, и в них нет переменных, которые были бы связаны в одной и свободны в другой формуле. Тогда - формулы, в которых свободные переменные формул F и G остаются свободными, а связанные – связанными.

4. Пусть - формула, содержащая свободные переменные x, y, z. Тогда и -формулы, в которых переменная x – связанная, а остальные свободные.

Равносильные формулы логики предикатов.

Формулы F и G равносильны в логике предикатов, если они равносильны на всех множествах. При этом пишут .

Рассмотрим равносильные формулы логики предикатов:

1.

- перенос квантора через отрицание

2.

- вынос квантора за скобки

3.

- перестановка одноимённых

кванторов

Примеры:

1. Переведите следующие высказывания на язык алгебры предикатов:

а) все целые числа неотрицательны

Решение:

б) хотя бы одно натуральное число делится на 6

Решение:

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

а)

Решение: Найдётся целое число либо составное, либо чётное.

б)

Решение: Если любое рациональное число составное, то оно нечётное.

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

Решение: Для любого натурального числа x найдётся целое число y такое, что их сумма будет отрицательной.

V. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО НАПИСАНИЮ И ОФОРМЛЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

Общие положения

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

Обучающимся заочного отделения предлагается контрольная работа по дисциплине «Элементы математической логики».

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

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