игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Основы дискретной математики / Тест 7

Основы дискретной математики - тест 7

Упражнение 1:
Номер 1 
    Для следующей формулы  определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). 

\begin{array}{llllllllll}
(\forall x(P(x,y) & \rightarrow & \exists y(\forall z(Q(x,y,z) &\rightarrow & P(x,z)) &\rightarrow & P(z,y))) & \rightarrow & Q(x,y,z)) \\
\phantom{ (\forall x(P(}1\phantom{,}2 & & \phantom{\exists y(\forall z(Q(}3\phantom{,y,}4 & & \phantom{P(x,}5 & & \phantom{P(}6\phantom{,} 7& & \phantom{Q(}8\phantom{,}9\end{array}

Ответ:

 (1) F={2,3,5,6,9} C= {1, 4,7,8} 

 (2) F={1,5,8,9} C= {2, 4,6,7} 

 (3) F={2,6,8,9} C= {1,3,4,5,7} 

 (4) F={2,5,7,8,9} C= {1,4,6} 

 (5) F={2,6,8,9} C= {1,4,5,7} 

Номер 2 
    Для следующей формулы  определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). 

\begin{array}{llllllllll}
(\forall x(P(x,y) & \rightarrow &\exists z (\forall y(Q(x,y,z) &\rightarrow & P(x,z)) \vee P(z,y))) &\rightarrow& \exists zQ(x,y,z))\\
\phantom{ (\forall x(P(}1\phantom{,}2 & & \phantom{\exists z (\forall y(Q(}3 \phantom{,y,}4 & & \phantom{P(x,}5 \phantom{)) \vee P(}6 \phantom{,}7 & & \phantom{\exists zQ(x,}8 \phantom{,}9
\end{array}

Ответ:

 (1) F={2,3,5,6} C= {1, 4,7,8,9} 

 (2) F={1,5,8,9} C= {2, 4,6,7} 

 (3) F={2,6,8} C= {1,3,4,5,7,9} 

 (4) F={2,5,7,8,9} C= {1,3,4,6} 

 (5) F={2,7,8} C= {1,3,4,5,6,9} 

Номер 3 
    Для следующей формулы  определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). 

\begin{array}{llllllllll}
 ((\forall xP(x,y) & \rightarrow & \exists z (\forall y(Q(x,y,z) &\wedge &P(x,z)) &\vee & P(z,y))) &\rightarrow &\exists zQ(x,y,z)) \\
\phantom{ ((\forall xP(}1\phantom{,}2 & & \phantom{\exists z (\forall y(Q(}3\phantom{,y,}4& &\phantom{P(x,}5& &\phantom{P(}6\phantom{,}7 & & \phantom{\exists zQ(x,}8\phantom{,}9
\end{array}

Ответ:

 (1) F={2,3,7,8} C= {1, 4, 5, 6, 9} 

 (2) F={1,3,7,8 } C= {2, 4,5, 6, 9} 

 (3) F={2,6,8} C= {1,3,4,5,7,9} 

 (4) F={2,3,7,8,9} C= {1,4,6} 

 (5) F={2,7,8} C= {1,3,4,5,6,9} 

Упражнение 2:
Номер 1 
  Предположим, что P(x,y) означает "x - это родитель y ", а  M(x) означает " x - это мужчина". Если F(v, w) равно

(M(v) ∧ ∃x∃y ( P(x,y) ∧ P(x,v) ∧  ¬ (y = v) ∧ P(y,w))),

то каково значение выражения F(v, w)?

Ответ:

 (1) v это брат w 

 (2) v это племянник w 

 (3) v это дядя w 

 (4) v это дед w 

 (5) v это двоюродный брат w 

Номер 2 
  Предположим, что P(x,y) означает "x - это родитель y ", а  M(x) означает " x - это мужчина". Если F(v, w) равно

(M(v) ∧ ∃x∃y∃z ( P(x,y) ∧ P(x,z) ∧  ¬ (y = z) ∧ P(y,v) ∧ P(z,w))),

то каково значение выражения F(v, w)?

Ответ:

 (1) v - это брат w 

 (2) v - это племянник w 

 (3) v - это дядя w 

 (4) v - это дед w 

 (5) v - это двоюродный брат w 

Номер 3 
  Предположим, что P(x,y) означает "x - это родитель y ", а  F(x) означает " x - это женщина". Если G(v, w) равно

(F(v) ∧ ∃x∃y ( P(x,y) ∧ P(x,w) ∧  ¬ (y = w) ∧ P(y,v) )),

то каково значение выражения G(v, w)?

Ответ:

 (1) v это сестра w 

 (2) v это племянница w 

 (3) v это тетя w 

 (4) v это бабушка w 

 (5) v это двоюродная сестра w 

Упражнение 3:
Номер 1 
   Какие из следующих формул логики предикатов являются тождественно истинными?

  • ( ∀x P(x) ∨ ∀x Q(x) ) →​ ∀x ( P(x) ∨  Q(x) )
  • ∀x ( P(x) ∨  Q(x) ) →​ ( ∀x P(x) ∨ ∀x Q(x) )
  • (∃x P(x) ∨ ∃x Q(x) ) →​ ∃x ( P(x) ∨  Q(x) ) 
    •

    Ответ:

     (1) только 1 

     (2) только 3 

     (3) 1 и 2 

     (4) 1 и 3 

     (5) 2 и 3 

    Номер 2 
       Какие из следующих формул логики предикатов являются тождественно истинными?

  • ( ∀x P(x) ∧ ∀x Q(x) ) →​ ∀x ( P(x) ∧  Q(x) )
  • ∀x ( P(x) ∧   Q(x) ) →​ ( ∀x P(x) ∧  ∀x Q(x) )
  • (∃x P(x) ∧ ∃x Q(x) ) →​ ∃x ( P(x) ∧   Q(x) ) 
    •

    Ответ:

     (1) только 1 

     (2) только 2 

     (3) 1 и 2 

     (4) 1 и 3 

     (5) 2 и 3 

    Номер 3 
       Какие из следующих формул логики предикатов являются тождественно истинными?

  • ( ∀x P(x) →​ ∀x Q(x) ) →​ ∀x ( P(x) →​  Q(x) )
  • ∀x ( P(x) →​  Q(x) ) →​ ( ∀x P(x) →​  ∀x Q(x) )
  • (∃x P(x) →​ ∃x Q(x) ) →​ ∃x ( P(x) →​   Q(x) ) 
    •

    Ответ:

     (1) только 1 

     (2) только 2 

     (3) только 3 

     (4) 1 и 3 

     (5) ни одна 

    Упражнение 4:
    Номер 1 
     Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат 
R = {(a,b),(b,c), (b,d), (c,d), (d,a), (d,b), (e,d)}. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?

  • ∃x ∀y ((y = x) ∨ R(y,x) ∨  ∃u(R(y,u) ∧ R(u,x)))
  • ∀x ∃y ( R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x)))
  • ∀x (∃yR(y,x) →​ ∀z ((z = x) ∨  R(z,x) ∨ ∃u(R(z,u) ∧ R(u,x)))
    •

    Ответ:

     (1) только 1 

     (2) 1 и 2 

     (3) 1 и 3 

     (4) только 2 

     (5) 2 и 3 

    Номер 2 
     Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат 
R = {(a,b),(b,c), (b,e), (c, a), (c,d), (d,a), (d,b), (e,d) }. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?

  • ∃x ∀y ((y = x) ∨ R(y,x) ∨  ∃u(R(y,u) ∧ R(u,x)))
  • ∃ x ∀y (¬ (y = x) →​ ( R(x,y) ∨ ∃u(R(x,u) ∧ R(u,y))))
  • ∀x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x))) 
    •

    Ответ:

     (1) только 1 

     (2) 1 и 2 

     (3) 1 и 3 

     (4) только 2 

     (5) 2 и 3 

    Номер 3 
     Пусть на множестве V= {a, b, c , d , e} задан двухместный предикат 
R = {(a,b),(b,c), (b,e), (c, b), (c,d), (d,a), (d,b), (e,d) }. Какие из следующих замкнутых формул будут истинны на системе G = <V; R>?

  • ∃x ∀y ((y = x) ∨ R(y,x) ∨  ∃u(R(y,u) ∧ R(u,x)))
  • ∃ x ∀y ( R(x,y) ∨ ∃u(R(x,u) ∧ R(u,y))
  • ∀x ∀y ((y = x) ∨ R(y,x) ∨ ∃u(R(y,u) ∧ R(u,x))) 
    •

    Ответ:

     (1) только 1 

     (2) 1 и 2 

     (3) 1 и 3 

     (4) только 2 

     (5) 2 и 3 

    Упражнение 5:
    Номер 2 
      Пусть в сигнатуру системы, описывающей результаты экзаменов
входит  предикат Студ(З), выделяющий в основном множестве подмножество номеров зачетных книжек студентов, и предикат  Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Только один студент сдал все экзамены на отлично"?


  • ∃x ∀p  (Экз(x, p, отл)  ∧ ∀y (∀p Экз(y, p, отл) →​ (y=x) ))
  • ∃x (∀p Экз(x, p, отл) ∧  ∀y  ((Студ(y) ∧ ¬ (y=x)) →​ (∀p∀o¬ Экз(y, p, o) ∨ ∃o∃p (¬ (o= отл ) ∧  Экз(y, p, o)))))
  • ∀x ∀y  ((Студ(x) ∧(Студ(y) ∧¬ (y=x)) →​ ∃o∃p (¬ (o= отл ) ∧ (Экз(x, p, o)  ∨  Экз(y, p, o)) ))
    •

    Ответ:

     (1) только 1 

     (2) 1 и 2 

     (3) 1 и 3 

     (4) только 2 

     (5) 2 и 3 

     (6) ни одна 

    Номер 3 
     Пусть в сигнатуру системы, описывающей результаты экзаменов
входит предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения
"Все студенты, успешно сдавшие алгебру, успешно сдали дискретную математику или информатику".


  • ∀x ∀o∃b( Экз(x, алг, o) ∧ ¬ (o= неуд ) ∧ ¬(b= неуд ) ∧ (Экз(x, дм , b) ∨ Экз(y, инф, b))
  • ∀x (¬ Экз(x, алг, неуд) →​ ∃b (¬ (b= неуд )∧ (Экз(x, дм , b) ∨ Экз(x, инф, b))))
  • ∀x (∃o( Экз(x, алг, o) ∧ ¬ (o= неуд )) →​  ( Экз(x, дм , неуд ) →​ ¬Экз(y, инф, неуд)))
    •

    Ответ:

     (1) только 1 

     (2) 1 и 2 

     (3) 1 и 3 

     (4) только 2 

     (5) 2 и 3 

     (6) ни одна 

    Упражнение 6:
    Номер 1 
       Пусть F = ∀x∀yP(x,y,z) →​ ∃z∀yQ(x,y,z).
Какие из следующих формул являются предваренными формами эквивалентными F?

  • A= ∃q∀y∃u∃p ( P(u,p,z) →​ Q(x,y,q) )
  • B= ∃u ∃q∃p∀y ( P(u,p,z) →​ Q(x,y,q) )
  • C= ∃u∀y ∃q∃p ( P(u,p,z) →​ Q(x,y,q) )
    •

    Ответ:

     (1) только A 

     (2) A и B 

     (3) A и C 

     (4) только B 

     (5) B и C 

     (6) ни одна 

    Номер 2 
       Пусть F = ∃x∀yP(x,y,z) →​ ∀y∃z Q(x,y,z).
Какие из следующих формул являются предваренными формами эквивалентными F?

  • A= ∀y ∃q ∀u∃p ( P(u,p,z) →​ Q(x,y,q) )
  • B= ∀u ∃q∃p∀y ( P(u,p,z) →​ Q(x,y,q) )
  • C= ∀u∀y ∃p ∃q ( P(u,p,z) →​ Q(x,y,q) )
    •

    Ответ:

     (1) только A 

     (2) A и B 

     (3) A и C 

     (4) только B 

     (5) B и C 

     (6) ни одна 

    Номер 3 
       Пусть F = ∀y ∃xP(x,y,z) →​ ∀z∃x Q(x,y,z).
Какие из следующих формул являются предваренными формами эквивалентными F?

  • A= ∀q ∃p ∃ x∃u ( P(u,p,z) →​ Q(x,y,q) )
  • B= ∀q ∃x ∃p∀u  ( P(u,p,z) →​ Q(x,y,q) )
  • C= ∃p ∀q∀u ∃x ( P(u,p,z) →​ Q(x,y,q) )
    •

    Ответ:

     (1) только C 

     (2) A и B 

     (3) A и C 

     (4) только B 

     (5) B и C 

     (6) ни одна 



    Главная / Алгоритмы и дискретные структуры / Основы дискретной математики / Тест 7