Преобразуем эту формулу, используя соответствующие эквивалентности
U
.
И
зобразим
схему, соответствующую заключительной
формуле
B
A
Контрольные вопросы и задания
1. Построить таблицу истинности для формулы:
(P (Q P)) (P R);
(P (Q R)) ((P Q) (P R));
(P (Q P)) ((Q P) Q);
(С)С;
(P Q) (P(Q P));
((A B) C) ;
(A B) (B C);
(C ((A C) A)) B.
2. С помощью таблиц истинности показать эквивалентность формул:
A B (A) B;
(A B) (A) (B);
(A B) (A ) (B);
A (B C) ((A B) (A C);
A (B C) (A B) (A C).
Доказать формулы обобщённого склеивания:
;
;
;
.
4. Доказать эквивалентность формул:
(A B) (
B)
(
)
A
B;(A B) (A C) (B D) (C D) (A D) (B C);
A (A C) (B C) (A B) (A C);
(A B) (B C) (C A) (A B) (B C) (C A);
(A B) (B C) (C D) (A C) (B C) (B D);
(A B C) (B C D) (C D A)
(A B) (A D) (B D) C;
(A B) ((A B) ( A B)) A B;
( B C) (C ) (B C) C (A B);
(A D) (C D) (A B) (C B) (A C) (D B);
A (C P) (A C) P.
5. Упростить формулы:
(A
(A
B));(A
)
(B
C);
A (
(A
B));(B A) (A B);
(A
);
;(A B) (B C)) (C A);
( B C) (A C ) ( A B
)
(A
B
C).
6. Доказать тождественную истинность формул:
(P R) ((Q R) ((P Q) R));
(Q R) ((P Q) (P R));
(P Q) ((P (Q R)) (P R));
(P Q) ((Q R) (P R));
(P Q) ((P Q) P);
(Q P) ((Q P) Q).
7. Являются ли следующие формулы тождественно ложными:
((A B) B) A;
(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) && (a[i]<>x) && (! marked[i]));
while (!((i>=n) | | (a[i]=x) | | (marked[i]));
while (!(!(i<n) | | (a[i]<>x) && marked[i])).
10. Упростить схемы:
а
)
b
)
c
)
d
)