nextupprevious

Next:6.4 Геометрия
Up:6 Формулировки заданий
Previous:6.2 Грамматики, языки и
 
 

6.3 Формулы и программы


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

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

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

4. Проверить, является ли заданная ДНФ совершенной (СДНФ).

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

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

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

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

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

10. По заданной логической формуле построить эквивалентную логическую формулу, в которой знак отрицания встречается только перед переменными.

У к а з а н и е. Воспользоваться эквивалентными преобразованиями

NOT NOT множитель   ==> множитель

NOT (множитель OR конъюнкция)   ==>  NOT множитель AND NOT конъюнкция

NOT(конъюнкция AND логическая-формула)  ==> NOT конъюнкция OR NOT логическая-формула
 

11. Реализовать упрощение логических формул относительно правил преобразования, заданных следующими схемами правил:

TRUE OR логическая-формула  ==> TRUE

TRUE AND конъюнкция  ==> конъюнкция

конъюнкция OR TRUE  ==> TRUE

множитель AND TRUE   ==>  множитель

NOT FALSE  ==> TRUE

NOT TRUE  ==> FALSE

12. Реализовать упрощение логических формул относительно правил преобразования, заданных следующими схемами правил:

конъюнкция OR конъюнкция  ==> конъюнкция

множитель AND множитель ==> множитель

FALSE OR логическая-формула  ==> логическая-формула

конъюнкция OR FALSE   ==> конъюнкция

FALSE AND конъюнкция  ==>  FALSE

множитель AND FALSE  ==> FALSE

13. Реализовать упрощение логических формул относительно правил преобразования, заданных следующими схемами правил:

NOT NOT множитель  ==> множитель

множитель AND конъюнкция OR множитель == >множитель

(конъюнкция OR логическая-формула) AND конъюнкция == > конъюнкция

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

15. Определить, эквивалентны ли две заданные правильные ДНФ.

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

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

18. По заданной правильной ДНФ $\alpha$ построить правильную ДНФ логической формулы NOT.

19. Определить, содержит ли логическая формула $\alpha$ хотя бы одно вхождение логической формулы $\beta$.

20. Две логические формулы $\alpha, \beta$ назовем похожими, если справедливо хотя бы одно из следующих условий:
1) $\alpha$ = $\beta$;
2) $\alpha$ = NOT$\alpha$' и $\beta$ = NOT $\beta$', где $\alpha$' и $\beta$ 'похожие;
3) $\alpha$ = ($\alpha$') и $\beta$ = ($\beta$'), где $\alpha$' и $\beta$' похожие;
4) $\alpha$ = $\alpha$' op$\alpha$'' и$\beta$ = $\beta$' op $\beta$'' где op -  это OR или AND, причем, либо $\alpha$',$\beta$' похожие и $\alpha$",$\beta$" похожие, либо $\alpha$',$\beta$" похожие и $\alpha$",$\beta$' похожие.
Все остальные пары $\alpha, \beta$ непохожие.
Определить, являются ли похожими две заданные логические формулы.

21. Переменная $x$ называется фиктивной в логической формуле $\alpha$, если существует логическая формула $\beta$, эквивалентная $\alpha$ и не содержащая вхождений переменной $x$. По заданной логической формуле найти все встречающиеся в ней фиктивные переменные.

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

23. По заданной логической формуле определить, верно ли, что на наборах противоположных значений аргументов она принимает противоположные значения, т.е. для любых  x,y, ...,z

f(x, y, ..., z) = NOT f (NOT x, NOT y, ... , NOT z)

(этим свойством обладает, например, логическая формула X AND Y OR NOT Y AND X).

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

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

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

27. По заданной расширенной формуле построить эквивалентную логическую формулу.

У к а з а н и е. Воспользуйтесь следующими схемами правил преобразования:

$\alpha$ -> $\beta$   ==>  NOT $\alpha$ OR $\beta$
$\alpha$<-> $\beta$ ==> $\alpha$ AND $\beta$ OR NOT $\alpha$ AND NOT $\beta$
для произвольной логической формулы $\alpha$ и расширенной логической формулы $\beta$.

28. По заданной расширенной формуле построить такую эквивалентную расширенную формулу, в которой знак отрицания NOT может стоять только перед переменными.

У к а з а н и е. Воспользуйтесь правилами преобразования:

NOT ( $\alpha$-> $\beta$ ) ==>$\alpha$ AND NOT $\beta$
NOT ($\alpha$ <-> $\beta$ ) ==> $\alpha$ AND NOT $\beta$ OR NOT $\alpha$ AND $\beta$
для произвольной логической формулы $\alpha$ и расширенной логической формулы $\beta$.

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

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

