Математическая логика и теория алгоритмов (стр. 4 )

необходимые  для  оценки  знаний,  умений,  навыков  и  (или)  опыта

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

процессе  освоения  образовательной  программы

ПРИМЕРНАЯ  КОНТРОЛЬНАЯ  РАБОТА  1

Верно ли, что  a ∧ b → (b ∨ c → a ∧ b) – закон логики? Найдите  СДНФ  и  СКНФ:  (x →  y) ∨ ↔ ∧ y Упростите:  a → с ∧ (a → с ∨ b) ∨ Почему отрицание нельзя выразить через  ∨  и  →  ?

ПРИМЕРНАЯ  КОНТРОЛЬНАЯ  РАБОТА  2

Постройте  РКС, реализующую формулу:  c ∧ a  → (∧ c ∨  ) →  a ∨ c Найдите полином Жегалкина:  (x →  y) ∨ ↔ ∧ y Правильно ли рассуждение: Если  2 > 3,  то 15 – простое.  Если  либо  2 < 5, либо  3 > 6, то 15 – не простое. Но 3 ≤ 6.  Значит,  2 ≤ 3. Верно ли, что если  F ∨ G  F ∧ G,  то  F G  ?

ПРИМЕРНАЯ  КОНТРОЛЬНАЯ  РАБОТА  3

Найдите область истинности  D1(P)  предиката:  P(x) = 2 /(x–1) > 3 + x Истинно ли высказывание?  ∀  a ∈ R  ((a > 0) → (a2 > 0)) Определите вид формулы  ИП:  ∀  x  (P(x, y) →  Q(x, y)) Приведите к  ППНФ:  ∃  x  (P(x, y) ∨ (∀  y  (Q(y) → R(x))))

ПРИМЕРНАЯ  КОНТРОЛЬНАЯ  РАБОТА  4

Что делает машина  Тьюринга?

М	q1	q2
a0	a0Лq2	a0Cq0
1	1Лq1	a0Пq2

Напишите программу машины  Тьюринга,  преобразующую слова

НЕНАВИСТЬ ⇒  ЛЮБОВЬ

1п…п1  ⇒  11…11

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

ПРИМЕРНЫЙ  ПЕРЕЧЕНЬ  ПРАКТИЧЕСКИХ  ЗАДАНИЙ

Что делают следующие программы?

invert	q0	q1		erase	q0	q1	q2	q3
a0	1Пq0	a0	a0Пq3	a0Пq3
0	1Лq1	0	0Лq2	a0 Лq2	0Cq0
1	0Лq1	1	1Лq2	a0 Лq2	1Cq0

Проследите их работу из начальных конфигураций  10101(q1)  и  10110(q1).

Напишите программу  МТ,  прибавления  1  к числу в десятичном алфавите. Напишите программу  МТ,  перерабатывающую слово  КРИЗИС  в слово  РАСЦВЕТ. Напишите программу  МТ,  прибавления  1  к числу в десятичном алфавите. Напишите программы машин  Тьюринга:  1… 1п…п1…1  ⇒  1… 1п…п1…1;  1… 1п…п1…1 ⇒  1… 1п…пп…п. Сконструируйте из стандартных машин  МТ, стирающую два числа слева от текущего:

.

Сконструируйте МТ, переставляющую два числа на ленте:  . Что делают машины    ? Сконструируйте из стандартных машин  МТ, вычисляющую функцию  . Постройте рекурсивное описание функций:

f(x) = x + 2 ,  f(x) = 5⋅x + 1,  f(x) = 5x.

Докажите, что функции  f(x,  y) = |5⋅x – y| ,  f(x) =   являются  ПРФ. Будут ли высказываниями:  а)  “Верно ли, что  2 + 1 = 3 ?”,  б)  “Если сегодня пятница, то будет лекция по алгебре”,  в)  “3 – простое число”,  г)  “Сегодня,  29  декабря  2009  года,  в  21-00  по московскому времени произойдёт солнечное затмение”,  д)  “Натуральное число называется простым, если оно имеет ровно два различных натуральных делителя:  единицу и само число”. Истинны или ложны:  а)  2 ∈ { х ∈ R  | 2·х3 – 3·х2 + 1 = 0},  б)  ∅ ∈ ∅,  в)  0 < ln 2 < 1,  м)  sin > 0. Какие из данных противоречивы:  а)  x = 0, (x ∧ y) = 1;  б)  a = 1, (a ∨ b) = 1;  в)  a = 1, (b → a) = 1;  г) x = 1,  (x ∨ b) = 0;  д)  u = 0,  (u ∨ v) = 0 Будут ли формулами:  а)  ((a ∨ ) ∧ (b → c)),  б)  ,  в)  (((a∨ ) ∧ (b → c)),  г)  (a → ) ? Восстановите скобки:  а)  a → b ∨ ↔ ∧ b → c ∨ ; 

б)  a ∧ (b ∨ c) ↔ →  b ∨ c;

Классифицируйте формулы:  a → b ∨ b → c;  (a → b) ∨ (b → c); 

(a ↔ b) ∧  ;  a ∧ (b ∨ c) ↔ .

Если  F – закон логики, то  F ∨ G;  F ∧ G;  G → F;  F → G  законы логики? Упростите формулы:  a ∧ (b ∨ c) ↔ b ∧ a;  → ((p ∨ q) → p); 

(p↔ q) ∧ (p ∨ q);  (p → q) ∧ (q → ) ∧ (r → p).

Приведите формулы  к  КФ  и  ДФ:  ; 

(a→ ) → (b → c) ∧ ∧ ,  x → y →  ;  →  x ∧ ∨ v ;

(a → b) → ((a → (b →  c)) → (a →  c)).

Можно ли формулу, равносильную  ∨  ,  записать, используя только связки  ∧ , ∨ ,  но не используя отрицания? Найдите по таблицам истинности  СДНФ  и  СКНФ  следующих формул: 

(a → b) ∧ ↔ b∨ a ;  (x ∨  (∧ y)) ↔  (x ∨ y) ;  ;  xy → z ;  .

Упростите  РКС: Постройте наиболее простые  РКС  по функциям проводимости:

(a → b) ∨  (b → a),  x ∨ ( ∧  y) →  (x ∨ y),  (x ∨  y ∨  z)  ∧  (x ∧ ↔  x ∧  )