Является ли высказыванием предложение Мойте руки перед едой нет
 Скачать 0.85 Mb.
|
|
Вопрос 1 Является ли высказыванием предложение: «Мойте руки перед едой»? нет Является ли высказыванием предложение: «Зимой в Сибири поля покрыты снегом»? Да Является ли высказыванием предложение: «7 больше 11»? Да Является ли высказыванием предложение: «Физику я скорее всего не сдам»? Нет Является ли высказыванием предложение: «Завтра может пойти дождь»? Нет Является ли высказыванием предложение: «Я лгу»? Нет Является ли высказыванием предложение: «Добро пожаловать в Донмакголь»? Нет Высказыванием называется … повествовательное предложение. Истинное или ложное Какие предложения являются высказываниями? 1. Пусть всегда светит солнце! 2. Возможно завтра будет солнечная погода. 3. Сегодня ясный день. 4. Когда же будет тепло? 5. Небо закрыто тучами. 3,5 Каждая связка из последовательности … сильнее связки, расположенной правее, но слабее связки, расположенной левее. ¬, &, v, -> Какое из трех множеств совпадает с множеством всех подформул формулы ¬(x v ¬y)? 1) { x, y, ¬y, x v ¬y } 2) { x, y, ¬y, x v ¬y, ¬(x v¬y) } 3) { x, y, x v y } 2 Формула называется …, если при любых значениях содержащихся в ней переменных ее значение равно ИСТИНА. Тождественно истинной Формула называется …, если при любых значениях содержащихся в ней переменных ее значение равно ЛОЖЬ. тождественно ложной Является ли следующая формула тождественно истинной или тождественно ложной: (x v ¬x) (y &¬y) ? является тождественно ложной Выяснить, является ли следующая формула тождественно истинной или тождественно ложной: x (x y) (x ¬y)? является тождественно ложной Выяснить, является ли следующая формула тождественно истинной или тождественно ложной: (x y z) (x (y z))? является тождественно истинной Выяснить, является ли следующая формула тождественно истинной или тождественно ложной: (¬y ¬x) (x y)? является тождественно истинной Формула В логически следует из формулы А, если … формула В имеет значение ИСТИНА при всех интерпретациях, при которых формула А имеет значение ИСТИНА. Формулы А и В логически эквивалентны, если формулы А и В являются логическим следствием друг друга Вопрос 2 Известно, что высказывание x y истинно, а высказывание (x y)&(y x) ложно. Что можно сказать о высказывании y x ? Это высказывание ложно Правило А, А является правилом ... вывода исчисления высказываний Исчисление высказываний … Непротиворечиво И счисление называется …, если в нем найдется такая выводимая формула А, что формула ¬А также выводима противоречивым Каждая формула, выводимая в исчислении высказываний, является … тождественно истинной Исчисление высказываний является непротиворечивым, поскольку ... ...не существует такой выводимой формулы А, что формула ¬А также выводима Множество схем аксиом исчисления высказываний является … Независимым Множество схем аксиом исчисления называется …, если для каждой схемы существует полученная по этой схеме аксиома, не выводимая в другом исчислении, отличающимся от рассматриваемого лишь отсутствием этой схемы. Независимым Существует ли алгоритм, позволяющий для каждой формулы за конечное число шагов узнать, выводима она или нет? Существует Является ли заданное выражение схемой аксиомы: ¬A→ (B→¬A)? Нет Является ли выражение аксиомой исчисления высказываний: ¬A→ (B→¬A)? Да Является ли выражение аксиомой исчисления высказываний: ¬A→ ((B→С)→¬A)? Да Является ли заданное выражение схемой аксиом исчисления высказываний: A → (B→A)? Да Чтобы узнать, выводима ли некоторая формула в исчислении высказываний, достаточно выяснить, является ли она … тождественно истинной Множество всех формул, выводимых в некотором исчислении, называется …, если существует алгоритм, позволяющий для каждой правильно построенной формулы определить, принадлежит ли она этому множеству. Разрешимым Какие формулы выводимы в исчислении высказываний? тождественно истинные формулы Можно ли из заданного множества предложений получить пустую резольвенту? ¬z v ¬y v x, ¬x v ¬z, ¬x, y v ¬z, z Да Какая из трех формул выводима в исчислении высказываний: 1.( x & ¬y & ¬x & z ) v ( ¬x & y & ¬y & z ) 2. ( x v ¬y v ¬x v z )&( ¬x v y v ¬y v z ) 3. x & ¬y & z. 2 Можно ли из заданного множества предложений получить пустую резольвенту? ¬z v ¬y ¬x v ¬z ¬x ¬y ¬z Нет Какие из формул являются предложениями? 1. A v ¬B&C 2. A v ¬B vC 3. A v ¬A vC 4. (A v ¬B)& C 2 и 3 Какие из формул являются предложениями? 1. A v ¬B&CvD 2. ¬Av ¬BvC 3. Av ¬DvC 4. ¬ (Av ¬B)& ¬C 2 и 3 Выводима ли в исчислении высказываний формула ( A → B ) → (( C → A ) → ( C → B )) ? Да Выводима ли в исчислении высказываний формула (A B) (¬(C ¬A) ¬(C ¬B)) ? Да Выводима ли в исчислении высказываний формула (A&B&C) (A B)&(A C) ? Да Выводима ли в исчислении высказываний формула (A B) ((¬C A) (¬C B)) ? Да Какие предложений можно резольвировать? 1. ¬Av ¬BvC 2. Av ¬DvC 3. BvC 1 и 2, 1 и 3 Вопрос 3 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=(x+y)z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=x+y. Определите значение F(2,1) Введите значение (или -1, если функция неопределена) 9 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=(x+y)z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=x+y. Определите значение F(1,1) Введите значение (или -1, если функция неопределена) 4 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=(x+y)z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=x+y. Определите значение F(1,2) Введите значение (или -1, если функция неопределена) 9 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=(x+y)z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=x+y. Определите значение F(1,0) Введите значение (или -1, если функция неопределена) 1 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x+2, g 2 (x,y)=x 2 , g 3 (x,y)=x+y. Определите значение F(2,1) Введите значение (или -1, если функция неопределена) 11 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x+2, g 2 (x,y)=x 2 , g 3 (x,y)=x+y. Определите значение F(1,2) Введите значение (или -1, если функция неопределена) 7 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x+2, g 2 (x,y)=x 2 , g 3 (x,y)=x+y. Определите значение F(1,1) Введите значение (или -1, если функция неопределена) 6 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x+2, g 2 (x,y)=x 2 , g 3 (x,y)=x+y. Определите значение F(0,1) Введите значение (или -1, если функция неопределена) 3 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=xy. Определите значение F(2,1) Введите значение (или -1, если функция неопределена) 5 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=xy. Определите значение F(1,2) Введите значение (или -1, если функция неопределена) 5 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=xy. Определите значение F(0,1) Введите значение (или -1, если функция неопределена) 1 Функция F(x,y) получена суперпозицией функций f(x,y,z) и g 1 (x,y), g 2 (x,y), g 3 (x,y). f(x,y,z)=x+y+z g 1 (x,y)=x, g 2 (x,y)=y, g 3 (x,y)=xy. Определите значение F(1,1) Введите значение (или -1, если функция неопределена) 3 Вопрос 4 На множестве натуральных чисел определены предикаты P(x)= «х – простое число», Е(х)= «х– четное число», D(x,y)=«у делится на х». При каких значениях переменных выражение P(x) → ( y(E(y)&D(x,y)) является истинным? При любом значении переменной х На множестве натуральных чисел определены предикаты P(x)=«х – простое число», Е(х)=«х– четное число», D(x,y)=«у делится на х». При каких значениях переменных выражение x(E(x)&P(x)&D(x,y))является истинным? Таких значений не существует На множестве натуральных чисел определены предикаты P(x)=«х – простое число», Е(х)=«х– четное число», D(x,y)=«у делится на х». При каких значениях переменных выражение x(E(x)&P(x)&D(x,y))является истинным? При у – четных Исчисление предикатов является... непротиворечивой теорией В исчислении предикатов доказуемы... общезначимые формулы Общезначима ли формула xP(x) →P(y)? Да Фразу «х является простым числом» можно назвать … одноместным предикатом На множестве натуральных чисел определены предикаты P(x)= «х – простое число», Е(х)= «х– четное число», D(x,y)= «у делится на х». При каких значениях переменных выражение x(P(x) → y(E(y)&D(x,y))) является истинным? 1. При х – четных и у – кратных х. 2. При х=2 и у – четных. 3. При у – четных. 4. Таких значений не существует. 5. При любых значениях переменных 5 В каком виде можно записать выражение «существует такое х, что сумма х+у больше числа х»? 1. x y P(x,y) 2. x y P(x) 3. x P(x,y) 4. x P (x) 3 Даны предикаты P(x)="x имеет крылья" и Q(y)="y является птицей". Формула, соответствующая выражению "любая птица имеет крылья": 1. x (Q(x)→P(x)) x P(x)→Q(x) 3. x Q(x)→P(x) x y P(x)→Q(y) 1 В каком виде можно записать выражение «для каждого х сумма х+у больше числа х»? 1. x y P(x,y) 2. x y P(x) 3. x P(x,y) 4. x P(x,y) 4 Фразу "сумма х+z больше х" можно назвать … двуместным предикатом Фразу "х делится на у" можно назвать … двуместным предикатом Вопрос 5 Проанализировать рассуждение на истинность: Всякий попугай является птицей. Некоторые попугаи, живущие рядом с людьми, умеют разговаривать. Существует птица, не живущая с людьми, но умеющая разговаривать. Следовательно, эта птица – попугай. Ложно Какие переменные в данной формуле являются свободными x y zP(x,y,z,p)? P Верно ли тождество (¬ uP(u)→ ¬ y u Q(y,u))→ x R(x) ≡ x y u (¬P(u)&Q(y,u) v R(x))? Верно Верно ли тождество: ( xP(x)→ yQ(y))→R(z) ≡ xP(x)& y ¬Q(y)v R(z) Верно Какие из данных формул находятся в предваренной форме 1. x y z uA(x,y,z,u) 2. ¬ x y(A(x,y)&B(x,y)) 3. x yA(x,y) B(x,y) 4. x y(A(x,y) v ¬B(x,y)) 1,4 Какие из данных формул находятся в предваренной форме 1. ¬ x y z uA(x,y,z,u) 2. x yA(x,y)& x yB(x,y) 3. x yA(x,y) B(x,y) 4. x yA(x,y) v x yB(x,y) нет ни одной формулы в предваренной форме Какие переменные в данной формуле являются связанными x y(P(x,y,z,p)→Q(x,z))? X,y Скулемовская форма для формулы ¬ x y x y x y формула (или формулы) с номером 1. A(c,y)&B(c,y) 2. ¬A(c,y) v B(c,y) 3. ¬A(x,f(x)) v ¬B(x,f(x)) 3 Скулемовская форма для формулы ¬ x y z uA(x,y,z,p) формула (или формулы) с номером 1. A(x,y,z,p) 2. ¬A(b,y,f ( y) ,p) 3. ¬A(x,f(x),g ( y ) ,h(x,y)) нет правильного ответа Формула F общезначима, если она … истинна в любой интерпретации Какие из выражений являются формулами исчисления предикатов 1.P(x) 2. xQ(x) 3. x xR(x,y) 1 и 2 Вопрос 6 Функция f(x,y) получена операцией примитивной рекурсии из функций g(x) и h(x,y,z). Вычислить значение f(4,1), если g(x)=x+1 и h(x,y,z)=xz 20 Функция f(x,y) получена операцией примитивной рекурсии из функций g(x) и h(x,y,z). Вычислить значение f(4,2), если g(x)=x+1 и h(x,y,z)=xz 80 Функция f(x,y) получена операцией примитивной рекурсии из функций g(x) и h(x,y,z). Вычислить значение f(3,3), если g(x)=x и h(x,y,z)=xz 81 Функция f(x,y) получена операцией примитивной рекурсии из функций g(x) и h(x,y,z). Вычислить значение f(3,2), если g(x)=x и h(x,y,z)=xz 27 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(3), если С=1 и h(x,y)=(x+1)y 6 Функция f(x,y) получена операцией примитивной рекурсии из функций g(x) и h(x,y,z). Вычислить значение f(3,1), если g(x)=x и h(x,y,z)=xz 9 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(4), если С=1 и h(x,y)=(x+1)y 24 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(2), если С=5 и h(x,y)=3y 45 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(3), если С=5 и h(x,y)=3y 135 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(2), если С=2 и h(x,y)=x+y 3 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(3), если С=2 и h(x,y)=x+y 5 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(4), если С=2 и h(x,y)=x+y 8 Функция f(x) получена операцией примитивной рекурсии из константы С и функции h(x,y). Вычислить значение f(1), если С=5 и h(x,y)=3y 15 Вопрос 7 Машины Тьюринга это … …формализация понятия алгоритма. Не существует машины Тьюринга, решающей проблему… самоприменимости. Работа машины Тьюринга заканчивается, если… машина переходит в конечное состояние. Пусть q 1 – начальное состояние, q 0 – конечное состояние машины Тьюринга. Какие команды не противоречат определению правильных вычислений на машине Тьюринга: 1) q 1 a i a i H q 0 2) q 1 a 0 a i R q 3 3) q 0 a j a i R q 3 1, 2 Пусть q 1 – начальное состояние, q 0 – конечное состояние машины Тьюринга. Какие команды не противоречат определению правильных вычислений на машине Тьюринга: 1) q 4 a 0 -> a j L q 2 2) q 2 a 2 -> a 2 L q 2 3) q 1 a 1 -> a 0 H q 0 4) q 0 a 0 -> a j R q 1 1, 2, 3 Пусть q 1 – начальное состояние, q 0 – конечное состояние машины Тьюринга. Какую функцию реализует заданная машина, если ее применять ко входному слову 1 Х+1 ? q 1 1 1 R q 2 q 2 1 1 R q 2 q 2 0 1 L q 3 q 3 1 1 L q 3 q 3 0 0 R q 0 Функцию f(x) = x+1 Пусть q 1 – начальное состояние, q 0 – конечное состояние машины Тьюринга. Какую функцию реализует заданная машина, если ее применять ко входному слову 1 Х+1 ? q 1 1 1 R q 2 q 3 0 1 R q 3 q 3 1 1 R q 0 q 2 1 1 R q 2 q 2 0 1 R q 3 работа машины зацикливается Пусть q 1 – начальное состояние, q 0 – конечное состояние машины Тьюринга. Какая из трех машин Тьюринга, если ее применять ко входному слову 1 Х+1 , правильно вычисляет функцию o(x), равную нулю для всех x? 1) q 1 1 1 L q 2 ; q 2 0 1 L q 3 ; q 3 0 1 L q 4 ; q 4 0 1 H q 0 2) q 1 1 0 R q 2 ; q 2 1 0 R q 2 ; q 2 0 1 H q 0 3) q 1 1 1 L q 2 ; q 2 0 1 L q 2 ; q 2 1 1 H q 0 2 Пусть q 1 – начальное состояние, q 0 – конечное состояние машины Тьюринга. Какая из трех машин Тьюринга, если ее применять ко входному слову 1 Х+1 , правильно вычисляет функцию f(x)=x+2? 1. q 2 1 1 R q 3 ; q 3 1 0 H q 0 ; q 1 1 0 L q 2 ; q 2 0 1 R q 2 2. q 2 1 0 R q 2 ; q 2 0 1 L q 3 ; q 3 0 1 H q 0 ; q 1 1 0 R q 2 3. q 1 1 1 L q 2 ; q 3 0 1 H q 0 ; q 2 0 1 L q 3 3 Вопрос 8 Проблема самоприменимости алгоритмически … Неразрешима Проблема останова является алгоритмически… неразрешимой. ... называется система вычислений по строго определенным правилам, которая после их выполнения приводит к решению поставленной задачи. Алгоритмом Если преобразование начальных данных происходит по шагам и на каждом шаге из данных, имевшихся на предыдущем шаге, по предписанным правилам получается новая совокупность величин, можно говорить о … дискретности алгоритма Если на каждом шаге результат работы алгоритма однозначно определяется совокупностью данных, полученных на предыдущем шаге, это означает, что алгоритм является … Детерминированным Если имеется критерий, позволяющий определить, что является результатом работы алгоритма, значит алгоритм … направленный. Множество объектов, к которым применим алгоритм, называется областью его … применимости. Функция, область определения которой совпадает с областью применимости некоторого алгоритма, а значение всегда совпадает с результатом применения этого алгоритма, называется … вычислимой. Тезис Черча утверждает, что класс вычислимых функций, определенных на множестве целых неотрицательных чисел, совпадает с множеством всех частично-рекурсивных функций Класс алгоритмически вычислимых частичных числовых функций совпадает с классом всех частично-рекурсивных функций Функция называется примитивно-рекурсивной, если она получена... из простейших функций конечным числом операций суперпозиции и примитивной рекурсии Согласно тезису Клини-Черча все вычислимые функции являются частично-рекурсивными Вопрос 9 Функция x–y является частично-рекурсивной Какие из функций являются простейшими в терминах теории частично рекурсивных функций? 1) f(x) = s(x). 2) f(x) = U 1 1 (x). 3) f(x) = O 2 (x,s(x)). 4) f(x) = sin(x). 1, 2 Какие из функций являются простейшими в терминах теории частично рекурсивных функций? 1) f(x) = U 2 2 (x,s(x)). 2) f(x,y,z) = U 2 3 (x,y,z). 3) f(x,y) = o 2 (x,у). 4) f(x) = s(o 2 (U 1 2 (x,y),y)). 2 Какие из функций являются примитивно рекурсивными в терминах теории частично рекурсивных функций? 1) f(x) = x+s(x). 2) f(x,y) = x/y 3) f(x,y) = s(O(U 2 2 (x,y))). 4) f(x) = U 1 1 (x)+x. 1, 3, 4 Пусть μ z - оператор минимизации для рекурсивных функций. Какие из выражений являются верными: 1) f(x,y,z) = μ z (g(x,z)=y) 2) f(x) = μ z (g(x,z)=y) 3) f(x,y) = μ z (g(x,y)=z) 4) f(x,y) = μ z (g(x,z)=y) 4 Какие из функций являются частично рекурсивными? 1) f(x,y) = x+y 2) f(x) = x! 3) f(x,y) = x-y 4) f(x,y)=x y 5) f(x,y)=0 3 Какие из функций являются всюду определенными? 1) f(x,y) = x+y 2) f(x) = x! 3) f(x,y) = x-y 4) f(x,y)=0 1, 2, 4 Какие из функций являются всюду определенными? 1) f(x,y) = x-y 2) f(x,y)=x y 3) f(x,y) = x/y 4) f(x,y)=0 2,4 Какие из функций являются частично рекурсивными: 1) f(x,y) = x+y 2) f(x) = x! 3) f(x,y)=x y 4) f(x,y) = x/y 5) f(x,y)=0 4 Является функция f(x,y)=xy+6 общерекурсивной? Да Является ли функция f(x,y)=xy 7 +sin x частично рекурсивной? Нет Функция называется частично-рекурсивной, если она получена... из простейших функций конечным числом операций суперпозиции, примитивной рекурсии и минимизации. 10 вопрос Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(4), если f(x)=x mod 3 Введите значение функции или -1, если значение функции неопределенное -1 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(0), если f(x)=x 2 Введите значение функции или -1, если значение функции неопределенное 0 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(10), если f(x)=x+5. Введите значение функции или -1, если значение функции неопределенное 5 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(10), если f(x)=x 2 Введите значение функции или -1, если значение функции неопределенное -1 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(9), если f(x)=x 2 Введите значение функции или -1, если значение функции неопределенное 3 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(3), если f(x)=x+5. Введите значение функции или -1, если значение функции неопределенное -1 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(5), если f(x)=x+5. Введите значение функции или -1, если значение функции неопределенное 0 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(4), если f(x)=x+5. Введите значение функции или -1, если значение функции неопределенное -1 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(2), если f(x)=x mod 3 Введите значение функции или -1, если значение функции неопределенное 2 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(3), если f(x)=x mod 3 Введите значение функции или -1, если значение функции неопределенное -1 Функция g(x) получена операцией минимизации из функции f(x). Вычислить значение g(4), если f(x)=x 2 Введите значение функции или -1, если значение функции неопределенное 2 |