31. $\uparrow$ Определить, является ли пустым заданный логический фрагмент.

32. $\uparrow$ Определить, является ли тотальным заданный логический фрагмент.

33. $\uparrow$ Определить, является ли свободным заданный логический фрагмент.

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

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

36. $\uparrow$ Определить, эквивалентны ли два заданных логических фрагмента.

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

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

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

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

41. $\uparrow$ По заданному тотальному логическому фрагменту построить эквивалентную логическую формулу.

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

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

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

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

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

47. $\uparrow$ Логическая переменная $x$ называется несущественной для логического фрагмента L, если существует логический фрагмент , эквивалентный $L$ и такой, что он не содержит вершин с условием $x$. По заданному логическому фрагменту определить, является ли переменная $x$ несущественной для него.

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

49. $\uparrow$ Логический фрагмент назовем упорядоченным (по отношению к фиксированному порядку, заданному на множестве логических переменных), если на любом пути от начала к висячей вершине условие с меньшим номером всегда проверяется раньше условия с большим номером. По заданному свободному логическому фрагменту, к каждой вершине которого ведет не более одной стрелки, построить эквивалентный упорядоченный фрагмент.

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

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

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

53. Построить синтаксический анализатор для понятия описание-переменных, которое использует обычное понятие идентификатора и определяется следующим образом:

описание-переменных::= VAR пробел список-описаний пробелы

пробелы ::= пробел {пробел}*

список-описаний ::=  описание |  описание;  список-описаний

описание::= список-идентификаторов : идентификатор

список-идентификаторов ::=  идентификатор {пробелы идентификатор}* пробелы

54. Построить синтаксический анализатор для понятия переменная, которое определяется следующим образом:

переменная ::= идентификатор {|  | .идентификатор | [список выражений]}

список-выражений ::=  выражение {выражение}*

выражение::= простое-выражение

Определение понятия простое-выражение см. в словаре (§2).

55. $\downarrow$ Построить синтаксический анализатор для определяемого в словаре понятия линейная-программа.

56. Построить синтаксический анализатор для определяемого в словаре понятия простая-программа.

57. $\downarrow$ Построить синтаксический анализатор для определяемого в словаре понятия простое-выражение.

58. По заданному простому выражению, не содержащему вхождений идентификаторов, вычислить его значение.
 

59. Внешнее представление вещественных чисел определим следующим образом:

вещественное  ::= { знак | пусто } мантисса порядок

мантисса ::= {цифра}* цифра . {цифра}* цифра

порядок ::= { E знак цифра цифра | E  знак цифра |  пусто}

пусто ::=

знак ::=  + | -

Построить произведение двух заданных в таком представлении вещественных чисел, предполагая, что сумма длин их записи не превосходит 100.

60. Вычислить с округлением, оставляя в мантиссе результата не более 10 знаков после десятичной точки, частное от деления двух вещественных чисел, заданных в описанном в предыдущем задании представлении (предполагая снова, что сумма длин записи исходных чисел не превосходит 100).

61. Задана последовательность вещественных чисел в описанном в задании 59 представлении. Числа последовательности перечисляются через запятую, общая длина последовательности ограничена 100 символами. Вычислить сумму этой последовательности чисел.

62. Задана обратная польская запись некоторого простого выражения, не содержащего вхождений идентификаторов. Вычислить значение этого выражения.

63. Задана прямая польская запись некоторого простого выражения, не содержащего вхождений идентификаторов. Вычислить значение этого выражения.

64. Выполнить заданную линейную программу для заданных начальных значений всех встречающихся в ней переменных. Определить значения этих переменных после выполнения линейной программы (если не возникнет ошибки переполнения).

65. $\downarrow$ В заданной линейной программе удалить первый оператор каждой пары следующих друг за другом операторов в случае, если их левые части совпадают, а правая часть второго оператора не содержит вхождений переменной, совпадающей с его левой частью.

66. Вхождение оператора $A$ линейной программы назовем избыточным, если среди предшествующих ему имеется еще одно вхождение этого оператора, причем левые части всех операторов, находящихся между двумя этими вхождениями, а также левая часть самого оператора $A$ не встречаются в правой части оператора $A$. Например, второе вхождение оператора

x := y+z

в линейной программе

x:=y+z; u:=u-z; x:=y+z

избыточно.

В заданной линейной программе удалить все избыточные вхождения операторов.

67. $\downarrow$ Вхождение оператора $A$ в линейную программу называется несущественным, если среди следующих после него операторов имеется еще одно вхождение оператора, скажем $B$, с той же переменной-левой частью, что и у $A$, причем эта переменная не встречается в правой части ни одного из операторов, находящихся между $A$ и $B$. Например, вхождение оператора

