Высказывание (суждение) - это повествовательное предложение, в котором что-либо утверждается или отрицается. По поводу любого высказывания можно сказать истинно оно или ложно.
Логические величины: понятия, выражаемые словами: ИСТИНА (true), ЛОЖЬ (false).
Логическая константа: ИСТИНА (true), ЛОЖЬ (false).
Логическая переменная: символически обозначенная логическая величина. Следовательно, если известно, что А, В, Х, У и пр. - логические величины, то это значит, что они могут принимать значения только ИСТИНА или ЛОЖЬ.
Логическое выражение: простое или сложное высказывание. Сложные высказывания строятся из простых с помощью логических операций (связок).
Логические операции
Конъюнкция (логическое умножение). В русском языке выражается союзом И.
В математической логике используются знаки & Конъюнкция - двухместная операция, записывается в виде А^В (А, В - операнды). Значение такого выражение будет ЛОЖЬ, если хотя бы значение одного из операндов ложно.
Дизъюнкция (логическое сложение). В русском языке выражается союзом ИЛИ.
В математической логике используются знаки Дизъюнкция - двухместная операция, записывается в виде АВ. Значение такого выражение будет ИСТИНА, если хотя бы значение одного из операндов истинно.
Отрицание. В русском языке выражается союзом НЕ (в некоторых высказываниях применяется оборот - неверно, что…).
В математической логике используются знаки Отрицание - одноместная (унарная) операция, записывается в виде А или.
Логическая формула (логическое выражение) - формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА или ЛОЖЬ. В логических формулах часто ИСТИНА представляется как 1, ЛОЖЬ как 0.
Правила выполнения логических операций отражены в таблице истинности.
Таблица истинности
Последовательность выполнения логических операций в логических формулах определяется старшинством операций. Самая старшая операция - отрицание (она выполняется раньше других), затем идет - конъюнкция (и), а затем дизъюнкция (или).
Логические схемы
Удобным способом представления логических выражений являются логические схемы. Вот как изображаются на таких схемах три основные логические операции.
В этой таблице использованы следующие обозначения:
1 - истина, 0 - ложь, и, или, не - логические операции.
Пример1: Нарисуйте схему для логического выражения 1 или 0 и 1. Затем вычислите значение логического выражения.
Решение: Схема - Вычисление:
Пример2: Дана логическая схема. Постройте логическое выражение. Затем вычислите значение логического выражения.
Решение: Дана схема -
Составим формулу - (1 или 0) и 1. Вычислим значение по схеме 1 или 0 = 1,
затем 1 и 1 = 1. Значит (1 или 0) и 1 = 1.
Логическая информация и основы логики
Прямое отношение к программированию имеет дисциплина, которая называется математической логикой. Основу математической логики составляет алгебра логики, или исчисление высказываний. Под высказыванием понимается любое утверждение, в отношении которого можно однозначно сказать, истинно оно или ложно. Например, «Луна - спутник Земли» - истинно; «5 > 3» - истинно; «Москва - столица Китая» - ложно; «1 = 0» - ложно. Истина или ложь являются логическими величинами. Логические значения приведенных выше высказываний однозначно определены; другими словами, их значения являются логическими константами.
Логическое значение неравенства х < 0, где х - переменная, является переменной величиной. В зависимости от значения х оно может быть либо истиной, либо ложью. В связи с этим возникает понятие логической переменной.
Основы формального аппарата математической логики создал в середине XIX в. английский математик Джордж Буль. В его честь исчисление высказываний называют булевой алгеброй, а логические величины - булевскими.
Одиночные высказывания могут быть объединены в составные логические формулы с помощью логических операций.
Имеются три основные логические операции: отрицание, конъюнкция (логическое умножение) и дизъюнкция (логическое сложение).
Операция отрицания обозначается в математической логике значком ¬ и читается как частица не. Это одноместная операция.
Например, ¬ (x = у) читается «не (х равно y)». В результате получится истина, если х не равно у, и ложь, если х равно у. Отрицание изменяет значение логической величины на противоположное.
Операция конъюнкции обозначается значком & и читается как частица и. Это двухместная операция. Например, (х > 0) & (х < 1) читается «х больше 0 и х меньше 1». Данная логическая формула примет значение истина, если х
(0,1), и ложь - в противном случае. Следовательно, результат конъюнкции - истина, если истинны оба операнда. Знак операции дизъюнкции v читается как частица или. Например, (х = 0) v (х = 1) читается «х равно 0 или х равно 1». Формула дает истину, если х - двоичная цифра (0 или 1). Следовательно, дизъюнкция дает в результате истину, если хотя бы один операнд - истина.
В Паскале логические значения обозначаются служебными словами false (ложь) и true (истина), а идентификатор логического типа - boolean.
Кроме величин (констант и переменных) типа boolean логические значения false, true принимают результаты операций отношения.
Операции отношения (рис. 18) осуществляют сравнение двух операндов и определяют, истинно или ложно соответствующее отношение между ними.
Примеры записи отношений: х<у; a+b>=c/d; abs(m-n)<=l. Примеры вычисления значений отношений:
Логические операции выполняются над операндами булева типа. Имеются четыре логические операции: Not - отрицание; And - логическое умножение (конъюнкция); Or - логическое сложение (дизъюнкция). Кроме этих трех обязательных операций в Турбо Паскале имеется еще операция - исключающее ИЛИ. Ее знак - служебное слово Хоr. Это двухместная операция, которая в результате дает значение истина, если оба операнда имеют разные логические значения.
Операции перечислены в порядке убывания приоритетов. Результаты логических операций для различных значений операндов приведены в табл. 3.5.
Таблица 3.5
Операции отношения имеют самый низкий приоритет. Поэтому если операндами логической операции являются отношения, то их следует заключать в круглые скобки. Например, математическому неравенству 1 ≤ х ≤ 50 соответствует следующее логическое выражение:
(1<=X) And (X<=50)
Логическое выражение есть логическая формула, записанная на языке программирования. Логическое выражение состоит из логических операндов, связанных логическими операциями и круглыми скобками. Результатом вычисления логического выражения является булева величина (false или true). Логическими операндами могут быть логические константы, переменные, функции, операции отношения. Один отдельный логический операнд является простейшей формой логического выражения.
Примеры логических выражений (здесь d, b, с - логические переменные; х, у - вещественные переменные; k - целая переменная):
Если d=true; b=false; c=true; x=3.0; y=0.5; k=5, то результаты вычисления будут следующими:
В примере использована логическая функция odd(k). Это функция от целого аргумента k, которая принимает значение true, если значение k нечетное, и false, если k четное.
Логический оператор присваивания имеет структуру, представленную на рис. 19.
Примеры логических операторов присваивания:
2) b:=(x>y) and (k<>0);
3) c:=d or b and not (odd(k) and d).
Программирование ветвлений на Паскале
Основные темы параграфа:
♦ оператор ветвления на Паскале;
♦ программирование полного и неполного ветвления;
♦ программирование вложенных ветвлений;
♦ логические операции;
♦ сложные логические выражения.
Оператор ветвления на Паскале
В языке Паскаль имеется оператор ветвления. Другое его название - условный оператор, Формат полного оператора ветвления следующий:
if <логическое выражение> then <оператор1>
else <оператор2>
Здесь if - «если», then - «то», else - «иначе».
Программирование полного и неполного ветвления
Сравните запись алгоритма БИД1 из предыдущего параграфа с соответствующей программой.
Очень похоже на перевод с русского языка на английский. Обратите внимание на следующее отличие: в программе нет специального служебного слова, обозначающего конец ветвления. Здесь признаком конца оператора ветвления является точка с запятой. (Разумеется, оставлять в программе пустую строку совсем не обязательно. Здесь это сделано только ради наглядности.)
Простой формой логического выражения является операция отношения. Как и в АЯ, в Паскале допускаются все виды отношений (ниже указаны их знаки):
< (меньше); >= (больше или равно);
> (больше); = (равно);
<= (меньше или равно); <> (не равно).
А теперь запрограммируем на Паскале алгоритм БИД2, в котором использовано неполное ветвление.
Опять все очень похоже. Ветвь else в операторе ветвления может отсутствовать.
Программирование вложенных ветвлений
Запишем на Паскале программу определения большего из трех чисел, Блок-схема которая показана на рис. 6.6. Структура этого алгоритма - вложенные ветвления. Алгоритм на АЯ (БИТ2) приведен в предыдущем параграфе.
Обратите внимание на то, что перед else точка с запятой не ставится. Вся ветвящаяся часть структуры алгоритма заканчивается на точке с запятой после оператора D:=C.
Составим программу упорядочения значений двух переменных.
Этот пример иллюстрирует следующее правило Паскаля: если на какой-то из ветвей оператора ветвления находится несколько последовательных операторов, то их нужно записывать между служебными словами begin и end. Конструкция такого вида:
begin <последовательность операторов> end
называется составным оператором. Следовательно, в описанной выше общей форме ветвления <оператор1> и <оператор2> могут быть простыми (один) и составными операторами.
Логические операции
Наконец, составим еще один, третий вариант программы определения большего числа из трех.
Нетрудно понять смысл этой программы. Здесь использованы три последовательных неполных ветвления. А условия ветвлений представляют собой сложные логические выражения, включающие логическую операцию and (И). С логическими операциями вы встречались, работая с базами данных и с электронными таблицами.
Напомним, что операция and называется логическим умножением или конъюнкцией. Ее результат - «истина», если значения обоих операндов - «истина». Очевидно, что если А> В и А > С, то А имеет наибольшее значение и т. д. В Паскале присутствуют все три основные логические операции:
and - И (конъюнкция),
or - ИЛИ (дизъюнкция),
not - НЕ (отрицание).
Сложные логические выражения
Обратите внимание на то, что отношения, связываемые логическими операциями, заключаются в скобки. Так надо делать всегда! Например, требуется определить, есть ли среди чисел А, В, С хотя бы одно отрицательное. Эту задачу решает следующий оператор ветвления:
if (A<0) or (B<0) or (C<0)
then write ("YES") else write ("NO");
Выражение, истинное для отрицательного числа, может быть записано еще и так:
Коротко о главном
Оператор ветвления (условный оператор) Паскаля имеет вид:
if <логическое выражение>
then <оператор1> else <оператор2>
На ветвях условного оператора могут находиться простые или составные операторы. Составной оператор - это последовательность операторов, заключенная между служебными словами begin и end.
В сложных логических выражениях используются логические операции: and, or, not.
Вопросы и задания
1. Как программируется на Паскале полное и неполное ветвление?
2. Что такое составной оператор? В каких случаях составной оператор используется в операторе ветвления?
3. Выполните на компьютере все программы, приведенные в данном параграфе.
4. Составьте не менее трех вариантов программы определения наименьшего из трех данных чисел.
5. Составьте программу сортировки по возрастанию значений в трех переменных: А, В, С.
6. Составьте программу вычисления корней квадратного уравнения по данным значениям его коэффициентов.
Высказывание (суждение) - это повествовательное предложение, в котором что-либо утверждается или отрицается. По поводу любого высказывания можно сказать, истинно оно или ложно. Например:
«Лед - твердое состояние воды» - истинное высказывание.
«Треугольник, это геометрическая фигура» - истинное высказывание.
«Париж - столица Китая» - ложное высказывание.
6 < 5 - ложное высказывание.
Логические величины: понятия, выражаемые словами: ИСТИНА, ЛОЖЬ (true, false). Следовательно, истинность высказываний выражается через логические величины.
Логическая константа: ИСТИНА или ЛОЖЬ.
Логическая переменная: символически обозначенная логическая величина. Следовательно, если известно, что А, В, X, Y и пр. - переменные логические величины, то это значит, что они могут принимать значения только ИСТИНА или ЛОЖЬ.
Логическое выражение - простое или сложное высказывание. Сложное высказывание строится из простых с помощью логических операций (связок).
Логические операции. В математической логике определены пять основных логических операций: конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность. Первые три из них составляют полную систему операций, вследствие чего остальные операции могут быть выражены через них (нормализованы). В информатике обычно используются эти три операции.
Конъюнкция (логическое умножение). В русском языке она выражается союзом И. В математической логике используются знаки & или . Конъюнкция - двухместная операция; записывается в виде: А В. Значение такого выражения будет ЛОЖЬ, если значение хотя бы одного из операндов ложно.
Дизъюнкция (логическое сложение). В русском языке этой связке соответствуют союз ИЛИ. В математической логике она обозначается знаком v. Дизъюнкция - двухместная операция; записывается в виде: A v В. Значение такого выражения будет ИСТИНА если значение хотя бы одного из операндов истинно.
Отрицание. В русском языке этой связке соответствует частица НЕ (в некоторых высказываниях применяется оборот «неверно что...»). Отрицание - унарная (одноместная) операция; записывается в виде: А или .
Логическая формула (логическое выражение) - формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА или ЛОЖЬ.
Пример 1. Рассмотрим сложное высказывание: «Число 6 делится на 2, и число 6 делится на 3». Представить данное высказывание в виде логической формулы. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Toгда соответствующая логическая формула имеет вид: А & В. Очевидно, ее значение - ИСТИНА. Пример 2. Рассмотрим сложное высказывание: «Летом я поеду в деревню или в туристическую поездку».
Обозначим через А простое высказывание «летом я поеду Я деревню», а через В - простое высказывание «летом я поеду в туристическую поездку». Тогда логическая форма сложного высказывания имеет вид
Пример 3. Рассмотрим высказывание: «Неверно, что 4 делится на 3».
Обозначим через А простое высказывание «4 делится на 3». Тогда логическая форма отрицания этого высказывания имеет вид А
Правила выполнения логических операций отражены в следующей таблице, которая называется таблицей истинности.
Последовательность выполнения операций в логических формулах определяется старшинством операций. В порядке убывания старшинства логические операции расположены так: отрицания, конъюнкция, дизъюнкция. Кроме того, на порядок операции влияют скобки, которые можно использовать в логических формулах.
Приложения математической логики в базовом курсе
Математическая логика в базах данных. При изучении базового курса информатики ученики впервые встречаются с элементами математической логики в теме «Базы данных» (БД). В реляционных БД логическими величинами являются поля логического типа. Логический тип используется наряду с другими типами полей, и ученики должны научиться выделять его.
Первое понятие о логической величине можно дать как ответ на альтернативный вопрос. Например: «Имеется ли данная книга в библиотеке?» или «Поступил ли абитуриент в университет», или «На улице идет дождь?» и т.п. Ответами на такие вопросы могут быть только «да» или «нет». Синонимами являются «истина», «ложь»; «true», «false». Если поле таблицы будет принимать только такие значения, то ему назначается логический тип.
Например, реляционная база данных ФАКУЛЬТАТИВЫ содержит сведения о посещении учениками трех факультативов по геологии, цветоводству и танцам. На реляционном языке ее структура описывается так:
ФАКУЛЬТАТИВЫ (УЧЕНИК . ГЕОЛОГИЯ, ЦВЕТОВОДСТВО, ТАНЦЫ)
Поля ГЕОЛОГИЯ, ЦВЕТОВОДСТВО и ТАНЦЫ будут иметь логический тип. Значение ИСТИНА для каждого поля обозначает, что ученик посещает данный факультатив, а ЛОЖЬ - не посещает.
Логические выражения используются в запросах к базе данных в качестве условий поиска. Логические выражения разделяются на простые и сложные. В простых выражениях всегда используется лишь одно поле таблицы, и не применяются логические операции. В сложных логических выражениях используются логические операции. Простое логическое выражение представляет собой либо имя поля логического типа, либо отношение (в математике говорят «неравенство»). Отношения для числовых величин сохраняют смысл математических неравенств; при вычислении отношений для символьных величин учитывается лексикографический порядок; даты сравниваются в порядке их календарной последовательности.
Основная проблема - научить учеников формальному представлению условий поиска в виде логических выражений. Например, от фразы «найти все книги, лежащие выше пятой полки» нужно перейти к логическому выражению: ПОЛКА > 5; или условие «выбрать всех неуспевающих по физике» представить в виде: ФИЗИКА < 3; или «выбрать все дни, когда шел дождь» ОСАДКИ = «дождь».
Особое внимание надо обратить на использование полей логического типа в условиях поиска. Обычно к ним не применяются отношения. Логическое поле само несет логическое значение: «истина» или «ложь». Например, условие «выбрать всех учеников, посещающих танцы» представится одним именем логического поля ТАНЦЫ.
Сложные логические выражения содержат в себе логические операции. Рассматриваются три основные операции математической логики: конъюнкция (И), дизъюнкция (ИЛИ), отрицание (НЕ).
Обычно при объяснении этого вопроса учитель отталкивается от семантического смысла высказываний на русском языке, содержащих союзы И, ИЛИ, частицу НЕ. Например, высказывание: «Сегодня будет контрольная по алгебре И по физике» справедливо, если состоятся обе контрольные и ложно, если хотя бы одна не состоится. Другое высказывание: «Сегодня будет контрольная по алгебре ИЛИ по физике» будет истинным, если состоится хотя бы одна контрольная работа. И, наконец, высказывание: «Сегодня НЕ будет контрольной» истинно, если контрольная не состоится, т. е. если высказывание о том, что сегодня будет контрольная, оказывается ложным. Из подобных примеров учитель делает выводы о правилах выполнения логических операций: если А и В - логические величины, то выражение
А и В истинно только в том случае, если истинны оба операнда;
А или В ложно только в том случае, если ложны оба операнда;
Не А меняет значение логической величины на противоположное: не истина - ложь; не ложь - истина.
1. Логические величины, операции, выражения. Логические выражения в качестве условий в ветвящихся и циклических алгоритмах.
Для того чтобы понять работу ветвящихся и циклических алгоритмов, рассмотрим понятие логического выражения.
В некоторых случаях выбор варианта действий в программе должен зависеть от того, как соотносятся между собой значения каких-то переменных.
Например, расчёт корней квадратного уравнения производится по-разному в зависимости от дискриминанта (вспомните математику).
В результате сравнения значений двух выражений возможны два варианта ответа: сравнение истинно или ложно ?
Например:
2+3 > 3+1 - да (истинно)
0 < -5 - нет (ложно)
Выражения такого вида мы будем называть логическими выражениями .
Логическое выражение, подобно математическому выражению, выполняется (вычисляется), но в результате получается не число, а логическое значение: истина (true) или ложь (false). Логическая величина - это всегда ответ на вопрос, истинно ли данное высказывание.
Нам известны шесть операций сравнения:
С помощью этих операций мы будем составлять логические выражения. Причём в выражениях не обязательно присутствуют только константы, но и переменные.
Как выполняются операции отношения для числовых величин понятно из математики. Как же сравниваются символьные величины? Отношение «равно» истинно для двух символьных величин, если их длинны одинаковы и все соответствующие символы совпадают. Следует учитывать, что пробел тоже символ.
Символьные величины можно сопоставлять и в отношениях >, <, >=, <=. Здесь упорядоченность слов (последовательности символов) определяется по алфавитному принципу.
«кот» = «кот»
«кот» < «лис»
«кот» > «дом»
Выражение, состоящее из одной логической величины или одного отношения, будем называть простым логическим выражением.
Часто встречаются задачи, в которых используются не отдельные условия, а совокупность связанных между собой условий (отношений). Например, в магазине вам нужно выбрать туфли, размер которых r = 45, цвет color = белый, цена price не более 400руб.
Другой пример: школьник выяснил, что сможет купить шоколадку, если она стоит 3руб. или 3руб. 50коп.
В первом примере мы имеем дело с тремя отношениями, связанными между собой союзом "и" и частицей "не", во втором - с двумя отношениями, связанными союзом "или". Подобные условия назовём составными , и для их обозначения в алгоритме договоримся использовать союзы "и ", "или ", "не ", которые будем рассматривать как знаки логических операций, позволяющих из простых условий создавать составные, подобно тому, как из простых переменных и констант с помощью знаков +, - и т. д. можно создавать алгебраические выражения.
Так условия наших примеров в алгоритме могут выглядеть таким образом:
первое: (r = 45) и (color = белый) и (не (price>400))
второе: (цена=3) или (цена=3.5)
Выражение, содержащее логические операции, будем называть сложным логическим выражением.
Объединение двух (или нескольких) высказываний в одно с помощью союза «и» называется операцией логического умножения или конъюнкцией .
В результате логического умножения (конъюнкции) получается истина, если истинны все логические выражения.
Объединение двух (или нескольких) высказываний с по мощью союза «или» называется операцией логического сложения или дизъюнкцией .
В результате логического сложения (дизъюнкции) получается истина, если истинно хотя бы одно логическое выражения.
Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией .
Отрицание изменяет значение логической величины на противоположное: не истина = ложь; не ложь = истина.
Если в сложном логическом выражении имеется несколько логических операций, то возникает вопрос, в каком порядке их выполнит компьютер. По убыванию старшинства логические операции располагаются в таком порядке:
отрицание (не );
конъюнкция (и );
дизъюнкция (или ).
В логических выражениях можно использовать круглые скобки. Так же как и в математических формулах, скобки влияют на последовательность выполнения операций. Если нет скобок, то операции выполняются в порядке их старшинства.
Пример. Пусть a, b, c - логические величины, которые имеют следующие значения: a = истина, b = ложь, c = истина. Необходимо определить результаты вычисления следующих логических выражений:
a и b
a или b
не a или b
a и b или c
a или b и c
не a или b и c
(a или b) и (с или b)
не (a или b) и (с или b)
не (a и b и c)
Получим в результате:
Пример . Составить алгоритм для вычисления:
Алгоритм Вычисление x
начало
ввод (а, c)
если (4*а – с >=0) и (а<>0) то
начало
x:= корень(4*а – с)/(2*a)
вывод (х)
конец
иначе
вывод («нет решения»)
конец
Компьютер сначала проверит условие (4*а - с >=0) и (а<>0) и если оно окажется истинно, то вычислить x, иначе выведет сообщение «нет решения».
Пример . Составить алгоритм для вычисления суммы всех чисел от 1 до n.
Алгоритм Вычисление суммы чисел
переменные a, c, x - вещественные
начало
ввод (n)
x:= 1
пока x
s:= s + x
x:= x +1
конец
вывод (s)
конец
До тех пор пока условие x
