Преобразуем эту формулу, используя соответствующие эквивалентности u
.
И
зобразим
схему, соответствующую заключительной
формуле
B
A
Варианты заданий.
1. Построить таблицу истинности для формулы:
a) ( (P (Q P)) (P R));
b) ((P (Q R)) ((P Q) (P R)));
c) ((P (Q P)) ((Q P) Q));
d) СС;
e) (((P Q) (P(Q P)));
f) ((A B) C) ;
g) (A B) (B C);
h) C ((A C) A) B.
2. С помощью таблиц истинности показать эквивалентность формул:
a) (A B) (A B);
b) (A B) (A B);
c) (A B) (A B);
d) (A (B C)) ((A B) (A C);
e) (A (B C)) ((A B) (A C)).
Доказать формулы обобщённого склеивания:
а)
;
b)
;
c)
;
d)
.
4. Доказать эквивалентность формул:
a)
(A
B)
(
B)
(
)
A
B;
b) (A B) (A C) (B D) (C D) (A D) (B C);
c) A (A C) (B C) (A B) (A C);
d) (A B) (B C) (C A) (A B) (B C) (C A);
e) (A B) (B C) (C D) (A C) (B C) (B D);
f) (A B C) (B C D) (C D A)
(A B) (A D) (B D) C;
g) (A B) ((A B) ( A B)) A B;
h) (
B
C)
(C
)
(B
C)
C
(A
B);
i) (A D) (C D) (A B) (C B) (A C) (D B);
j) A (C P) (A C) P.
5. Упростить формулы:
a) (A B) A B;
b)
(A
(A
B));
c) (A
)
(B
C);
d) A
(
(A
B));
e) (B A) (A B);
f)
(A
);
g)
;
h) (A B) (B C)) (C A);
i) (
B
C)
(A
C )
( A
B
)
(A
B
C).
6. Доказать тождественную истинность формул:
a) (P R) ((Q R) ((P Q) R));
b) (Q R) ((P Q) (P R));
c) (P Q) ((P (Q R)) (P R));
d) (P Q) ((Q R) (P R));
e) (P Q) ((P Q) P);
f) (Q P) ((Q P) Q).
7. Являются ли следующие формулы тождественно ложными:
а) ((A B) B) A; б) A (A B);
в) (A B) (A B); г) (A B) (A B);
д) (A B) ((B C) (A C)).
8. Построить формулу U такую, чтобы данная формула была тождественно истиной:
а) U Q) Q) U));
б) (((RQ U) U Q) R)).
9. Являются ли эквивалентными условия выхода в операторах цикла:
а) while (i<n)and(a[i]<>x)and(not marked[i]);
б) while not((i>=n)or(a[i]=x)or(marked[i]));
в) until not((i<n)or(a[i]<>x))or(marked[i]).
10. Упростить схемы:
а
)
b)
c
)
d
)
11. Составить релейно-контактные схемы для функций, считая, X Y ~ X Y :
а) (X Y) (Y Z); б) ((X Y) (Y Z))(X Z);
в) (X Y) (X (Y Z)); г) (X (Y Z)) (Y X).