Задача 9. Определить, сколько количество значащих нулей в двоичной записи десятичного числа 126 ?

Определить, сколько количество значащих нулей в двоичной записи десятичного числа 126?

Ответ: 1

Задача 10.

Укажите через запятую в порядке возрастания все числа, не превосходящие 25, запись которых в двоичной системе счисле­ния оканчивается на 101. Ответ запишите в десятичной системе счисления.

Ответ: 5, 13, 21

§5. Логические операции и логические функции.

Логика – это наука о формах и способах мышления. Основы формальной логики заложил древнегреческий учёный Аристотель, живший в 384-322 годах до нашей эры. В процессе своих исследований он ввёл понятие высказывание. Высказывание – это суждение (предложение), которому можно приписать истинность значения (либо истина, либо ложь).

Высказывания бывают простые и сложные. Пример простого высказывания: «На улице светит солнце» – A, «В классе идут занятия» – B.

Сложные высказывания строятся методом соединения простых высказываний с применением логических связок. Пример сложного высказывания: «На улице светит солнце и в классе идут занятия». Здесь и –логическая связка.

Алгебра высказываний – наука, изучающая закономерности, связанные с образованием сложных высказываний, её основоположниками являются английские учёные Д.Морган (1806-1871 г.г.) и Д.Буль (1815- 1864 г.г.).

В алгебре высказываний не интересуются сущностью простых и сложных высказываний (эпизодами, которые они описывают), а интересуются только их истинностным характером, т.е. семантикой высказываний. Для этого вводится семантическая область S, содержащая два символа И (истинно) и Л (ложно). Если высказывание истинно, то ему ставится в соответствие символ И, если же оно – ложно, то символ Л.

С математической точки зрения всё это означает, что в алгебре высказываний при анализе семантики высказываний оперируют с множеством S = { И; Л }, элементами которого являются два символа – И и Л.

Теперь на множестве S = { И; Л } можно ввести понятие операции, как правило, по которому определённой паре операндов A и B ставится в соответствие результат операции X в качестве сложного высказывания.

Эти правила имеют форму таблиц, называемых таблицами истинности, и они таковы.

1. Операция конъюнкции (Табл. 5). Ей соответствует логическая связка русского языка – союз “ и”. В логической операции конъюнкции сложное высказывание истинно только тогда, когда истинны простые высказывания.

Таблица 5

Здесь и далее: А, В – операнды как простые высказывания; Х – результат операции как сложное высказывание.

2. Операция дизъюнкции (Табл. 6). Ей соответствует логическая связка русского языка – союз “ или ”. В логической операции дизъюнкции сложное высказывание истинно только тогда, когда истинны либо первое либо второе из двух простых высказываний.

Таблица 6

3. Операция исключающее ИЛИ (Табл. 7). Ей соответствует логическая связка русского языка – оборот “ или ” … “ или ”. В логической операции «исключающее ИЛИ» сложное высказывание истинно только тогда, когда истинно только одно из двух простых высказываний.

Таблица 7

4. Операция импликации (Табл. 8). Ей соответствует логическая связка русского языка – оборот “ если … то ”. Истинностное состояние сложного высказывания при этой логической операции оценивается с точки зрения реальности ситуаций, описываемых простыми высказываниями. В этом случае сложное высказывание ложно тогда и только тогда, когда A истинно, а B ложно.

Таблица 8

5. Операция эквивалентности (Табл. 9). Ей соответствует логическая связка русского языка – оборот “ тогда и только тогда … когда ”. Истинностное состояние сложного высказывания при этой логической операции оценивается с точки зрения равенства простых высказываний в семантической области. В этом случае сложное высказывание истинно тогда, когда А и В равны в семантической области (т.е одновременно либо истинны, либо ложны).

Таблица 9

6. Операция отрицания суть одномерная операция, применяемая к одному операнду, например, A (Табл. 10). Она соответствует логической связке “ не ” русского языка.

Таблица 10

Операнд	Результат операции
A
Л	И
И	Л

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

