Задачи по математической логике. Фролов И.С. - 13 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

61. Докажите полноту систем функций:
a) {∧, ∨, ¬};
b) {∧, ¬};
c) {∨, ¬};
d) {⇒, ¬};
e) {⇒, 0};
f) {⇒, :};
g) {⊕, ∨, 1};
h) {⊕, ∧, 1};
i) {⇔, ∨, 0};
j) {⇔, ∧, 0};
k) {|};
l) {↓}.
62. Докажите, что нельзя с помощью суперпозиций выразить:
a) ¬ через ∧, ∨, ⇒ и ⇔;
b) ⇒ через ∧ и ∨;
c) ∧ через ∨ и ⇒;
d) ∨ через ⇔ и ⊕.
63. Постройте многочлен Жегалкина для функций от трех пере-
менных, заданных следующими таблицами значений:
a) 0 0 0 1 0 0 0 0;
b) 0 0 1 0 0 1 0 0;
c) 0 0 0 0 0 1 1 1;
d) 1 0 0 1 0 1 1 0;
e) 0 1 0 1 1 0 1 0;
f) 1 0 1 1 1 1 0 1.
64. Приведите к многочлену Жегалкина следующие функции:
a) xy ∨ xz;
b) (x ∨ y)(y ∨ xz);
c) (x ↓ y) | z;
d) (x ⇒ y)(y ↓ z);
e) ((x ⇒ y) ∨ ¬z) | x;
f) x(x ⇔ z) ∨ (x ↓ y).
65. Решите логические уравнения:
a) x ∨ y = 0;
b) (x ∧ y = 1;
c) (x ∨ y) = x;
d) (x ⇒ y) = y;
e) (1 ⇒ x) ⇒ y = 0;
f) xy = x ⇒ y.
g) x ⇔ y = x ∨ y.
66. Решите системы логических уравнений:
a)
½
x ⇔ y = x,
x ∨ y = x;
b)
½
x ⇒ y = xy,
y ⇒ x = x ∨ y;
c)
½
xy = x ⇒ y,
x ∨ y = x.
67. Постройте релейно-контактные схемы для следующих логи-
ческих функций, считая, что x ⇒ y = x ∨ y :
a) (x ⇒ y)(y ⇒ z);
b) ((x ⇒ y)(y ⇒ z)) ⇒ (x ⇒ z);
c) (x ⇒ y) ⇒ x(y ∨ z);
d) (x ⇒ (y ⇒ z)) ⇒ (y ⇒ x).
VII. Исчисление высказываний
68. Являются ли доказательствами в ИВ следующие последова-
тельности формул:
a) (A ⇒ (A ∨ B));
b) (A ⇒ (A ∨ B)), ((A ⇒ (A ∨ B)) ⇒ (B ⇒ (A ⇒ (A ∨ B)))),
(B ⇒ (A ⇒ (A ∨ B)));
c) (A ⇒ (B ⇒ A)), ((A ⇒ (B ⇒ A)) ⇒ B), B .
69. Выводами из каких множеств гипотез Γ являются следующие
последовательности формул:
13

Страницы