Линейные алгоритмы. Величины логического типа

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

План • Логический тип данных
• Операции сдвига
• Экспериментальный раздел работы

• Задания для самостоятельной работы
• Материал для чтения

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

Переменные логического типа описываются с помощью идентификатора Boolean. Они могут принимать два значения: False (ложь) или True (истина) (False и True — стандартные константы), под них выделяется 1 байт памяти. Логический тип является перечислимым: False < True, Ord(False) = 0, Ord(True) = 1, Succ(False) = True, Pred(True) = False.
В Турбо Паскале имеются четыре логические операции: логическое сложение, или, дизъюнкция, — or; логическое умножение, или конъюнкция, — and; отрицание — not, исключающее " или " (сложение по модулю два) — хor. Результаты выполнения данных операций над переменными логического типа приведены в таблице.

Значение операнда		Результат операций
x	y	not x	x and у	x or у	x xor y
False	False	True	False	False	False
False	True	True	False	True	True
True	False	False	False	True	True
True	True	False	True	True	False

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

Операции сдвига

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

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

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

Program My6_1;
Uses Crt;
Var a,b:Boolean;
Begin
ClrScr;
a:=True;b:=True;
WriteLn (a : 6, b : 6, a and b : 6);
a:=True;b:=False;
WriteLn (a : 6, b : 6, a and b : 6);
a:=False;b:=True;
WriteLn (a : 6, b : 6, a and b : 6);
a:=False;b:=False;
WriteLn (a : 6, b : 6, a and b : 6);
ReadLn
End.

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

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

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

Program My6_2;
Uses Crt;
Var m, n : Integer;
Begin
    ClrScr;
    WriteLn ( ' Введите число и величину, сдвига ' );
    ReadLn (m, n);
    WriteLn ( ' При сдвиге на ', n, ' разрядов влево числа ' ,m, ' получаем число ' , m shl n);
    WriteLn ( ' Введите число и величину сдвига ' );
    ReadLn (m, n);
   WriteLn (При сдвиге на ' , n, ' разрядов вправо числа, ' ,m, ' получаем число ' , m, shr n);
    ReadLn
    Ehd.

Убедитесь, что при вводе m = 32, n = 1 получаются числа 64 (результат сдвига влево) и 16 (результат сдвига вправо). Сдвиги вправо отрицательных чисел приводят к интересным результатам. Например, если вы введете -1 и 1 для того и другого сдвигов, то получите -2 и 32 767. Если первый результат вполне объясним, то для понимания второго требуется вспомнить о представлении отрицательных целых чисел в дополнительном коде. Пусть у нас не 16 разрядов для представления чисел (тип Integer), а 4. Представление -1 в дополнительном коде есть 11112, Сдвиг вправо на один разряд приводит к числу 01112, а это не что иное, как 710.
3. Выполните обычные действия с программой Му6_3, набрав только первые три оператора WriteLn.

Program My6_3;
Uses Crt;
Begin
   ClrScr;
   WriteLn (1365 and 2730);
   WriteLn (1365 or 2730);
   WriteLn (1365 xor 2730);
   WriteLn (1365 and $FF);
   WriteLn (1365 and $FF0);
   WriteLn (1365 and $FF00);
   ReadLn
End.

Мы видим, что с величинами типа Integer можно выполнять логические операции, причем они выполняются поразрядно над двоичными представлениями чисел. Почему выбраны числа 1365 и 2730? Переведите их в двоичную систему счисления: 136510 = 0101010101012, 273010 = 1010101010102 (рассматриваются только 12 младших разрядов). Операция and дает в результате число 0, а операции or и хоr - 4095. Поэкспериментируйте с программой. Убедитесь, например, что

-256 and 255 = 0
-256 or 255 = -1
-256 xor 255 = -l

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

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

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

x	y	xÞ у
False	False	True
False	True	True
True	False	False
True	True	True

Проверьте, что хÞу эквивалентна not(x) or y. Составьте программу проверки эквивалентности этих двух логических функций.
2. В математической логике известна функция Шеффера (x | у), ее таблица истинности имеет вид :

x	y	x \| у
False	False	True
False	True	True
True	False	True
True	True	False

Проверьте, что х | у эквивалентна not(x) or not(y). Составьте программу проверки эквивалентности этих двух логических функций.
3. В математической логике известна фикция Вебба, или стрелка Пирса (хßу), ее таблица истинности имеет вид

x	y	x ß у
False	False	True
False	True	False
True	False	False
True	True	False

Проверьте, что хßу эквивалентна not(x) and not(y). Составьте программу проверки эквивалентности этих двух логических фушфий.
4. Дана некоторая логическая функция; например, (х Þ у) Þ z. Постройте таблицу истинности данной функции. Схема построения приведена в таблице. В первом столбце приведены всевозможные наборы значений переменных х, y и z (True обозначено еденицей, False— нулем).

x y z	xÞy	(xÞy) Þ z
000	1	0
001	1	1
010	1	0
011	1	1
100	0	1
101	0	1
110	1	0
111	1	1

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

• (х | y) | z
• (x ß y) ß z
• (xÞy) and z;
• not (x or not y and z);
• x and not (y or not z);
• not (not x or у and z).
6. Дана логическая функция (х ß y) ß ( z ß v). Постройте ее таблицу истинности.

x y z v	х ß y	z ß v	(х ß y) ß ( z ß v)
0000	1	1	0
0001	1	0	0
0010	1	0	0
0011	1	0	0
0100	0	1	0
0101	0	0	1
0110	0	0	1
0111	0	0	1
1000	0	1	0
1001	0	0	1
1010	0	0	1
1011	0	0	1
1100	0	1	0
1101	0	0	1
1110	0	0	1
1111	0	0	1

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

1. Слово "логика" употребляется в разных значениях, например, логика событий, логика характера и т.д. Во всех случаях имеется в виду определенная последовательность и взаимозависимость событий или поступков. Слово "логика" употребляется и в связи с процессами мышления. Основателем науки логика считается древнегреческий философ Аристотель (IV в. до н. э.), В XIX веке благодаря работам английского ученого Джорджа Буля возникла наука математическая логика. Джордж Буль перенес на логику законы и правила алгебраических действий, ввел логические операции, предложил способ записи высказываний в символической форме. Алгебра логики — раздел математической логики, изучающей строение (форму, структуру) сложных высказываний и способы установления их истинности с помощью алгебраических методов. Высказывание — повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Все высказывания условно разделяются на простые и составные. Составные высказывания образуются из простых. Например, высказывания х и у — простые, высказывание x and у — составное.

2. Законы алгебры логики позволяют производить тождественные преобразования логических выражений.

Основные законы алгебры логики

(1) законы рефлексивности:
        х or х = х; x and x = x;
(2) законы коммутативности:
        х or у = у or х; х and у = у and х;
(3) законы ассоциативности:
        х or (у or z — (х or у) or z
        х and (у and z) — (x and у) and z;
(4) законы дистрибутивности:
        х and (у or z) = х and у or x and z;
        х or (у and z) — (x or y) and (x or z);
(5) закон двойного отрицания:
        not (not x) = x;
(6) законы де Моргана:
        not (x and у) = not x or not у;
        not (x or у) = not x and not у;
(7) законы поглощения:
        х or x and y = x; x and (x or у) = х;
(8) законы, определяющие действия с логическими константами False и True:
        х or False = х;
        х and False = False;
        х or True = True;
        x and True = x;
        not False = True;
        not True = False;
        not x or_x — True;
        not x and x = False.
Из основных можно вывести и другие законы, например:
(9) законы склеивания:
        х and у or not x and y = у;
        (х or у) and (not x or у) = у;
(10) закон Блейка — Порецкого
        x or not x and y = x or y
(11) закон свертки логического выражения:
       x and у or not x and z or y and z = x and y or not x and z.
Примечания
1. Приведем пример вывода закона Блейка — Порецкого:
        х or not x and у = х and True or not x and у = х and (y or not y) or not x and y = x and y or x and not y or not x and у = x and у or x and not у or not x and у or x and у = x or у
2. Упражнения для закрепления материала могут быть следующими Даются логическое выражение (например, not (not x or not y) = ?) и варианты ответов: not x or у или х or у и т.д., - необходимо выбрать правильный ответ.
3. Любую логическую функцию можно преобразовать в:
• дизъюнктивную нормальную форму (ДНФ);
• конъюнктивную нормальную форму (КНФ).
В первом случае логическая функция записывается в виде дизъюнкции конъюнкций, образованных из переменных и их отрицаний. Во втором случае наоборот.
Примеры:
        not х оr у and z
        х and у and z or not у and not z (ДНФ)

x and (y or not z) — нет,

(not x or у) and z
x and у and (z or not v) (КНФ)

x and (y and z or not v) — нет

Сформулируем алгоритм преобразования логической функции к ДНФ:
• записать функцию с использованием только операций or, and y not;
• с помощью законов де Моргала операцию отрицания довести до отдельных переменных и убрать выражения вида not (not х) по закону двойного отрицания;
• с помощью первого закона дистрибутивности убрать все конъюнкции дизъюнкции и провести поглощение.
В результате получим ДНФ представления логической функции для получения записи в виде КНФ следует изменить третий пункт алгоритма:
• с помощью второго закона дистрибутивности убрать все дизъюнкции конъюнкций и провести поглощение.
Если все конъюнкции в ДНФ содержат все логические переменные или их отрицания, то ДНФ наpзывается совершенной (СДНФ). Аналогично определяют и совершенную КНФ (СКНФ)
Рассмотрим построение совершенных ДНФ и КНФ на примере функции (х Þ y) Þ not(z). Построим таблицу истинности данной функции.

x y z	(х Þ y) Þ not(z)
000	1
001	0
010	1
011	0
100	1
101	1
110	1
111	0

СДНФ:
((xÞy)= not z) = not x and not y and not z or not x and y and not z or x and not у and not z or x and not у and z or x and у and not z.
СКНФ:
((xÞy) = not z) = not(not x and not у 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 у or not z).