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

Цель
Изучить понятие предикатов

Задачи
Логика предикатов.
Связь предиката с булевыми функциями и высказываньями.
Примеры.

Разница
В высказывании все четко: это — конкретное утверждение о конкретных объектах — истинное или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно.

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

Понятие '' предикат'' обобщает понятие ''высказывание''. Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.

Определение
Предикатом называется повествовательное предложение, содержащее предметные переменные, определённые на соответствующих множествах; при замене переменных конкретными значениями (элементами) этих множеств предложение обращается в высказывание, т. е. принимает значение «истинно» или «ложно».

Определение
Предикатом называется функция P : M n → B , где B = { 0,1 } , M - любое множество,
т. е. функция P , сопоставляющая вектору (x1 , x2 ,..., xn ) значения 0 или 1.

Определение
Определенным на множествах M1,M2,…,Mn n-местным предикатом называется предложение, содержащее n переменных x1,x2,…,xn, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств M1,M2,…,Mn соответственно.

Пример предикатов
''Сократ - человек'', ''Платон - человек''.
Оба эти высказывания выражают свойство ''быть человеком''. Таким образом, мы можем рассматривать предикат ''быть человеком'' и говорить, что он выполняется для Сократа и Платона.

Возьмём высказывание:
''расстояние от Иркутска до Москвы 5 тысяч километров''. Вместо него мы можем записать предикат ''расстояние'' (означающий, что первый и второй аргумент этого предиката находятся на расстоянии, равном третьему аргументу) для аргументов ''Иркутск'', ''Москва'' и ''5 тысяч километров''.

Множество M называется предметной областью предиката P , x1 , x2 ,..., xn - предметные переменные, P - предикатный символ, n - местность предиката, декартово произведение M × M × ... × M область определения предиката P . Обозначение: P (x1 , x2 ,..., xn )- n - местный предикат, заданный на множестве M .

Областью истинности предиката P называется подмножество Tp (T, Ip)⊆ Mn его предметной области, на элементах которого значения предиката равны 1.

Классификация предикатов
тождественно истинное
тождественно ложное
выполнимое (опровержимое)

а) тождественно истинным, если при любой подстановке вместо переменных x1 , x2 ,..., xn любых конкретных предметов а1 , а2 ,..., аn из множеств M1,M2,…,Mn соответственно он превращается в истинное высказывание P(а1 , а2 ,..., аn);

б) тождественно ложным, если при любой подстановке вместо переменных x1 , x2 ,..., xn любых конкретных предметов из множеств M1,M2,…,Mn соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов а1 , а2 ,..., аn из множеств M1,M2,…,Mn соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат последний P(x1 , x2 ,..., xn ) превратится в истинное (ложное) высказывание P(а1 , а2 ,..., аn) .

Пример
Одноместный предикат "Город X расположен на берегу реки Волги", определенный на множестве названий городов, является выполнимым, потому что существуют города, названия которых превращают данный предикат в истинное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т. д.). Но данный предикат не будет тождественно истинным, потому что существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.).

Найти область истинности предиката
P ( X, Y ) = (( X + Y ) - нечётно ) ∨ (( X - Y ) делятся на 3) ,
где X = {1;3;6;7}, Y = {2;4;5}.

Решение

Найти область истинности предиката
P ( X ) = (( число 3 не делитель x ) → ( x ≤ 6 ))
на множестве однозначных натуральных чисел.

Решение
Определим области истинности предикатов P1 = {число 3 не не делитель x},
P2 = {x ≤ 6}, P = P1→ P2 .
IP1 = {1,2,4,5,7,8}, IP2 = {1,2,3,4,5,6}, IP = IP1→P2 = IP1 = {1,2,3,4,5,6,9}.
Ответ: I P = {1,2,3,4,5,6,9}.

Кванторы