Математическая логика и теория алгоритмов
Контрольная работа включает решение типовых задач по математической логике и теории алгоритмов. Первое задание — доказать или опровергнуть утверждение о трёх непустых множествах, не имеющих друг с другом общих элементов: опровержение строится на конкретном примере с диаграммами Эйлера, где условия выполняются, а множество остаётся непустым. Второе задание требует установить истинностное значение высказывания при истинных формулах; доказательство проводится от противного с опорой на то, что импликация ложна только при истинной посылке и ложном следствии. Отдельные задания посвящены переводу высказываний естественного языка на язык логики предикатов: о сумме любого отличного от нуля числа с обратным к нему числом, которая больше 2, и о делимости целого числа на 8 при необходимой делимости на 4. В каждом случае выбирается универсальное множество (действительные и целые числа), вводятся предикаты и строится формула с квантором общности и импликацией. Далее анализируются свойства бинарного отношения «делится нацело на» на множестве положительных целых чисел — рефлексивность, симметричность, антисимметричность, транзитивность — с указанием, какие из них выполняются, а какие нет. Завершает работу задание расположить пять функций в порядке возрастания скорости роста.









