Логика предикатов
Внимание! Все тесты в этом разделе разработаны пользователями сайта для собственного использования. Администрация сайта не проверяет возможные ошибки, которые могут встретиться в тестах.
Дискретная математика для СПО, зачет «логика предикатов».
Система оценки: 5* балльная
Список вопросов теста
Вопрос 1
Предложение, о котором нельзя сказать истинно оно или ложно.
Варианты ответов
- высказывание
- булева функция
- предикат
Вопрос 2
При любой подстановке вместо предметных переменных любых конкретных предметов из множеств соответственно предикат превращается в истинное высказывание и называтся .
Варианты ответов
- выполнимым
- тождественно истинным
- опровержимым
Вопрос 3
Операция, при который предикат превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превышаются в истинные высказывания.
Варианты ответов
- конъюнкция
- дизъюнкция
- отрицание
Вопрос 4
Операция, при который предикат превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых исходное высказывание превращается в ложное высказывание.
Варианты ответов
- конъюнкция
- дизъюнкция
- отрицание
Вопрос 5
Правило, по которому каждому одноместному предикату, определенному на множестве, сопоставляется высказывание, которое истинно в том н только в том случае, когда предикат тождественно истинен, и ложно в противном случае.
Варианты ответов
- квантор общности
- квантор существования
- функция-высказывание
Вопрос 6
Правило, по которому каждому одноместному предикату, определенному на множестве, ставится в соответствие высказывание, которое ложно в том и только в том случае, когда предикат тождественно ложен, и истинно в противном случае.
Варианты ответов
- квантор общности
- квантор существования
- функция-высказывание
Вопрос 7
Формула логики предикатов на множестве при подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, превращается в выполнимый предикат и называется.
Варианты ответов
- опровержимой
- выполнимой
- тавтологией
Вопрос 8
Формула логики предикатов при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно множествах превращается в тождественно истинный предикат. и называется.
Варианты ответов
- тождественно ложной
- тавтологией
- противоречием
Вопрос 9
Формула логики предикатов на множестве при подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, превращается в тождественно истинный предикат и называется.
Варианты ответов
- тождественно ложной
- тавтологией
- тождественно истинной
Вопрос 10
Операция, при который предикат превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один из исходных предикатов.
Варианты ответов
- конъюнкция
- дизъюнкция
- импликация
Вопрос 11
Пусть х, у и z переменные со значениями из (-∞,∞). Указать какое из следующих выражений является двуместным предикатом
Варианты ответов
- x+y=z
- sin(x+у) >1
- x^2>z+y
- 2×2=4
- х>у
Вопрос 12
Пусть х, у и z переменные со значениями из (-∞,∞). Указать какое из следующих выражений не является предикатом
Варианты ответов
- x+y=z
- sin(x)>y
- x^2>y
- 2×2=4
- x^2 \(\left(\forall x(Р(х)\wedge\overline<\left(Q(x\right)>\right)\)
- \(\existsхР(х)\wedge\existsх\overline
\)
- \(\forallхР(х)\vee\forallхQ(x)\)
- \((\forallхР(х))\wedge\overline\)
- \(\existsх(Р(х)\wedge\existsхQ(x))\)
Вопрос 14
Предложение «х – четное число» является …
Варианты ответов
- высказыванием
- одноместным тождественно ложным предикатом
- одноместным тождественно истинным предикатом
- одноместным выполнимым предикатом
Вопрос 15
Одноместным тождественно ложным предикатом на множестве R является предложение…
Варианты ответов
- «x^2 у)»
- «х + 1 = х»
Найти выражения-предикаты
Какие из следующих выражений являются предикатами ?
а) «x делится на 5» (x принадлежит N)
б) «Река x впадает в озеро Байкал» (x пробегает множество всевозможных рек)
в) «x^2+2x+4″(x принадлежит R)
г) «(x+y)^2=x^2+2xy+y^2» (x,y принадлежат R)
д) «x есть брат y » (x,y пробегают множество всех людей)
е) «x и y лежат по разные стороны от z » (x,y пробегают множество всех точек , а z — всех прямых одной плоскости)
ж) «ctg(45 градусов)=1»
з) «x перпендикулярна y» (x,y пробегают множество всех прямых одной плоскости)
и) «x^2+x-6=0″(x принадлежит R)
к) «Для всех вещественных чисел x выполняется равенство x^2+x-6=0
Как я понимаю ,предикатом является удтверждение , высказанное о каком-либо субъекте , и оно вроде как должно иметь какой-то логической результат ?
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Лямба выражения и предикаты (решение логической задачи)
Доброго всем дня. Требуется ваша помощь. В общем поставлена задача: решить логическую задачу "Волк.
Написать указанные предикаты на языке Пролог, проверить определения, вызвав предикаты в интерпретаторе
1. Предикаты для работы со структурами и атомами Задание: Написать указанные предикаты на языке.
Встроенные предикаты. Предикаты взаимодействия, размещение данных
Есть три вопроса: С равенством разобрался, вроде ничего сложного. Про предикаты нашел много.
Описать предикаты: найти квадрат числа X; куб числа X
1) Найти квадрат числа X; куб числа X. помогите(((
4957 / 3575 / 1151
Регистрация: 01.09.2014
Сообщений: 9,676
Сообщение от glorius59
Подскажите , как решать подобные задания и на что надо опираться , чтобы сделать данное задания и похожие ?
Нужно опираться на определения предиката и высказывания, и нужно использовать различие между ними. Эти определения могут немного различаться в разных источниках. Вы их знаете?
Регистрация: 06.12.2021
Сообщений: 86
Предикат это грубо говоря , высказывание в которое можно подставлять аргументы
Добавлено через 3 минуты
высказывание — это предложение ,про которое однозначно можно сказать , истинно оно или ложно
4957 / 3575 / 1151
Регистрация: 01.09.2014
Сообщений: 9,676
Сообщение от glorius59
Предикат это грубо говоря , высказывание в которое можно подставлять аргументы
Используя такое определение, вы и получите только грубые ответы. В частности, из него непонятно, является ли высказывание частным случаем предиката. Почему бы не заглянуть в учебное пособие и привести точное определение? Но в любом случае какие у вас есть сомнения насчет того, что «x делится на 5» — предикат?
Регистрация: 06.12.2021
Сообщений: 86
Предикат становится высказыванием , если подставить в него какое-то определенное значение переменной
Добавлено через 1 минуту
как я понимаю , главное отличие предиката в том ,что выражение может быть истинным или ложным в отличие от высказывания , про которое известно точно
Добавлено через 35 секунд
высказывание является частным случаем предиката
4957 / 3575 / 1151
Регистрация: 01.09.2014
Сообщений: 9,676
Сообщение от glorius59
высказывание является частным случаем предиката
Сообщение от glorius59
главное отличие предиката в том ,что выражение может быть истинным или ложным в отличие от высказывания , про которое известно точно
То есть если никому в настоящее время неизвестно, каждое ли четное число больше 2 представляется в виде суммы двух простых, то, значит, это утверждение не является высказыванием, но является предикатом?
Тем не менее какая-то ясность появилась. И что, вам непонятно, будет ли результат подстановки конкретного натурального числа вместо x во фразу «x делится на 5» высказыванием? Например, вам непонятно, будет ли «12 делится на 5» истинным или ложным, с одной стороны, или про эту фразу нельзя сказать, что она истинна или ложна? Или будет ли результат подстановки некоторого действительного числа вместо x в «x^2+2x+4» истинным или ложным, или про него нельзя сказать, что он истинен или ложен? Или вы не знаете, будет ли «ctg(45) = 1» истинным или ложным, или эта фраза является, например, командой или вопросом, к которым понятия истинности и ложности неприменимы? В соответствии с правилом 4.7 форума жду ваших мыслей об этих и других пунктах задания.
Регистрация: 06.12.2021
Сообщений: 86
Выражение является предикатом , если есть по крайней мере одно такое значение x , при котором данное выражение выполняется или не выполняется , надеюсь что я правильно понял основную мысль
Добавлено через 1 минуту
пункты задания я сделал , ответы следующие :
a) да
б) да
в) да
г) нет
д) да
е) нет
ж) нет
з) нет
и) да
к) да
Добавлено через 1 минуту
Я случайно ошибся, повторил два раза слово «выражение» . Данное выражение , которое вы привели в пример : оно не будет ни выражением , ни предикатом , потому что мы 1) не знаем ,всегда ли оно будет правдой либо всегда будет неправдой 2) мы не знаем , найдется ли такой x среди мн-ва , что результат данного выражения изменится
Добавлено через 6 минут
определение предиката неправильно написал , там должно быть «если найдется хотя бы один такой x , что результат выражения изменится»
Добавлено через 4 минуты
определение конечно коряво сформулировал ,но думая общая мысль понятна
Тест по дискретной математике «Предикаты. Бинарные отношения»
1. Какое из следующих выражений не является предикатом?
1) x делится на 5; 2) ; 3) x есть брат y ; 4) .
2. Область истинности предиката – это…
1) множество всех значений переменных;
3) множество значений переменных, при которых значение предиката истинно;
4) множество значений переменных, при которых значение предиката истинно или ложно.
3. Укажите тождественно ложный предикат
1) ; 2) ; 3) lnx < 0 ; 4 ) .
4. Как обозначается квантор общности?
5. Укажите истинные высказывания
а. ( » x) ( $ y) (x + y = 7) б. ( $ y) ( » x) (x + y = 7)
в. ( $ x) ( $ y) (x + y = 7) г. ( » x) ( » y) (x + y = 7)
1) а, в; 2) в; 3) а, б, в; 4) а, б.
6. В высказывании ( » x) P(x) ® P(y)
1) переменная x свободна, а переменная y связана;
2 ) переменная y свободна, а переменная x связана;
3 ) переменные x и y свободны;
4 ) переменные x и y связаны;
7. Найдите множество истинности предиката « a кратно 3», заданного над множеством M =
8. Постройте отрицание следующего высказывания «Существуют факты, непонятные мудрецам»
1) «Все факты понятны мудрецам»;
2) «Существуют факты, понятные мудрецам»;
3) «Все факты непонятны мудрецам»;
4) «Все факты понятны или непонятны мудрецам».
9. Укажите симметричное бинарное отношение на множестве людей
1) быть братом; 2) быть сыном; 3) быть моложе; 4) работать в одной фирме.
10. Укажите отношение эквивалентности на множестве натуральных чисел
1) “быть больше” ; 2) “быть равным” ; 3) “быть делителем” ; 4) “быть меньше” .
1. Какое из следующих выражений не является предикатом?
1) Река x впадает в озеро Байкал; 2) x и y лежат по разные стороны от z ;
3) x перпендикулярна y ; 4) Обозначим через x неизвестный множитель.
2. Область определения предиката – это…
1) множество всех значений переменных;
3) множество значений переменных, при которых значение предиката истинно;
4) множество значений переменных, при которых значение предиката истинно или ложно.
3. Укажите тождественно ложный предикат
1) ; 2) ; 3) ; 4 ) .
4. Как обозначается квантор существования
5. Укажите истинные высказывания
а. ( » x) ( $ y) ( ) б. ( $ y) ( » x) ( )
в. ( $ x) ( $ y) ( ) г. ( » x) ( » y) ( )
1) а, в; 2) в; 3) а, б, в; 4) а, б.
6. В высказывании ( » x) P(x) ® P(y)
1) переменная x свободна, а переменная y связана;
2 ) переменная y свободна, а переменная x связана;
3 ) переменные x и y свободны;
4 ) переменные x и y связаны;
7. Найдите множество истинности предиката « a
8. Постройте отрицание следующего высказывания «Некоторые животные зимой впадают в спячку»
1) «Все животные зимой впадают в спячку»;
2) «Ни одно животное зимой не впадает в спячку»;
3) «Все животные не зимой впадают в спячку»;
4) «Некоторые животные зимой не впадают в спячку».
9. Укажите симметричное бинарное отношение на множестве натуральных чисел
1) “быть больше” ; 2) “быть равным” ; 3) “быть делителем” ; 4) “быть меньше” .
10. Укажите отношение эквивалентности на множестве людей
1) быть мужем ; 2) быть сыном; 3) быть моложе; 4) работать в одной фирме.
§ 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. Среди следующих пар предикатов выберите те, в которых предикаты являются отрицаниями друг друга:
«Треугольник 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. Каким условиям будут удовлетворять области истинности предикатов А(х) и В(х), определенных на множестве М, если истинны высказывания: