Тестовое задание 4.
Функция mod вычисляет остаток от деления нацело пер- |
|
будет равно … |
|
|||||||
вого аргумента на второй. Значение переменной K после |
|
|
|
|
|
|||||
выполнения следующей программы: |
|
|
|
|
|
|||||
k:=0; |
|
|
|
|
|
1. |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
2. |
|
7 |
|
||
нц |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
||
для i от 1 до 100 |
|
3. |
|
288 |
|
|||||
если (mod(i,3)=2) и (mod(i,5)=1) |
|
|
|
|
||||||
|
4. |
|
3 |
|
||||||
|
то k:=k+1 |
|
|
|
|
|
||||
|
|
|
|
|||||||
|
|
|
|
|||||||
все |
|
|
|
|
|
|
|
|
|
|
кц |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Тестовое задание 5. |
|
|
|
|
|
|||||
Если начальные значения переменных |
|
|
|
|
|
|||||
равны соответственно A=1, B=1 и C=4, |
|
|
|
|
|
|||||
то чему будет равно значение перемен- |
|
|
|
|
|
|||||
ной F в конце алгоритма в операторе |
|
|
|
|
|
|||||
Вывод… |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
1. |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2. |
|
-4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4. |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
АЛГЕБРА ЛОГИКИ. ЛОГИЧЕСКИЕ ФУНКЦИИ. БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ.
В XIX в. в трудах английского математика Дж. Буля начала формироваться новая область математических знаний - алгебра логики, созданная для решения традиционных логических задач алгебраическими методами. Объектом изучения алгебры логики стали функции, принимающие в качестве значений, как и их аргументы, элементы из заданного двухэлементного множества, и различные операции над этими функциями. Такие функции и операции получили общее название логических. Их исследования в алгебре логики тесно связаны с изучением высказываний, понимаемых как предложения, относительно которых можно утверждать, истинны они или ложны. Например, высказывание "Сумма внутренних углов треугольника равна 180° " - истинно, а высказывание "Все углы треугольника - прямые" - ложно.
103
Употребляемые в обычной речи логические связки "и", "или", "если ..., то", "эквивалентно", частица "не" позволяют из уже заданных высказываний строить новые, более "сложные" высказывания. Так, из высказываний "х>2", "х<3" при помощи связки "и" можно получить "х>2 и х<3", при помощи связки "или" - "х>2 или х<3".
Истинность или ложность получаемых таким образом высказываний зависит от истинности или ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Для обозначения истинности вводится символ Да, True (T или 1), а для обозначения ложности — Нет, False (F или 0 иногда -1). Логические связки в выражениях обозначаются соответственно знаками и называются:
И, AND & (или Λ) - логическим умножением (конъюнкцией) ИЛИ, Or V - логическим сложением (дизъюнкцией),
EСЛИ ..., ТО -> - следованием (импликацией), = ~ - эквивалентностью
НЕ, NOT ¬ или черточкой сверху - логическим отрицанием.
Производимые с их помощью операции над высказываниями, имеющими значения только T (1) или F (0). Связки и частицу "не" можно рассматривать как операции над величинами, принимающими значения "0" и "1", и результатом применения этих операций (значением перечисленных логических функций) также являются числа "0" и "1". Указанные логические операции стали записывать формулами, например:
((x v y) & z) а & b
Введенные операции позволяют каждой формуле, при заданных значениях входящих в нее высказываний, приписать одно из двух значений — "0" или "1". Тем самым каждая формула может одновременно рассматриваться как некоторый способ задания или реализации функций алгебры логики, то есть таких функций, которые определены на наборах нулей и единиц и которые принимают значения тоже "0" или "1". При этом формулы называются эквивалентными, если они реализуют равные логические функции (подчеркнем, что не совпадающие, а равные по значениям). Для задания функций алгебры логики иногда используют таблицы, содержащие все наборы значений переменных и значения функций на этих наборах. Это так называемый табличный способ задания функций. Сами же таблицы в алгебре логики назы-
вают таблицами истинности.
Так, например, сводная таблица, задающая логические отрицание х, умножение (конъюнкцию) х & у, сложение (дизъюнкцию) х v у, следование (импликацию) х -> у , эквивалентность х~y, имеет следующий вид:
|
х |
у |
NOT |
х & у |
х v у |
х→у |
х~y |
( & ) |
( v ) |
XOR |
|
|
|
(х) |
NOT |
NOT |
NOT(~) |
Not(→) |
|
||||||
|
|
|
|
|
|
|
|
|||||
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
104 |
|
|
|
|
|
Поясним образование высказываний с помощью операций импликации и эквивалентности:
Высказывание, образованное с помощью операции логического следования (импликации), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).
Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.
Тестовые задания. Задание1
Символом F обозначено логическое |
|
Логической функции F соответствует |
|||
выражение от трех аргументов: X, Y, |
|
логическое выражение… |
|||
Z. Дан фрагмент таблицы истинности |
|
|
|
|
|
выражения F: |
|
1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ. ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ФУНКЦИИ.
На основании заданного таблицей определения основных логических функций строятся таблицы для произвольных формул (функций) алгебры логики. С помощью построения таблиц истинности можно найти значение произвольной логической функции, доказать или опровергнуть утверждение об эквивалентности различных формул.
Для преобразования формул (например, с целью замены на эквивалентную, но короче записываемую) используют равенства, имеющие в алгебре логики силу законов:
1. Законы одинарных элементов:
х V 1 = 1 |
Закон универсального |
х & 1 = х |
множества |
х V 0 = х |
Закон нулевого |
х & 0 = 0 |
множества |
2. Законы отрицания |
|
NOT(NOT(x)) = x |
Закон двойного отрицания |
|
|
|
105 |
х V NOT(х) = 1 |
Закон исключѐнного третьего |
х & NOT(х) = 0 |
Закон противоречия |
NOT(xVy) = NOT(х) & NOT(у), |
Законы двойственности |
NOT(x&y) = NOT(х) V NOT(у) |
Законы де Моргана |
3. Комбинационные законы |
|
|
|
х v х = х, |
Закон |
|
|
х & х = х |
тавтологии |
|
|
х & у = у & х, |
Закон |
|
|
х v у = у v х |
коммутативности |
||
(x & y) & z = x & (y & z), |
Закон |
|
|
(x v y) v z = x v (y v z) |
ассоциативности |
||
x & (x v z) = x, |
Закон |
|
|
x v (x & z) = x |
поглощения |
||
x & (y v z) = (x & y) v (x & z), |
Закон |
|
|
x v (y & z) = (x v y) Λ (x v z) |
|
дистрибутивности |
|
(х & у) v (NOT(х) & у) = х, |
|
Закон |
|
(х v у) & (NOT(х) v у) = х |
|
склеивания |
|
а так же аналоги эквивалентности и импликации |
|||
х→у = NOT(х) v у |
|
|
Импликация |
x ~ y = (NOT(х) & у ) v (х &NOT(у)) |
Эквивалентность |
||
Эти равенства, устанавливаемые, например, с помощью таблиц истинности, позволяют уже без помощи таблиц получать другие равенства. В этом случае методом получения равенств являются так называемые тождественные преобразования, которые меняют формулу, но не функцию, реализуемую этой формулой (так как каждый шаг такого преобразования означает переход к эквивалентной формуле).
Символы логических умножения, сложения и отрицания играют роль базовых, т. к. всякая функция алгебры логики может быть выражена формулой, записываемой с их помощью (пример: законы противоречия и исключенного третьего). Это имеет принципиальное значение для обработки информации центральным процессором компьютера, т.к. процессор обрабатывает информацию, закодированную в двоичном алфавите и имеющую форму электрических сигналов, причем делает он это посредством электронных схем.
106
Основными элементами этих схем являются полупроводниковые транзисторы, различные соединения которых при прохождении через них электрических сигналов, интерпретируемых как "0" (напряжение от 0 до 0.8 вольт) и "1" (напряжение от 2.4 до 5.0 вольт), реализуют основные логические функции - логические умножение, сложение и отрицание. Этого оказалось достаточно, чтобы процессор мог производить не только любые логические операции, но и все арифметические действия в двоичной системе счисления. Более того, с помощью этих же электронных схем, реализующих только логические умножение, сложение и отрицание, запоминание битов информации осуществляет основной элемент оперативной памяти - статический триггер. Таким образом, алгебра логики выступает здесь в качестве алгебры переключательных схем или дискретных (цифровых) сигналов. Наличие законов алгебры логики и возможность тождественных преобразований позволяют при конструировании сложных интегрированных и переключательных схем получать их технически упрощенными, сохраняя эквивалентной реализуемую ими логическую функцию.
Тестовые задания Задание 1
В результате упрощения |
1. |
2. |
логического выражения |
3. |
4. |
|
||
полу- |
|
|
чится выражение… |
|
|
Задание 2
Логическая функция |
1. |
2. |
|
|
|
||
принимает значение |
3. |
4. |
|
|
|
||
Ложь (0) при … |
|
|
|
|
Задание 3 |
|
|
На рисунке приведена таблица истин- |
В заголовке третьего столбца таблицы |
||
ности для выражения, содержащего |
должно быть указано логическое вы- |
||
две логические операции. Одна из них |
ражение… |
||
– |
(второй столбец). |
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
3 |
|
|
|
4 |
|
|
|
|
107