Какие из следующих выражений являются предикатами

от admin

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

В логике предикатов используется следующая сим­волика:

1. Символы р, q, r, . — переменные высказывания, принимающие два значения: 1 — истина, 0 — ложь.

2. Предметные переменные — х, у, z. которые про­бегают значения из некоторого множества М: х°, у° , z° , . — предметные константы, то есть значения пред­метных переменных;

3. Р( · ), f( · ) — одноместные предикатные перемен­ные; Q(·,·. ·), R(·,·. ·) — n-местные предикатные пе­ременные. Р°( · ), Q°(·,·. ·) — символы постоянных предикатов.

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

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

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

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

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

2.Если F(·,·. ·) — n-местная предикатная перемен­ная или постоянный предикат, a x1t x2, . хn — предмет­ные переменные или предметные постоянные, не обяза­тельно все различные, то F(x1, x2, . хn) есть формула. В этой формуле предметные переменные являются свобод­ными. Формулы вида 1 и 2 называются элементарными.

3.Если А и В — формулы, причем такие, что одна и та же предметная переменная не является в одной из них свя­занной, а в другой свободной, то A v В , А& В, АВ есть формулы. В этих формулах те переменные, которые в ис­ходных формулах были свободными, являются свободны­ми, а те, которые были связанными, являются связанными.

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

5. Если -А(x) — формула, в которую предметная пере­менная х входит свободно, то слова Vх А(х) и А(х) являются формулами, причем предметная переменная в них входит связанно.

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

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

1) ;

2);

3) ;

4);

5);

6).

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

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

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

а) переменных высказываний;

б) свободных предметных переменных из множества М;

в) предикатных переменных.

При конкретных значениях этих переменных фор­мула принимает конкретное логическое значение.

Пример 2. Дана формула , где предикаты Р(х), Q(х) и R(х) определены на множестве N. Найти ее значение, если

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

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

Решение. В обоих случаях конъюнкция Р(х) & Q(х) есть утверждение, что число х делится на 12. Но тогда при всех х, если число х делится на 12, то оно делится и на 2, и, значит, в случае 1) формула истинна.

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

Пример 3. Вычислить значение формулы

, если предикат Р(х,у) имеет значение Р°(х,у) «число х меньше числа у» и определен на множестве .

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

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

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

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

Ясно, что все равносильности алгебры высказыва­ний будут верны, если в них вместо переменных выска­зываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Сюда, в первую очередь, следует отнести равносильности:

, .

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

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

1) ;

2) ;

3).

1) ;

2)

3) ;

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

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

.

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

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

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

Следовательно, .

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

.

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

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

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

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

1);

2) ;

3);

4);

5);

6) .

3.14. Даны утверждения А(n): «число n делится на 3», В(п): «число n делится на 2», С(n): «число п делит­ся па 4», D(n) «число n делится на 6», Е(п): «число n делится на 12». Укажите, какие из следующих утверж­дений истинны, какие ложны:

1) ;

2) ;

3) ;

4) ;

5);

3.15. Пусть предикат Р(х,у) определен на множе­стве М = N × N и означает « х < у ».

1) Какие из следующих предикатов тождественно истинные и какие тождественно ложные:

2) Для тех предикатов из 1), которые не являются ни тождественно истинными, ни тождественно ложны­ми, указать область истинности и область ложности.

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

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

3.17. Среди следующих пар предикатов выберите те, в которых предикаты являются отрицаниями друг друга:

«а < b» и «b < а »;

«Треугольник ABC прямоугольный» и «Треуголь­ник ABC тупоугольный»;

3) «Целое число k четно» и «Целое число k нечетно»; 4) «Функция f нечетна» и «Функция f четна»;

5) «Натуральное число n — простое» и «Натуральное число n — составное.»

3.18. Доказать следующие равносильности:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

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

1)

2)

3)

4)

5)

6)

3.20. Пусть предикат А(х) и В(х) — любые предикаты. Kакие из следующих формул равносильны формуле (*)?

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

1) кванторов существования;

2) кванторов общности.

3.22. Доказать, что формулы ине равносильны.

3.23. Доказать, что формулы ине равносильны.

3.24. Доказать, что

1)

2) то же с заменой & на v;

3) можно ли в 1) и 2) заменить F(x) и G(y)двухместными предикатами, зависящими от x и y?

3.25. Пусть А(х) и В(х) два одноместных предиката, определенных на множестве М таких, что высказывание истинно. Доказать, что высказываниеложно.

3.26. Даны два предиката Q(х,у) и R(y,z), опреде­ленные на множестве М × М , где М = <а, b, с> . Для сле­дующих предложений записать их выражения без использования кванторных операций:

3.27. Каким условиям будут удовлетворять области истинности предикатов А(х) и В(х), определенных на множестве М, если истинны высказывания:

6.4. Задачи

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

1) .

2) .

3) .

4) .

5) .

6) .

7) .

8) .

9) .

10) .

2. Пусть – натуральное число. Даны следующие утверждения.

· – “число кратно 5”;

· – “число кратно 2”;

· – “число кратно 4”;

· – “число кратно 10”;

· – “число кратно 20”.

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

1) .

2) .

3) .

4) .

5) .

6) .

7) .

8) .

9) .

10) .

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

Практикум

Здесь x, у, z, t — переменные по множеству действительных чисел, a, b — по множеству целых чиссл,у^?- по множеству функций.

  • 6. Выделите простые высказывания и логические связки между ними. Запишите исходные предложения символически. Найдите их значения.
  • а) число (-14) четное и отрицательное;
  • 6) число 1 — 42 отрицательное или рациональное;
  • в) число 1 — 42 отрицательное и рациональное;
  • г) если число 1 — 42 рациональное, то оно положительное;
  • д) число log0,5 положительное или иррациональное.
  • 7. Обозначим буквой А предложение «Четырехугольник имеет две равные стороны», а буквой В — предложение «Четырехугольник имеет два равных угла». Прочитайте предложения по их символической записи:

Пусть дан четырехугольник с попарно различными сторонами. Определите значение предложения А—>В.

Приведите пример четырехугольника, для которого предложение А^>В неверно.

8. Даны высказывания трех мальчиков.

Петя: «Я пойду в театр или в кино».

Вася: «Я сдам экзамены по математике и по физике».

Андрей: «Если я сдам экзамен по математике, то пойду в театр».

Известно, что каждый мальчик не сдержал обещание. Сделайте выводы.

9. Задумано натуральное число. Вася и Петя высказали по одному утверждению.

Петя: «Если число нечетное, то оно меньше 15».

Вася: «Если число составное, то оно четное».

Известно, что высказывание Пети истинно, а высказывание Васи ложно. Какое число задумано?

  • 10. К каждому из следующих предикатов с натуральной переменной п примените сначала квантор общности, а затем квантор существования:
  • 1) п — простое число; 2)и>1; 3)/;:5.

Сформулируйте полученные высказывания и выясните, какие из них истинны.

  • 11. Запишите символически каждое из следующих предложений, выявите в нем свободные и связанные переменные:
  • 1) существует такое число х, что х больше у;
  • 2) для любого числа;’ верно, что л* больше у;
  • 3) существуют такие числа * и у, что х больше у;
  • 4) каковы бы ни были числа х иу,х больше у;
  • 5) для всякого числа х найдется такое число уу что л’ больше у;
  • 6) существует такое число у, что для любого числа х верно, что х больше у.

Здесь д; и у — действительные переменные.

  • 12. Запишите символически следующие предложения:
  • 1) существует число, равное своему квадрату;
  • 2) четвертая степень любого числа неотрицательна;
  • 3) неравенство 2*>3 верно хотя бы для одного числа х;
  • 4) куб некоторого числа равен 7;
  • 5) неравенство 2* >0 верно для всякого числа х.

Докажите истинность этих высказываний.

  • 13. Прочитайте следующие предзожения разными способами (вначале используя в формулировке переменную дг, затем без указания этой переменной):
  • 1) 3.r(.v 2 1), 5) V*(.r 2 >0). Какие из высказываний истинны? Обоснуйте.
  • 14. Прочитайте следующие высказывания и выясните, какие из них верны:
  • 1) V* (л>4 -> * 2 > 10), 2) V.r (дг>4 -> л; 2 > 10),
  • 3) V* (дг> 1 v х 2).
  • 15. Для предложения х>у запишите символически результаты всех возможных вариантов применения кванторов по двум переменным (восемь вариантов). Прочитайте полученные высказывания и выясните, истинны ли они, если переменные х и у могут принимать:
    • а) действительные значения; б) натуральные значения.

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

    • 16. Для предложения ху запишите символически результаты всех возможных вариантов применения кванторов по двум переменным. Прочитайте полученные высказывания и выясните, истинны ли они. Буквы хм у- это переменные по множеству целых чисел.
    • 17. Прочитайте, нс используя буквы а и b, следующие предложения и выясните, какие из них верны:

    Переменные а н b обозначают прямые.

    • 18. Запишите символически следующие предложения и проанализируйте их:
    • 1) для любого числа а существует число, синус которого равен а
    • 2) для любого числа а существует число, равное синусу а;
    • 3) существует число а, такое, что синус любого числа будет равен а;
    • 4) существует число а, такое, что синус любого числа будет меньше а.
    • 19. Даны предложения о числовой функции / Приведите пример такой функции, для которой предложение истинно, и пример функции, для которой оно ложно.

    20. Даны следующие функции:

    где <*>обозначает дробную часть числа х. Найти все функции, для которых верно предложение:

    • 21. Запишите следующие предложения о числовой функции /символически, используя кванторы. Приведите пример функции, для которой предложение верно, и пример функции, для которой оно ложно.
    • 1) Любое действительное число является значением функции/
    • 2) Ни одно положительное число не является значением функции/
    • 3) Разным значениям аргумента соответствуют разные значения функции.
    • 4) Функция / принимает постоянное значение при всех значениях аргумента из отрезка [2; 3].
    • 5) Функция/ограниченна на промежутке (0; 1).
    • 6) Функция / на интервале (0; 1) принимает только отрицательные значения.
    • 7) Функция/может принимать отрицательные значения только в точках интервала (0; 1).
    • 22. Установите между предикатами, если возможно, отношение следования:
      • а)дг : 15 и д: : 5; б) х>у и х>у; в) (л> 10) v (у> 10) и х+у>20;
      • г) «четырехугольник х есть ромб» и «диагонали четырехугольника х перпендикулярны»;
      • д) «углы х и у вертикальные» и «углы х и у равны».

      а) А = «х — прямоугольник», В = «Диагонали х равны»;

      б) А = «Прямая а параллельна />, а прямая b параллельна с»,

      В = «Прямая а параллельна с»;

      в) А = «Треугольник прямоугольный»,

      В = «Один из углов треугольника равен сумме двух других».

      • 24. Вставьте вместо многоточия одно из словосочетаний «необходимо, но недостаточно», «достаточно, но не необходимо», «нс необходимо и не достаточно», «необходимо и достаточно» так, чтобы получилось истинное высказывание. Обоснуйте выбор.
      • а) Для того чтобы в четырехугольник можно было вписать окружность, . чтобы это был ромб.
      • б) Для того чтобы четырехугольник был параллелограммом, . , чтобы его диагонали точкой пересечения делились пополам.
      • в) Для того чтобы две прямые были параллельными, . , чтобы они лежали в одной плоскости.
      • г) Для того чтобы выполнялось неравенство х 2 >у 2 , . , чтобы число * было больше числа у.
      • д) Для того чтобы выполнялось равенство X 2 =у 2 9 . , чтобы ЧИСЛО .V было равно числу у.
      • е) Для того чтобы целое число делилось на 48, , чтобы это число

      делилось на 8 и на 6.

      • 25. Вставьте вместо многоточия один из математических терминов так, чтобы получилось верное утверждение.
      • а) Равенство площадей фигур является . условием для того, чтобы фигуры были равны.
      • б) Равенство х 2 +х=у 2 +у является . условием для того, чтобы числа х и у были равны.
      • в) Равенство ab=0 является . условием для того, чтобы я=0.
      • г) Неравенство д>1 является . условием для неравенствах 2 >1.
      • 26. Выделите в следующих предложениях простые высказывания, обозначьте их буквами и представьте данные предложения в виде формул:
        • а) число 13 5 +5 делится на 11 и на 19;

        б) если дробь несократима, то или ее числитель, или ее

        знаменатель не делится на 13;

        в) если сегодня не выходной день, то Коля идет в школу, если у него нет высокой температуры;

        г) если число х меньше числа у, то если эти числа одного знака, то — > —,

        а если они разных знаков, то — 2 , то одно из чисел у делится нар, а другое на р не делится.

        27. Найдите вес наборы значений переменных, при которых формула принимает значение лжи.

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

        29. Докажите, что следующие формулы являются тавтологиями:

        30. Докажите равносильность следующих формул:

        • 31. Приведите пример предложений А и В, чтобы формула (Л—>1# приняла ложное значение. Сформулируйте предложение, выраженное этой формулой.
        • 32. Проверьте, равносильны ли следующие пары формулы. Если нет, приведите пример предложений, при которых одна из формул принимает значение истины, а другая — значение лжи:
        • 1)Л->йий->Л 2) А которое в произведении с х равно нейтральному по умножению числу (такое число у называется обратным к х).
        • 38. Пусть даны предикаты А(х) и В(х). Запишите формулами следующие утверждения:
        • 1) Предюжение А(х) верно при некоторых х, при которых верно В(х).
        • 2) Предюжение А(х) верно при всех х, при которых верно В(х).
        • 3) Предюжение А(х) верно только при тех х, при которых верно В(х).
        • 4) Предложение А(х) верно при всех тех и только тех х, при которых верно В(х).
        • 39. Проанализируйте истинность предложений:
        • 1) Равенство х=х верно при некоторых положительных значениях х.
        • 2) Равенство х=х верно при всех положительных значениях х.
        • 3) Равенство х=х верно только при положительных значениях х. Постарайтесь закончить истинное предложение: «Равенство |*|=л; верно для всех тех и только тех х, которые удовлетворяют неравенству . »
        • 40. Проанализируйте истинность предложений:
        • 1) Равенство .t 4 =3jc верно при некоторых положительных значениях .т.
        • 2) Равенство л; 4 =3х верно при всех положительных значениях л
        • 3) Равенство лг 4 =3* верно только при положительных значениях х.
        • 41. Проанализируйте истинность предложений:
        • 1) Неравенство г >3 верно при некоторых положительных значениях х.
        • 2) Неравенство дг 3 >3 верно при всех положительных значениях л
        • 3) Неравенство г >3 верно только при положительных значениях jc.
        • 42. Сформулируйте отрицания к следующим предложениям в позитивной форме. Для этого вначале представьте предложения в виде формул и, воспользовавшись законами логики, постройте отрицания. Приведите примеры чисел, при которых отрицание принимает истинное значение.
        • а) Если число рациональное, то оно не целое.
        • б) Если число делится на 2 и на 4, то оно делится на 8.
        • в) Если сумма чисел а и b является целым числом, то хотя бы одно слагаемое есть целое число.
        • г) Если произведение двух целых чисел делится на 4, то хотя бы одно число делится на 4.
        • д) Числа а, Ь, с равны между собой.
        • 43. Переформулируйте предложения с помощью правила контрапозиции:
          • а) если число оканчивается на 0, то оно делится на 5;
          • б) если стол дубовый, то он деревянный;
          • в) если сумма чисел а п b является иррациональным числом, то хотя бы одно слагаемое есть иррациональное число;
          • г) если квадрат целого числа является четным числом, то само число также четно;
          • д) если х равно у и у равно z, то х равно z.
          • 1) Все ромбы являются параллелограммами.
          • 2) Ни один ромб нс является трапецией.
          • 3) Некоторые прямоугольники являются ромбами.
          • 4) Некоторые прямоугольники не являются ромбами.
          • 5) Найдется трапеция, являющаяся прямоугольником.

          Какие из исходных предложений истинны?

          • 45. Дана числовая функция у =/(.*). Используя кванторы, запишите предложение: «Функция / принимает отрицательные значения при всех положительных значениях аргумента». Постройте отрицание. Прочитайте. Приведите два примера функций, для одной из которых это предложение истинно, а для другой — ложно. Верно ли предложение для функции / (х) = sin .v?
          • 46. Выполните те же самые задания, данные в задаче № 45, для предложения: «Функция / принимает отрицательные значения при некоторых положительных значениях аргумента».
          • 47. Даны предикаты А(х) = «г делится на 4», В(х) = «х делится на 2», С(х) = «х делится на 8», гдех- переменная по множеству целых чисел. Прочитайте предложения, заданные следующими формулами. Постройте отрицания, прочитайте полученные предложения. Докажите или опровергните данные предложения (то есть обоснуйте, что именно верно: исходное предложение или его отрицание).

          • 48. Сформулируйте отрицания к следующим высказываниям. Вначале запишите каждое предложение формулой, затем, используя законы логики, постройте отрицания. Определите, какие из исходных высказываний истинны, а какие ложны.
          • 1) Сумма любых двух рациональных чисел является рациональным числом.
          • 2) Произведение двух некоторых не целых чисел является целым числом.
          • 3) Любое натуральное число является квадратом некоторого натурального числа.
          • 4) Существует действительное число, меньшее любого натурального числа.
          • 5) Найдется натуральное число, меньшее всякого натурального числа.
          • 6) Каждое целое число, делящееся на 5, по модулю больше либо равно 5.
          • 49. Прочитайте предложения, заданные формулами. Докажите или опровергните:
          • 50. Опровергните следующие предложения. Для этого вначале запишите каждое предложение формулой, затем, используя законы логики, постройте отрицание и покажите его истинность.
          • 1) Равенство неверно ни для каких различных натуральных чисел х и

Похожие статьи