Рациональные числа: определения, примеры. Математическая логика: Методические указания по курсу "Основы дискретной математики" Какое из чисел является рациональным

Данная статья посвящена изучению темы "Рациональные числа". Ниже приведены определения рациональных чисел, даны примеры, рассказано о том, как определить, является ли число рациональным, или нет.

Рациональные числа. Определения

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

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

Определение 1. Рациональные числа

Рациональные числа - числа, которые можно представить в виде положительной обыкновенной дроби a b , отрицательной обыкновенной дроби - a b или числа ноль.

Таким образом, можно оставить ряд свойств рациональных чисел:

1. Любое натуральное число является рациональным числом. Очевидно, каждое натуральное число n можно представить в виде дроби 1 n .
2. Любое целое число, включая число 0 , является рациональным числом. Действительно, любое целое положительное и целое отрицательное число легко представляется в виде соответственно положительной или отрицательной обыкновенной дроби. Например, 15 = 15 1 , - 352 = - 352 1 .
3. Любая положительная или отрицательная обыкновенная дробь a b является рациональным числом. Это следует напрямую из данного выше определения.
4. Любое смешанное число является рациональным. Действительно, ведь смешанное число можно представить в виде обыкновенной неправильной дроби.
5. Любую конечную или периодическую десятичную дробь можно представить в виде обыкновенной дроби. Поэтому, каждая периодическая или конечная десятичная дробь является рациональным числом.
6. Бесконечные и непериодическое десятичные дроби не являются рациональными числами. Их невозможно представить в форме обыкновенных дробей.

Приведем примеры рациональных чисел. Числа 5 , 105 , 358 , 1100055 являются натуральными, положительными и целыми. Сдедовательно, это рациональные числа. Числа - 2 , - 358 , - 936 представляют собой целые отрицательные числа, и они также рациональны в соответствии с определением. Обыкновенные дроби 3 5 , 8 7 , - 35 8 также являются примерами рациональных чисел.

Приведенное выше определение рациональных чисел можно сформулировать более кратко. Еще раз ответим на вопрос, что такое рациональное число.

Определение 2. Рациональные числа

Рациональные числа - это такие числа, которые можно представить в виде дроби ± z n , где z - целое число, n - натуральное число.

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

0 n = 0 ÷ n = 0 ; - m n = (- m) ÷ n = - m n .

Таким образом, можно записать:

z n = z n , п р и z > 0 0 , п р и z = 0 - z n , п р и z < 0

Собственно, данная запись и является доказательством. Приведем примеры рациональных чисел, основываясь на втором определении. Рассмотрим числа - 3 , 0 , 5 , - 7 55 , 0 , 0125 и - 1 3 5 . Все эти числа являются рациональными, так как их можно записать в виде дроби с целым числителем и натуральным знаменателем: - 3 1 , 0 1 , - 7 55 , 125 10000 , 8 5 .

Приведем еще одну эквивалентную форму определения рациональных чисел.

Определение 3. Рациональные числа

Рациональное число - это такое число, которое можно записать в виде конечной или бесконечной периодической десятичной дроби.

Данное определение напрямую следует из самого первого определения этого пункта.

Подведем итог и сформулируем резюме по данному пункту:

1. Положительные и отрицательные дробные и целые числа составляют множество рациональных чисел.
2. Каждое рациональное число можно представить в виде обыкновенной дроби, числитель которой является целым числом, а знаменатель - натуральным числом.
3. Каждое рациональное число можно также представить в виде десятичной дроби: конечной или бесконечной периодической.

Какое из чисел является рациональным?

Как мы уже выяснили, любое натуральное число, целое число, правильная и неправильная обыкновенная дробь, периодическая и конечная десятичная дробь являются рациональными числами. Вооружившись этими знаниями можно без труда определить, является ли какое-то число рациональным.

Однако на практике часто приходится иметь дело не с числами, а с числовыми выражениями, которые содержат корни, степени и логарифмы. В некоторых случаях ответ на вопрос "рационально ли число?" является далеко не очевидным. Рассмотрим методы ответа на этот вопрос.

Если число задано в виде выражения, содержащего только рациональные числа и арифметические действия между ними, то результат выражения - рациональное число.

Например, значение выражения 2 · 3 1 8 - 0 , 25 0 , (3) является рациональным числом и равно 18 .

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

Теперь разберемся со знаком корня.

Оказывается, что число m n , заданное в видя корня степени n от числа m рационально лишь тогда, когда m является n -ой степенью какого-то натурального числа.

Обратимся к примеру. Число 2 не является рациональным. Тогда как 9 , 81 - рациональные числа. 9 и 81 - полные квадраты чисел 3 и 9 соответственно. Числа 199 , 28 , 15 1 не являются рациональными числами, так как числа под знаком корня не являются полными квадратами каких-либо натуральных чисел.

Теперь возьмем более сложный случай. Является ли рациональным число 243 5 ? Если возвести 3 в пятую степень, получается 243 , поэтому исходное выражение можно переписать так: 243 5 = 3 5 5 = 3 . Следовательно, данное число рационально. Теперь возьмем число 121 5 . Это число нерационально, так как не существует натурального числа, возведение которого в пятую степень даст 121 .

Для того, чтобы узнать, является ли логарифм какого-то числа a по основанию b рациональным числом необходимо применить метод от противного. К примеру, узнаем, рационально ли число log 2 5 . Предположим, что данное число рационально. Если это так, то его можно записать в виде обыкновенной дроби log 2 5 = m n .По свойствам логарифма и свойствам степени справедливы следующие равенства:

5 = 2 log 2 5 = 2 m n 5 n = 2 m

Очевидно, последнее равенство невозможно так как в левой и правой частях находятся соответственно нечетное и четное числа. Следовательно, сделанное предположение неверно, и число log 2 5 не является рациональным числом.

Стоит отметить, что при определении рациональности и иррациональности чисел не стоит принимать скоропостижных решений. Например, результат произведения иррациональных чисел не всегда является иррациональным числом. Наглядный пример: 2 · 2 = 2 .

Также существуют иррациональные числа, возведение которых в иррациональную степень дает рациональное число. В степени вида 2 log 2 3 основание и показатель степени являются иррациональными числами. Однако само число является рациональным: 2 log 2 3 = 3 .

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

10 - Математическая логика и) xy → x ∨ x (y ∨ z) ; а) * xy ∨ xz ; к) (x | y) → (x | z) ; б) x ~ y; л) (x ∨ y)(x ∨ z) ∨ xy ; в) * xy ; м) (x ∨ y) x ∨ z ; г) xyz ; д) x (y ∨ z) → (xy ∨ z) ; н) (x ↓ y) ~ (x ⊕ y) ; о) (x ~ y) ~ (x ~ z) ; ж) (x ⊕ y → c) ↓ c ; п) (x ~ y) ⊕ (x ~ z) ; з) * x → (y → x) ; р) (x ∨ y)(x ∨ z) (x ∨ w). 17. Получить СДНФ, а затем перейти к СКНФ: б) * (x → y) → (y → x); 18.* Пусть задана функция f (сложное высказывание) от трёх аргументов (элементарных высказываний) x , y , z и f (x , y , z)= x . Построить для данной функции СДНФ. 19. Получить СКНФ, а затем перейти к СДНФ: г) * (x | y) xy ; 20. Получить МДНФ для формул: а) * ((x ⊕ y) ~ z) → x ; б) * ((1 ⊕ xy) ⊕ xz) ∨ (z → y); в) * (x ⊕ y) → z ∨ y ; г) * ((A → B) ~ (C ~ D)) ∨ B → A ⋅ (C ~ D) ; д) * (A ∨ B ∨ C ∨ D)(A ∨ B ∨ C ∨ D); е) * x ∨ yz ∨ xz ; ж) * (x → y) → z ∨ x ; з) * xy ∨ xy ∨ xz ; 22.* Из контактов x , y , z составить схему так, чтобы она замыкалась тогда и только тогда, когда замкнуты какие-нибудь два из трёх контактов x , y , z . 24.* Упростить схемы рис.1 , а и б. а) б) Рис. 1 - 11 - Математическая логика 25.* Записать на языке предикатов: а) все студенты учатся; б) некоторые студенты отличники; в) для любого числа можно найти большее число; г) x + y = z ; д) всякий предмет обладает свойством А; е) нечто обладает свойством А; ж) всякий предмет не обладает свойством А; з) нечто не обладает свойством А; и) каждое рациональное число есть действительное число; к) некоторые действительные числа являются рациональными; л) ни одно рациональное число не является действительным; м) некоторые рациональные числа не являются действительными. 26.* Попытайтесь объяснить, почему в упражнениях 25а и 25и использова- лась импликация, а в 25б и 25к – конъюнкция. 27.* Записать на языке предикатов: а) детям до 16 лет (D(x)) и роботом (R(x)) входить (B(x)) за- прещено; б) всем детям до 16 лет (D(x)) и роботом (R(x)) надлежит полу- чить справки (C(x)). 28.* Записать на языке предикатов: а) всякое N , делящееся на 12, делится на 2, 4 и 6; б) каждый студент выполнил, по крайней мере, одну лаборатор- ную работу; в) через две различные точки проходит единственная прямая. 29. Записать на языке предикатов: д)* каждый студент (C(x)) – спортсмен (S(x)) имеет какого- нибудь кумира (y) (B(x,y)) среди киноартистов (K(y)); е)* если некоторые большие ЭВМ (Б(x)) связаны (C(x,y)) с другим большим ЭВМ (Б(y)), то значит, не существует мини ЭВМ (M(x)), имеющих средства сопряжения (S(x)); 30.* При каких условиях: а) ∀x P (x) ≡ ∃x P(x) ; б) ∃x P(x) ≡ O, a ∀x P(x) ≡ 1 ; 33.* Это – ставший классический пример, иллюстрирующий дополнительные сложности, связанные с отрицанием: известно, что предложение «Ны- нешний король Франции лыс» не соответствует действительности. Как это записать на языке предикатов. РЕШЕНИЯ И ОТВЕТЫ. - 12 - Математическая логика 1а. Выберем элементарные высказывания служебным образом: А – студент отлично учится; В – студент занимается общественной работой; С – студент имеет нарушения; D – студент получает стипендию. Тогда символическая форма сложного высказывания будет иметь вид A ⋅B⋅C → D . 1б. Символическая запись может иметь вид: П⋅З → С⋅Р → П.() 3. В логике высказываний правильными следует считать высказывания ти- па «Неверно, что Петя пошел в институт», так как высказывания не де- лимы. 8. A ∨ B ≡ A → B ≡ (A → B) → B , A & B ≡ A → B . 11.а ABC ∨ A BC ∨ ABC ∨ ABC или то же самое, но в более простой форме АВ ∨ АС ∨ ВС. 11б. А В ∨ ВС ∨ АС. 13а. xy z . 13в. Формула уже в ДНФ. Почему? 14а. (x ∨ z)(y ∨ z) . 14б. Формула уже в КНФ. Почему? 15а. xyz ∨ x yz ∨ xyz ∨ xyz . 15б. xyz ∨ xyz ∨ x yz ∨ xyz ∨ x yz ∨ x yz ∨ xyz . 15д. xy ∨ x y ∨ xy ∨ x y (≡ 1) . 16а. () ()() xy ∨ xy ≡ xy ∨ x (xy ∨ z)≠ x ∨ x x ∨ y (x ∨ z)(y ∨ z) ≡ (x ∨ y ∨ zz)(x ∨ z ∨ y y)(y ∨ z ∨ x x) ≡ (x ∨ y ∨ z)(x ∨ y ∨ z) (x ∨ y ∨ z) (x ∨ y ∨ z) . 16в. (x ∨ y) (x ∨ z)(x ∨ y) . 16з. СКНФ отсутствует, т.к. это тавтология. - 13 - Математическая логика 17б. Это тавтология, поэтому для неё нет СКНФ. 18. xyz ∨ xy z ∨ x yz ∨ x yz . 19г. Это противоречие, поэтому для него нет СКНФ. 20а. ((x ⊕ y) ~ z) → x ≡ (x ⊕ y)z ∨ (x ⊕ y)z ∨ x ≡ () (x ⊕ y)z ⋅ (x ⊕ y)z ∨ x ≡ (x ⊕ y ∨ z) x ⊕ y ∨ z ∨ x ≡ (xy ∨ x y ∨ z)(xy ∨ x y ∨ z)∨ x ≡ xyz ∨ x yz ∨ xy z ∨ x y z ∨ x yz ∨ xy z - СДНФ x ∨ y z ∨ yz - СКДНФ и МДНФ. 20б. ((1 ⊕ xy) ⊕ xz) ∨ (z → y) ≡ (xy ⊕ xz)∨ yz ≡ xyxz ∨ xy xz ∨ yz ≡ ()() xyz ∨ x ∨ y x ∨ z ∨ yz ≡ xyz ∨ x ∨ y z ∨ yz ≡ xyz ∨ x yz ∨ x yz ∨ x y z ∨ x y z ∨ x y z ∨ x yz - СДНФ x ∨ y ∨ z - МДНФ. 20в. xyz ∨ xyz ∨ x yz ∨ x yz ∨ x yz - СДНФ xy ∨ x y ∨ yz - МДНФ. 20г. A BCD ∨ A BCD ∨ ABCD ∨ A BCD ∨ ABCD ∨ A BCD ∨ ABCD ∨ ABCD ∨ A BCD ∨ A BCD - СКНФ A B ∨ CD ∨ CD - МДНФ. 20д. A∨C∨ D. 20е. x∨z . 20ж. x∨z . 20з. xy ∨ x y ∨ xz или xy ∨ x y ∨ yz . 21в. xy ∨ xz . 21г. 1. 22. См. рис. 2. - 14 - Математическая логика Рис. 2 23а. См. рис. 3. а) б) Рис. 3 23. Упрощенные схемы будут иметь вид, представленный на рис. 4. а) б) Рис. 4 25а. ∀x (C(x)→Y(x)) , где C(x) – «х - студент», а Y(x) – «х - учится». 25б. ∃x (C(x) & O(x)) . 25в. Запишем двухместный предикат в виде обычного отношения: ∀х ∃y (x < y) . 25г. Запишем в виде трехместного предиката: ∀x,y ∃z S(x,y,z) . Предикат S принимает значение “истинно”, когда x + y = z , и «ложь» в противном случае. При навешивании соответствующих кванто- ров поучается утверждение о том, что для любых x и y существует сумма. 25д. ∀x A(x). 25e. ∃x A(x). 25ж. ∀x ¬ A(x). 25з. ∃x ¬ A(x). - 15 - Математическая логика 25и. ∀x (Q(x) →R(x)). 25к. ∃x (Q(x) & R(x)) 25л. ∀x (Q(x) → ¬ R(x)). 25м. ∃x (Q(x) & ¬ R(x)). 26. В теоретико-множественной интерпретации обычно импликация соот- ветствует включению, а конъюнкция - пересечению. Например, ∀х (Q(x) → R(x)). Справедливо, поскольку Q ⊆ R ; а ∃x (Q(x) & R(x)) справедливо, поскольку Q ∩ R не пусто. Ошибкой было бы 25к запи- сать как ∃x (R(x) →Q(x)), поскольку это равносильно ∃x (¬R(x) ∨ Q(x)), а это высказывание будет истинным для любого х, не являющимся дей- ствительным числом. 27. Здесь несколько перефразированы упражнения известного логика С.Клини, который предлагает следующие решения: а) ¬∃x ((D(x) ∨ R(x)) & B(x) , что равносильно ∀x ((Dx) ∨ R(x)) → ¬ B(x)) ; б) ошибкой была бы запись ∀x (D(x) & R(x) → C(x)) , так как D(x) & R(x) – пусто. Правильным решением будет ∀x (D(x) → C(x)) & ∀x (R(x) → C(x)) или ∀x (D(x) ∨ R(x) → C(x)) . 28a. ∀x (А(х) → Д(х) & Ч(х) & Ш(х)). 28б. ∀x ∃y B(x,y) . 28в. ∀x,y (¬(x=y) → ∃p ((x∈p) & (y∈p) & ∀q ((x∈q) & (y∈q) → (p=q)) . 29д. ∀x (C(x) & S(x)) → ∃y (B(x,y) & K(y)) . 29е. ∃x Б(х) & ∀y (C(x,y) → Б(y)) → ¬ ∃x (M(x) & S(x)) . 30а. Когда х определён на предметной области из одного элемента. 30б. Когда предметная область пуста (но здесь можно и возразить). 31. Отрицаниями будут предложения в и г. Ответ можно получить фор- мально, если для предиката ∀х ∃y B(x,y) взять отрицание и совершить равносильное преобразования: ¬∀x ∃y B(x,y)≡∃x ¬∃y B(x,y)≡∃x ∀y ¬B(x,y) 32. Само исходное предложение на языке предикатов запишется как: ∃x K(x) & ∀x (K(x)→Л(х)) . В литературе обычно не обсуждается вариант «огульного» отрицания, т.е. ¬(∃x K(x) & ∀x (Kx)→Л(х)) , поскольку здесь следовало уточнить, что всё таки отрицается: факт лысости короля или факт существования короля во Франции. В связи с этим предлагается два варианта отрицания: - 16 - Математическая логика ∃х К(х) & ∀x (K(x) → ¬ Л(х)) ; ¬ ∃х К(х) & ∀x (K(x) → Л(х)) . СПИСОК ЛИТЕРАТУРЫ. 1. Клини С. Математическая логика. – М. : Мир, 1973, с. 11 – 126. 2. Столл Р. Множества. Логика. Аксиоматические теории. – М. : Просве- щение, 1968, с. 71 – 93, 108 – 132. 3. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. – М. : МГУ, 1982, с. 1 – 95. 4. Гильберг Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. – М. : Наука, т. 1, с. 23 – 45, 74 – 141. 5. Новиков П.С. Элементы математической логики. – М. : Наука, 1973, с 36 – 65, 123 – 135. 6. Гиндикин С.Г. Алгебра логики в задачах. – М. : Наука, 1972.

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

а) железо тяжелее свинца;

б) каша – вкусное блюдо;

