Факультет Математики и Информатики ГрГУ: Логические формулы и фрагменты

Вход

Главная страница >> Учебный процесс >> Задачник >> Логические формулы и фрагменты

Логические формулы и фрагменты

Номер 1		К »
Задача 1. Построить синтаксический анализатор для определяемого в словаре понятия логическая-формула.


Номер 2		К »
Задача 2. Построить синтаксический анализатор для определяемого в словаре понятия дизъюнктивная-нормалъная-формула (ДНФ).


Номер 3		К »
Задача 3. Проверить, является ли заданная логическая формула правильной ДНФ.


Номер 4		К »
Задача 4. Проверить, является ли заданная ДНФ совершенной.


Номер 5		К »
Задача 5. Вычислить значение заданной логической формулы, не содержащей вхождений переменных.


Номер 6		К »
Задача 6. Вычислить значение заданной ДНФ для заданных значений встречающихся в ней переменных.


Номер 7		К »
Задача 7. Заданную ДНФ преобразовать в эквивалентную правильную ДНФ.


Номер 8		К »
Задача 8. Заданную ДНФ преобразовать в эквивалентную СДНФ.


Номер 9		К »
Задача 9. Заданную логическую формулу преобразовать в эквивалентную ДНФ.


Номер 10		К »
Задача 10. По заданной логической формуле построить эквивалентную логическую формулу, в которой знак отрицания встречается только перед переменными. Указание. Воспользоваться эквивалентными преобразованиями NOT NOT переменная? переменная NOT(формула-1} OR (формула-2) ? NOT(формула-1) AND NOT (форму ла2? NOT(конъюнкция-1 AND конъюнкция-2) ? NОТ(конъюнкция-1) OR NOT (конъюнкция-2)


Номер 11		К »
Задача 11. Реализовать упрощение логических формул относительно правил преобразования, заданных следующими схемами правил: TRUE OR формулам? TRUE TRUE AND конъюнкция? конъюнкция формула OR TRUE? TRUE конъюнкция AND TRUE? конъюнкция NOT FALSER? TRUE NOT TRUE? FALSE


Номер 12		К »
Задача 12. Реализовать упрощение логических формул отновительно правил преобразования, заданных следующими схемами правил: формула OR формула? формула конъюнкция AND конъюнкция? конъюнкция FALSE OR формула? формула формула OR FALSE? формула FALSE AND конъюнкциям? FALSE конъюнкция AND FALSE? FALSE


Номер 13		К »
Задача 13. Реализовать упрощение логических формул относительно правил преобразования, заданных следующими схемами правил: NOT NOT множитель? множитель конъюнкция-1 AND конъюнкция-2 OR конъюнкция-1? кочъюнкция-1 (конъюнкция OR формула)АND конъюнкция? конъюнкция


Номер 14		К »
Задача 14. Определить, эквивалентны ли две заданные логические формулы.


Номер 15		К »
Задача 15. Определить, эквивалентны ли две заданные правильные ДНФ.


Номер 16		К »
Задача 16. По заданной правильной ДНФ определить, представляет ли она тождественно истинную логическую формулу, т. е. верно ли, что она эквивалентна формуле TRUE.


Номер 17		К »
Задача 17. Определить, эквивалентна ли заданная логическая формула формуле FALSE.


Номер 18		К »
Задача 18. По заданной правильной ДНФ а построить правильную ДНФ логической формулы NОТ(a).


Номер 19		К »
Задача 19. Определить, содержит ли логическая формула a хотя бы одно вхождение логической формулы b .


Номер 20		К »
Задача 20. Две логические формулыa , b назовем похожими, если а) либо a =b ; б) либо a = NOT a ', b = NOT b ', где a ', b ' похожие; в) либо a =(a '), b =(b '), где a ', b ' похожие; г) либо a =a 1 op a 2, b =b 1 op b 2. где opI {OR,AND}, причем либо a 1, b 1 похожие и a 2, b 2 похожие, либо a 2, b 1 похожие и a 1, b 2 похожие. Все остальные пары a , b .непохожие. Определить, являются ли похожими две заданные логические формулы.


Номер 21		К »
Задача 21. Переменная х называется фиктивной в логической формуле а, если существует логическая формула b , эквивалентная a и не содержащая вхождений переменной х. По заданной логической формуле найти все встречающиеся в ней фиктивные переменные.


Номер 22		К »
Задача 22. По заданной логической формуле определить, сохраняет ли она свое значение при любой перестановке значений аргументов.


Номер 23		К »
Задача 23. По заданной логической формуле определить, верно ли, что на наборах противоположных значений аргументов она принимает противоположные значения, т. е. " х1,..., хn f { х1, ..., хn)=not f (NOT х1, NOT х2, .... NOT хn) (этим свойством обладает, например, логическая формула Х AND Y OR NOT Y AND X ).


Номер 24		К »
Задача 24. Пару скобок в логической формуле назовем избыточной, если после ее удаления формула остается эквивалентной исходной. Удалить все избыточные пары скобок в заданной логической формуле.


Номер 25		К »
Задача 25. Построить синтаксический анализатор для понятия расширенная-формула.


