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

Логика предикатов

Внимание! Все тесты в этом разделе разработаны пользователями сайта для собственного использования. Администрация сайта не проверяет возможные ошибки, которые могут встретиться в тестах.

Дискретная математика для СПО, зачет «логика предикатов».
Система оценки: 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 x_1t x₂, . х_n — предмет­ные переменные или предметные постоянные, не обяза­тельно все различные, то F(x_1, x₂, . х_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. Каким условиям будут удовлетворять области истинности предикатов А(х) и В(х), определенных на множестве М, если истинны высказывания: