Программный способ записи алгоритмов

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

Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на "понятном" ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем.

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.

Контрольные вопросы

1. Формы записей алгоритма
2. Словесный способ записи алгоритма
3. Графический способ записи алгоритма
4. Псевдокод
5. Программный способ записи алгоритма

Логические основы алгоритмизации

Тема 2.1 Основы алгебры логики

Логические операции с высказываниями: конъюнкция, дизъюнкция, инверсия. Законы логических операций. Таблицы истинности.

В результате изучения данной темы студент должен:

знать:

- операцию отрицания, таблицу истинности, условную схему;

- операцию логического сложения, таблицу истинности, условную схему;

- операцию логического умножения, таблицу истинности, условную схему;

- понятие импликации, таблицу истинности;

- понятие эквивалентности, таблицу истинности.

уметь:

- строить таблицы истинности для основных логических операций;

Определение. Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Определение. Логическое высказывание — это любое повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истинно oнo или лoжнo.

Пример

предложение “6 — четное число” следует считать высказыванием, так как оно истинное. Предложение “Рим — столица Франции” тоже высказывание, так как оно ложное.

Работу логических элементов описывают с помощью таблиц истинности.

Определение. Таблица истинности это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

1. Одноместная операция (отрицание)

Определение. Операция, выражаемая словом “не”, называется отрицанием и обозначается чертой над высказыванием (или знаком ù ). Высказывание истинно, когда A ложно, и ложно, когда A истинно.

Пример. “Луна — спутник Земли” (А); “Луна — не спутник Земли” ( ).

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение инвертора — на рисунке 5.1, а таблица истинности — в табл. 5.1а.

Рис. 5.1

Рассмотрим таблицу значений

Рис 5.1.а

1. Логическое сложение

Определение.Операция, выражаемая связкой “или” (в неразделительном, неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Например, высказывание

“10 не делится на 2 или 5 не больше 3”

ложно, а высказывания

“10 делится на 2 или 5 больше 3”,
“10 делится на 2 или 5 не больше 3”,
“10 не делится на 2 или 5 больше 3”

истинны.

Условное обозначение схемы ИЛИ представлено на схеме. Знак “1” на схеме — от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y").