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

(а) (A ∩ B) = A \ (A \ B)

(б) A ∩ (B \ A) = ∅

(в) (A \ B) ∪ B = A

Какие из следующих условий можно выразить булевскими формулами от переменных p₁, p₂, p₃, p₄, использующими лишь логические связки ∧и ∨(без отрицания ¬)?

По крайней мере две переменные из p₁, p₂, p₃, p₄истинны (равны 1).

В точности две переменных из p₁, p₂, p₃, p₄истинны (равны 1).

Хотя бы одна переменная из p₁, p₂, p₃, p₄истинна (равна 1).

Какие из следующих условий можно выразить булевскими формулами от переменных p₁, p₂, p₃, p₄, использующими лишь логические связки ∧и ∨(без отрицания ¬)?

По крайней мере две переменные из p₁, p₂, p₃, p₄истинны (равны 1).

Не все из переменных из p₁, p₂, p₃, p₄ложны (равны 0).

Нечетное число переменных из p₁, p₂, p₃, p₄истинны (равны 1).

Пусть задан неориентированный нагруженный граф 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; 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, 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)

Какие из следующих условий можно выразить булевскими формулами от переменных p₁, p₂, p₃, p₄, использующими лишь логические связки ∨и ∧(без отрицания ¬)?

По крайней мере три переменных из p₁, p₂, p₃, p₄истинны (равны 1).

В точности три переменных из p₁, p₂, p₃, p₄истинны (равны 1).

Четное число переменных из p₁, p₂, p₃, p₄истинны (равны 1).

Какие из следующих равенств справедливы для всех множеств A, B и C?

(а) (A ∩ B) \ C = A ∩ (B \ C)

(б) (A ∩ B) ∪ C = A ∩ (B ∪ C)

(в) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)

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

∃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, инф, неуд)))

Используя алгоритм БыстроеЗамыкание, вычислить замыканиедля набора исходных продуктов X = { c,d} и следующей системы технологических процессов F:

a, b, d →​ h;

a, c, d, g →​ f;

d, g →​ b;

e, f →​ c;

b, k →​ a;

d, c →​ k;

h, d, c →​ b;

h, d →​ g;

c, d, k →​ h.

Определите длину кратчайшей цепочки технологических процессов, приводящей к получению a.