в) математика интересный предмет;

г) сегодня плохая погода.

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

а) железо тяжелее свинца;

б) кислород ­– газ;

в) информатика интересный предмет;

г) железо легче свинца.

18. Какое из приведенных высказываний является отрицанием высказывания: «Все простые числа нечетны»:

а) «Существует четное простое число»;

б) «Существует нечетное простое число»;

в) «Все простые числа четны»;

г) «Все нечетные числа простые»?

19. Какой логической операции соответствует следующая таблица истинности:

а) конъюнкции;

б) дизъюнкции;

в) импликации;

г) эквивалентности.

20. Какой логической операции соответствует следующая таблица истинности:

а) эквивалентности;

б) конъюнкции;

в) импликации;

г) дизъюнкции.

21. Пусть через A обозначено высказывание «Этот треугольник равнобедренный», а через

B ­– высказывание «Этот треугольник равносторонний». Укажите истинное высказывание:

22. Если существует набор высказываний A 1 , A 2 , … A n , обращающий формулу алгебры высказываний F(X 1 , X 2 , …, X n) в истинное высказывание, то эта формула называется:

а) выполнимой;

б) тавтологией;

в) противоречием;

г) опровержимой.

23. Тавтологией называется такая формула алгебры высказываний F(X 1 , X 2 , …, X n):

а) которая обращается в истинное высказывание при всех наборах переменных;

б) для которой существует набор высказываний, обращающий формулу в истинное высказывание;

в) которая обращается в ложное высказывание при всех наборах переменных;

г) для которой существует набор высказываний, обращающий формулу в ложное высказывание.

24. Какая из формул является опровержимой:

25. Какая из формул является выполнимой:

26. Какому высказыванию соответствует утверждение: «Для любого числа существует число такое, что »:

27. Какое утверждение соответствует высказыванию :

а) «Существуют числа и такие, что ;

б) «Для всех и справедливо равенство ;

в) «Существует число , такое, что для всех чисел »;

г) «Для любого числа существует число такое, что ».

28. Какое из высказываний ложно:

29. Укажите множество истинности предиката «x кратно 3», заданного над множеством M={1, 2, 3, 4, 5, 6, 7, 8, 9}:

а) TP={3, 6, 9};

в) TP={1, 2, 3, 4, 5, 6, 7, 8, 9};

г) TP={3, 6, 9, 12}.

30. Укажите множество истинности предиката «x кратно 3», заданного над множеством M={3, 6, 9, 12}:

а) TP={3, 6, 9, 12}; б) TP={3, 6, 9};

в) TP={1, 2, 3, 4, 5, 6, 7, 8, 9}; г) TP=Æ.

31. Укажите множество истинности предиката «x 2 +x+6=0 », заданного над множеством действительных чисел:

а) TP=Æ; б) TP={1, 6}; в) TP={–2, 3}; г) TP={–3, 2}.

32. Укажите множество истинности предиката :

33. Укажите множество истинности предиката :

38. Введем следующие одноместные предикаты:

Q(x) : «x ­– рациональное число»;

R(x) : «x ­– действительное число».

Тогда предикат может рассматриваться как перевод на язык алгебры предикатов такого высказывания:

а) некоторые рациональные числа действительные;

б) некоторые рациональные числа не являются действительными;

в) ни одно рациональное число не является действительным;

г) все рациональные числа действительные.

Практические задания к разделу 3

Понятие предиката и операции над ними.

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

а) «х делится на 5» (х Î N );

б) «Река х впадает в озеро Байкал» (х пробегает множество названий всевозможных рек);

в) «х2 + 2 х + 4» (х Î R ) ;

г) «(х + у )2 = х2 + 2 х y + y 2» (x , y ÎR );

д) «х есть брат у » (х, у пробегают множество всех людей);

е) «х и у » (x , у пробегают множество всех студентов данной группы);

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

з) «ctg 45° = 1»;

и) «х перпендикулярна у » (х , у пробегают множество всех прямых одной плоскости).

3.2. Для каждого из следующих высказываний найти пре­дикат (одноместный или многоместный), который обращается в данное высказывание при замене предметных переменных подходящими значениями из соответствующих областей:

а) «3 + 4 = 7»;

б) «Вера и Надежда - сестры»;

в) «Сегодня - вторник»;

г) «Город Саратов находится на берегу реки Волги;

д) «sin 30° = 1/2»;

е) « - великий русский поэт»;

ж) «32 + 42= 52;

з) «Река Индигирка впадает в озеро Байкал»;

Построив такой предикат, постарайтесь или точно указать его область истинности, или как-то ее обрисовать.

Решение. и) Можно указать три предиката, каждый из которых обращается в данное высказывание при соответ­ствующей подстановке. Первый предикат одноместный:

«https://pandia.ru/text/78/081/images/image003_46.png" width="181" height="48">. Он превращается в данное высказывание при подстановке . Получающееся высказывание истинно. Указанным значением не исчерпыва­ется множество истинности построенного предиката. Как не­трудно установить, это множество следующее: . Второй предикат также одноместный: «» (y Î R) . Он превращается в данное высказывание при подста­новке у = 1. Ясно, что этим значением и исчерпывается множество истинности этого предиката..png" width="240" height="48">. Он превращается в данное высказы­вание при подстановке , у = 1. Его область истинности представляет собой множество упорядоченных пар, сово­купность которых графически изображается в виде бесконеч­ного семейства кривых, называемых тангенсоидами.

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

а) https://pandia.ru/text/78/081/images/image010_35.png" width="135" height="21 src=">

в) https://pandia.ru/text/78/081/images/image012_34.png" width="136" height="21 src=">

д) https://pandia.ru/text/78/081/images/image014_28.png" width="232" height="24 src=">

ж) https://pandia.ru/text/78/081/images/image016_23.png" width="204" height="24 src=">

и) https://pandia.ru/text/78/081/images/image018_18.png" width="201" height="24 src=">

л) https://pandia.ru/text/78/081/images/image020_17.png" width="101 height=21" height="21">» от­носительно переменной x , которая пробегает множество R. Говорят, что в получением выражении переменная у связана, а переменная х свободна. Вместо переменной у мы уже ничего не можем подставлять, в то время как вместо х могут быть подставлены действительные числа, в результате чете одноместный предикат будет превращаться в высказывания. Например, высказывание «» можно прочи­тать так: «Существует действительное число у , такое, что х )($у)(х + у = 7)» истинно. Его можно прочитать следующим образом: «Для любого действительного числа су­ществует такое действительное число, сумма которого с пер­вым равна 7». В выражении «("х )($у)(х + у = 7)» уже нет свободных переменных. Обе переменные х и у стоят под зна­ками кванторов и потому являются связанными. Само же выражение уже не является предикатом, оно есть высказы­вание, истинное, как мы установили. Впрочем, если мы хотим, то, развивая понятие предиката, можем считать, что выска­зывание - это 0-местный предикат, т. е. предикат без перемен­ных. Но мы должны осознавать, что количественный переход от одноместного предиката к 0-местному приводит к качествен­ному скачку, так что 0-местный предикат - это объект ка­чественно иной, нежели предикат одноместный, хотя и под­водимый нами условно под понятие «предикат».

б) Высказывание «($у)("х )(х + у = 7)» можно прочи­тать так: «Существует такое действительное число, которое, будучи прибавлено к любому действительному числу, в сумме дает 7». Нетрудно понять, что это утверждение ложно. В са­мом деле, рассмотрим одноместный предикат «("х )(х + у = 7)» относительно переменной у, применением к которому квантора существования получается данное высказывание. Ясно, что, какое бы действительное число ни подставить вместо предметной переменной у, например «("х )(х + 4 = 7)», предикат будет превращаться в ложное высказывание. (Высказывание «("х )(х + 4 = 7)» ложно, так как одномест­ный предикат «(х + 4 = 7)» превращается в ложное высказы­вание, например, при подстановке вместо переменной х чис­ла 5.) Поэтому высказывание «($у)("х )(х + у = 7)», полу­чающееся из одноместного предиката «("х )(х + у = 7)» применением операции взятия квантора существования по у, ложно.

и) Это высказывание можно прочитать так: «Любое дей­ствительное число равно самому себе тогда и только тогда, когда оно больше 1 или меньше 2». Чтобы выяснить, истинно или ложно это высказывание, будем пытаться искать такое действительное число х0, которое превратило бы одноместный предикат

в ложное высказывание. Если нам удастся найти такое число, то данное высказывание, получающееся из этого предиката «навешиванием» (т. е. применением операции взятия) кван­тора общности, ложно. Если же мы придем к противоречию, предположив, что такое х0 существует, то данное высказыва­ние истинно.

