Материал: Основы программирования на языке Паскаль. Основные понятия алгоритмического языка Паскаль. Кононов А.Д., Кононов А.А

2. Логические операции

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

Под высказыванием понимается всякое предложение, в котором содержится смысл утверждения (истинности) или отрицания (ложности). Одно и то же высказывание не может быть одновременно истинным и ложным или не истинным и не ложным. Отдельные высказывания можно обозначить заглавными буквами латинского алфавита A, B, C, … Если высказывание (суждение) А истинно, то, например, А = 1. Если С = 0, то высказывание С ложно.

Итак, рассматриваются только два значения высказывания: истинное или ложное (1 или 0). Такое условие алгебры логики приводит к соответствию между логическими высказываниями в математической логике и двоичными цифрами в двоичной системе счисления, что позволяет описывать работу схем и блоков машины и проводить их анализ и синтез с помощью алгебры логики.

Основными логическими операциями являются логическое отрицание, логическое умножение, логическое сложение, сложение по модулю 2.

Логические операции применяются к величинам логического типа, результат операций также логического типа.

В Паскале используются следующие логические операции:

NOT («не» - отрицание), AND («и» - логическое умножение, конъюнкция), OR («или» - логическое сложение, дизъюнкция), XOR (исключающее или). Операнды и результат могут принимать одно из значений: TRUE (истина) или FALSE (ложь).

Результаты операций определяются таблицей истинности (табл.4)

Таблица 4

Таблица истинности

Логическое отрицание (операция НЕ, инверсия).

Пусть имеется некоторое высказывание А. Отрицание этого высказывания обозначается , которое принято читать: не А.

Если высказывание А истинно (А=1), то высказывание ложно ( = 0). Если высказывание А ложно (А=0), то высказывание истинно ( =1 ). Таким образом, для логического отрицания справедливо следующее правило: = 1; = 0.

Логическое умножение (операция И, конъюнкция).

Операцию логического умножения двух переменных А и В обозначают А/\В (принято читать: А и В). Высказывание А/\В истинно только в том случае, если А истинно (А=1) и В истинно (В=1), то есть А/\В =1. Во всех остальных случаях это высказывание ложно, т.е. А/\В = 0. Следовательно, при логическом умножении справедливо следующее правило: 0/\0 =0; 0/\1=0; 1/\0=0; 1/\ 1 =1.

Правила логического умножения справедливы не только для двух сомножителей, но и для любого их количества, т.е. А/\В/\С/\D/\ ….

Логическое сложение (операция ИЛИ, дизъюнкция).

Операцию логического сложения двух переменных А и В обозначают А\/В (принято читать: А или В). Высказывание А\/В истинно (А\/В =1) в том случае, если хотя бы одно из значений А или В истинно (А =1 или В =1). Если же это условие не выполняется, то высказывание ложно (А\/В =0) Таким образом, при логическом сложении справедливо следующее правило:

0\/0 =0; 0\/1 =1; 1\/0 =1; 1\/1 =1.

Правило логического сложения справедливо не только для двух слагаемых, но и для любого их числа, т.е. А\/В\/С\/D\/….

Сложение по модулю 2 (ИЛИ исключающее).

Операцию сложения двух переменных А и В по модулю 2 обозначают А В. Высказывание А В истинно ( А В =1) в том случае, если только одно из переменных А или В истинно ( А =1, В =0 или А =0, В =1). Если же это условие не выполняется, то высказывание ложно (А В=0). Таким образом, сложение по модулю 2 выполняется по такому правилу:

0 0 =0; 0 1 =1; 1 0 =1; 1 1 =0.

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

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

Основные правила преобразования следующие:

А /\ = А /\ 0 =0;

А \/ = А \/ 1 =1;

А /\ А = А \/ А = А /\ 1 = А \/ 0 = А;

А /\ В = В /\ А; А \/ В = В \/ А;

(А /\ В) /\ С = А /\ (В /\ С) = А /\ В /\ С;

(А \/ В) \/ С = А \/ (В \/ С) = А \/ В \/ С;

(А /\ В) \/ С = (А \/ С) /\ (В \/ С);

(А \/ В) /\ С = (А /\ С) \/ (В /\ С);

= \/ ; = /\ ;

А В= (А /\ ) \/ ( /\ В) = (А \/ В) /\ ( \/ );

Если подставить в эти выражения значения 0 и 1 для всех переменных, то можно убедиться в справедливости рассмотренных формул алгебры логики.

При разработке узлов ЭВМ смысл ложных или истинных высказываний А, В, С во внимание не принимается; аппарат логики используется для выполнения заданных логических преобразований. Например, арифметические преобразования (сложение, вычитание) задаются в виде совокупности логических преобразований над аргументами.

Упражнения к разделу

Упражнение 1. Какие операции определены над переменными булевского типа?

Упражнение 2. Объясните ошибки в следующих записях:

а) 1 and 0 б) true + false в) true < 0 г) not 2 = 5

д) true or (1/0 > 1) е) x > 0 or y =4 ж) not not b or or d

Упражнение 3. Какие из приведенных ниже записей являются правильными с точки зрения языка Паскаль?

а) ‘A’ < ‘C’ б) ‘1’ < ‘9’ в) FALSE < TRUE

г) ‘A’< ‘B’ and 1 < 2 д) ‘0’ or ‘9’ е) (‘D’ > ‘C’) and (1 < 2)

Упражнение 4. Указать порядок выполнения операций при вычислении выражения:

