Пусть 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) )
Пусть 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) )
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).В точности две переменных из p1, p2, p3, p4истинны (равны 1).Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).
Пусть задан неориентированный нагруженный граф
G:
V= {a, b, c, d, e, f, g, h, k }, E= {(a, b; 9), (a, c; 6), (b, c; 10), (b, d; 5), (b, e; 4), (d, e; 6), (d, f; 4), (e, f; 25),(f, g; 20), (g, h; 8), (g, k; 10), (h, k; 7) }
(здесь каждая скобка
(u,v; D) задает ребро
(u,v) из
E и его "вес"
c(u,v)=D ).Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, c) II) (f, g) III) (g, k)
Пусть задан неориентированный нагруженный граф
G:
V= {a, b, c, d, e, f, g, h }, E= {(a,b; 5), (a, h; 7), (b, c; 4), (b, f; 3), (c, d; 6), (c,f; 7), (d, e; 10), (e, f; 9), ( b,g; 15), (g, h; 10) }
(здесь каждая скобка
(u,v; D) задает ребро
(u,v) из
E и его "вес"
c(u,v)=D ).Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, g) II) (c, f) III) (d, l)
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k }, E= {(a, b; 10), (a, c; 7), (b, f; 21), (b, d; 9), (c, d; 8), (f, e; 7), (f, g; 8), (e, k; 12), (e, h; 10), (g, h; 8) }
(здесь каждая скобка
(u,v; D) задает ребро
(u,v) из
E и его "вес"
c(u,v)=D ).Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (a, b) II) (e, h) III) (b, f)
Пусть в сигнатуру системы, описывающей результаты экзаменоввходит предикат Студ(З), выделяющий в основном множестве подмножество номеров зачетных книжек студентов, и предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения "Только один студент сдал все экзамены на отлично"?∃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)) ))
Пусть в сигнатуру системы, описывающей результаты экзаменоввходит предикат Экз(З, П, О), где З - номер зачетной книжки студента, П - предмет (возможные значения: дм - дискретная математика, инф - информатика, алг - алгебра), О - оценка, полученная за экзамен (ее возможные значения: отл, хор, уд, неуд). Какие из следующих формул правильно выражают смысл предложения"Все студенты, успешно сдавшие алгебру, успешно сдали дискретную математику или информатику".∀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, инф, неуд)))
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).Не все из переменных из p1, p2, p3, p4ложны (равны 0).Нечетное число переменных из p1, p2, p3, p4истинны (равны 1).
Пусть отношения
R и
S со схемами
R(A,B,C) и
S(B,C,D) заданы перечислениями своих кортежей:
R ={(a, 5, 8), (a, 6, 8), (a1, 3, 12), (a1, 6, 8)},S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}.
Какое отношение
Qi (i=1, 2, 3) задается выражением реляционной алгебры
Q = πBCD( R >< σ C <10(S))и какая из указанных формул
Fj (j=1,2) ему эквивалентна?
Q1 ={ (6, 8, d), (5, 8,d1) } F1= ∃a (R(a, b, c) ∧ S(b, c, d) ∧ (c > 10))Q2 ={ (5, 8, d), (6, 8, d), (5, 8,d1) } F2= ∃a ∃c ((R(a, b, c) ∧ S(b, c, d) ) ∧ (c > 10))Q3 = {(5, 8, d), (6, 8, d), (6, 2, d), (5, 8,d1) }