Практическое занятие № 4.

Тема: Логический тип данных.

Цель: Разобрать на практике логический тип данных и операции cдвига.

План занятия:

· обсуждение логического типа данных;

· обсуждение операций сдвига;

· эксперименты с программами вывода таблиц истинности,

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

· выполнение самостоятельной работы.

Ход работы:

1. Теоретические сведения:

Логический тип данных. Переменные логического типа опи­сываются с помощью идентификатора Boolean. Диапазон значе­ний — два: False (ложь) или True (истина), размер выделяемой памяти — 1 байт (False и True — стандартные константы). Тип является перечислимым, поэтому: False<True, Ord(False)=0, Ord(True)=1, Succ(False)=True, Pred(True)=False.

Перечислим четыре логические операции, реализованные в Турбо Паскале: логическое сложение, или дизъюнкция, — Or; логическое умножение, или конъюнкция, —And; отрицание -Not, исключающее «Или» (сложение по модулю два) — Хоr. Результаты выполнения операций над переменными логиче­ского типа х и у приведены в таблице:

Таблица истинности представляет собой таблицу, устанавлива­ющую соответствие между возможными значениями наборов переменных и значениями операции. С их помощью в математической логике обычно описываются значения логических функций. Следует четко понимать, что результатом выполнения опе­раций сравнения (отношения): « < » (меньше), « > » (больше), « < = » (меньше или равно), « > = » (больше или равно), « < > » (не равно), « = » (равно) является величина логического типа. Ее значение равно True, если отношение выполняется для значений входящих в него операндов, False – в противном случае. В языке Турбо Паскаль нет возможности ввода логических данных с помощью оператора Read. Однако предусмотрен вы­вод значений переменных логического типа с помощью опера­тора Write.

Операции сдвига. Речь идет о двух операциях: Shi — сдвиг влево и Shr — сдвиг вправо. Тип операндов и результата в опе­рациях сдвига Integer. Итак, m Shi n — значение m сдвигается влево на n разрядов; а при m Shr n — значение m сдвигается вправо на n разрядов. При выполнении операций разряды, вы­шедшие за пределы области памяти, выделяемой для типа дан­ных, теряются, а с другой стороны добавляются нули. Напри­мер, если m равно 32, то сдвиг влево на один разряд дает 64, а сдвиг вправо — 16. Операции равносильны умножению и деле­нию на два.

2. Экспериментальный раздел работы:

· Просмотрите текст программы, обращая внимание на ее структуру.

· Выполните обычные действия с программой (набор,
компиляцию, запись на диск, запуск).

Program Му4_1;

Uses Crt;

Var a,b: Boolean;

Begin

ClrScr;

a:=True; b:=True; WriteLn (a:b, b:b, a And b:6) ;

a :=True; b:-False; WriteLn (a : b, b: b,a And b:6) ;

a :=False; b:=True; WriteLn (a : b, b: 6, a And b:6) ;

a:=False; b:=FaIse; WriteLn (a:b, b:6, a And b:6) ;

ReadLn;

End.

Примечание:

При наборе программы не забывайте использовать команды рабо­ты с блоками. Набирается a:=True; b:=True; WriteLn(a:6, b:6, a And b:6); а затем этот фрагмент выделяется как блок, копируется 3 раза и модифицируется.

· Измените программу для проверки остальных рассмотренных выше логических операций.

· Выполните обычные действия с программой Му2_2 (набор,
компиляцию, запись на диск, запуск).

Program My4_2;

Uses Crt;

Var m,n: Integer;

Begin

ClrScr;

WriteLn ('Введите число и количество сдвигов') ;

ReadLn (m,n);

WriteLn (' При сдвиге на ' ,n,' разрядов влево

числа ' ,m,' получаем число ' ,m Shi n);

WriteLn ('Введите число и количество сдвигов') ;

ReadLn (m,n);

WriteLn (' При сдвиге на ' ,n,' разрядов вправо

числа ' ,m,' получаем число ' ,m Shr n) ;

ReadLn;

End.

Введите в том и другом случае числа 32 и 1, убедитесь, что получаются числа 64 и 16. Сдвиги вправо отрицательных чисел приводят к интересным результатам. Например, если Вы введе­те -1 и 1 для того и другого сдвигов, то получите -2 и 32767. Если первый результат вполне объясним, то второй требует вспомнить о представлении отрицательных целых чисел в до­полнительном коде. Пусть у нас не шестнадцать разрядов для представления чисел (тип Integer), a 4. Представление -1 в до­полнительном коде есть 1111₂- Сдвиг вправо на один разряд приводит к числу 0111₂, а это не что иное, как 7₁₀.

· Выполните набор программы Му4_3, набрав только первые

три оператора WriteLn). Откомпилируйте ее, запишите на диск.

Program Му5_3;

Uses Crt;

Begin

ClrScr;

WriteLn (1365 And 2730);

WriteLn (1365 Or 2730);

WriteLn (1365 Xor 2730);

WriteLn (1365 And $FF);

WriteLn(1365 And $FFO);

WriteLn (1365 And $FFOO);

ReadLn;

End.

Видно, что с величинами типа Integer можно выполнять логические операции, они выполняются поразрядно над двоич­ными представлениями чисел. Почему выбраны числа 1365 и 2730? Двоичное представление этих чисел имеет вид: 1365₁₀=010101010101₂, 2730₁₀=101010101010₂ (рассматрива­ются только 12 младших разрядов). Операция And дает в резу­льтате число 0, а операции Or и Хог — 4095. Поэксперименти­руйте с этой версией программы. Убедитесь, например, что - 256 And 256 = 0, а - 256 Or 256 = -1 и - 256 Хог 256 = -1. Попы­тайтесь дать разумное объяснение этому результату.

Добавьте к программе следующие три оператора WriteLn. В шестнадцатеричной системе счисления для обозначения цифр 10, 11, 12, 13, 14, 15 используются соответственно буквы ла­тинского алфавита А, В, С, D, E, F. Двоичное представление F — 1111₂. Знак $ означает, что величина (константа) записана в шестнадцатеричной системе счисления. Запустите програм­му. Убедитесь в том, что результат равен 85, 1360, 1280. Его правильность подтверждается выделением соответствующих раз­рядов из числа 010101010101₂ и переводом остатка в десяти­чную систему счисления. Исследуйте описанным способом пред­ставление в дополнительном коде отрицательных целых чисел.

3. Задания для самостоятельной работы

1. В математической логике известна функция следования, или импликация, (х=>у), ее таблица истинности имеет вид

Проверьте, что х=>у эквивалентно Not(x) Or у. Составьте программу проверки эквивалентности этих двух логических функций.

2. В математической логике известна функция Шеффера (х | у), ее таблица истинности имеет вид

Проверьте, что х|у эквивалентно Not(x) Or Not(y). Соста­вьте программу проверки эквивалентности этих двух логиче­ских функций.

3. Дана логическая функция, например, (x=>y)=>z. Построить таблицу истинности данной функции. Схема построения при­ведена в таблице (перепроверить данные таблицы). В первом столбике приведены возможные значения наборов переменных х, у и z (значение True обозна­чено как единица, значение False — как нуль).

Преобразуйте эту формулу в эквивалентную ей. Составьте программу проверки эквивалентности этих двух логических формул.

· Дополнительное задание:

Постройте таблицы истинности для следующих функций:

1. (х=>у) And z;

2. Not (x Or Not(y) And z);

3. х And Not(y Or Not(z));

4. Not(Not(x) Or у And z).

Материал для чтения

1. Слово «логика» употребляется в разных значениях, на­пример логика событий, логика характера и т. д. В этом случае имеется в виду определенная последовательность и взаимозави­симость событий или поступков. Слово «логика» употребляет­ся и в связи с процессами мышления. Когда говорят о логич­ном мышлении, то рассматривают его последовательность, дока­зательность и т. д. Итак, логика — особая наука о мышлении. Основателем ее считается древнегреческий философ Аристо­тель (IV в. до н. э.). Позднее она стала называться формальной логикой, и ее цель на протяжении всей истории развития неиз­менна: исследование того, как из одних утверждений можно выводить другие, при этом считается, что правильность рас­суждения определяется только его логической формой и не за­висит от конкретного содержания входящих в него рассужде­ний. В XIX веке благодаря усилиям английского ученого Джор­джа Буля возникла наука математическая логика. Джордж Буль перенес на логику законы и правила алгебраических дей­ствий, ввел логические операции, предложил способ записи высказываний в символической форме. Алгебра логики — раздел математической логики, изучающей строение (форму, структу­ру) сложных высказываний и способы установления их истин­ности с помощью алгебраических методов. Высказывание - повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Все высказывания условно разделяются на простые и сложные, или составные. Составные высказывания образуются из простых. Высказывания х и у -простые, высказывание х And у — составное, оно называется конъюнкцией и имеет 4 логические возможности, рассмотрен­ные выше, для определения возможности его истинности. Вы­сказывание х Or у тоже составное и называется дизъюнкцией.

2. Алгебра логики и ее законы. Операции алгебры: конъюнк­ция, дизъюнкция и отрицание. Эти операции позволяют произ­водить тождественные преобразования логических выражений.

Законы:

· закон одинаковости: х Or х=х; х And x=x;

· закон коммутативности: х Or y=y Or х, х And y=y And х;

· закон ассоциативности: х Or(y Or z)=(x Or у) Or z, x And(y And z)=(x And y) And z;

· законы дистрибутивности: х And (у Or z)=x And у Or x And z — первый; x Or у And z=(x Or y)And(x Or z) — вто­рой;

· закон двойного отрицания: Not(Not(x.))=x;

· законы де Моргана: Not(x.) Or Not(y)=Not(x And у);

· законы поглощения: х Or x And y=x; х And (x Or у)=х;

· законы, определяющие действия с логическими констан­тами False и True: x Or FaZse=x; х And False=False; x Or True=True; x And True=x; Not(False)=True; Not(True)= =False; Not(x) Or x=True; Not(x) And x=False.

Дополнительные законы (они выводятся из основных зако­нов):

• законы склеивания: х And у Or Not(x) And y=y; (x Or у)And (Not(x) Or y)=y;
• закон Блейка-Порецкого: x Or Not(x) And y=x Or y;
• закон свертки логического выражения: х And y Or Not(x)

And z Or у And z=x And у Or Not(x.) And z.

Примечания

1. Приведем пример вывода для закона Блейка-Порецкого: х Or Not(x) And y= x And True Or Not(x) And y= x And (y Or Not(y)) Or Not(x) And y= x And у Or x And Not(y) Not(x) And y= x And у Or x And Not(y) Or Not(x) And у Or x And y= x Or y.

2. Тип упражнений для закрепления материала может быть следу­ющим. Дается логическое выражение, например, Not(Not(x) Or
Not(y))—7 и варианты ответов: Not(x) Or у или х Or у и т. д., необ­ходимо выбрать правильный ответ.

3. Логические функции можно преобразовать в две различ­ные формы:

· дизъюнктивную нормальную форму (ДНФ);

· конъюнктивную нормальную форму (КНФ).

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

Примеры:

Not(x) Or у And z, x And y And z Or Not(y) And Not (z) -ДНФ, a x And (y Or Not(z)) -нет, (Not(x) Or y) And z, x And у And (z Or Not(v)) — КНФ, x And (yAnd z Or Not(v)) — нет.

Всякая сложная логическая функция может быть преобра­зована как к ДНФ, так и к КНФ. Алгоритм преобразования:

· записать функцию с использованием только операций Or, And, Not;

· с помощью законов де Моргана операцию отрицания дове­сти до отдельных переменных и убрать выражения типа Not(Not(x)) по закону двойного отрицания;

· с помощью первого закона дистрибутивности убрать все конъюнкции дизъюнкций и провести поглощение. В результате получим ДНФ представления логической фун­кции. Для получения записи в виде КНФ следует изменить тре­тий пункт алгоритма:

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

Рассмотрим построение совершенных ДНФ и КНФ на незна­чительно измененном 3-м примере из раздела самостоятельной работы занятия. Дана логическая функция (x:=>y)=>Not(z). По­строим таблицу истинности данной функции.

СДНФ( (x=>y)=>Not (z))=Not (x) And Not(y) And Not(z) Or Not (x) And у And Not (z) Or x And Not (y) And Not (z) Or x And Not (y) And (z) Or x And у And Not (z) .

СКНФ( (x=>y)=>Not (z))=Not (Not (x) And Not (y) And z) And Not (Not (x) And у And z) And Not (x And у And z) = (x Or у Or Not(z)) And (x Or Not(y) Or Not(z)) And (Not(x) Or Not (y) Or Not (z)),