а) a and b or not c and d

б) (x >= 0) or t and odd(x) or (y*y<> 4)

Упражнение 5. Вычислить следующие выражения при a = true и b = false:

а) a or b and not a б) (a or b) and not a

в) not a and b г) not (a and b)

Упражнение 6. Доказать тождества:

а) a and ( not a) = false б) a or ( not a) = true

в) not (not a) = a г) true or a = true

д) false and a = false е) a or a = a.

Упражнение 7. Записать на Паскале отношение, истинное при выполнении указанного условия и ложное в противном случае:

а) целое к делится на 7;

б) уравнение ax² + bx + c =0 ( a≠0 ) не имеет вещественных корней;

в) точка ( x,y ) лежит вне круга радиуса r с центром в точке ( 1, 0);

г) 0 < x < 1;

д) x = max (x,y,z);

e) x лежит вне отрезка [ 0,1];

ж) x принадлежит отрезку [ 2,5] или [ -1,1];

з) значение x принадлежит одному из отрезков [ -5, -4], [ 0,3], [ 4.2, 7]

3. Операции отношения

Предназначены для сравнения двух однотипных величин. Операции отношения следующие:

= равно

< > не равно

< меньше

<= меньше или равно

> больше

>= больше или равно

Результат сравнения имеет логический тип и принимает значение TRUE (истина), если указанное соотношение выполняется, и FALSE (ложь), если соотношение не выполняется.

Пример 1. Операция х<2.5 сравнивает значение, хранящееся в ячейке памяти, отведенной для переменной х, и вещественное число 2.5. При х=2.1 отношение х<2.5 имеет значение TRUE и значение FALSE при х=4.8. Напомним, что переменная х должна быть описана в разделе VAR программы как переменная вещественного типа.

N MOD 5 = 0 – отношение имеет значение TRUE, если переменная N целого типа будет иметь значение кратное 5, и FALSE, если N не кратно 5.

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

Пример 2. Длины сторон треугольника заданы переменными a,b,c. Записать в виде логического выражения условие того, что из трех отрезков длиной a,b,c можно построить треугольник.

Здесь необходимо проверить, выполняется ли система неравенств

a+b>c

b+c>a

a+c>b,

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

(a+b>c) AND (b+c>a) AND (a+c>b).

ЭВМ выбирает из памяти значения a,b,c, подставляет их в выражение и проверяет выполнение входящих в него неравенств. Если каждое из неравенств принимает значение TRUE, то и все выражение дает значение TRUE, то есть построить треугольник со сторонами a,b,c можно. Если хотя бы одно из неравенств есть FALSE, то треугольник построить нельзя.

Пример 3. Записать высказывание, что точка А не принадлежит отрезку [2,5].

На языке Паскаль это будет (А<2) OR (А>5). Выражение будет иметь значение TRUE,если хотя бы одна из скобок будет иметь значение TRUE.

Пример 4. Записать логическое выражение, определяющее принадлежность некоторого действительного числа Х одному из двух отрезков [a,b] или [c,d].

Решением является логическое выражение

(a<=x) AND (x<=b) OR (c<=x) AND (x<=d)

1 5 2 7 3 6 4

В нижней строке указан порядок выполнения операций (см. 3.5)

Пример 5. Записать условие принадлежности точки М с координатами (х, у) координатной четверти (х ≥ 0, у ≥ 0).

Задаче соответствует логическое выражение (х>=0) AND (у>=0). Координата х точки М будет сравниваться с нулем и если х – положительное число, то первая скобка получит значение TRUE. Затем координата у точки М будет сравниваться с нулем и вторая скобка получит значение TRUE, если число у положительно. Затем операция AND (конъюнкция) свяжет две скобки, и все выражение будет иметь значение TRUE, если обе скобки имели значение TRUE и точка М принадлежит первой координатной плоскости. В противном случае все выражение получит значение FALSE, то есть точка М не принадлежит первой четверти.

Пример 6. Записать на языке Паскаль выражение, которое принимает значение TRUE, когда точка с координатами (х,у) принадлежит заштрихованной области (рис.3).

4. Операции со строками

Для строк применимы операции конкатенации (+) и сравнения. Операция конкатенации присоединяет одну строку к другой.

Пример:

VAR

str,str1,str2:STRING[80];

BEGIN

str1:= ′ Turbo ′;

str2:= ′ Pascal ′:

str:= str1+str2;

END.

В результате выполнения оператора str := str1+str2 переменная str получит значение ′ Turbo Pascal ′.

Сравнивать можно строки разной длины. Лексикографическое сравнение осуществляется слева направо в строке по ASCII – кодам (приложение 3), соответствующим символам. Считается, что отсутствующие символы в более короткой строке имеют код меньше кода любого присутствующего символа. Например, ′xs′ больше, чем ′x′.

5. Выражения

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

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

Таблица 5

Приоритеты действий при вычислении выражений

Унарная (единичная) операция означает взятие противоположного элемента.

Упражнения к разделу

Упражнение 1. Даны три целых положительных числа I, J, K.

Составьте логические выражения для определения:

1. является ли I делителем числа J и K одновременно;

2. все ли эти числа четные;

3. I, J, K точно делятся на 2,3 и 5;

4. лежат ли эти числа в диапазоне от 2 до 10;

5. какие символы имеют порядковые номера I, J, K?

Упражнение 2. Составьте программу ввода в машину пяти переменных символьного типа CH1,CH2,CH3,CH4,CH5 и определите, есть ли среди символов: