Булева алгебра. Основные операции и правила булевой алгебры

Булевой или двоичной называют переменную величину хÎ{0,1}. Булевы переменные х₁, х₂,… являются аргументами булевых или переключательных функций, значения которых тоже принадлежат множеству {0,1}. В Паскале булевы переменные принимают значение true (истина) и false (ложь), при этом выполняется отношение true > false.

Общий вид булевой функции:

.

Для нас наибольший интерес будут представлять конъюнкция (логическое «И»), дизъюнкция (логическое «ИЛИ») и инверсия (логическое «НЕ»). Они будут широко использоваться при программировании логических выражений, определяющих ветвления в программах.

x1	x2	x1 xor x2
false	false	false
false	true	true
true	false	true
true	true	false

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

x1	x2	x1 and x2
false	false	false
false	true	false
true	false	false
true	true	true

x1	x2	x1 or x2
false	false	false
false	true	true
true	false	true
true	true	true

Раздел №7 (2 часа)

Алгоритмизация и программирование

План:

• Понятие алгоритма

• Основные условные элементы для создания схем алгоритмов

• Примеры простейших алгоритмов

Алгоритмизация и программирование

Понятие алгоритма

Понятие алгоритма является одним из главных понятий информатики. Само слово происходит от имени средневекового математика аль-Хорезм, (в некоторых источниках его полное имя приводится как Мухаммед аль-Хорезми, в других – Абу Джафар ибн Муса аль-Хорезми, в СЭС – Мухаммед бен Муса аль-Хорезми). Искаженное «аль-Хорезми», означающее буквально «из Хорезма» (Хорезм – название древнего государства на территории современного Узбекистана) и породило слово «алгоритм».

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

Пример: представим в виде алгоритма метод Евклида для нахождения наибольшего общего делителя пары натуральных чисел :

1. {Нахождение остатка}

2. {Замена}

3. {Остановка?} Если , то переход к п.1

4. {Остановка процесса} – искомое число.

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

Алгоритмический процесс это процесс последовательного преобразования конструктивных объектов, происходящий дискретными шагами. Каждый шаг состоит в смене одного конструктивного объекта другим.

Использование термина «конструктивный объект» в последнем определении связано с тем, что алгоритмы могут применяться к различным объектам – числам, буквам, словам, словосочетаниям, графам, логическим выражениям и т.п. Здесь этот термин используется как обобщающее понятие.

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

.

Обычно для каждого алгоритма можно выделить семь независимых параметров:

1) совокупность возможных исходных данных

2) совокупность возможных промежуточных результатов

3) совокупность результатов

4) правило начала

5) правило непосредственной переработки

6) правило окончания

7) правило извлечения результата