x:=u+v

в линейную программу

x:=u+v; u:=u*y; x:=y-v

несущественное.

Удалить вхождения всех несущественных операторов из заданной линейной программы, содержащей не более 200 вхождений операторов.
 

68. Преобразовать в обратную польскую запись заданное простое выражение.

69. $\downarrow$ Преобразовать в прямую польскую запись заданное простое выражение.

70. $\downarrow$ Восстановить простое выражение по заданной его обратной польской записи.

71. $\downarrow$ Восстановить простое выражение по заданной его прямой польской записи.

72. По заданному простому выражению построить линейную программу, которая вычисляет и засылает в переменную RESULT значение этого выражения.

73. По заданной линейной программе, в которой последний оператор содержит в левой части переменную RESULT, построить простое выражение, значение которого совпадает с тем значением, которое получает переменная RESULT после исполнения линейной программы.

74. Проверить правдоподобность заданной простой программы.

75. По заданной правдоподобной простой программе без операторов ввода определить, что будет напечатано при выполнении этой программы (если не возникает ошибки переполнения).

76. Упростить заданную правдоподобную простую программу, заменяя всякий оператор вида

IF константа-1 знак-отношения константа-2 THEN оператор

на оператор в случае истинности условия или удаляя этот условный оператор в случае ложности условия.

77. Из-за недосмотра программиста был утерян раздел описаний переменных правдоподобной простой программы. Восстановить его.

78. $\downarrow$ Построить синтаксический анализатор для определяемого в словаре понятия полином.

79. Проверить, является ли приведенным заданный полином.

80. $\downarrow$ По заданному полиному и (целым) значениям всех входящих в него переменных вычислить значение полинома.

81. Заданный полином преобразовать в приведенный.

82. По двум заданным приведенным полиномам построить третий полином, который является произведением двух исходных.

3. $\downarrow$ По заданному приведенному полиному построить другой приведенный полином, который является производной исходного по заданной переменной.

84. Заданное простое выражение преобразовать в полином. Если этого нельзя сделать, как, например, в случае простого выражения x*x*...*x (20 раз множитель $x$), то программа должна печатать сообщение об этом.

85. По двум заданным приведенным полиномам построить третий приведенный полином -- сумму исходных полиномов.

86. $\downarrow$ По двум заданным приведенным полиномам от одной переменной определить, делится ли первый полином на второй без остатка.

87. $\downarrow$ По заданному полиному определить его однородность, т.е. проверить, верно ли, что сумма показателей степеней переменных одинакова во всех одночленах полинома.
 

88. $\downarrow$ Определить, является ли полиномом в смысле данного в словаре определения (т.е. все его коэффициенты -- целые, а степень не превосходит 19) интеграл по заданной переменной от заданного приведенного полинома.

89. Задан приведенный полином $P$ от трех переменных . Определить, существует ли у определения P=0 хотя бы одно такое решение x, y, z в целых числах, что x<51, y<51  и z<51.

90. Задан приведенный полином $P$ от не более чем пяти переменных. Найти все целочисленные решения уравнения , при которых значение всякой переменной по модулю не превышает числа 3.

91. Степенью одночлена приведенного полинома называют сумму показателей встречающихся в нем переменных. Переставляя одночлены заданного приведенного полинома, добиться, чтобы они были упорядочены в соответствии с ростом их степеней.

92. $\downarrow$ Построить на экране ту часть целочисленного графика заданного полинома от одной переменной  f(x), которая лежит в квадрате 0<x<100, 0<f(x)<100.

 93. $\downarrow$Построить синтаксический анализатор для определяемого в словаре понятия формулировка-задачи.

94. Проверить, является ли корректной заданная формулировка задачи.

 95. Построить ответ на заданную корректную формулировку задачи.

96. Проверить, можно ли так переставить определения в заданной формулировке задачи, чтобы она стала корректной.

97. Слово, встречающееся в правой части одного (или нескольких) определений заданной корректной формулировки задачи, назовем исходным, если оно не встречается в левых частях определений. Найти все исходные слова заданной корректной формулировки задачи.

98. Определить, являются ли эквивалентными две заданные корректные формулировки задач.

99. Для заданной корректной формулировки задачи построить эквивалентную корректную формулировку задачи с минимальным числом определений.

100. Заданы две формулировки задач. Проверить, можно ли так переставить определения внутри каждой из формулировок, чтобы они стали корректными эквивалентными формулировками задач.
 

Next:6.4 Геометрия
Up:6 Формулировки заданий
Previous:6.2 Грамматики, языки и

© В.Н. Касьянов, Е.В.Касьянова,2004