UML_4822 дм практикум

принимает значение 1 только при х = 3 и х = 1 и 0 в остальных случаях. Но тогда высказывание х Q(х) ложно, а высказывание х Q(х) истинно.

Задача 249. Установите, какие из следующих высказываний истинны, а какие ложны, при условии, что область определения предикатов М совпадает с R:

1) x(x 5 x 3) ;

3) x x2 x 1 0 ;

4) x x2 5x 6 0 ;

5) x (x 5x 6 0) & (x2 2x 1) 0 ; 6) x x2 6x 8 0 x2 6x 8 0 ; 7) x x2 5x 6 0 x2 6x 8 0 ; 8) x x {2,5} x2 6x 8 0 ;

9) x x {3,5} x2 6x 8 0 .

Ответ. Истинны высказывания 3), 5), 6), 7), 8), остальные высказывания ложны.

Задача 250. Приведите примеры таких значений а, для которых данное высказывание: а) истинно; б) ложно (М = R).

a 20 ложно;

121

4) Например, при a 32 данное высказывание истинно, а при a>2

или a 2 ложно.

4.4. Формула логики предикатов, ее свойства и значение

Напомним символику логики предикатов:

1.Символы P, Q, R,... – переменные высказывания, принимающие два значения: 1 – истина, 0 – ложь, {И, Л}.

2.Предметные переменные – x, y, z,..., которые принимают значения из некоторого множества М; x0, y0, z0,... – предметные константы, то есть значения предметных переменных.

3.P( ), F( ) – одноместные предикатные переменные; Q( , ,..., ), R( , ,..., ) – n-местные предикатные переменные. P0( ), Q0( , ,..., ) – символы постоянных предикатов.

4.Символы логических операций: &, , , , –.

5.Символы кванторных операций х, х.

6.Вспомогательные символы: скобки, запятые.

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

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

2.Если Р( , ,..., ) – n-местная предикатная переменная или постоянный предикат Р0( , ,..., ), а х1, х2, ..., хn – предметные переменные или предметные постоянные, не обязательно все различимые, то Р(х1, х2, ..., хn) есть формула. В этой формуле предметные переменные являются свободными. Формулы вида 1 и 2 называются элементарными.

3.Если А и В – формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой свободной,

то слова А B, А&B, А B есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, являются свободными,

ате, которые были связанными, являются связанными.

4.Если А – формула, то и А – формула, и характер предметных переменных при переходе от формулы А к формуле А не меняется.

5.Если А(х) – формула, в которую предметная переменная входит

свободно, то слова x А(x) и x А(x) являются формулами, причем предметная переменная в них входит связанно.

6.Никакая другая строка символов формулой не является.

7.Принятые соглашения об опускании скобок в формулах ЛВ распространяются на формулы ЛП.

Покажем, например, что последовательность символов

x y P(x,y) z S(z) p

есть формула.

122

1.р - формула (п.1 определения);

2.P(x,y) - формула (п.2 определения);

3.S(z) - формула (п.2 определения);

4.z S(z) - формула (п.5 определения);

5.z S(z) p - формула (п.5 и п.3 определения);

6.y P(x,y) - формула (п.2 и п.5 определения);

7.x y P(x,y) - формула (п.2 и п.5 определения);

8.x y P(x,y) z S(z) p - формула (из 7 и 6 по п.3 определения). Не является формулой слово x Q(x, y) P(x). Здесь нарушено усло-

вие п.3, так как в формулу x Q(x, y) переменная х входит связано, а в формулу Р(х) переменная х входит свободно.

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

В качестве примера рассмотрим формулу

y z (P(x,y) P(y,z)),

в которой двухместный предикат Р(х,у) определен на множестве М М, где M={0,1,2,..., n}. В формулу входит предикат Р(x,y), предметные переменные x, y, z, две из которых y и z - связанные кванторами, а x - свободная. Пусть конкретное значение предиката Р(x,y): «x<y», а свободной переменной х придадим значение

х0=5 М.

Тогда при значениях у, меньших х0=5 предикат Р0(x0,y) принимает значение Л, а импликация P(x,y) P(y,z) при всех z М принимает истинное значение, то есть высказывание

y z (P(x,y) P0(y0,z))

имеет значение И.

Задача 251. Пусть заданы предикаты: N(x) - «х - натуральное число, x N»; C(x) - «х - целое число, x С»;

Р(x) - «х – простое число»;

В(x) - «х - положительное число»; T(x) - «х - четное число, x Т»; D(x,у) - «х делит у».

Сформулировать на языке ЛП приведенные высказывания и указать, какие из них истинны, какие ложны:

123

Ответ:

1)«Все натуральные числа - целые» (И);

2)«Некоторые натуральные числа - целые» (И);

3)«Все целые числа - натуральные» (Л);

11) «Всякое простое число нечетное» (Л).

Необходимо выполнить задания 4)-10) самостоятельно. Задача 252. Выразите на языке ЛП следующие высказывания:

1) «Не существует предмета, обладающего свойством Р» (или «неверно, что существует предмет, обладающий свойством Р»).

Ответ. x P x ;

2) «Существует по крайней мере один предмет, обладающий свойством Р» (выражение «существует по крайней мере один предмет» понимается в том смысле, что «существует предмет»).

Ответ. x P x ;

3) «Не существует более одного предмета, обладающего свойством Р» (или «существует не более одного предмета, обладающего свойством

Р»).

4)«Существует точно один предмет, обладающий свойством Р» (или «существует предмет, обладающий свойством Р и не существует более

одного предмета, обладающего этим свойством»).

Ответ. x P x y P y x y ;

5)«Существует не более двух предметов, обладающих свойством Р» (или «для всяких трех предметов x, y, z, если каждый из них обладает

свойством Р, то x=z или y=z или х=у»).

Ответ. x, y, z P x P y P x x z y z x y .

Задача 253. Какие из следующих выражений являются формулами логики предикатов? В каждой формуле выделите свободные и связанные переменные.

1. x z P(x, y) P( y, z) ;

2. p q & r p ;

124

3.P(x) & x Q(x) ;

4.x P(x) Q(x) x P(x) x R(x, y) ;

5.P(x) Q(x) y ( y R( y));

6.x z P(x, y) P( y, z) .

Решение. Выражения 1), 2), 4), 6) являются формулами, так как записаны в соответствии с определением формулы логики предикатов. Выражения 3) и 5) не являются формулами: в выражении 3) операция конъюнкции применена к формулам Р(х) и x Q(x) ; в первой из них перемен-

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

Вформуле 1) переменная у свободна, а переменные х и z не связаны.

Вформуле 2) нет предметных переменных. В формуле 4) переменная х

связана, а переменная у свободна.

Задача 254. Дана формула x P(x) & Q(x) R(x) , где предикаты

Р(х), Q(x) и R(x) определены на множестве N. Найти ее значение, если:

1)Р(х): «число х делится на 3»; Q(x): «число х делится на 4»; R(x): «число х делится на 2»;

2)Р(х): «число х делится на 3»; Q(x): «число х делится на 4»; R(x): «число х делится на 5».

Решение. В обоих случаях предикат P(x) & Q(x) есть утверждение,

что число х делится на 12. Но тогда при всех х, если число х делится на 12, то оно делится и на 2, и, значит, в случае 1) формула истинна.

Так как из делимости числа х на 12 не при всех х следует делимость числа х на 5, то в случае 2) формула ложна.

Задача 255. Вычислить значение формулы

x y P(x, y) x y P(x, y) ,

если предикат P(x, y) имеет значение Р0(х, у) – «число х меньше числа у» и определен на множестве М = N N.

Решение. Так как при указанном значении предиката P(x, y) высказывание x y P(x, y) означает утверждение, что для любого натурального числа х найдется натуральное число у, больше числа х, то это высказывание истинно. В то же время высказывание x y P(x, y) означает утвер-

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

125

Задача 256. Укажите, какие из следующих выражений являются формулами логики предикатов. В каждой формуле выделите свободные и связанные переменные:

1)x y P(x, y) ;

2)x, y P(x, y) ;

3)x P(x) y Q(x, y) ;

4)x y P(x, y) ;

5)P x P(x, y) ;

6)x P(x, y) & Q( y, z) .

Ответ. Выражения 1), 4), 5), 6) являются формулами логики предикатов, а остальные – нет.

Задача 257. Даны выражения А(n): «число n делится на 3»; В(n): «число n делится на 2»; С(n): «число n делится на 4»; D(n): «число n делится на 6»; E(n): «число n делится на 12».

Укажите, какие из следующих утверждений истинны, какие ложны:

1)n (A(n) & B(n) E(n));

2)n (B(n) & D(n) E(n)) ;

3)n (C(n) & D(n) E(n));

4)n (E(n) C(n) & D(n));

5)n (E(n) B(n) & D(n)) ;

6)n (B(n) & C(n) D(n)) .

Ответ. Истинны утверждения 1), 3), 4), 6), а ложны – 2) и 5).

4.5. Равносильные формулы

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

Определение. Две формулы логики предикатов 1 и 2 называются равносильными на области М, если выражают одну и ту же логическую функцию от содержащихся в них предикатных и свободных предметных переменных, то есть если они принимают обе значение И или обе значение Л при всех значениях этих переменных, отнесенных к области М.

Определение. Две формулы логики предикатов А и В называют равносильными, если они равносильны на всякой области.

Равносильные формулы ЛВ являются также равносильными формулами ЛП. Обозначение этого события А В.

126

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

Рассмотрим основные из этих равносильностей. Пусть А(х) и В(х) - переменные предикаты, С - переменное высказывание, тогда приведем основные равносильности.

Это означает, что если не существует х, при котором истинно А(х), то для всех х будет истинной A x .

На основе равносильностей (4.4) и (4.5) формулируется следующее правило построения отрицания высказывания с квантором:

квантор общности меняется на квантор существования и обратно, а знак отрицания переносится на выражение, стоящее за этим квантором.

Это же правило применимо и к формулам, содержащим несколько кванторов. Например,

x y P x, y x y P x, y x y P x, y .

Равносильности (4.6) и (4.7) получаются соответственно из равносильностей (4.4) и (4.5), если от обеих частей взять отрицание и воспользоваться законом двойного отрицания.

Если предикаты А(х) и В(х) одновременно тождественно истинные, то будет тождественно истинным и предикат А(х)&В(х), а поэтому будут

то есть в этом случае обе части равносильности (4.8) принимают значение «истина». Если хотя бы один из предикатов А(х) или В(х) будет не тождественно истинным, то и обе части равносильности (4.8) примут одинаковые (ложные) значения.

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

127

будет предикат С В(х) и, очевидно, истинными будут высказывания

ют истинные значения.

При С=И и условиях, заданных выше, и в этом случае обе части равносильности принимают одинаковые (истинные) значения. Если предикат В(х) не является тождественно истинным, то ложными будут x B x ,

Если область определения предиката Р(х) - конечное множество М={а1, а2, ..., аn}, то из самого смысла кванторов общности и существования следует, что

128

Однако, справедливы равносильности:

x A x x B x x A x y B y

x A x y B y x y A x B y .x A x & x B x x A x & y B y

x A x & y B y x y A x & B y .

Пример 258. Доказать равносильность

x(P(x) Q(x)) x P(x) xQ(x).

Решение. Для доказательства равносильности достаточно рассмотреть два случая:

1. Пусть предикаты P(х) и Q(х) тождественно ложны. Тогда будет тождественно ложным и предикат P(х) Q(х) . При этом будут ложными

высказывания х P(х) Q(х) и х P(х) хQ(х) .

2. Пусть теперь хотя бы один из предикатов (например P(х)) не тождественно ложный. Тогда будет не тождественно ложным и предикат P(x) Q(x). При этом будут истинными высказывания х P(х) их P(х) Q(х) , а, значит, будут истинными и исходные формулы.

Следовательно, x(P(x) Q(x)) x P(x) xQ(x).

Пример 259. Доказать равносильность

С & x A x x С & A(x) .

Доказательство. 1. Пусть высказывание С – ложно. Тогда для любого предиката А(х) будет тождественно ложным высказывание С & x A(x) , предикат С & A(x) также будет ложным и, следовательно, ложным является высказывание x(С & A(x)). Значит в этом случае обе исходные форму-

лы тождественно ложны.

2. Пусть высказывание С – истинно. Тогда, очевидно, значение исходных формул будет целиком зависеть от значений предиката А(х). Если А(х) – тождественный истинный предикат, то будут тождественно истинными высказывания x A(x), С& x A(x) , x(С & A(x)) , то есть исходные формулы являются одновременно тождественно истинными. Если предикат А(х) не тождественно истинный, тогда предикат С & A(x) будет ложным, так же как и высказывания x A(x), С& x A(x) , x(С & A(x)) , то есть

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

Задача 260. Найдите отрицание следующих формул:

1)х P(x) & Q(x) ;

2)х P(x) Q(x) ;

3)x y R(x, y) L(x, y) .

129

Решение.

1)х P(x) & Q(x) х P(x) & Q(x) х P(x) Q(x) ;

2)х P(x) Q(x) х P(x) Q(x) х P(x) & Q(x) ;

3)x y R(x, y) L(x, y) x y R(x, y) L(x, y)

x y R(x, y) L(x, y) x y R(x, y) L(x, y) x y R(x, y) & L(x, y) .

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

Задача 261. Пусть Р(х,у) - предикат «х делит у», а х, у - переменные для целых чисел. Сформулировать словами предложение, выраженное формулой

x y P x,3 P 3, y P 3, x y .

Построить отрицание этого предложения и прочитать его словами. Ответ. «Если каждое из произвольных чисел не делится на 3, то их

сумма не делится на 3». Отрицание этого предложения:

x y P x,3 P 3, y P 3, x y -

«существуют два целых числа таких, что каждое из них не делится на 3, а их сумма делится на 3».

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

Задача 262. Запишите в виде формулы высказывание «Функция f - монотонно убывающая». Постройте отрицание этой формулы и дайте словесное высказывание.

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

не равносильны.

Ответ. Равносильности в приведенной задаче не выполняются, так как конъюнкцию и дизъюнкцию, вообще говоря, нельзя переставлять.

Доказательство п.1 проведем на примере. Пусть А(х) - предикат «Быть четным числом»; В(х) - «Быть нечетным числом». Тогда высказы-

130