Семинар №5. Логика предикатов

Цель семинара:

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

План занятия:

Рассматривается тема логика предикатов на которую отводится 2 часа семинарских занятий.

Задача 1. Каким отношениям и функциям соответствуют следующие предикаты, определённые на множестве натуральных чисел:

1. Предикат тождества Е:N²→B:

E(a₁,a₂)=1 тогда и только тогда, когда a₁=a₂.

2. Предикат порядка Q:N²→B:

Q(a₁,a₂)=1 тогда и только тогда, когда a₁ ≤ a_2.

3. Предикат делимости D:N²→B:

D(a₁,a₂)=1 тогда и только тогда, когда a₁ делится на а₂.

4. Предикат суммы S:N³→B:

S(a₁,a₂,a₃)=1 тогда и только тогда, когда a₁+a₂=a_3.

5. Предикат произведения П:N³→B:

П(a₁,a₂,a₃)=1 тогда и только тогда, когда a₁*a₂=a₃.

Решение.

1. Двухместному предикату тождества Е-“x₁”=”x₂” взаимно однозначно соответствуют:

а) двухместное отношение R₁ – «быть равным», R₁ N²:(a₁,a₂) R₁ тогда и только тогда, когда E(a₁,a₂)=1;

б) одноместная функция (операция) тождества f₁(x₁)=x₂, а именно: f₁(x)=x, f:N→N.

2. Двухместному предикату порядка Q-“x₁ ≤ x₂” взаимно однозначно соответствует двухместное отношение R₂- «быть не больше», R₂ N₂:(a₁,a₂) R₂ тогда и только тогда, когда Q(a₁,a₂)=1.

Однако функции f(x₁)=x₂ для предиката порядка Q(x₁,x₂) не существует, так как не выполнено условие Р'(а₁,а₂,…а_n,а_n+1)=0 при одинаковых значениях переменной x₁ существует не единственно значение переменной x₂, при котором предикат Q истинен. Например, Q(2,4)=1 и Q(2,6)=1, однако 4≠6.

3. Двухместному предикату делимости D-“x₁ делится на х₂” взаимно однозначно соответствует двухместное отношение R₃- “делится”, R₃ N²:(a₁,a₂) R₃ тогда и только тогда, когда D(a₁,a₂)=1.

Однако функции f(x₁)=x₂ для предиката делимости D(x₁,x₂) не существует, так как не выполнено условие Р'(а₁,а₂,…а_n,а_n+1)=0, например D(6,2)=1 и D(6,3)=1, однако 2≠3.

4. Трехместному предикату суммы S- “х₁+х₂=х₃” взаимно однозначно соответствуют:

а) трёхместное отношение R₄ N³: (a₁,a_2, a₃) R₄ тогда и только тогда, когда S(a₁,a₂,a₃)=1;

б) двухместная функция (операция арифметики)- сложение f₂(x₁,x₂), а именно х₁+х₂=х₃.

5. Трёхместному предикату произведения П- “x₁*x₂=x₃” взаимно однозначно соответствуют:

а) трёхместное отношение R₃ N³: (a₁,a_2, a₃) R₅ тогда и только тогда, когда П (х₁,х₂,х₃)=1;

б) двухместная функция (операция арифметики)- умножение f₃(x₁,x₂)=x₃, а именно х₁*х₂=х_3.

Взаимная однозначность соответствия между S и f₂ (П и f₃), обусловлена выполнением для предиката S(П) условия Р'(а₁,а₂,…а_n,а_n+1)=0 для каждой системы элементов a₁,a₂ N существует единственный элемент а₃ N такой, что S(a₁,a₂,a₃)=1 (соответственно для П(a₁,a₂,a₃)=1).

Задача 2. Проиллюстрировать на примере предиката делимости, определённого в задаче 1, понятия переменного высказывания, истинного высказывания, ложного высказывания.

Решение.

Предикат делимости D(x₁,x₂)- это переменное (двухместное) высказывание, предметной областью которого могут служить любые множества действительных чисел, например множество N.

D(6,2)- высказывание, значение которого есть истина, т.е. истинное высказывание.

D(5,2)- ложное высказывание.

D(3,х), D(х,2)- переменные (одноместные) высказывания, истинность которых зависит от того, каким числом будет замещён символ x, но D(а,1)- истинное высказывание, так как для любого элемента а N имеет место: D(а,1)=1 (любое натуральное число делится на единицу).

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

Решение.

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

«если а делится на b и b делится на с, то а делится на с», состоит из трёх простых высказываний D(a,b), D(b,c) и D(a,c). Следовательно, транзитивное свойство делимости можно записать в виде составного высказывания (логической формулы):

«если D(a,b) и D(b,c), то D(a,с) или (D(a,b) & D(b,c)) → D(a,c).

Задача 4. Дать словесные формулировки следующих составных высказываний (предложений):

1. S(a,b,c) & D(a,d) & D(b,d)→D(c,d), где S и D- предикаты суммы и делимости соответственно (см.пример 1);

2. D(a,b) & S(a,b,c);

3. S(a,b,c) ~ S(b,a,c);

4. P₁ ~ P₂, где P₁ – предикат «число 3n является чётным»; Р₂- предикат «число n является чётным».

Примечание. Здесь и далее для обозначения связки (логической операции) отрицания будем использовать символ , принятые в логике предикатов.

Решение.

1. «Если каждое слагаемое a,b суммы целых чисел делится на некоторое число d, то и сумма с делится на это число»:

S(a,b,c) & D(a,d) & D(b,d)→D(c,d).

2. «Число а не делится на число b, и неверно, что их сумма равна с»: D(a,b) & S(a,b,c).

3. «От перестановки мест слагаемых a и b сумма с не меняется»- свойство коммутативности арифметической операции сложения: S(a,b,c) ~ S(b,a,c).

4. «Число 3n является чётным тогда и только тогда, когда n является чётным»: P₁ ~ P_2.

Эквивалентность может быть выражена и другими словесными формулировками, в том числе:

· «из того, что Р₁, следует то, что Р₂, и обратно»;

· «из того, что Р₂, следует то, что Р₁, и обратно»;

· «условия Р₁ необходимо и достаточно для того, чтобы Р₂»;

· «Р₂ необходимо и достаточно, чтобы Р₁»;

· «Р₁, если и только если Р₂»;

· «Р₂, если и только если Р₁»;

· «условия Р₁ и Р₂ эквивалентны»;

· «Р₂ тогда и только тогда, когда Р₁» и др.

Задача 5. Пусть х определён на множестве людей М, а Р(х)- предикат «х-смертен». Дать словесную формулировку предикатной формулы

Решение.

Выражение означает «все люди смертны». Оно не зависит от переменной х, а характеризует всех людей в целом, т.е. выражает суждение относительно всех х множества М.

Задача 6.Пусть Р(х)- предикат «х-чётное число», определённый на множестве М. Дать словесную формулировку высказывания определить его истинность.

Решение.

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

Пусть предикат Р(х) определён на множестве натуральных чисел N, т.е. , тогда высказывание - истинно. В общем случае высказывание истинно на любом множестве М, содержащем хотя бы одно чётное число, и ложно на любом множестве нечетных чисел.

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

Решение.

- высказывание «все числа- натуральные» истинно на любом множестве натуральных чисел и ложно, если М содержит хотя бы одно ненатуральное число, например целое отрицательное;

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

Задача 8. Записать предикатной формулой предложение «Любой человек имеет отца».

Решение.

Для построения предикатной формулы используем два предиката «х- человек» и «у- отец х» и для удобства восприятия обозначим их соответственно: ЧЕЛОВЕК (х) и ОТЕЦ (у). Тогда предложение «Любой человек имеет отца» в предикатной форме имеет вид:

Заметим, что если предикат ОТЕЦ(у,х) определён на множестве людей, то выражение «любой человек имеет отца» можно записать проще:

Задача 9. Пусть предикат Р(х,у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.

Решение.

Обозначим предикат «х любит у» через ЛЮБИТ (х,у). Предложения, соответствующие различным вариантам навешивания

ЛЮБИТ(х,у)- «для любого человека х существует человек у, которого он любит» или «всякий человек кого-нибудь любит» (рис. а);

ЛЮБИТ (х,у)- «существует такой человек у, что его любят все х» (рис. б)ж

ЛЮБИТ (х,у)- «все люди любят всех людей» (рис. в);

ЛЮБИТ (х,у)- «существует человек, который кого- то любит» (рис. г);

ЛЮБИТ (х,у)- «существует человек, который любит всех людей» (рис. д);

ЛЮБИТ (х,у)- «для всякого человека существует человек, который его любит» (рис. е).

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

Задача 10. Пусть Q(x,y)- предикат порядка «х≤у». Рассмотреть различные варианты квантификации его переменных. Определить истинность получаемых выражений для разных случаев интерпретации области определения М предиката, х, у М.

Решение.

- одноместный предикат от у: « для любого х имеет место х≤у». Если М- бесконечное множество неотрицательных целых чисел, то этот предикат ложен; на любом конечном множестве натуральных чисел предикат истинен в единственной точке, представляющей наибольшее число в М. При подстановке любого другого у из М этот предикат обращается в ложное высказывание;

- одноместный предикат от х: «для любого у имеет место х≤у». Если М-множество неотрицательных целых чисел, то этот предикат истинен в единственной точке х=0 и ложен при подстановке вместо х любого числа из М;

- одноместный предикат от у: «существует число в М, которое не больше у». Если М- любое непустое множество чисел, то данный предикат превращается в истинное высказывание при подстановке какого- либо у из М.

- одноместный предикат от х: « существует число в М, которое не меньше х». На любом непустом множестве М чисел данный предикат превращается в истинное высказывание при подстановке какого- либо х из М.

- высказывание « для любых х и у выполняется х≤у» ложно на любом множестве, состоящем более, чем из одного элемента, и истинно на множестве с одним элементом;

- высказывание «существуют такие х и у, что х≤у» истинно на любом непустом множестве;

- высказывание «для любого числа х существует число у, не меньше чем х» истинно на любом непустом множестве;

- высказывание «существует у такой, что для любого х х≤у»утверждает, что в М имеется единственный максимальный элемент;

- высказывание «существует х такой, что он не больше любого у» утверждает, что в М имеется единственный минимальный элемент.

- высказывание «для любого числа у существует число х, не больше, чем у» истинно на любом непустом множестве

Задача 11. Рассмотреть все возможные варианты навешивания кванторов на предикат D(х,у)- «х делится на у», определенный на множестве натуральных чисел N. Дать словесные формулировки полученных высказываний и определить их исьтинность.

Решение.

Операции навешивания кванторов приводят к следующим формулам:

- одноместный предикат «всякое натуральное число из N делится на натуральное число у из N»; истинный только для одного значения свободной переменной у=1;

- переменное высказывание «существует натуральное число, которое делится на у», истинное для любого значения свободной переменной у, взятой из множества N;

- переменное высказывание «натуральное число х делится на всякое натуральное число у», ложное для любого значения свободной переменной х, взятой из N;

- переменное высказывание «существует натуральное число, которое делит натуральное число х», истинное для любого значения свободной переменной х;

- высказывания «для любых двух натуральных чисел имеет место делимость одного на другое» ложные;

- высказывания «существуют такие два натуральных числа, что первое делится на второе», истинны;

- высказывание «существует натуральное число, которое делится на любое натуральное», ложное;

- высказывание « для всякого натурального числа найдется такое натуральное, которое делится на первое», истинное;

- для всякого натурального существует такое натуральное число, на которое оно делится», истинное»

- высказывание «существует натуральное число, которое является делителем всякого натурального числа», истинное.

Задача 12.Привести к ПНФ следующую предикатную формулу:

.

Решение.

Поскольку в данной предикатной формуле имеются два высказывания и , объединённые связкой & и общим отрицанием , то, применив правило де Моргана к исходной формуле, получим:

Воспользуемся далее эквивалентным соотношением

.

Продолжая перемещение символов непосредственно к символам предикатов, используем соотношение :

.

Так как квантор общности не дистрибутивен относительно дизъюнкции , поменяем в каком-либо предикате, например во втором, переменную x на новую переменную z:

.

Воспользовавшись дважды эквивалентным соотношением или соотношением , получим:

.

Поскольку квантор существования дистрибутивен относительно дизъюнкции окончательно получим префиксную нормальную форму для исходной предикатной формулы:

.