Т. А. Сливина математическая логика и теория алгоритмов

Задачи и упражнения

1. Выписать все подформулы формул:

а) ;
б) ;
в) .
2. Для формулы выполнить подстановки
а) ; б) .
3. Применяя правило подстановки и заключения установить доказуемость формул:
а) ;
б) ;
в) .
4. Применяя производные правила вывода, показать, что доказуемы формулы:
а) ;
б) .
5. Доказать, что
а) Н=АВ, ВС ├ АС;
б) Н=АВ ├ (СА)(СВ).
6. Дана формула и наборы значений переменных
1) (1, 0, 0); 2) (0, 1, 1). Записать вывод формулы А или ее отрицания из соответствующей совокупности формул.


Глава 3
ЛОГИКА ПРЕДИКАТОВ

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

§ 1. Понятие предиката. Логические операции над предикатами.
Кванторные операции.


Логика предикатов – это такая логика, которая рассматривает элементарное высказывание, не только с точки зрения его истинности или ложности, но и с точки зрения его структуры и содержания.
Логика предикатов делит элементарное высказывание на субъект (подлежащее) и предикат (сказуемое).
Субъект – это то, о чем что-то утверждается в высказывании.
Предикат – это то, что утверждается о субъекте.


Пример.
Высказывание – «7 простое число».
«7» – субъект, «простое число» – предикат.
Это высказывание утверждает, что «7» обладает свойством «быть простым числом».
Если в этом примере заменить число 7 переменной х из множества натуральных чисел, то получим высказывание «х – простой число». При разных значениях х это высказывание будет принимать различные значения – {0, 1}.
Можно сказать, что это высказывание определяет функцию одной переменной и принимающую значения из множества {0, 1}. Здесь предикат становится функцией субъекта и выражает свойство субъекта.
Одноместным предикатом Р(х) называется произвольная функция переменного х, определенного на множестве М и принимающая значения из множества {0, 1}.
Множество М на котором определен предикат Р(х), называется областью определения предиката.
Множество всех элементов х М, при которых предикат принимает значение «и», называется множеством истинности предиката Р(х):
.


Пример.
1. Р(х) – «х – простое число», определен на множестве N, а множество истинности I_P для него есть множество всех простых чисел.
2. Q(x) – «sin x = 0» определен на множестве R, а множество истинности I_Q =
3. F(x) – «Диагонали параллелограмма х перпендикулярны» определен на множестве всех параллелограммов, а его множество истинности I_F – множество всех ромбов.
Приведенные примеры одноместных предикатов выражают свойства предметов.
Предикат Р(х), определенный на множестве М, называется тождественно истинным, если I_P = M, и тождественно ложным, если I_P = Ø.