Ясно, что предикат «х = х » превращается в истинное вы­сказывание при подстановке вместо х любого действитель­ного числа, т. е. является тождественно истинным. Спраши­вается: можно ли указать действительное число, которое превратило бы предикат «» в ложное выска­зывание? Нет, потому что, какое бы действительное число мы ни взяли, оно либо больше 1, либо меньше 2 (либо одновремен­но и больше 1, и меньше 2, что вовсе не возбраняется в нашем случае). Следовательно, предикат «» тожде­ственно истинен. Тогда тождественно истинным будет и пре­дикат

И значит, данное высказывание

по определению операции взятия квантора общности истинно.

3.4. Пусть P (x) и Q (x) - одноместные предикаты, заданные на множестве М, такие, что высказывание https://pandia.ru/text/78/081/images/image027_14.png" width="63 height=23" height="23">ложно.

3.5. Определите, является ли один из предикатов, задан­ных на множестве действительных чисел, следствием другого:

а) «| х | < - 3», « x2 - 3x + 2 = 0 »;

б) «х4 = 16», « x2 = - 2 »;

в) «х - 1 > 0», « (x - 2) (х + 5) = 0»;

г) «sin x = 3», « x2 + 5 = 0»;

д) « х2 + 5x - 6 > 0», « x + 1 = 1 + x »;

е) «х2 £ 0», « x = sin p »;

ж) « x3 - 2x2 - 5ч + 6 = 0», «| х - 2| = 1».

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

3.6. Задайте множество М значений предметной перемен­ной так, чтобы на этом множестве второй предикат был бы следствием первого:

а) «х кратно 3», «х четно»;

б) «x 2 = 1», «x -1 = 0»;

в) «x нечетно», «х - квадрат натурального числа»;

г) «x - ромб», «x - параллелограмм»;

д) «x - параллелограмм», «x - ромб»;

е) «x - русский ученый», «x - математик»;

ж) «x - квадрат», «x - параллелограмм».

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

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

3.8. Докажите, что импликация двух предикатов, зави­сящих от одних и тех же переменных, с тождественно лож­ным следствием равносильна отрицанию ее посылки.

ЗАПИСИ НА ЯЗЫКЕ АЛГЕБРЫ ПРЕДИКАТОВ

и Анализ рассуждений средствами алгебры предикатов

Пример 1 . Что означает утверждение «Прямые а и b не па­раллельны»?

Чтобы раскрыть смысл формулы Ø(а || b), надо найти отрицание формулы $a (a Ì a & b Ì a) & (a Ç b = Æ Ú a = b). Имеем Ø(а || b) = Ø($a(a Ì a & b Ì a) & (a Ç b = Æ Ú a = b)) = Ø$a(a Ì a & b Ì a) Ú Ø(a Ç b = Æ Ú a = b)) = Ø$a(a Ì a & b Ì a) Ú a Ç b ¹ Æ & a ¹ b.

Но формула Ø$a(a Ì a & b Ì a), означающая на русском языке «Не существует плоскости, содержащей обе прямые а и b», передает отношение скрещивания прямых, а формула a Ç b ¹ Æ & a ¹ b, пере­водимая на русский язык предложением «Прямые а и b имеют общие точки, но не совпадают», выражает отношение пересечения прямых.

Таким образом, непараллельность прямых означает их пересе­чение или скрещивание. Пример 2 . Записать на языке алгебры предикатов так назы­ваемые «аристотелевские категорические суждения» часто исполь­зуемые в рассуждениях: «Все S суть Р », «Некоторые S суть Р », «Ни одно S не суть Р », «Некоторые S не суть Р ».

Запись приводится в табл. 1.1. В первом столбце этой таблицы указан вид суждения, возникающий при классификации категори­ческих суждений по сложному признаку, учитывающему количество (суждения общие и частные), выражаемое в формулировке кванторными словами «все», «некоторые», и качество (суждения утвердитель­ные и отрицательные), которое передается связками «суть», «не суть», «есть».

В втором столбце дается стандартная словесная формулировка суждений в традиционной логике, а в пятом - их запись на языке алгебры предикатов, при этом S(x) надо понимать как «х обладает свойством S », а Р(х) - как «х обладает свойством Р ».

В четвертом столбце показаны отношения между объемами Vs и VР понятий S и Р , если суждения понимаются в наиболее общем виде, когда они дают исчерпывающую информацию только о субъекте. Например, из суждения «Все S суть Р » ясно, что речь идет обо всех S , объем же предиката не определен: идет ли речь обо всех объектах, обладающих свойством P , или только о некоторых; только ли S суть P , или и другие объекты тоже суть Р . Иногда эту неопределенность в отношении объема предиката Р устраняет контекст, иногда это устранение и не требуется. Чтобы подчеркнуть отношение объема VР к объему Vs, используют более определенную формулировку «Все S и не только S суть Р » или «Все S и только они суть Р ». Вторая формулировка называется общевыделяющим утвер­дительным суждением. Первому суждению отвечает диаграмма Венна, представленная на рис. 1, а, второму-на рис. 1, б. С учетом сказанного суждение «Некоторые S суть Р » в общем виде понимается как «Неко­торые S и не только они суть Р », чему соответствует диаграмма рис. 2, а, но оно может означать и «Некоторые S и только они суть S » (рис. 2, б). Суждению «Все S не суть Р », понимаемому в общем виде, соответ­ствует диаграмма на рис. 3, а. Этому же суждению в выделяющей форме «Все S и только они не являются Р » отвечает диаграмма на рис. 3, б. Такая формулировка соответствует описанию отношения между противоречащими понятиями , т. е. такими, объемы которых не пересекаются и исчерпывают объем более общего родового поня­тия. Наконец, суждению «Некоторые S не есть Р » в общем виде соответствует диаграмма на рис. 4, а, а в выделяющем виде «Некото­рые S и только они не являются Р » - диаграмма на рис. 4, б. Таблица 3.1

Вид суждения	Запись в традиционной логике словесных формулировок	Запись на языке алгебры предикатов	Отношения между объемами Vs и VР
Общеутвердительное	Все S суть P		Рис.1
Частноутвердительное	Некоторые S суть Р		Рис. 2
Общеотрицательное	Ни одно S не суть Р
Частноотрицательное	Некоторые S не суть Р		Рис.4

Пример 3 . Проанализировать рассуждение «Все люди смертны; Сократ - человек; следовательно, Сократ смертен». Первая посылка рассуждения есть общеутвердительное суждение (см. пример 2). Введем обозначения: Ч(х): х - человек; С (х): х - смертен; с - Сократ.

Структура рассуждения:

"х(Ч(х)ÞС(х)), Ч(с) ├ С(с). (3.1)

Пусть следование (3.1) не имеет места. Тогда в некоторой области Do должен существовать набор (a, li(x), lj(x)) для (с, Ч(х), С(х)), при котором будут выполняться следующие условия:

"х(li(x) Þ lj (х)) = И; li(a) = И; lj(a) = Л.

Но тогда импликация li(a) Þ lj (a) имеет значение Л, а значит, по определению квантора общности, "х(li(x) Þ lj (х)) = Л, что противо­речит первому условию. Поэтому следование 2.8 верное, а исходное рассуждение правильное.

Пример 4 . Проанализировать рассуждение: «Всякая хоккейная команда, могущая победить ЦСКА, - команда высшей лиги. Ни одна команда высшей лиги не может победить ЦСКА. Значит ЦСКА непо­бедима».

О бозначения: П(x): команда х может победить ЦСКА; В (x): команда х из высшей лиги.

Структура рассуждения:

"х(П(х) Þ В(х)), "х(В(х) Þ ØП(х)) ├ Ø$хП(х).

Устанавливаем, правильно ли полученное следование, методом равносильных преобразований. Пользуясь следствием б) обобщения предложения 1.10, преобразовываем формулу "х(П(х) Þ В(х))&"х(В(х) Þ ØП(х)) Þ Ø$хП(х).

Имеем: "х(П(х) Þ В(х)) & "х(В(х) Þ ØП(х)) Þ Ø$хП(х) = "х((П(х) Þ В(х)) & (В(х) Þ ØП(х))) Þ Ø$хП(х) = Ø("х((ØП(х) Ú В(х)) & (ØВ(х) Ú ØП(х))) & $хП(х)) =

= Ø("х(ØП(х) Ú (В(х) & ØВ(х)))) & $хП(х) = ØЛ = И.

В этих равносильных образованиях дважды использовалось свойство конъюнкции A & ØA= Л и один раз свойство дизъюнкции А Ú Л = А.

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

Пример 5 . Проанализировать рассуждение: «Если бы какая-ни­будь команда могла обыграть ЦСКА, то и какая-нибудь команда высшей лиги могла бы. «Динамо» (Минск) - команда высшей лиги, а не может обыграть ЦСКА. Значит, ЦСКА непобедима».

Обозначения: П(х): команда х может победить ЦСКА; В(х): команда х из высшей лиги; д - «Динамо» (Минск).

Структура рассуждения:

"х П(х ) Þ $х (В(х )& П(х )), В(д) & ØП(д) ├ Ø$х П(х ). (3.2)

Замечание. При формализации рассуждений следует учитывать, что в естественном языке во избежание частых повторов одних и тех же слов или словосочетаний широко пользуются синонимическими оборотами. Понятно, что при переводе они должны передаваться одной и той же формулой. В нашем примере такими синонимами являются предикаты «команда х может обыграть ЦСКА» и «команда х может победить ЦСКА», и оба они передаются формулой П(х ).

Следование (3.2) неверно. Чтобы это доказать, достаточно ука­зать хотя бы одну интерпретацию формул, выражающих посылки и заключение, в которой посылки будут принимать значение И, а за­ключение - значение Л. Такой интерпретацией, например, является следующая: D = {1, 2, 3, 4}. В этой интерпретации имеем, после вычислений,

И Þ И, И &ØЛ ├ ØИ, или И, И ├ Л.

Итак, в этой интерпретации обе посылки имеют значение И, а за­ключение - значение Л. Значит, следование (3.2) неверно, а рас­суждение неправильное.

3.9. Введя подходящие одноместные предикаты на соот­ветствующих областях, переведите следующие высказывания, на язык алгебры предикатов:

а) Все рациональные числа действительные.

б) Ни одно рациональное число не является действительным.

в) Некоторые рациональные числа действительные.

г) Некоторые рациональные числа не являются действи­тельными.

Решение. Введем следующие одноместные предикаты

Q (х): «х - рациональное число»;

R (x): «х - действительное число».

Тогда перевод приведенных высказываний на язык алге­бры предикатов будет таким:

а) https://pandia.ru/text/78/081/images/image038_14.png" width="144" height="21 src=">

в) https://pandia.ru/text/78/081/images/image040_13.png" width="137" height="21 src=">

3.10. Введите одноместные предикаты на соответствующих областях и запишите при их помощи следующие высказыва­ния в виде формул алгебры предикатов:

а) Всякое натуральное число, делящееся на 12, делится на 2, 4 и 6.

б) Жители Швейцарии обязательно владеют или француз­ским, или итальянским, или немецким языком .

в) Функция, непрерывная на отрезке , сохраняет знак или принимает нулевое значение.

г) Некоторые змеи ядовиты.

д) Все собаки обладают хорошим обонянием.

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

а) Если a есть корень многочлена от одной переменной с вещественными коэффициентами, то также корень этого мно­гочлена.

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

в) Через две различные точки проходит единственная прямая.

г) Каждый студент выполнил по меньшей мере одну ла­бораторную работу.

д) Если произведение натуральных чисел делится на про­стое число, то на него делится по меньшей мере один из сом­ножителей.

е) Через три точки, не лежащие на одной прямой, проходит единственная плоскость.

ж) Наибольший общий делитель чисел a и b делится на всякий их общий делитель.

з) Для каждого действительного числа х существует та­кой у , что для каждого z , если сумма z и 1 меньше у , то сумма х и 2 меньше 4.

и) х - простое число.

к) Каждое четное число, большее четырех, является сум­мой двух простых чисел (гипотеза Гольдбаха).

3.12. Запишите следующие высказывания на языке алге­бры предикатов:

а) Существует точно один х , такой, что Р (х) .

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

в) Существует не более двух х , таких, что Р (х).

г) Существуют точно два различных х , такие, что Р (х).

3.13. Что можно сказать о множестве М, если для любого предиката В (х) на множестве М истинно высказывание ?

3.14. Пусть Р (х) означает «x - простое число», Е (х) означает «х - четное число», О (х) - «х - нечетное число», D (x, y ) - «х делит у » или «у делится на х ». Переведите на русский язык следующие символические записи на языке алгебры предикатов, учитывая, что переменные х и у пробе­гают множество натуральных чисел:

а) P (7) ;

б) E (2) & P (2) ;

в) https://pandia.ru/text/78/081/images/image044_13.png" width="136" height="21 src=">;

д) https://pandia.ru/text/78/081/images/image046_14.png" width="237" height="23 src=">;

ж) https://pandia.ru/text/78/081/images/image048_12.png" width="248" height="23 src=">;

и) https://pandia.ru/text/78/081/images/image050_10.png" width="109" height="21 src=">.png" width="127" height="23">.png" width="108" height="23"> ├ ?

Проверку правильности следования можно проводить и с по­мощью диаграмм Венна, если посылки и заключения - одноместные предикаты, зависящие от одной переменной. Для категорических суждений, каковыми являются в нашем примере посылки и заключе­ния, отношения между объемами понятий S и Р описаны в примере 2. Этим описанием мы и воспользуемся.

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

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

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

