Используя теорему Поста, выяснить, какие из следующих трех систем функций от 3-х аргументов, заданных последовательностями 8 нулей и единиц, являются полными (наборы значений аргументов упорядочены лексикографически). F={ (1001 0110), (0111 1100), (0001 0011) }, G={ (1111 1111), (0101 0101), (0000 0011) }, H= { (0011 0111), (0110 1000), (1111 0000) }.

Правильный ответ:

• # Пусть задан ориентированный нагруженный граф G: V= {a, b, c, d, e, f, g, h }, E= {(a,b; 21), (a, c; 5), (a, d; 4), (a, e; 16), (a, f; 13), (a, g; 10), (b, e; 10), (b, f; 8), ( b,g; 5), (b, h; 2), (c, e; 10), (c,f; 7), (d, b; 10), (d, g; 5), (d, h; 21), (g,b; 10), (g, h; 10) } (здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
• # Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)? По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).В точности две переменных из p1, p2, p3, p4истинны (равны 1).Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).
• # Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∨ Y , g = X →​ ¬ Y , h = X+Y
• # Полная система булевых функций называется базисом, если при удалении из нее любой функции она становится неполной. Какие функции следует удалить из следующей системы F, чтобы она стала базисом? F: f = X ∧ Y∧ ¬ Z, g = X ∨ Y , h = X+Y+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) )