Варианты заданий
Преобразовать формулы к дизъюнктивной и конъюнктивной нормальным формам:
а) (((A B) (C A)) (B C));
б) (((((A B) A) B) C) C);
в) ((A (B C)) ((A C) (A B))).
2. По данному набору значений переменных построить элементарную конъюнкцию, истинную только для этого набора значений переменных.
3. По данному набору значений переменных построить элементарную дизъюнкцию, ложную только для этого набора значений переменных.
4. Привести к совершенной дизъюнктивной нормальной форме, то есть найти СДНФ, эквивалентную данной формуле:
а) (( С С;
б) (((А
в) .
5. Привести к совершенной конъюнктивной нормальной форме, то есть найти СКНФ, эквивалентную данной формуле:
а) С С;
б) )С)));
в) С)) С)).
6. Построить формулу U такую, чтобы данная формула была тождественно истиной:
а) U Q) Q) U));
б) (((RQ U) U Q) R)).
7. Для функций g и h, определённых в таблице 1, найти СКН - и СДН – формы и простейшие формулы, реализующие эти функции.
8. Составить две булевы функции, планирующие 1-разрядный двоичный сумматор по следующей таблице
|
x1 |
x2 |
e1 |
|
e2 |
|
1 1 0 1 1 0 0 0 |
1 0 1 1 0 1 0 0 |
1 1 1 0 0 0 0 1 |
1 0 0 0 1 1 0 1 |
1 1 1 1 0 0 0 0 |
где x1 и x2 - одноимённые разряды 1-го и 2-го слагаемых; e1 - единица переноса из младшего разряда; e2 – единица переноса в старший разряд суммы; - результат суммирования.
9. Построить формулу от трёх переменных, которая истинна в том и только в том случае, когда ровно две переменные ложны.
10. Построить формулу от трёх переменных, которая принимает такое же значение, как и большинство (меньшинство) переменных.
11. По СКНФ формулы U построить:
а) СДНФ двойственной формулы U*;
б) СКНФ формулы U;
в) СДНФ формулы U.
12. По СДНФ формулы U и СДНФ формулы B построить:
а) СКНФ и СДНФ формулы (U B);
б) СКНФ и СДНФ формулы (U B);
в) СКНФ и СДНФ формулы (U B).