Ни на одной из этих диаграмм суждение https://pandia.ru/text/78/081/images/image030_13.png" width="108" height="23"> является частноутвердительным суждением, то возможные для нее диаграммы приведены на рис. 6.

Задача 2. 1

Выразить перечисленные ниже символьные высказывания словами, если Р(х)- одноместный предикат, определенный на множестве М:

Задача 2. 2

Что произойдет с экстенсионалом предиката А(x), который определен как неравенство x*x<2*x-1, если обе стороны этого неравенства умножить на k, где k:

Задача 2. 3

Пусть R(x) - "x -действительное число",

Q(x) - "x -рациональное число". Используя эти символы, записать формульно:

1. все рациональные числа действительны

2. ни одно рациональное число не является действительным

3. некоторые рациональные числа являются действительными

4. некоторые рациональные числа не являются действительными

Задача 2. 4

Введены следующие предикаты:

J(x)- "x - судья",

L(x)- "x - юрист",

S(x)- "x - жулик",

Q(x)- "x - старик",

V(x)- "x - бодрый",

P(x)- "x - политик",

C(x)- "x - член парламента",

W(x)- "x - женщина",

U(x)- "x - домашняя хозяйка",

А(x, y) - "x восхищается y",

j - Джонс.

Найти соотвествие между словестным описанием и формулами:

Все судьи - юристы

Некоторые юристы - жулики

Ни один судья не является жуликом

Некоторые судьи - старики, но бодрые

Судья Джонс не стар и не бодр

Не все юристы судьи

Некоторые юристы, являющиеся политиками, члены парламента

Ни один член парламента не бодр

Все старые члены парламента - юристы

Некоторые женщины одновременно являются юристами и членами парламента

Ни одна женщина не является одновременно политиком и домашней хозяйкой

Некоторые женщины - юристы, являются одновременно и домашними хозяйками

Все женщины - юристы, восхищаются каким-либо судьей

Некоторые юристы восхищаются только судьями

Некоторые юристы восхищаются женщинами

Некоторые жулики не восхищаются ни одним юристом

Судья Джонс не восхищается ни одним жуликом

Существуют как юристы, так и жулики, которые восхищаются судьей Джонсом

Только судьи восхищаются судьями

a. $x $y (L(x)/\S(y)/\A(x, j)/\A(y, j)/\J(j))

b. "x (J(x)® "y (A(x, y) ®J(y)))

c. "x (C(x) ® ù "(x))

d. "x (C(x)/\Q(x) ®L(x))

e. $x (W(x)/\L(x)/\C(x))

f. $x (W(x)/\L(x)/\U(x))

g. "x (W(x) ® ù (P(x)/\U(x)))

h. "x (W(x)/\L(x) ®$y (J(y)/\A(x, y)))

j. "x (J(x) ®L(x))

k. $x (L(x)/\ $y (W(y)/\A(x, y)))

l. $x (L(x)/\S(x))

m. $x (S(x)/\ "y (L(y)/\ ù A(x, y)))

n. "x (J(x) ® ù S(x))

o. "x (J(j)/\ ù A(j, x)/\S(x))

p. $x (J(x)/\Q(x)/\"(x))

q . $x (L(x)/\ $y (W(y)/\A(x, y)))

r. J(i)/\ ù Q(j)/\ ù "(j)

s. ù "x (L(x) ®J(x))

t. $x (L(x)/\P(x)/\C(x))

Задача 2. 5

Перевести на язык формул следующие фразы:

если всякое число делится на всякое число, то оно четное

для каждого действительного числа х существует такое у, что для каждого к, если сумма к и 1 меньше у, то сумма х и 2 меньше 4

найдется такое четное число, которое делится на любое число, если это любое число - простое

наибольший общий делитель чисел а и b делится на всякий их общий делитель

для того, чтобы любое число было простым, необходимо, чтобы оно не делилось на любое нечетное число

для всякого действительного числа существует большее действительное число

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

если произведение конечного числа сомножителей равно 0, то по крайней мере один из сомножителей равен 0

Задача 2. 6

Введены следующие предикаты:

P(x) - "х - простое число"

E(x) - "х - четное число"

O(x) - "х - нечетное число"

D(x, y) - "у делится на х"

Перевести формулы на русский язык:

3. "x (D(2, x) ®E(x))

4. $x (E(x)/\D(x, 6))

5. "x (ù E(x) ® ù D(2, x))

6. "x (E(x)/\"y (D(x, y) ®E(y)))

7. "x (P(x) ®$y (E(y)/\D(x, y)))

8. "x (O(x) ®*y (P(y) ® ù D(x, y)))

Задача 2. 7

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

1. = $x (A(x) ®B(x))¬®"x (A(x) ®$x B(x))

2. = $x (A(x) ¬®B(x)) ¬®"x (A(x)\/B(x)) ® $x (A(x)/\B(x))

Задача 2. 8

Доказать следующие тавтологии:

1. = "x A(x)® $x A(x)

2. = ù "x A(x)¬® $x ù A(x)

3. = $x A(x) ¬® ù "x ù A(x)

Задача 2. 9

Получить предикатные выражения в правильной нормальной форме:

1. "x(("y F(x, y)/\ "y G(x, y, z))\/ "y$z H(x, y, z))

2. $x(ù ($y P(x, y) ®$z Q(z) ®R(x)))

Задача 2. 10

Привести к конъюктивной нормальной форме выражение:

"x (P(x) ®("y (P(y) ®P(f(x, y)))) /\

/\ ù (""y (Q(x, y) ®P(y))))

Задача 2. 11

Построить истинностные таблицы для следующих формул (предикаты определены на множестве из двух элементов):

1. "x(P(x) ®Q)\/(Q/\P(y))

2. "x(S(x) ®L)¬® $x(S(x) ®L)

3. "x $y((B(x)/\D(y))\/(B(x) ®C))

4. "x P(x) ¨S)/\(P(y)\/S)

5. ($x D(x)/\A) ¨($x E(x)\/A)

6. ("x A(x) ®Q) \/ (Q®$x A(x))

7. (A(y)\/Q)¨($x A(x)/\Q)

Задача 2. 12

Дано: D={a, b}, P(a, a)=и, P(a, b)=л, P(b, a)=л, P(b, b)=и Определить истинностные значения формул:

1. "x $y P(x, y)

2. $x "y P(x, y)

3. "x "y (P(x, y) ®P(y, x))

4. "x "y P(x, y)

5. $y ù P(a, y)

7. "x $y (P(x, y)/\P(y, x))

8. $x "y (P(x, y) ®P(y, x))\/P(x, y)

Задача 2. 13

Проверить на логичность следующие рассуждения:

Каждый студент честен. Джон не честен. Значит, Джон не студент.

Святого Франциска любит каждый, кто любит кого-нибудь. Каждый кого-нибудь да любит. Следовательно, Святого Франциска любит каждый.

Ни одно животное не бессмертно. Кошки - животные. Значит, некоторые кошки не бессмертны.

Перья есть только у птиц. Ни одно млекопитающее не является птицей. Значит, все млекопитающие лишены перьев.

Все политики - лицедеи. Некоторые лицедеи - лицемеры. Значит, некоторые политики - лицемеры.

Глупец был бы способен на это. Я на это не способен. Значит, я не глупец.

Если кто-нибудь может решить эту задачу, то и какой-нибудь математик мог бы. Саша - математик, а не может. Значит, проблема не разрешима.

Всякий математик может решить эту задачу, если кто-нибудь может ее решить. Саша - математик, а не может решить. Значит, проблема неразрешима.

Всякий, кто может решить эту задачу - математик. Саша не может ее решить. Следовательно, Саша не математик.

Всякий, кто может решить эту задачу - математик. Ни один математик не может решить эту задачу. Следовательно, она неразрешима.

Если какое-нибудь число, лежащее строго между 1 и 101, делит 101, то простое число, меньшее 11, делит 101. Ни одно простое число, меньшее 11, не делит 101. Значит, ни одно число между 1 и 101 не делит 101.

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

Для любого человека найдется человек, который старше его. Если - x потомок y, то x не старше y. Все люди потомки Адама. Следовательно, Адам не человек.

Для любого множества x существует множество y такое, что мощность y больше мощности x. Если x включено в y, то мощность x не больше мощности y. Всякое множество включено в V. Следовательно, V не множество.

Все пресмыкающиеся имеют 4 ноги, либо вообще не имеют ног. У лягушки 4 ноги. Значит, она пресмыкающееся.

Всякий студент, сдавший сессию вовремя, получает стипендию. Петров стипендию не получает. Следовательно, он не студент.

Все птицы несут яйца. Ни один крокодил не является птицей. Следовательно, крокодилы не несут яиц.

Преподаватель доволен, если все его студенты сдают экзамен с первой попытки. Никто не может сдать логику с первой попытки. Следовательно, преподаватель логики всегда недоволен.

Всякий пятикурсник получает диплом, если он сдал все экзамены. Диплом получили не все. Значит, кто-то не сдал все экзамены.

Ни один человек не любит насекомых. Пауки - не насекомые. Значит, их кто-то любит.

Все учителя рисования - мужчины. Все уроки в младших классах проводят женщины. Следовательно, в младших классах не учат рисованию.

Всякий, кто окончил школу, может говорить по-английски. Никто в семье Мюллера не говорит по-английски. Людей без среднего образования не принимают в институт. Следовательно, ни один из Мюллеров не учится в институте.

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

Всякий, кто находится в здравом уме, может понимать математику. Ни один из сыновей Тома не может понимать математику. Сумасшедшие не допускаются к голосованию. Следовательно, ни один из сыновей Тома не допускается к голосованию.

Всякий парикмахер в N бреет всех тех и только тех, кто не бреется сам. Следовательно, в N нет ни одного парикмахера.

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

Задача 2. 14

Восстановите пропущенные посылки или заключение так, чтобы следующие рассуждения были логичны:

Только храбрецы достойны любви. Ему везет в любви. Он не храбрец.

Взрослых пускали только с детьми. Меня пустили. Значит, я либо ребенок, либо пришел с ребенком.

Задача 2. 15

Справедливы следующие утверждения:

знание структуры данных необходимо для совершенствования дисциплины ума;

только опыт программирования может создать дисциплинированный ум;

для того, чтобы написать компилятор, надо иметь возможность анализировать задачи;

недисциплинированный ум не может анализировать задачи;

всякий, кто писал структурные программы, может рассматриваться как опытный программист.

Можно ли из этих предположений определить справедливость нижеследующих утверждений:

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

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

8. анализ задач не возможен теми, кто игнорирует структуры данных;

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

Задача 2. 16

Записать посылки в виде формул и применить все известные методы для доказательства правильности заключений.

Посылки: 1. дракон счастлив, если все его дети могут летать;

2. зеленый дракон может летать;

3. дракон зеленый, если, по крайней мере, один из его родителей зеленый, а иначе он ярко-розовый.

Заключения: 1. Зеленые драконы счастливы.

2. Бездетные драконы счастливы (здесь вам могут понадобиться некоторые очевидные пропущенные посылки).

3. Что делать ярко-розовому дракону для того, чтобы быть счастливым?

Задача 2. 17

Пользуясь символами, введенными для предикатов, и арифметическими знаками (например, "+" и "<"), перевести на язык формул:

1. Если произведение конечного числа сомножителей равно нулю, то по меньшей мере один из сомножителей равен нулю (Px обозначает "х есть произведение конечного числа сомножителей", а Fxy - "х есть один из сомножителей числа у").

2. Наибольший общий делитель чисел a и в делится на всякий их общий делитель (Fxy обозначает "х есть один из делителей числа у", а Gxyz - "z есть наибольший общий делитель чисел х и у").

3. Для всякого действительного числа х существует большее действительное число y(Rx).

4. Существуют такие действительные числа х, у, z, что сумма чисел х и у больше, чем произведение чисел х и z.

5. Для каждого действительного числа х существует такое у, что для каждого z, если сумма z и 1 меньше у, то сумма х и 2 меньше 4.

Задача 2. 18

Пусть А0, А1, ..., Аn, ... представляет собой последовательность действительных чисел. С помощью ограниченных кванторов перевести в символическую форму:

1. Утверждение, что а есть предел этой последовательности; 2. Утверждение, что эта последовательность имеет предел; 3. Утверждение, что эта последовательность есть последовательность Коши (т. е. что если дано е>0, то существует такое положительное число k, что из n, m>k вытекает úAn - Amú < e).

Написать отрицание каждой из формул.

Задача 2. 19

Построить выводы, соответствующие следующим рассуждениям:

Ни один республиканец или демократ не является социалистом. Норман Томас - социалист. Следовательно, он не республиканец.

Всякое рациональное число есть действительное число. Существует рациональное число. Следовательно, существует действительное число.

Ни один первокурсник не любит второкурсников. Все, живущие в Даскомбе, - второкурсники. Следовательно, ни один первокурсник не любит никого из живущих в Даскомбе.

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

Некоторым нравится Элвис. Некоторые не любят никого, кому нравится Элвис. Следовательно, некоторых любят не все.

Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекались к ответственности. Следовательно, некоторые люди, привлекавшиеся к ответственности, не являются торговцами наркотиками.

Все первокурсники встречаются со всеми второкурсниками. Ни один первокурсник не встречается ни с одним студентом с предпоследнего курса. Существуют второкурсники. Следовательно, ни один второкурсник не является студентом предпоследнего курса.

Все рациональные числа являются действительными числами. Некоторые рациональные числа - целые числа. Следовательно, некоторые действительные числа - целые числа.