Номер 26		К »
Задача 26. По заданным расширенной формуле и набору значений встречающихся в ней переменных вычислить значение расширенной формулы.


Номер 27		К »
Задача 27. По заданной расширенной формуле построить эквивалентную логическую формулу. Указание. Воспользуйтесь следующими схемами правил преобразования: формула1R формула-2 ? NOT формула-1 OR формула-2 формула-1? формула-2 ? формула-1 AND формула-2 OR NOT формула-1 AND NOT формула-2


Номер 28		К »
Задача 28. По заданной расширенной формуле построить такую эквивалентную расширенную формулу, в которой знак отрицания NOT может стоять только перед переменными. Указание. Воспользуйтесь правилами преобразования: NOT (a R b )? a AND NOT b NOT (a ? b )? a AND NOT b OR NOT a AND b для произвольных расширенных логических формул a ,b .


Номер 29		К »
Задача 29. Определить, эквивалентны ли две заданные расширенные формулы.


Номер 30		К »
Задача 30. Определить, эквивалентны ли заданные ДНФ и расширенная формула.


Номер 31		К »
Задача 31. Определить, является ли пустым заданный логический фрагмент.


Номер 32		К »
Задача 32. Определить, является ли тотальным заданный логический фрагмент.


Номер 33		К »
Задача 33. Определить, является ли свободным заданный логический фрагмент.


Номер 34		К »
Задача 34. Заданный логический фрагмент преобразовать в эквивалентный свободный логический фрагмент.


Номер 35		К »
Задача 35. Тотальный логический фрагмент преобразовать в свободный логический фрагмент, к каждой вершине которого ведет не более одной дуги.


Номер 36		К »
Задача 36. Определить, эквивалентны ли два заданных логических фрагмента.


Номер 37		К »
Задача 37. Определить, эквивалентны ли заданные ДНФ и тотальный логический фрагмент.


Номер 38		К »
Задача 38. Определить, эквивалентны ли заданная логическая формула и тотальный логический фрагмент.


Номер 39		К »
Задача 39. По заданной логической формуле построить эквивалентный логический фрагмент.


Номер 40		К »
Задача 40. По заданной ДНФ построить эквивалентный логический фрагмент.


Номер 41		К »
Задача 41. По заданному тотальному логическому фрагменту построить эквивалентную логическую формулу.


Номер 42		К »
Задача 42. По заданному тотальному логическому фрагменту построить эквивалентную ДНФ.


Номер 43		К »
Задача 43. По заданному логическому фрагменту, к каждой вершине которого ведет не более одной дуги, построить эквивалентный свободный логический фрагмент.


Номер 44		К »
Задача 44. Пусть задан логический фрагмент Ф, в котором нет циклов. Пару вершин а, b в Ф назовем близнецами, если их пометки совпадают и (в случае, когда а и 6 - невисячие вершины, а а+, а- и b+, b- - вершины, к которым ведут плюс- и минус-стрелки от а к b соответственно) вершины а+, а-, а также b+ , b- - близнецы. Определить, есть ли в Ф хотя бы одна пара близнецов.


Номер 45		К »
Задача 45. В условиях предыдущей задачи по Ф построить эквивалентный логический фрагмент, в котором нет ни одной пары близнецов.


Номер 46		К »
Задача 46. Вершину а в логическом фрагменте Ф назовем несущественной, если существует вершина b, отличная от а, к которой ведут обе стрелки, выходящие из а. Если такую вершину удалить из Ф, направляя все стрелки, которые вели к ней в Ф, к вершине b, то получим новый логический фрагмент, эквивалентный исходному. Удалить все несущественные вершины заданного логического фрагмента.


Номер 47		К »
Задача 47. Логическая переменная x называется несущественной для логического фрагмента L, если существует логический фрагмент L', эквивалентный L и такой, что он не содержит вершин с условием х. По заданному логическому фрагменту определить, является ли переменная х существенной для него.


Номер 48		К »
Задача 48. Заданный логический фрагмент преобразовать в такой эквивалентный фрагмент, в котором имеется не более одной вершины, от которой нет ни одного пути к висячей зершине.


Номер 49		К »
Задача 49. Логический фрагмент назовем упорядоченным (по отношению к фиксированному порядку, заданному на множестве логических переменных X. == {X1, ...,Xn}), если на любом пути от начала к висячей вершине условие с меньшим номером всегда проверяется раньше условия с большим номером. По заданному свободному логическому фрагменту, к каждой вершине которого ведет не более одной стрелки, построить эквивалентный упорядоченный фрагмент.


Номер 50		К »
Задача 50. По заданному упорядоченному (см. условие предыдущей задачи) логическому фрагменту построить эквивалентный упорядоченный фрагмент с минимальным количеством вершин.


Номер 51		К »
Задача 51. Определить, эквивалентны ли заданная расширенная логическая формула и тотальный логический фрагмент.


Номер 52		К »
Задача 52. По заданной расширенной логической формуле построить эквивалентный тотальный логический фрагмент.

[Назад] [Содержание ] [Вперед]