Основы программирования

Упражнение 1:

Номер 1

Пусть е – булевское выражение. Какая из формул выражает закон "исключающего третьего"?

Ответ:

(1) e = e

(2) not e /= e

(3) not (not e) = e

(4) e or not e = True

(5) e and not e = False

Номер 2

Пусть (e) or (v) = False, где e и v – два булевских выражения. Согласно принципу дизъюнкции это означает, что:

Ответ:

(1) e = False; v = True

(2) e = False; v = False

(3) e = True; v = True

(4) e = True; v = False

Номер 3

Пусть (e) and (v) = True, где e и v – два булевских выражения. Согласно принципу конъюнкции это означает, что:

Ответ:

(1) e = False; v = True

(2) e = False; v = False

(3) e = True; v = True

(4) e = True; v = False

Упражнение 2:

Номер 1

Дано истинностное присваивание p = True; q = False; r = True. Какая из формул принимает значение True для этого присваивания?

Ответ:

(1) (p and q) or (not r and p)

(2) (p or q) and (not r and p)

(3) (not p or not q) and(not r or not p)

(4) p and q and r

(5) p or q or r

Номер 2

Дано истинностное присваивание p = True; q = False; r = False. Какая из формул принимает значение True для этого присваивания?

Ответ:

(1) (p and q) or (not r and p)

(2) (p or q) and (not r and p)

(3) (not p or q) and(not r or not p)

(4) p and q and r

(5) p or q or r

Номер 3

Дано истинностное присваивание p = False; q = False; r = True. Какая из формул принимает значение True для этого присваивания?

Ответ:

(1) (p and q) or (not r and p)

(2) (p or q) and (not r and p)

(3) (not p or not q) and (not r or not p)

(4) p and q and r

(5) p or q or r

Упражнение 3:

Номер 1

Пусть e(p, q, r) – булевское выражение, зависящее от трех булевских переменных. Сколько строк содержит таблица истинности для этого выражения?

Ответ:

(1) 1

(2) 2

(3) 4

(4) 8

(5) 16

Номер 2

Пусть e(p, q, r) – булевское выражение, зависящее от трех булевских переменных. Сколько различных истинностных присваиваний можно построить в этом случае?

Ответ:

(1) 1

(2) 2

(3) 4

(4) 8

(5) 16

Номер 3

Пусть e – булевское выражение, зависящее от n булевских переменных. Какие утверждения справедливы для истинностных присваиваний и таблицы истинности этого выражения?

Ответ:

(1) число строк в таблице истинности совпадает с числом различных истинностных присваиваний

(2) число столбцов в таблице истинности совпадает с числом различных истинностных присваиваний

(3) число столбцов в таблице истинности на 1 больше числа ее строк

(4) число различных истинностных присваиваний равно math

Упражнение 4:

Номер 1

Какие булевские выражения являются тавтологиями:

Ответ:

(1) not(not e) = e

(2) not(p and q) = (not p) and (not q)

(3) not(p and q) = (not p) or (not q)

(4) (p or q) and (p or r) = p or (q and r)

Номер 2

В какой из последовательностей булевские операции расставлены в соответствии со своими приоритетами?

Ответ:

(1) not; and; or; implies; =

(2) =; not; and; or; implies

(3) not; =; or; and; implies

(4) not; =; and; or; implies

(5) not; implies; =; and; or

Номер 3

Пусть e – булевское выражение. Для операции эквивалентности справедливо e = e. Это означает, что эквивалентность обладает свойством:

Ответ:

(1) симметричности

(2) антисимметричности

(3) рефлексивности

(4) транзитивности

Упражнение 5:

Номер 1

Какие утверждения об импликации p implies q являются корректными?

Ответ:

(1) импликация ложна тогда и только тогда, когда посылка p истинна, а заключение q ложно

(2) импликация истинна тогда и только тогда, когда посылка p истинна и заключение q истинно

(3) импликация ложна тогда и только тогда, когда заключение q ложно

(4) если посылка p ложна, то импликация истинна независимо от значения заключения q

Номер 2

Известно, что в огороде нет бузины, Вы – программист, а Петр программистом не является, а про дядьку в Киеве ничего не известно. Какое высказывание в соответствии с законами импликации является ложным?

Ответ:

(1) если в огороде бузина, то в Киеве - дядька

(2) если в огороде бузина, то Петр – великий программист

(3) если Петр – великий программист, то и я великий программист

(4) если я программист, то Петр – великий программист

Номер 3

Рассмотрим импликацию p implies q, где булевское выражение p является посылкой, а q – заключением. Какое из утверждений является некорректным?

Ответ:

(1) если импликация истинна и p – истинно, то и заключение q истинно

(2) если импликация истинна, а p – ложно, то об истинности заключения q ничего сказать нельзя

(3) если импликация истинна и q – истинно, то и посылка p истинна

(4) если импликация истинна и q – истинно, то о посылке p ничего сказать нельзя

Упражнение 6:

Номер 1

В программировании булевские переменные и выражения могут принимать три значения – True, False, Undefined (неопределено). Пусть переменная p имеет значение True, а q – Undefined. Какие из выражений будут иметь значение Undefined?

Ответ:

(1) p or q

(2) q or p

(3) p or else q

(4) q or else p

Номер 2

В программировании булевские переменные и выражения могут принимать три значения – True, False, Undefined (неопределено). Пусть переменная p имеет значение False, а q – Undefined. Какие из выражений будут иметь значение Undefined?

Ответ:

(1) p and q

(2) q and p

(3) p and then q

(4) q and then p

Номер 3

Импликация p implies q в языке Eiffel по определению является полустрогой операцией. Какие утверждения являются справедливыми?

Ответ:

(1) p implies q = (not p) or q

(2) p implies q = (not p) or else q

(3) если посылка p ложна, то импликация истинна и тогда, когда заключение q неопределенно

(4) результат импликации всегда определен

Упражнение 7:

Номер 1

Пусть задано множества букв S1 = { а, о, к, м, п} и множество слов: S2 = {имя, мама, мак, потоп, папа, компас}. Укажите формулы теории предикатов, принимающих истинные значения. Здесь Forall обозначает квантор всеобщности, а Exist – квантор существования

Ответ:

(1) Forall s1: S1| s1 – гласная

(2) Exist s2: S2 |длина (s2) – простое число

(3) Forall s1: S1 | Exist s2: S2|s2 содержит s1

(4) Exist s1: S1 | Forall s2: S2| s2 содержит s1

(5) Exist s1: S1| s1 – гласная

Номер 2

Пусть заданы множества целых чисел: S1 = { 3, 5, 7, 11}, S2 = {2, 4, 8, 10}, S3 = { 3, 11, 5, 10}. Укажите формулы теории предикатов, принимающих истинные значения. Здесь Forall обозначает квантор всеобщности, а Exist – квантор существования

Ответ:

(1) Forall s: S1| s – простое число

(2) Exist s: S2 | s – простое число

(3) Forall s: S1 | Exist s1: S2|s < s1

(4) Exist s: S1 | Forall s1: S2| s < s1

(5) Forall s2: S3 | (Exist s: S1| s = s2 or else Exist s1: S2| s1 = s2)

Номер 3

Пусть заданы множества слов: S1 = { племя, око, кот, питон}, S2 = { мама, мак, мел, потоп, папа, компас}. Укажите формулы теории предикатов, принимающих истинные значения. Здесь Forall обозначает квантор всеобщности, Exist – квантор существования, s[i] это i-й символ слова s

Ответ:

(1) Forall s1: S1| Exist s2: S2 |длина (s1) < длина (s2)

(2) Forall s1: S1| Forall s2: S2 |длина (s1) < длина (s2)

(3) Exist s2: S2 |длина (s2) – простое число

(4) Forall s1: S1 |длина (s1) – простое число

(5) Exist s1: S1 | Exist s2: S2|Exist i : Integer | Exist j: Integer | s1[i] = s2[j]

Упражнение 8:

Номер 1

Какие утверждения являются корректными?

Ответ:

(1) если в булевском выражении e некоторое подвыражение u заменить на тавтологичное подвыражение v, то полученное после замены выражение e1 эквивалентно e

(2) таблица истинности для введенных полустрогих операций содержит 9 строк

(3) формула с квантором всеобщности Forall s: S | P(s) по определению имеет значение True, если S – пустое множество

(4) формула с квантором существования Exist s: S | P(s) по определению имеет значение True, если S – пустое множество

(5) False сильнее True

Номер 2

В упражнении 5 приводится текст объявления: "Вход запрещен всем, кто не авторизован или не имеет сопровождающего". Этот текст содержит запрет, которого не добивался видимо автор объявления. В упражнении предлагается переписать объявления. Выполнив это упражнение, укажите, тексты каких объявлений являются корректными?

Ответ:

(1) вход разрешен только тем, кто авторизован или имеет сопровождающего

(2) вход разрешен только тем, кто авторизован и имеет сопровождающего

(3) вход запрещен тем, кто не авторизован или не имеет сопровождающего

(4) вход запрещен тем, кто не авторизован и не имеет сопровождающего

Номер 3

Рассмотрим обобщение задачи о шляпах (упражнение 13). Пусть N – число людей в ряду, M – число цветов шляп ( в упражнении N = 100, M = 2). Какая формула, задающая число правильных ответов,  верна для наилучшей стратегии в этой задаче (надеемся, что Вы нашли эту стратегию):

Ответ:

(1) N / 2

(2) N / M

(3) (N+M) / 2

(4) N – M+1

(5) N - M

Основы программирования - тест 5