Рис. 2. Иллюстрация операции пересечения множеств

Так, если А и В – два множества, то пересечением или общей частьюмножеств А и В называется множество А Ç В, состоящее из тех и только тех элементов, которые принадлежат каждому из множеств А и В. Тогда можно утверждать, что А Ç В = А · В.

Рисунок 2 иллюстрирует содержание операции пересечения множеств, где A – область на диаграмме Эйлера – Венна, точки которой принадлежат множеству A, B – область, точки которой принадлежат множеству B, заштрихованная область есть область, точки которой принадлежат множеству А Ç В.

Рис. 3. Иллюстрация операции объединения множеств

Объединением множеств А и В называется множество А È В, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из подмножеств А или В. Отсюда следует: А È В = А Ú В.

На рисунке 3 вся заштрихованная область представляет множество точек, принадлежащих множеству А Ú В.

Дополнением множества А до универсального множества называется множество А¢ тех и только тех элементов, которые не принадлежат множеству А. Тогда: А¢ = , где - отрицание А.

Рис. 4. Универсальное множество

На диаграмме Эйлера-Венна все точки прямоугольника (рис. 4) принадлежат универсальному множеству I в данном конкретном рассмотрении. Путь точки заштрихованной области принадлежат множеству A, которое в данном рассмотрении будет подмножеством универсального множества. Тогда все точки незаштрихованной области (рис. 4) будут принадлежать множеству А¢, которое является дополнением множества A до универсального множества I.

Алгебра высказываний представляет частный случай булевой алгебры, в которой символы И и Л заменяются символами 0 и 1 соответственно.

В этой новой алгебре, которую ещё называют алгеброй логики, имеется ряд законов, позволяющих производить равноси­льные преобразования логических выражений. Приведем соотношения, отра­жающие эти законы.

1. Закон двойного отрицания:

.

2. Переместителъный (коммутативный) закон:

- для логического сложения (дизъюнкции):

A B = B A;

- для логического умножения (конъюнкции):

А · В = В · А.

Результат операции над высказываниями не зависит от того, в каком поряд­ке берутся эти высказывания. Аналогично в обычной алгебре:

а + b = b + a, а b = b a.

3. Сочетательный (ассоциативный) закон:

- для логического сложения (дизъюнкции):

(A B) C = A (B C);

- для логического умножения (конъюнкции):

(А · В) · С = А · (В · С).

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

(а + ) + с = а + ( + с) = а + b + с,

(b с) = а с) = а b .

4. Распределительный (дистрибутивный) закон:

- для логического сложения (дизъюнкции):

(A B) · C = (A · C) (B · C);

- для логического умножения (конъюнкции):

(A · B) C = (A C) · (B C).

Определяет правило выноса общего высказывания за скобку.

Аналогично в обычной алгебре: .

5. Закон общей инверсии (законы де Моргана):

- для логического сложения (дизъюнкции):

= ;

- для логического умножения (конъюнкции):

= .

6. Закон идемпотентности (от латинских слов idem — тот же самый и роtens — сильный; дословно — равносильный):

- для логического сложения:

A A = А;

- для логического умножения:

А · А = А.

7. Законы исключения констант:

- для логического сложения (дизъюнкции):

A 1 = 1, A 0 = A;

- для логического умножения (конъюнкции):

А · 1 = А, А · 0 = 0.

8. Закон противоречия:

А · = 0.

Невозможно, чтобы противоречащие высказывания были одновременно ис­тинными.

9. Закон исключения третьего:

A = 1.

Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.

10. Закон поглощения:

- для логического сложения:

A A · B) = A;

- для логического умножения:

A · (A B) = A.

11. Закон исключения (склеивания):

- для логического сложения (дизъюнкции):

(А · В · В) = В;

- для логического умножения (конъюнкции):

(A B) · ( B) = В.

12. Закон контрапозиции (правило перевертывания):

(А В) = (В А).

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

§6. Логические задачи.

Поиск по сайту: